nach oben

Swarm Intelligence

12.12.2023

Improved decentralized cooperative multi-agent path finding for robots with limited communication

verfasst von: Abderraouf Maoudj, Anders Lyhne Christensen

Erschienen in: Swarm Intelligence

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Multi-agent path finding (MAPF) holds significant practical relevance in numerous real-world applications involving fleets of mobile robots. The efficiency of such systems is directly determined by the quality of the paths calculated. Accordingly, extensive effort has been directed toward creating effective algorithms to address the MAPF problem. Yet, many existing MAPF algorithms still depend on offline centralized planning, paired with often unrealistic assumptions—such as robots having complete observability of the environment and moving in a deterministic fashion. The resultant plans are typically unsuitable for direct implementation on real robots where these assumptions do not usually apply. Aiming for more effective robot coordination under realistic conditions, we introduce an enhanced decentralized method. In this method, each robot coordinates solely with neighbors within a limited communication radius. Each robot attempts to follow the shortest path from its starting point to its designated target, addressing conflicts with other robots as they occur. Our method also incorporates path replanning, local motion coordination, and mechanisms to avoid robots becoming trapped in livelocks or deadlocks. Simulation-based results from various benchmark scenarios confirm that our enhanced decentralized method is both effective and scalable, accommodating up to at least 1000 robots.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Beinschob, P., & Reinke, C. (2015). Graph SLAM based mapping for AGV localization in large-scale warehouses. In 2015 IEEE International conference on intelligent computer communication and processing (ICCP), (pp. 245–248). IEEE.

Bobanac, V., & Bogdan, S. (2008). Routing and scheduling in multi-AGV systems based on dynamic banker algorithm. In Proceedings of the 16th mediterranean conference on control and automation, (pp. 1168–1173). IEEE.

CBS, EECBS and PIBT. https://github.com/Jiaoyang-Li/CBSH2-RTC, https://github.com/Jiaoyang-Li/EECBS, and https://github.com/Kei18/pibt2

Damani, M., Luo, Z., Wenzel, E., & Sartoretti, G. (2021). PRIMAL\(_2\): Pathfinding via reinforcement and imitation multi-agent learning-lifelong. IEEE Robotics and Automation Letters, 6(2), 2666–2673.CrossRef

Draganjac, I., Petrović, T., Miklić, D., Kovačić, Z., & Oršulić, J. (2020). Highly-scalable traffic management of autonomous industrial transportation systems. Robotics and Computer-Integrated Manufacturing, 63, 101915.CrossRef

Gange, G., Harabor, D., & Stuckey, Peter J. (2019). Lazy CBS: Implicit conflict-based search using lazy clause generation. In Proceedings of the international conference on automated planning and scheduling, (Vol. 29, pp. 155–162). AAAI Press.

Grenouilleau, F., van Hoeve, W.-J., & Hooker, J. N. (2019). A multi-label A* algorithm for multi-agent pathfinding. In Proceedings of the international conference on automated planning and scheduling, (Vol. 29, pp. 181–185). AAAI Press.

Hönig, W., Kumar, T.K., Cohen, L., Ma, H., Xu, H., Ayanian, N., & Koenig, S. (2016). Multi-agent path finding with kinematic constraints. In Proceedings of the twenty-sixth international conference on automated planning and scheduling (ICAPS), (pp. 477–485). AAAI Press.

Kammel, C., Kögel, T., Gareis, M., & Vossiek, M. (2022). A cost-efficient hybrid UHF RFID and odometry-based mobile robot self-localization technique with centimeter precision. IEEE Journal of Radio Frequency Identification, 6, 467–480.CrossRef

Lam, E., & Le Bodic, P. (2020). New valid inequalities in branch-and-cut-and-price for multi-agent path finding. In Proceedings of the international conference on automated planning and scheduling (ICAPS), (pp. 184–192). AAAI Press.

Li, J., Chen, Z., Harabor, D., Stuckey, P. J., & Koenig, S.(2021a). Anytime multi-agent path finding via large neighborhood search. In International joint conference on artificial intelligence, (pp. 4127–4135). IJCAI.

Li, J., Harabor, D., Stuckey, P. J., Ma, H., Gange, G., & Koenig, S. (2021). Pairwise symmetry reasoning for multi-agent path finding search. Artificial Intelligence, 301, 103574.MathSciNetCrossRefMATH

Li, J., Ruml, W., & Koenig, S. (2021c). EECBS: A bounded-suboptimal search for multi-agent path finding. In Proceedings of the AAAI conference on artificial intelligence, (pp. 12353–12362). AAAI Press.

Lian, Y., Xie, W., & Zhang, L. (2020). A probabilistic time-constrained based heuristic path planning algorithm in warehouse multi-AGV systems. IFAC-PapersOnLine, 53(2), 2538–2543.CrossRef

Ma, H., Harabor, D., Stuckey, P. J., Li, J., & Koenig, S. (2019). Searching with consistent prioritization for multi-agent path finding. In Proceedings of the AAAI conference on artificial intelligence, (pp. 7643–7650). AAAI Press.

Ma, H., Li, J., Kumar, T. K., & Koenig, S. (2017). Lifelong multi-agent path finding for online pickup and delivery tasks. In Proceedings of the international conference on autonomous agents and multiagent systems (AAMAS), (pp. 837–845). IFAAMAS.

