CS Events
PhD DefenseToward Efficient and Optimal Multi-Robot Motion Planning: Provable Guarantees and Effective Heuristics |
|
||
Monday, May 17, 2021, 04:00pm - 06:00pm |
|||
Speaker: Shuai Han
Location : Remote via Zoom
Committee:
Prof. Jingjin Yu (advisor and chair)
Prof. Kostas Bekris
Prof. Abdeslam Boularias
Prof. Sven Koenig (external member, University of Southern California)
Event Type: PhD Defense
Abstract: The labeled Multi-Robot Motion Planning (MRMP) problem, despite its large number of 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, including scalability and optimality. For MRMP in a continuous workspace, we first find a polynomial computation time, constant-factor optimal algorithmic framework. Then, a second method is developed with similar theoretical guarantees, while at the same time pushes robot density to above 50%. For MRMP in a discretized graph structure, we propose two heuristics: a database-driven heuristic for quickly resolve path conflicts and a space utilization optimization principle that can improve the efficiency and optimality of existing decoupled MRMP algorithms. Both heuristics extend their effectiveness to a lifelong, dynamic MRMP formulation. Finally, we propose a general integer programming framework for path-based optimization problems. The framework is easy to adapt to different path optimization formulations and can generate optimal solutions efficiently.
: