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

article

The increasing cost tree search for optimal multi-agent pathfinding

Authors:

Meir Goldenberg,

Ariel FelnerAuthors Info & Claims

Artificial Intelligence, Volume 195

Pages 470 - 495

https://doi.org/10.1016/j.artint.2012.11.006

Published: 01 February 2013 Publication History

Abstract

We address the problem of optimal pathfinding for multiple agents. Given a start state and a goal state for each of the agents, the task is to find minimal paths for the different agents while avoiding collisions. Previous work on solving this problem optimally, used traditional single-agent search variants of the A* algorithm. We present a novel formalization for this problem which includes a search tree called the increasing cost tree (ICT) and a corresponding search algorithm, called the increasing cost tree search (ICTS) that finds optimal solutions. ICTS is a two-level search algorithm. The high-level phase of ICTS searches the increasing cost tree for a set of costs (cost per agent). The low-level phase of ICTS searches for a valid path for every agent that is constrained to have the same cost as given by the high-level phase. We analyze this new formalization, compare it to the A* search formalization and provide the pros and cons of each. Following, we show how the unique formalization of ICTS allows even further pruning of the state space by grouping small sets of agents and identifying unsolvable combinations of costs. Experimental results on various domains show the benefits and limitations of our new approach. A speedup of up to 3 orders of magnitude was obtained in some cases.

References

[1]

Bennewitz, Maren, Burgard, Wolfram and Thrun, Sebastian, Finding and optimizing solvable priority schemes for decoupled path planning techniques for teams of mobile robots. Robotics and Autonomous Systems. v41 i2-3. 89-99.

[2]

Bonet, Blai and Geffner, Hector, Planning as heuristic search. Artificial Intelligence. v129 i1-2. 5-33.

Digital Library

[3]

Dechter, Rina and Pearl, Judea, Generalized best-first search strategies and the optimality of A*. Journal of the ACM. v32 i3. 505-536.

Digital Library

[4]

Dresner, Kurt and Stone, Peter, A multiagent approach to autonomous intersection management. JAIR. v31. 591-656.

Digital Library

[5]

Ariel Felner, Meir Goldenberg, Guni Sharon, Roni Stern, Tal Beja, Nathan R. Sturtevant, Jonathan Schaeffer, Robert Holte, Partial-expansion A* with selective node generation, in: AAAI, 2012, pp. 471-477.

[6]

Arnon Gilboa, Amnon Meisels, Ariel Felner, Distributed navigation in an unknown physical environment, in: AAMAS, 2006, pp. 553-560.

Digital Library

[7]

Devin K. Grady, Kostas E. Bekris, Lydia E. Kavraki, Asynchronous distributed motion planning with safety guarantees under second-order dynamics, in: WAFR, 2010, pp. 53-70.

[8]

Hart, P.E., Nilsson, N.J. and Raphael, B., A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics. vSCC-4 i2. 100-107.

[9]

Helmert, Malte, Understanding Planning Tasks: Domain Complexity and Heuristic Decomposition. 2008. Lecture Notes in Computer Science, 2008.Springer.

Digital Library

[10]

M. Renee Jansen, Nathan R. Sturtevant, A new approach to cooperative pathfinding, in: AAMAS, vol. 3, 2008, pp. 1401-1404.

Digital Library

[11]

Mokhtar M. Khorshid, Robert C. Holte, Nathan R. Sturtevant, A polynomial-time algorithm for non-optimal multi-agent pathfinding, in: SOCS, 2011, pp. 76-83.

[12]

Richard E. Korf, Finding optimal solutions to Rubik's cube using pattern databases, in: AAAI/IAAI, 1997, pp. 700-705.

Digital Library

[13]

Richard E. Korf, Multi-way number partitioning, in: IJCAI, 2009, pp. 538-543.

Digital Library

[14]

Richard E. Korf, Larry Taylor, Finding optimal solutions to the twenty-four puzzle, in: National Conference on Artificial Intelligence (AAAI-96), 1996, pp. 1202-1207.

Digital Library

[15]

