Multi-Robot Motion Planning with Unlabeled Goals for Mobile Robots with Differential Constraints

Abstract

This paper studies the multi-robot motion-planning problem with unlabeled goals where n robots have to reach m goals. The proposed approach also takes into account the underlying dynamics of each robot to produce dynamically-feasible trajectories that enable the robots to reach all the goals while avoiding collisions with the obstacles and each other. The approach leverages the idea of combining sampling-based motion planning with goal assignment and multi-agent search. In fact, the goal-assignment layer seeks to effectively utilize the robots based on estimated costs to reach the remaining goals. The multi-agent search provides nonconflicting paths over roadmap graphs, which then guide the sampling-based expansion of a motion tree. The goal assignments and multi-agent paths are frequently updated based on the progress made during the motion-tree expansion. Simulation experiments using an increasing number of robots with nonlinear dynamics demonstrate the efficiency of the approach.