Abstract
The learning-based approach has been proved to be an effective way to solve multi-agent path finding (MAPF) problems. For large warehouse systems, the distributed strategy based on learning method can effectively improve efficiency and scalability. But compared with the traditional centralized planner, the learning-based approach is more prone to deadlocks. Communication learning has also made great progress in the field of multi-agent in recent years and has been be introduced into MAPF. However, the current communication methods provide redundant information for reinforcement learning and interfere with the decision-making of agents. In this paper, we combine the reinforcement learning with communication learning. The agents select its communication objectives based on priority and mask off redundant communication links. Then we use a feature interactive network based on graph neural network to achieve the information aggregation. We also introduce an additional deadlock detection mechanism to increase the likelihood of an agent escaping a deadlock. Experiments demonstrate our method is able to plan collision-free paths in different warehouse environments.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Foerster, J., Assael, I.A., De Freitas, N., Whiteson, S.: Learning to communicate with deep multi-agent reinforcement learning. In: Advances in Neural Information Processing Systems 29 (2016)
Jiang, J., Dun, C., Huang, T., Lu, Z.: Graph convolutional reinforcement learning. In: International Conference on Learning Representations (2019)
Jiang, J., Lu, Z.: Learning attentional communication for multi-agent cooperation. In: Advances in Neural Information Processing Systems 31 (2018)
Kim, D., Moon, S., Hostallero, D., Kang, W.J., Lee, T., Son, K., Yi, Y.: Learning to schedule communication in multi-agent reinforcement learning. In: International Conference on Learning Representations (2018)
Li, Q., Gama, F., Ribeiro, A., Prorok, A.: Graph neural networks for decentralized multi-robot path planning. In: 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 11785–11792. IEEE (2020)
Li, Q., Lin, W., Liu, Z., Prorok, A.: Message-aware graph attention networks for large-scale multi-robot path planning. IEEE Robot. Autom. Lett. 6(3), 5533–5540 (2021)
Liu, Z., Chen, B., Zhou, H., Koushik, G., Hebert, M., Zhao, D.: Mapper: multi-agent path planning with evolutionary reinforcement learning in mixed dynamic environments. In: 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 11748–11754. IEEE (2020)
Long, P., Fan, T., Liao, X., Liu, W., Zhang, H., Pan, J.: Towards optimally decentralized multi-robot collision avoidance via deep reinforcement learning. In: 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 6252–6259. IEEE (2018)
Ma, Z., Luo, Y., Ma, H.: Distributed heuristic multi-agent path finding with communication. In: 2021 IEEE International Conference on Robotics and Automation (ICRA), pp. 8699–8705. IEEE (2021)
Riviere, B., Hönig, W., Yue, Y., Chung, S.J.: Glas: global-to-local safe autonomy synthesis for multi-robot motion planning with end-to-end learning. IEEE Robot. Automation Lett. 5(3), 4249–4256 (2020)
Sartoretti, G., Kerr, J., Shi, Y., Wagner, G., Kumar, T.S., Koenig, S., Choset, H.: Primal: Pathfinding via reinforcement and imitation multi-agent learning. IEEE Robot. Automation Lett. 4(3), 2378–2385 (2019)
Sharon, G., Stern, R., Felner, A., Sturtevant, N.R.: Conflict-based search for optimal multi-agent pathfinding. Artif. Intell. 219, 40–66 (2015)
Sheng, J., et al.: Learning structured communication for multi-agent reinforcement learning. arXiv preprint arXiv:2002.04235 (2020)
Silver, D.: Cooperative pathfinding. In: Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, vol. 1, pp. 117–122 (2005)
Sukhbaatar, S., Fergus, R., et al.: Learning multiagent communication with backpropagation. In: Advances in Neural Information Processing Systems 29 (2016)
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., Philip, S.Y.: A comprehensive survey on graph neural networks. IEEE Trans. Neural Networks Learning Syst. 32(1), 4–24 (2020)
Xu, Y., Li, Y., Liu, Q., Gao, J., Liu, Y., Chen, M.: Multi-agent pathfinding with local and global guidance. In: 2021 IEEE International Conference on Networking, Sensing and Control (ICNSC), vol. 1, pp. 1–7 (2021)
Acknowledgment
This research was supported by National Key R &D Program of China 2018YFB1305500, National Natural Science Foundation (61977019, U1813206) and Shenzhen basic research program (JCYJ20180507183837726, JSGG20201103093802006).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Ye, Z., Li, Y., Guo, R., Gao, J., Fu, W. (2022). Multi-agent Pathfinding with Communication Reinforcement Learning and Deadlock Detection. In: Liu, H., et al. Intelligent Robotics and Applications. ICIRA 2022. Lecture Notes in Computer Science(), vol 13455. Springer, Cham. https://doi.org/10.1007/978-3-031-13844-7_47
Download citation
DOI: https://doi.org/10.1007/978-3-031-13844-7_47
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-13843-0
Online ISBN: 978-3-031-13844-7
eBook Packages: Computer ScienceComputer Science (R0)