CS Events

Qualifying Exam

Near-Optimal Scalable Multi-Robot Path Planning : Algorithms, and Applications


Download as iCal file

Friday, June 10, 2022, 11:00am


Speaker: Teng Guo

Location : Virtual


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.


Rutgers University School of Arts & Sciences

Contact  Professor Jingjin Yu