More Web Proxy on the site http://driver.im/

research-article

Public Access

A distributed solver for multi-agent path finding problems

Authors:

Phoebe O. Toups Dugas,

William YeohAuthors Info & Claims

DAI '19: Proceedings of the First International Conference on Distributed Artificial Intelligence

Article No.: 2, Pages 1 - 7

https://doi.org/10.1145/3356464.3357702

Published: 13 October 2019 Publication History

Abstract

Multi-Agent Path Finding (MAPF) problems are traditionally solved in a centralized manner. There are works focusing on completeness, optimality, performance, or a tradeoff between them. However, there are only a few works based on spatial distribution. In this paper, we introduce ros-dmapf, a distributed MAPF solver. It consists of multiple MAPF sub-solvers, which---besides solving their assigned sub-problems---interact with each other to solve a given MAPF problem. In the current implementation, the sub-solvers are answer set planning systems for multiple agents, and are created based on spatial distribution of the problem. Interactions between components of ros-dmapf are facilitated by the Robot Operating System (ROS). The highlights of ros-dmapf are its scalability and a high degree of parallelism. We empirically evaluate ros-dmapf using the move-only domain of the asprilo system and results suggest that ros-dmapf scales up well. For instance, ros-dmapf gives a solution of length around 600 for a MAPF problem with 2000 robots in randomly generated 100×100 obstacle-free maps---a problem beyond the capability of a single sub-solver---within 7 minutes on a consumer laptop. We also evaluate ros-dmapf against some other MAPF solvers and results show that the system performs well. We also discuss possible improvements for future work.

References

[1]

Eli Boyarski, Ariel Feiner, Roni Stern, Guni Sharon, David Tolpin, Oded Betzalel, and Solomon Eyal Shimony. 2015. ICBS: Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding. In International Joint Conference on Artificial Intelligence (IJCAI). 740--746.

[2]

Eli Boyarski, Ariel Felner, Roni Stern, Guni Sharon, David Tolpin, Oded Betzalel, and Solomon Eyal Shimony. 2015. ICBS: Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding. In International Joint Conference on Artificial Intelligence (IJCAI). 740--746.

[3]

Satyendra Singh Chouhan and Rajdeep Niyogi. 2015. DMAPP: A Distributed Multi-agent Path Planning Algorithm. In Australasian Joint Conference on Artificial Intelligence (AI). 123--135.

[4]

Liron Cohen, Tansel Uras, T. K. Satish Kumar, Hong Xu, Nora Ayanian, and Sven Koenig. 2016. Improved Solvers for Bounded-Suboptimal Multi-Agent Path Finding. In International Joint Conference on Artificial Intelligence (IJCAI). 3067--3074.

[5]

Boris de Wilde, Adriaan ter Mors, and Cees Witteveen. 2014. Push and Rotate: a Complete Multi-Agent Pathfinding Algorithm. Journal of Artificial Intelligence Research (JAIR) 51 (2014), 443--492.

Digital Library

[6]

Esra Erdem, Doga Gizem Kisa, Umut Öztok, and Peter Schüller. 2013. A General Formal Framework for Pathfinding Problems with Multiple Agents. In AAAI Conference on Artificial Intelligence. 290--296.

[7]

Ariel Felner, Jiaoyang Li, Eli Boyarski, Hang Ma, Liron Cohen, T. K. Satish Kumar, and Sven Koenig. 2018. Adding Heuristics to Conflict-Based Search for Multi-Agent Path Finding. In International Conference on Automated Planning and Scheduling (ICAPS). 83--87.

[8]

Graeme Gange, Daniel Harabor, and Peter J. Stuckey. 2019. Lazy CBS: Implicit Conflict-Based Search Using Lazy Clause Generation. In International Conference on Automated Planning and Scheduling (ICAPS). 155--162.

[9]

Martin Gebser, Roland Kaminski, Benjamin Kaufmann, and Torsten Schaub. 2019. Multi-Shot ASP Solving with Clingo. Theory and Practice of Logic Programming (TPLP) 19, 1 (2019), 27--82.

[10]