Maoudj, A., & Christensen, A. L. (2022). Decentralized multi-agent path finding in warehouse environments for fleets of mobile robots with limited communication range. In 13th international conference on swarm intelligence (ANTS2022), (pp. 104–116). Springer.

Maoudj, A., Kouider, A., & Christensen, A. L. (2023). The capacitated multi-AGV scheduling problem with conflicting products: Model and a decentralized multi-agent approach. Robotics and Computer-Integrated Manufacturing, 81, 102514.CrossRef

Okumura, K., Machida, M., Défago, X., & Tamura, Y. (2022). Priority inheritance with backtracking for iterative multi-agent path finding. Artificial Intelligence, 310, 103752.MathSciNetCrossRefMATH

Rathi, A., & Vadali, M. (2021). Dynamic prioritization for conflict-free path planning of multi-robot systems. arXiv preprint arXiv:2101.01978

Reijnen, R., Zhang, Y., Nuijten, W., Senaras, C., & Goldak-Altgassen, M. (2020). Combining deep reinforcement learning with search heuristics for solving multi-agent path finding in segment-based layouts. In 2020 IEEE symposium series on computational intelligence (SSCI), (pp. 2647–2654). IEEE.

Ryan, M. R. K. (2008). Exploiting subgraph structure in multi-robot path planning. Journal of Artificial Intelligence Research, 31, 497–542.CrossRefMATH

Sajid, Q., Luna, R., & Bekris, K. (2012). Multi-agent pathfinding with simultaneous execution of single-agent primitives. In International symposium on combinatorial search, (pp. 88–96). AAAI Press.

Sartoretti, G., Kerr, J., Shi, Y., Wagner, G., Kumar, T. S., Koenig, S., & Choset, H. (2019). Primal: Pathfinding via reinforcement and imitation multi-agent learning. IEEE Robotics and Automation Letters, 4(3), 2378–2385.CrossRef

Sharon, G., Stern, R., Felner, A., & Sturtevant, N. R. (2015). Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence, 219, 40–66.MathSciNetCrossRefMATH

Skrynnik, A., Andreychuk, A., Yakovlev, K., & Panov, A. I. (2022). POGEMA: partially observable grid environment for multiple agents. arXiv preprint arXiv:2206.10944

Stephan, J., Fink, J., Kumar, V., & Ribeiro, A. (2017). Concurrent control of mobility and communication in multirobot systems. IEEE Transactions on Robotics, 33(5), 1248–1254.CrossRef

Stern, R., Sturtevant, N. R, Felner, A., Koenig, S., Ma, H., Walker, T. T., Li, J., Atzmon, D., Cohen, L., Satish Kumar, T.K. et al. (2019). Multi-agent pathfinding: Definitions, variants, and benchmarks. In Symposium on combinatorial search (SoCS), (pp. 151–158). AAAI Press.

Surynek, P. (2009). A novel approach to path planning for multiple robots in bi-connected graphs. In 2009 IEEE international conference on robotics and automation, (pp. 3613–3619). IEEE.

Surynek, P., Felner, A., Stern, R., Boyarski, E. (2016). Efficient SAT approach to multi-agent path finding under the sum of costs objective. In Proceedings of the Twenty-second European conference on artificial intelligence, ECAI, (pp. 810–818). IOS Press.

Van Den B., Jur P., & Overmars, M. H. (2005). Prioritized motion planning for multiple robots. In 2005 IEEE/RSJ international conference on intelligent robots and systems, pp 430–435. IEEE.

Varambally, S., Li, J., & Koenig, S. (2022). Which MAPF model works best for automated warehousing? In Proceedings of the international symposium on combinatorial search, (Vol. 15, pp. 190–198). IOS Press.

Wagner, G., & Choset, H. (2011). M*: A complete multirobot path planning algorithm with performance bounds. In 2011 IEEE/RSJ international conference on intelligent robots and systems, (pp. 3260–3267). IEEE.

Dingding, Yu., Xianliang, H., Liang, K., & Ying, J. (2022). A parallel algorithm for multi-AGV systems. Journal of Ambient Intelligence and Humanized Computing, 13(4), 2309–2323.CrossRef

Yu, J., & LaValle, S.M. (2013). Structure and intractability of optimal multi-robot path planning on graphs. In Proceedings of the twenty-seventh AAAI conference on artificial intelligence, (pp. 1443–1449). AAAI Press.

Zhang, Z., Guo, Q., & Yuan, Peijiang. (2017). Conflict-free route planning of automated guided vehicles based on conflict classification. In 2017 IEEE international conference on systems, man, and cybernetics (SMC), (pp. 1459–1464). IEEE.

Zhao, Y., Liu, X., Wang, G., Shaobo, W., & Han, S. (2020). Dynamic resource reservation based collision and deadlock prevention for multi-AGV. IEEE Access, 8, 82120–82130.CrossRef

Titel: Improved decentralized cooperative multi-agent path finding for robots with limited communication
verfasst von: Abderraouf Maoudj
Anders Lyhne Christensen
Publikationsdatum: 12.12.2023
Verlag: Springer US
Erschienen in: Swarm Intelligence
Print ISSN: 1935-3812
Elektronische ISSN: 1935-3820
DOI: https://doi.org/10.1007/s11721-023-00230-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Premium Partner