Multi-Agent Pathfinding for Deadlock Avoidance on Rotational Movements
Frodo Kin Sun Chan, Yan Nei Law, Bonny Lu, Tom Chick, Edmond Shiao Bun Lai, Ming Ge · 2022 17th International Conference on Control, Automation, Robotics and Vision (ICARCV) · 2022
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.