AAAI Publications, Workshops at the Twenty-Seventh AAAI Conference on Artificial Intelligence

Font Size: 
Fast, Near-Optimal Computation for Multi-Robot Path Planning on Graphs
Jingjin Yu, Steven M. LaValle

Last modified: 2013-06-29

Abstract


We report a new method for computing near optimal makespan solutions to multi-robot path planning problem on graphs. Our focus here is with hard instances - those with up to 85% of all graph nodes occupied by robots. Our method yields 100-1000x speedup compared with existing methods. At the same time, our solutions have much smaller and often optimal makespans.

Full Text: PDF