Multi-Agent Pathfinding for Deadlock Avoidance on Rotational Movements

Abstract

Deadlock is always a challenging problem for multi-agent pathfinding, especially when the system is in high scales in terms of number of agents and map size. Some recent studies showed that the agents can learn to resolve the deadlock problem through reinforcement learning. However, most of them are not designed for non-holonomic robots, which are commonly applied in warehouses. In particular, the rotation movement may cause the agents staying at the same locations for a long time, and the deadlock happens more frequently especially in dense environment. In this paper, an algorithm called MAPF-rot with a deadlock breaking scheme is proposed to tackle the deadlock problem arising from the rotation movement in the multi-agent pathfinding problem. Experiments are performed to demonstrate the efficiency of the proposed algorithm.