Published Papers

Volume 32 - Issue 1 (Regular Issue)
Transactions Papers

Multi-agent pathfinding for deadlock handling in rotational movements

Frodo Kin Sun Chan, Yan Nei Law and Edmond Shiao Bun Lai
Pages: 1-10Published: 04 Feb 2025
DOI: 10.33430/V32N1THIE-2023-0047
Cite thisHide

Chan KS, Law YN and Lai SB, Multi-agent pathfinding for deadlock handling in rotational movements, HKIE Transactions, Vol. 32, No. 1 (Regular Issue), Article THIE-2023-0047, 2025, 10.33430/V32N1THIE-2023-0047

 Copy

Abstract:

Multi-agent pathfinding (MAPF) is a challenging problem especially in environments with a large number of agents and small map size. Although some recent studies revealed that the reinforcement learning approach is feasible to train the agents for resolving the deadlock problem at large scales in terms of the number of agents, the robots, which commonly appear in warehouses, are ignored in their design. As the robots in warehouses using zero-radius right-angle turns (e.g., KIVA robots) usually stay in the same location for a long time with the same rotation movements, the deadlock problem becomes more severe especially in dense areas. In this paper, a reinforcement and imitation learning algorithm with a deadlock avoidance scheme with reinforcement and imitation learning, a deadlock breaking scheme and a deadlock resolving scheme are proposed for resolving the deadlock problem by considering the configurations for a rotation-based warehouse environment including moving forward, rotating clockwise, and rotating anticlockwise only. In addition, a light model of the proposed algorithm is also presented to speed up the inference process. In the experimental results, the proposed algorithm and its light version are shown to be effective and useful for handling different scenarios of the deadlock problem.

Keywords:

Multi-agent systems; robotics and automation; reinforcement learning; multi-agent pathfinding; zero-radius turning; right angle turning; mobile robots

Reference List:

  1. Baxter JL, Burke E, Garibaldi JM and Norman M (2007). Multi-robot search and rescue: A potential field based approach. Autonomous Robots and Agents, 76, pp. 9-16.
  2. Cáp M, Novák P, Selecký M, Faigl J and Vokffnek J (2013). Asynchronous decentralized prioritized planning for coordination in multirobot system. In: 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems. Tokyo: IEEE, pp. 3822–3829.
  3. Chan FKS, Law YN, Lu B, Chick T, Lai ESB and Ge M (2022). Multi-Agent Pathfinding for Deadlock Avoidance on Rotational Movements. In: 2022 17th International Conference on Control, Automation, Robotics and Vision. Singapore: IEEE, pp. 765-770.
  4. Chung J, Gulcehre C, Cho K and Bengio Y (2014). Empirical evaluation of gated recurrent neural networks on sequence modelling. arXiv preprint,abs/1412.3555.
  5. Cui R, Gao B and Guo J (2011). Pareto-optimal coordination of multiple robots with safety guarantees. Autonomous Robots, 32(3), pp. 189-205.
  6. Ferner C, Wagner G and Choset H (2013). ODrM*: optimal multirobot path planning in low dimensional search spaces. In: 2013 IEEE International Conference on Robotics and Automation. Karlsruhe: IEEE, pp. 3854-3859.
  7. Foerster J, Assael IA, de Freitas N and Whiteson S (2016). Learning to communicate with deep multiagent reinforcement learning. In: Proceedings of the 30th International Conference on Neural Information Processing Systems. Barcelona:Curran Associates Inc., pp. 2145–2153.
  8. Foerster J, Farquhar G, Afouras T, Nardelli N and Whiteson S (2017). Counterfactual multi-agent policy gradients. arXiv preprint, abs/1705.08926.
  9. Gupta JK, Egorov M and Kochenderfer M (2017). Cooperative multiagent control using deep reinforcement learning. In: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems. São Paulo: International Foundation for Autonomous Agents and Multiagent Systems, pp. 66-83.
  10. Hönig W, Kiesel S, Tinka A, Durham JW and Ayanian N (2019). Persistent and Robust Execution of MAPF Schedules in Warehouses. IEEE Robotics and Automation Letters, 4(2), pp. 1125-1131.
  11. Iandola FN, Han S, Moskewicz MW, Ashraf K, Dally WJ, Keutzer K (2016). SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and <0.5MB model size. arXiv preprint, abs/1602.07360.
  12. Li P, Yang H, Li H and Liang S (2022). Nonlinear ESO-based tracking control for warehouse mobile robots with detachable loads. Robotics and Autonomous Systems, 149(C), pp. 103945.
  13. Lowe R, Wu Y, Tamar A, Harb J, Abbeel OP and Mordatch, I. (2017). Multi-agent actor-critic for mixed cooperative-competitive environments. In: Proceedings of the 31st International Conference on Neural Information Processing Systems. Long Beach: Curran Associates Inc., pp. 6382–6393.
  14. Ma H, Tovey CA, Sharon G, Kumar TS and Koenig S (2016). Multi-Agent Path Finding with Payload Transfers and the Package-Exchange Robot-Routing Problem. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. Phoenix: AAAI press, pp. 3166–3173.
  15. Morris R, Pasareanu C, Luckow K, Malik W, Ma H, Kumar S and Koenig S (2016). Planning, scheduling and monitoring for airport surface operations. In: AAAI-16 Workshop on Planning for Hybrid Systems.
  16. Sanchez G and Latombe J (2002). Using a PRM planner to compare centralized and decoupled planning for multi-robot systems. In: Proceedings 2002 IEEE International Conference on Robotics and Automation. Washington: IEEE, pp. 2112-2119.
  17. Sartoretti G, Kerr J, Shi Y, Wagner G, Satish Kumar TK, Koenig S and Choset H (2019). PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning. IEEE Robotics and Automation Letters, 4(3), pp. 2378-2385.
  18. Sharon G, Stern R, Felner A and Sturtevant N (2012). Conflict-based search for optimal multi-agent path finding. In: Proceedings of the AAAI Conference on Artificial Intelligence 26(1). Toronto: AAAI Press, pp. 563-569.
  19. Silver D (2005). Cooperative pathfinding. In: Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. Marina Del Rey: AAAI Press, pp. 117-122.
  20. Van Den Berg J, Guy SJ, Lin M and Manocha D (2011). Reciprocal n-body collision avoidance. In: 14th International Symposium of Robotic Research. Lucerne: Springer Tracts in Advanced Robotics, pp. 3-19.
  21. Veloso M, Biswas J, Coltin B and Rosenthal S (2015). CoBots: Robust symbiotic autonomous mobile service robots. In: Proceedings of the 24th International Conference on Artificial Intelligence. Buenos Aires: AAAI Press, pp. 4423-4429.
  22. Wang C, Deng D, Xu L and Wang W (2022). Resource Scheduling Based on Deep Reinforcement Learning in UAV Assisted Emergency Communication Networks. IEEE Transactions on Communications, 70(6), pp. 3834-3848.
  23. Wang G, Wu C, Du Z, Tsutomu Y, Rui Y and Lei Z (2023). DRL-Assisted Network Selection for Federated IoV. IEEE Internet of Things Magazine, 6(3), pp. 86-90.
  24. Wurman PR, D’Andrea R and Mountz M (2008). Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI Magazine, 29(1), pp. 9-20.
>> more<< less