Prioritized planning algorithm for multi-robot collision avoidance based on artificial untraversable vertex

This paper presents a method to avoid collisions and deadlocks between mobile robots working collaboratively in a shared physical environment. Based on the shared knowledge of the robot’s direction and coordinates, we define five conflict types between robots and propose a new concept named Artificial Untraversable Vertex (AUV) to resolve the potential conflicts. Since conflict avoidance between robots is typically a real-time process, a heuristic search algorithm D* Lite with fast replanning characteristics is introduced. Once a robot finds that it may collide with another robot while moving along the preplanned path, a new conflict-free path can be calculated based on the AUV and D* Lite. The experimental results demonstrate that the proposed Multi-Robot Path Planning (MRPP) method can effectively avoid collisions and deadlocks between mobile robots.