Scalable Distributed Algorithms for Multi-Robot Near-Optimal Motion Planning

Abstract

This paper investigates a class of motion planning problems where multiple unicycle robots desire to safely reach their respective goal regions with minimal traveling times. We present a distributed algorithm which integrates decoupled optimal feedback planning and distributed conflict resolution. Collision avoidance and finite-time arrival at the goal regions are formally guaranteed.Further, the computational complexity of the proposed algorithm is independent of the robot number. A set of simulations is conduct to verify the scalability and near-optimality of the proposed algorithm.