Decentralized and complete multi-robot motion planning in confined spaces

Abstract

This paper presents the Push-Swap-Wait (PSW) algorithm, a scalable, decentralized and complete approach for multi-robot motion planning in confined spaces. The algorithm builds upon a “push and swap” paradigm that has been used effectively in centralized navigation. This push and swap approach was expanded to apply to decentralized planning by adding a waiting mode to handle situations in which communication between robots is lost. The completeness of the PSW algorithm can be guaranteed in cases where the environment can be modeled as a tree T for which the number of leaf nodes is greater than the number of robots navigating through it. The algorithm has a time complexity that is linear with the number of robots currently within communication, indicating that this algorithm is well suited for scaling to large systems of robots. To validate the PSW algorithm it was implemented successfully in multi-robot simulations and on hardware with four Dr. Robot Jaguar Lite Robots.