Multi-robot path-planning with subgraphs
Malcolm Ryan · International Conference on Robotics and Automation · 2006
In this paper we consider the problem of planning paths for an homogeneous group of robots around a shared roadmap. We show that significant speedup can be achieved if we decompose the roadmap into subgraphs of known structure, such as stacks and cliques, and build plans hierarchically, first between connected subgraphs, then inside the subgraphs. We show that this approach while suboptimal is nevertheless complete and can provide a significant improvement in planning time over a nonhierarchical planner.