Past Events

PhD Defense

Toward Efficient and Optimal Multi-Robot Motion Planning: Provable Guarantees and Effective Heuristics


Download as iCal file

Monday, May 17, 2021, 04:00pm - 06:00pm


Speaker: Shuai Han

Location : Remote via Zoom


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.


Join Zoom Meeting

Join by SIP

Meeting ID: 952 6928 4275
Password: 964241
One tap mobile
+13126266799,,95269284275# US (Chicago)
+16465588656,,95269284275# US (New York)

Join By Phone
+1 312 626 6799 US (Chicago)
+1 646 558 8656 US (New York)
+1 301 715 8592 US (Washington DC)
+1 346 248 7799 US (Houston)
+1 669 900 9128 US (San Jose)
+1 253 215 8782 US (Tacoma)
Meeting ID: 952 6928 4275
Find your local number:

Join by Skype for Business