Scalable Asymptotically-Optimal Multi-Robot Motion Planning

TitleScalable Asymptotically-Optimal Multi-Robot Motion Planning
Publication TypeConference Paper
Year of Publication2017
AuthorsDobson, A, Solovey, K, Shome, R, Halperin, D, Bekris, KE
Conference Name1st IEEE International Symposium on Multi-Robot and Multi-Agent Systems (MRS)
Date Published12/2017
Publisher[Best Paper Award]
Conference LocationLos Angeles, CA, USA

Discovering high-quality paths for multi-robot problems can be achieved, in principle, through asymptotically-optimal data structures in the composite space of all robots, such as a sampling-based roadmap or a tree. The hardness of motion planning, however, which depends exponentially on the number of robots, renders the explicit construction of such structures impractical. This work proposes a scalable, sampling-based planner for coupled multi-robot problems that provides desirable path-quality guarantees. The proposed dRRT* is an informed, asymptotically-optimal extension of a prior method dRRT, which introduced the idea of building roadmaps for each robot and implicitly searching the tensor product of these structures in the composite space. The paper describes the conditions for convergence to optimal paths in multi-robot problems. Moreover, simulated experiments indicate dRRT* converges to high-quality paths and scales to higher numbers of robots where various alternatives fail. It can also be used on high-dimensional challenges, such as planning for robot manipulators.