Multi-Robot Motion Planning With Dynamics via Coordinated Sampling-Based Expansion Guided by Multi-Agent Search

Abstract

This letter combines sampling-based motion planning with multi-agent search to efficiently solve challenging multi-robot motion-planning problems with dynamics. This idea has shown promise in prior work that developed a centralized approach to expand a motion tree in the composite state space of all the robots along routes obtained by multi-agent search over a discrete abstraction. Still, the centralized expansion imposes a significant bottleneck due to the curse of dimensionality associated with the high-dimensional composite state space. To improve efficiency and scalebility, we propose a coordinated expansion of the motion tree along routes obtained by the multi-agent search. We first develop a single-robot sampling-based approach to closely follow a given route σ . The salient aspect of the proposed coordinated expansion is to invoke the route follower one robot at a time, ensuring that robot i follows σ while avoiding not only the obstacles but also robots 1, . . . , i - 1. In the next iteration, the motion tree could be expanded from another state along other routes. This enables the approach to progress rapidly and achieve significant speedups over a centralized approach.