Martin Gebser, Philipp Obermeier, Thomas Otto, Torsten Schaub, Orkunt Sabuncu, Van Nguyen, and Tran Cao Son. 2018. Experimenting with Robotic Intra-Logistics Domains. Theory and Practice of Logic Programming (TPLP) 18, 3-4 (2018), 502--519.

[11]

Michael Gelfond and Vladimir Lifschitz. 1988. The Stable Model Semantics for Logic Programming. In Logic Programming, Proceedings of the Fifth International Conference and Symposium (ICLP/SLP). 1070--1080.

[12]

Meir Goldenberg, Ariel Felner, Roni Stern, Guni Sharon, Nathan R. Sturtevant, Robert C. Holte, and Jonathan Schaeffer. 2014. Enhanced Partial Expansion A*. Journal of Artificial Intelligence Research (JAIR) 50 (2014), 141--187.

Digital Library

[13]

Jörg Hoffmann and Bernhard Nebel. 2001. The FF Planning System: Fast Plan Generation Through Heuristic Search. Journal of Artificial Intelligence Research (JAIR) 14 (2001), 253--302.

Digital Library

[14]

Wolfgang Hönig, Scott Kiesel, Andrew Tinka, Joseph W. Durham, and Nora Ayanian. 2018. Conflict-Based Search with Optimal Task Assignment. In International Conference on Autonomous Agents and MultiAgent Systems (AAMAS). 757--765.

[15]

Jiaoyang Li, Daniel Harabor, Peter J. Stuckey, Hang Ma, and Sven Koenig. 2019. Disjoint Splitting for Multi-Agent Path Finding with Conflict-Based Search. In International Conference on Automated Planning and Scheduling (ICAPS). 279--283.

[16]

Jiaoyang Li, Daniel Harabor, Peter J. Stuckey, Hang Ma, and Sven Koenig. 2019. Symmetry-Breaking Constraints for Grid-Based Multi-Agent Path Finding. In AAAI Conference on Artificial Intelligence. 6087--6095.

[17]

Jiaoyang Li, Pavel Surynek, Ariel Felner, Hang Ma, T. K. Satish Kumar, and Sven Koenig. 2019. Multi-Agent Path Finding for Large Agents. In AAAI Conference on Artificial Intelligence. 7627--7634.

[18]

Minghua Liu, Hang Ma, Jiaoyang Li, and Sven Koenig. 2019. Task and Path Planning for Multi-Agent Pickup and Delivery. In International Conference on Autonomous Agents and MultiAgent Systems (AAMAS). 1152--1160.

[19]

Ryan Luna and Kostas E. Bekris. 2011. Push and Swap: Fast Cooperative Path-Finding with Completeness Guarantees. In International Joint Conference on Artificial Intelligence (IJCAI). 294--300.

[20]

Hang Ma, Wolfgang Hönig, T. K. Satish Kumar, Nora Ayanian, and Sven Koenig. 2019. Lifelong path planning with kinematic constraints for multi-agent pickup and delivery. In AAAI Conference on Artificial Intelligence, Vol. 33. 7651--7658.

Digital Library

[21]

Hang Ma, Glenn Wagner, Ariel Felner, Jiaoyang Li, T. K. Satish Kumar, and Sven Koenig. 2018. Multi-Agent Path Finding with Deadlines. In International Joint Conference on Artificial Intelligence (IJCAI). 417--423.

[22]

Robert Morris, Corina S. Pasareanu, Kasper Søe Luckow, Waqar Malik, Hang Ma, T. K. Satish Kumar, and Sven Koenig. 2016. Planning, Scheduling and Monitoring for Airport Surface Operations. In AAAI Workshop on Planning for Hybrid Systems.

[23]

Van Nguyen, Philipp Obermeier, Tran Cao Son, Torsten Schaub, and William Yeoh. 2017. Generalized Target Assignment and Path Finding Using Answer Set Programming. In International Joint Conference on Artificial Intelligence (IJCAI). 1216--1223.

[24]

Morgan Quigley, Brian Gerkey, Ken Conley, Josh Faust, Tully Foote, Jeremy Leibs, Eric Berger, Rob Wheeler, and Andrew Ng. 2009. ROS: an Open-source Robot Operating System. In ICRA Workshop on Open Source Software in Robotics.

