CS Events Monthly View
Qualifying ExamNear-Optimal Scalable Multi-Robot Path Planning : Algorithms, and Applications |
|
||
Friday, June 10, 2022, 11:00am |
|||
Speaker: Teng Guo
Location : Virtual
Committee:
Professor Jingjin Yu
Professor Kostas Bekris
Professor Abdeslam Boularias
Professor Peng Zhang
Event Type: Qualifying Exam
Abstract: In Multi-Robot Path Planning (MRPP), given a graph and n robots with assigned starts and goals, we need to find a collision-free path for each robot connecting the start vertex and the goal vertex. It has many applications in video games, warehouse automation, formation control, and swarm robotics. Solving MRPP optimally in terms of makespan or sum-of-costs is NP-hard. Therefore, research on near-optimal solvers that have good scalability and acceptable suboptimality is an attractive topic. In this talk, we first propose a polynomial time algorithm with asymptotic expected sub-1.5 makespan optimality guarantee, which utilizes a novel Rubik Table result. The method scales up to 30,000+ robots on 300x300 grids. In addition, we extend the algorithm to three dimensional grids and apply it on large-scale drone swarms in both simulation and real drone experiments. Then we introduce two divide-and-conquer based heuristics that enhance the scalability of classical MRPP solvers while keeping 1.x optimality.
Organization:
Rutgers University School of Arts & Sciences
Contact Professor Jingjin Yu
Department of Computer Science