Lavalle, Steven M. and Hutchinson, Seth A., Optimal motion planning for multiple robots having independent goals. IEEE Transactions on Robotics and Automation. v14. 912-925.

[16]

Ryan Luna, Kostas E. Bekris, Push and swap: Fast cooperative path-finding with completeness guarantees, in: IJCAI, 2011, pp. 294-300.

Digital Library

[17]

Mackworth, Alan K., Consistency in networks of relations. Artificial Intelligence. v8 i1. 99-118.

[18]

Pallottino, Lucia, Giovanni Scordio, Vincenzo, Bicchi, Antonio and Frazzoli, Emilio, Decentralized cooperative policy for conflict resolution in multivehicle systems. IEEE Transactions on Robotics. v23 i6. 1170-1183.

Digital Library

[19]

Ryan, Malcolm, Exploiting subgraph structure in multi-robot path planning. JAIR. v31. 497-542.

Digital Library

[20]

Malcolm Ryan, Constraint-based multi-robot path planning, in: ICRA, 2010, pp. 922-928.

[21]

Guni Sharon, Roni Stern, Meir Goldenberg, Ariel Felner, The increasing cost tree search for optimal multi-agent pathfinding, in: IJCAI, 2011, pp. 662-667.

Digital Library

[22]

Guni Sharon, Roni Stern, Meir Goldenberg, Ariel Felner, Pruning techniques for the increasing cost tree search for optimal multi-agent pathfinding, in: SOCS, 2011, pp. 150-157.

[23]

David Silver, Cooperative pathfinding, in: AIIDE, 2005, pp. 117-122.

[24]

A. Srinivasan, T. Kam, S. Malik, R.K. Brayton, Algorithms for discrete function manipulation, in: ICCAD, 1990, pp. 92-95.

[25]

Trevor S. Standley, Finding optimal solutions to cooperative pathfinding problems, in: AAAI, 2010, pp. 173-178.

[26]

Trevor S. Standley, Richard E. Korf, Complete algorithms for cooperative pathfinding problems, in: IJCAI, 2011, pp. 668-673.

Digital Library

[27]

Roni Stern, Tamar Kulberis, Ariel Felner, Robert Holte, Using lookaheads with optimal best-first search, in: AAAI, 2010, pp. 185-190.

[28]

Sturtevant, Nathan R., Benchmarks for grid-based pathfinding. IEEE Transactions on Computational Intelligence and AI in Games. v4 i2. 144-148.

[29]

Nathan R. Sturtevant, Michael Buro, Improving collaborative pathfinding using map abstraction, in: AIIDE, 2006, pp. 80-85.

[30]

Nathan R. Sturtevant, Robert Geisberger, A comparison of high-level approaches for speeding up pathfinding, in: AIIDE, 2010, pp. 76-82.

[31]

Xiaoxun Sun, William Yeoh, Po-An Chen, Sven Koenig, Simple optimization techniques for A*-based search, in: AAMAS, 2009, pp. 931-936.

Digital Library

[32]

Pavel Surynek, An optimization variant of multi-robot path planning is intractable, in: AAAI, 2010, pp. 1271-1273.

[33]

Jur van den Berg, Rajat Shah, Arthur Huang, Kenneth Y. Goldberg, Anytime nonparametric A*, in: AAAI, 2011, pp. 105-111.

[34]

Ko-Hsin Cindy Wang, Adi Botea, Fast and memory-efficient multi-agent pathfinding, in: ICAPS, 2008, pp. 380-387.

Digital Library

[35]

Ko-Hsin Cindy Wang, Adi Botea, Tractable multi-agent path planning on grid maps, in: IJCAI, 2009, pp. 1870-1875.

Digital Library

[36]

Zhang, W. and Korf, R.E., Performance of linear-space search algorithms. Artificial Intelligence. v79. 241-292.

Digital Library

Cited By