[25]

Guni Sharon, Roni Stern, Ariel Felner, and Nathan R. Sturtevant. 2015. Conflict-Based Search for Optimal Multi-Agent Pathfinding. Artificial Intelligence (AIJ) 219 (2015), 40--66.

Digital Library

[26]

David Silver. 2005. Cooperative Pathfinding. In Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE). 117--122.

[27]

Patrik Simons, Ilkka Niemelä, and Timo Soininen. 2002. Extending and Implementing the Stable Model Semantics. Artificial Intelligence (AIJ) 138, 1-2 (2002), 181--234.

Digital Library

[28]

Tran Cao Son and Marcello Balduccini. 2018. Answer Set Planning in Single-and Multi-Agent Environments. Künstliche Intelligenz (KI) 32, 2-3 (2018), 133--141.

[29]

Roni Stern, Nathan R. Sturtevant, Ariel Felner, Sven Koenig, Hang Ma andw Thayne T. Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, T. K. Satish Kumar, Roman Barták, and Eli Boyarski. 2019. Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks. In International Symposium on Combinatorial Search (SOCS). 151--159.

[30]

Pavel Surynek, Ariel Felner, Roni Stern, and Eli Boyarski. 2016. Efficient SAT Approach to Multi-Agent Path Finding Under the Sum of Costs Objective. In European Conference on Artificial Intelligence (ECAI). 810--818.

[31]

Manuela M. Veloso, Joydeep Biswas, Brian Coltin, and Stephanie Rosenthal. 2015. CoBots: Robust Symbiotic Autonomous Mobile Service Robots. In International Joint Conference on Artificial Intelligence (IJCAI). 4423--4429.

[32]

Glenn Wagner and Howie Choset. 2015. Subdimensional Expansion for Multi-robot Path Planning. Artificial Intelligence (AIJ) 219 (2015), 1--24.

Digital Library

[33]

Ko-Hsin Cindy Wang and Adi Botea. 2008. Fast and Memory-Efficient Multi-Agent Pathfinding. In International Conference on Automated Planning and Scheduling (ICAPS). 380--387.

[34]

Ko-Hsin Cindy Wang and Adi Botea. 2011. MAPP: a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees. Journal of Artificial Intelligence Research (JAIR) 42 (2011), 55--90.

[35]

Christopher Makoto Wilt and Adi Botea. 2014. Spatially Distributed Multiagent Path Planning. In International Conference on Automated Planning and Scheduling (ICAPS). 332--340.

[36]

Peter R. Wurman, Raffaello D'Andrea, and Mick Mountz. 2008. Coordinating Hundreds of Cooperative, Autonomous Vehicles in Warehouses. AI Magazine 29, 1 (2008), 9--20.

Digital Library

[37]

Jingjin Yu and Steven M. LaValle. 2016. Optimal Multirobot Path Planning on Graphs: Complete Algorithms and Effective Heuristics. IEEE Transactions on Robotics (T-RO) 32, 5 (2016), 1163--1177.

Digital Library

Cited By

Wong CWeng KYu B(2024)Multi-Robot Navigation System Design Based on Proximal Policy Optimization AlgorithmInformation10.3390/info1509051815:9(518)Online publication date: 26-Aug-2024
https://doi.org/10.3390/info15090518
Pertzovskiy AZivan RAgmon NAgmon NAn BRicci AYeoh W(2023)CAMS: Collision Avoiding Max-Sum for Mobile Sensor TeamsProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598625(104-112)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598625
Rajaratnam DSchaub TWanko PChen KLiu SSon T(2023)Solving an Industrial-Scale Warehouse Delivery Problem with Answer Set Programming Modulo Difference ConstraintsAlgorithms10.3390/a1604021616:4(216)Online publication date: 21-Apr-2023
https://doi.org/10.3390/a16040216
Show More Cited By

Index Terms

A distributed solver for multi-agent path finding problems
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Cooperation and coordination
      2. Multi-agent systems

Recommendations

