Alternating Partition Prioritized Planning for Scalable Multi-Robot Coordination in Congested Environments

Motion planning for mobile robots is a well-studied problem in robotics. However, when it comes to Multi-Robot Motion Planning (MRMP) in congested environments with deadlock-prone layouts, such as narrow passages and crossroads, the problem is challenging. In this paper, we propose an efficient and scalable MRMP method guided with workspace skeleton, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Alternating Partition Prioritized Planning</i> (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathtt {AP3}$</tex-math></inline-formula>), enabling safe navigation of multi-robot systems in spatially-constrained settings. This method breaks the global fixed priority ordering and executes priority-changeable motion planning over topological skeleton partitions, achieving more flexible multi-robot coordination and efficient deadlock resolution. We also introduce a novel skeleton support planning algorithm that creates subproblems over the skeleton partitions to solve local collisions instead of restarting the path search from scratch to enhance the scalability of our planner. Evaluations across various scenarios show that <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathtt {AP3}$</tex-math></inline-formula> outperforms existing MRMP methods, significantly improving the solving efficiency and scalability.