Toward efficient and optimal multi-robot motion planning: provable guarantees and effective heuristics
Creators: name: Han, Shuai
Publisher: name: No Publisher Supplied
Year: 2021

description: The labeled Multi-Robot Motion Planning (MRMP) problem, despite its wide range of different setups and variations, generally requires routing a set of mobile robots from a start configuration to a goal configuration as fast as possible, without collisions. In recent years, MRMP has been extensively studied, and significant progress has been made on solving MRMP with great efficiency as well as solution quality. However, due to the problem's hardness and importance in industrial applications, there is always the need to seek higher performance. This dissertation proposes methods with provable guarantees and effective heuristics to improve the current MRMP algorithm development from a few different perspectives, especially scalability and optimality.The first half of this dissertation focuses on MRMP in a continuous workspace. By partitioning the workspace using a grid structure, We propose a framework that can reach polynomial computation complexity and at the same time produces solutions with an expected constant-factor optimality guarantee. Furthermore, we propose a second framework with similar guarantees as the first one, while simultaneously pushes the robot density limit to more than 50%, i.e., over half of the workspace may be occupied by robots. Due to the discretizing nature of both frameworks, existing graph-based MRMP solvers (e.g., an integer linear programming based solver) can be adapted as subroutines, which results in highly efficient implementations that quickly compute near-optimal solutions.To provide more practically applicable algorithms, in the second part of this dissertation, we propose several MRMP solving principles and heuristics to improve the existing decoupled MRMP algorithms in a grid environment, The improvements also benefit the continuous workspace algorithms proposed in the first part of this dissertation. The traditional decoupled MRMP algorithm structure has two phases: first, each robot plans its individual path, ignoring other robots; second, collisions between the initial paths are resolved. In this dissertation, we develop a space utilization optimization heuristic (along with a heuristic design principle) and a database-driven collision-resolution heuristic, each targeting one of the two phases. The direct synergy of the two heuristics gives a near-optimal MRMP algorithm with exceptional scalability. Meanwhile, we show that the space utilization optimization heuristic can be easily incorporated with existing MRMP algorithms to make them more efficient and optimal. Moreover, both heuristics can be directly applied to a popular MRMP variation where the robots keep getting new goals after reaching the previous goals, rendering efficient algorithms.In the last part of this dissertation, We further study different applications, variations, and alternative objective functions of MRMP. After introduced and examined a wide range of path-based optimization problems, We describe a generalized integer programming methodology that easily adapt to the different variations and has high-performance in terms of computation time and the achieved optimality.