He XTang XCai WLi J(2024)A stochastic process approach for multi-agent path finding with non-asymptotic performance guaranteesArtificial Intelligence10.1016/j.artint.2024.104084329:COnline publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1016/j.artint.2024.104084
Fine GAtzmon DAgmon NAgmon NAn BRicci AYeoh W(2023)Anonymous Multi-Agent Path Finding with Individual DeadlinesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598724(869-877)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598724
Andreichuk A(2023)Efficient Bounded-Suboptimal Search for the Multiagent Pathfinding ProblemScientific and Technical Information Processing10.3103/S014768822305001550:5(357-367)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.3103/S0147688223050015
Show More Cited By

Recommendations

The increasing cost tree search for optimal multi-agent pathfinding
IJCAI'11: Proceedings of the Twenty-Second international joint conference on Artificial Intelligence - Volume Volume One

We address the problem of optimal path finding for multiple agents where agents must not collide and their total travel cost should be minimized. Previous work used traditional single-agent search variants of the A* algorithm. We present a novel ...
Conflict-based search for optimal multi-agent pathfinding

In the multi-agent pathfinding problem (MAPF) we are given a set of agents each with respective start and goal positions. The task is to find paths for all agents while avoiding collisions. Most previous work on solving this problem optimally has ...
Multi-agent pathfinding with continuous time
Abstract
Multi-Agent Pathfinding (MAPF) is the problem of finding paths for multiple agents such that each agent reaches its goal and the agents do not collide. In recent years, variants of MAPF have risen in a wide range of real-world ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Artificial Intelligence

Artificial Intelligence Volume 195, Issue

February, 2013

551 pages

ISSN:0004-3702

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2012.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 February 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

75
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

He XTang XCai WLi J(2024)A stochastic process approach for multi-agent path finding with non-asymptotic performance guaranteesArtificial Intelligence10.1016/j.artint.2024.104084329:COnline publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1016/j.artint.2024.104084
Fine GAtzmon DAgmon NAgmon NAn BRicci AYeoh W(2023)Anonymous Multi-Agent Path Finding with Individual DeadlinesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598724(869-877)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598724
Andreichuk A(2023)Efficient Bounded-Suboptimal Search for the Multiagent Pathfinding ProblemScientific and Technical Information Processing10.3103/S014768822305001550:5(357-367)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.3103/S0147688223050015
Shen BChen ZLi JCheema MHarabor DStuckey PKoenig SStern RVallati M(2023)Beyond pairwise reasoning in multi-agent path findingProceedings of the Thirty-Third International Conference on Automated Planning and Scheduling10.1609/icaps.v33i1.27217(384-392)Online publication date: 8-Jul-2023
https://dl.acm.org/doi/10.1609/icaps.v33i1.27217
Atzmon DBernardini SFagnani FFairbairn DKoenig SStern RVallati M(2023)Exploiting geometric constraints in multi-agent pathfindingProceedings of the Thirty-Third International Conference on Automated Planning and Scheduling10.1609/icaps.v33i1.27174(17-25)Online publication date: 8-Jul-2023
https://dl.acm.org/doi/10.1609/icaps.v33i1.27174
Chen SErmiş GSharpanskykh A(2023)Multi-agent planning and coordination for automated aircraft ground handlingRobotics and Autonomous Systems10.1016/j.robot.2023.104480167:COnline publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1016/j.robot.2023.104480
Semiz FYorgancı MPolat F(2023)Solving an industry-inspired generalization of lifelong MAPF problem including multiple delivery locationsAdvanced Engineering Informatics10.1016/j.aei.2023.10202657:COnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.aei.2023.102026
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
Zhang HChen JLi JWilliams BKoenig SPelachaud CTaylor MFaliszewski PMascardi V(2022)Multi-Agent Path Finding for Precedence-Constrained Goal SequencesProceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems10.5555/3535850.3536013(1464-1472)Online publication date: 9-May-2022
https://dl.acm.org/doi/10.5555/3535850.3536013
Zhong XLi JKoenig SMa H(2022)Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding2022 International Conference on Robotics and Automation (ICRA)10.1109/ICRA46639.2022.9812020(10731-10737)Online publication date: 23-May-2022
https://dl.acm.org/doi/10.1109/ICRA46639.2022.9812020
Show More Cited By

View Options

View options

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 Issue’s Table of Contents