Article

Multi-agent Pathfinding with Communication Reinforcement Learning and Deadlock Detection

Authors:

Wen FuAuthors Info & Claims

Intelligent Robotics and Applications: 15th International Conference, ICIRA 2022, Harbin, China, August 1–3, 2022, Proceedings, Part I

Pages 493 - 504

https://doi.org/10.1007/978-3-031-13844-7_47

Published: 01 August 2022 Publication History

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.

References

[1]

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)

[2]

Jiang, J., Dun, C., Huang, T., Lu, Z.: Graph convolutional reinforcement learning. In: International Conference on Learning Representations (2019)

[3]

Jiang, J., Lu, Z.: Learning attentional communication for multi-agent cooperation. In: Advances in Neural Information Processing Systems 31 (2018)

[4]

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)

[5]

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)

[6]

Li Q, Lin W, Liu Z, and Prorok A Message-aware graph attention networks for large-scale multi-robot path planning IEEE Robot. Autom. Lett. 2021 6 3 5533-5540

[7]

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)

[8]

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)

[9]

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)

[10]

Riviere B, Hönig W, Yue Y, and Chung SJ Glas: global-to-local safe autonomy synthesis for multi-robot motion planning with end-to-end learning IEEE Robot. Automation Lett. 2020 5 3 4249-4256

[11]

Sartoretti G, Kerr J, Shi Y, Wagner G, Kumar TS, Koenig S, and Choset H Primal: Pathfinding via reinforcement and imitation multi-agent learning IEEE Robot. Automation Lett. 2019 4 3 2378-2385

[12]

Sharon G, Stern R, Felner A, and Sturtevant NR Conflict-based search for optimal multi-agent pathfinding Artif. Intell. 2015 219 40-66

[13]

Sheng, J., et al.: Learning structured communication for multi-agent reinforcement learning. arXiv preprint arXiv:2002.04235 (2020)

[14]

Silver, D.: Cooperative pathfinding. In: Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, vol. 1, pp. 117–122 (2005)

[15]

Sukhbaatar, S., Fergus, R., et al.: Learning multiagent communication with backpropagation. In: Advances in Neural Information Processing Systems 29 (2016)

[16]

Wu Z, Pan S, Chen F, Long G, Zhang C, and Philip SY A comprehensive survey on graph neural networks IEEE Trans. Neural Networks Learning Syst. 2020 32 1 4-24

[17]

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)

Cited By

Rahman MLiu TAlqahtani SElkind E(2023)Adversarial behavior exclusion for safe reinforcement learningProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/54(483-491)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/54
Rahman MAlqahtani SPintor MChen XTramèr F(2023)Task-Agnostic Safety for Reinforcement LearningProceedings of the 16th ACM Workshop on Artificial Intelligence and Security10.1145/3605764.3623913(139-148)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3605764.3623913

Index Terms

Multi-agent Pathfinding with Communication Reinforcement Learning and Deadlock Detection

Index terms have been assigned to the content through auto-classification.

Recommendations

SCRIMP: Scalable Communication for Reinforcement- and Imitation-Learning-Based Multi-Agent Pathfinding
AAMAS '23: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems

In this paper, we propose SCRIMP, a multi-agent reinforcement learning approach for multi-agent path finding. Our method learns individual policies from very small FOVs (3x3), by relying on a highly-scalable global/local communication mechanism based on ...
Reinforcement Learning of Communication in a Multi-agent Context
WI-IAT '11: Proceedings of the 2011 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology - Volume 02

In this paper, we present a reinforcement learning approach for multi-agent communication in order to learn what to communicate, when and to whom. This method is based on introspective agents that can reason about their own actions and data so as to ...
Model-based Sparse Communication in Multi-agent Reinforcement Learning
AAMAS '23: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems

Learning to communicate efficiently is central to multi-agent reinforcement learning (MARL). Existing methods often require agents to exchange messages intensively, which abuses communication channels and leads to high communication overhead. Only a few ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Intelligent Robotics and Applications: 15th International Conference, ICIRA 2022, Harbin, China, August 1–3, 2022, Proceedings, Part I

Aug 2022

800 pages

ISBN:978-3-031-13843-0

DOI:10.1007/978-3-031-13844-7

Editors:
Honghai Liu
Harbin Institute of Technology, Shenzhen, China
,
Zhouping Yin
Huazhong University of Science and Technology, Wuhan, China
,
Lianqing Liu
Shenyang Institute of Automation, Shenyang, Liaoning, China
,
Li Jiang
Harbin Institute of Technology, Harbin, China
,
Guoying Gu
Shanghai Jiao Tong University, Shanghai, China
,
Xinyu Wu
Shenzhen Institute of Advanced Technology, Shenzhen, China
,
Weihong Ren
Harbin Institute of Technology, Shenzhen, China

© The Author(s), under exclusive license to Springer Nature Switzerland AG 2022.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 August 2022

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rahman MLiu TAlqahtani SElkind E(2023)Adversarial behavior exclusion for safe reinforcement learningProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/54(483-491)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/54
Rahman MAlqahtani SPintor MChen XTramèr F(2023)Task-Agnostic Safety for Reinforcement LearningProceedings of the 16th ACM Workshop on Artificial Intelligence and Security10.1145/3605764.3623913(139-148)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3605764.3623913

View Options

View options

Media

Figures

Other

Tables

View Table of Contents