Self-Organizing Agent Coalitions in Distributed Multi-agent Systems
CICN '10: Proceedings of the 2010 International Conference on Computational Intelligence and Communication Networks

Self-Organization refers to the process through which a system changes its internal organization to adapt to changes in its goals & the environment, without explicit external control. The self-organizing capability seen in many natural and artificial ...
Multi-Agent Path Finding with Destination Choice
PRIMA 2020: Principles and Practice of Multi-Agent Systems
Abstract
Multi-agent path finding problem (MAPF) is a problem to find collision-free paths on a graph for multiple agents from their initial locations to their destinations. MAPF has mainly two types of variants regarding the usage of agent destination; ...
Supporting internet-scale multi-agent systems
DKE 40

The Internet provides a large-scale environment for (intelligent) software agents. Agents are autonomous (mobile) processes, capable of communication with other agents, interaction with the world, and adaptation to changes in their environment. Current ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

DAI '19: Proceedings of the First International Conference on Distributed Artificial Intelligence

October 2019

85 pages

ISBN:9781450376563

DOI:10.1145/3356464

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 October 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Office of Integrative Activities
Division of Human Resource Development
Division of Information and Intelligent Systems

Conference

DAI '19

DAI '19: First International Conference on Distributed Artificial Intelligence

October 13 - 15, 2019

Beijing, China

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
853
Total Downloads

Downloads (Last 12 months)231
Downloads (Last 6 weeks)27

Reflects downloads up to 09 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wong CWeng KYu B(2024)Multi-Robot Navigation System Design Based on Proximal Policy Optimization AlgorithmInformation10.3390/info1509051815:9(518)Online publication date: 26-Aug-2024
https://doi.org/10.3390/info15090518
Pertzovskiy AZivan RAgmon NAgmon NAn BRicci AYeoh W(2023)CAMS: Collision Avoiding Max-Sum for Mobile Sensor TeamsProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598625(104-112)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598625
Rajaratnam DSchaub TWanko PChen KLiu SSon T(2023)Solving an Industrial-Scale Warehouse Delivery Problem with Answer Set Programming Modulo Difference ConstraintsAlgorithms10.3390/a1604021616:4(216)Online publication date: 21-Apr-2023
https://doi.org/10.3390/a16040216
Meli DNakawala HFiorini P(2023)Logic programming for deliberative robotic task planningArtificial Intelligence Review10.1007/s10462-022-10389-w56:9(9011-9049)Online publication date: 18-Jan-2023
https://dl.acm.org/doi/10.1007/s10462-022-10389-w
Pianpak PLi JSon T(2023)Load Balancing in Distributed Multi-Agent Path Finder (DMAPF)Engineering Multi-Agent Systems10.1007/978-3-031-48539-8_9(130-147)Online publication date: 29-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-48539-8_9
Ho FGeraldes RGoncalves ARigault BSportich BKubo DCavazza MPrendinger H(2022)Decentralized Multi-Agent Path Finding for UAV Traffic ManagementIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2020.301939723:2(997-1008)Online publication date: Feb-2022
https://doi.org/10.1109/TITS.2020.3019397
CAO TRAN SPONTELLI EBALDUCCINI MSCHAUB T(2022)Answer Set Planning: A SurveyTheory and Practice of Logic Programming10.1017/S147106842200007223:1(226-298)Online publication date: 1-Apr-2022
https://doi.org/10.1017/S1471068422000072
Pianpak PSon T(2022)Improving Problem Decomposition and Regulation in Distributed Multi-Agent Path Finder (DMAPF)PRIMA 2022: Principles and Practice of Multi-Agent Systems10.1007/978-3-031-21203-1_10(156-172)Online publication date: 16-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-21203-1_10
Pianpak PCao Son T(2021)DMAPF: A Decentralized and Distributed Solver for Multi-Agent Path Finding Problem with ObstaclesElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.345.24345(99-112)Online publication date: 17-Sep-2021
https://doi.org/10.4204/EPTCS.345.24
Gomez RHernandez CBaier J(2021)A Compact Answer Set Programming Encoding of Multi-Agent PathfindingIEEE Access10.1109/ACCESS.2021.30535479(26886-26901)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3053547

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents