Scalable Asymptotically-Optimal Multi-Robot Motion Planning
This addresses a scalability bottleneck in multi-robot systems for robotics applications, representing an incremental improvement over existing methods.
The paper tackles the problem of finding asymptotically-optimal paths in multi-robot motion planning, which becomes impractical with increasing numbers of robots due to high dimensionality, and presents dRRT* as a scalable method that converges to high-quality paths in simulations, scaling to higher robot counts where naive approaches fail.
Finding asymptotically-optimal paths in multi-robot motion planning problems could be achieved, in principle, using sampling-based planners in the composite configuration space of all of the robots in the space. The dimensionality of this space increases with the number of robots, rendering this approach impractical. This work focuses on a scalable sampling-based planner for coupled multi-robot problems that provides asymptotic optimality. It extends the dRRT approach, which proposed building roadmaps for each robot and searching an implicit roadmap in the composite configuration space. This work presents a new method, dRRT* , and develops theory for scalable convergence to optimal paths in multi-robot problems. Simulated experiments indicate dRRT* converges to high-quality paths while scaling to higher numbers of robots where the naive approach fails. Furthermore, dRRT* is applicable to high-dimensional problems, such as planning for robot manipulators