Multi-agent Pathfinding with n Agents on Graphs with n Vertices: Combinatorial Classification and Tight Algorithmic Bounds | SpringerLink
Skip to main content
Springer Nature Link
Log in

Multi-agent Pathfinding with n Agents on Graphs with n Vertices: Combinatorial Classification and Tight Algorithmic Bounds

  • Conference paper
  • First Online:
Algorithms and Complexity (CIAC 2017)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 10236))

Included in the following conference series:

  • 1173 Accesses

Abstract

We investigate the multi-agent pathfinding (MAPF) problem with n agents on graphs with n vertices: Each agent has a unique start and goal vertex, with the objective of moving all agents in parallel movements to their goal s.t. each vertex and each edge may only be used by one agent at a time. We give a combinatorial classification of all graphs where this problem is solvable in general, including cases where the solvability depends on the initial agent placement.

Furthermore, we present an algorithm solving the MAPF problem in our setting, requiring \(\mathcal {O}(n^2)\) rounds, or \(\mathcal {O}(n^3)\) moves of individual agents. Complementing these results, we show that there are graphs where \(\Omega (n^2)\) rounds and \(\Omega (n^3)\) moves are required for any algorithm.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Yu and Rus [8] also give a MAPF algorithm, cf. second to last paragraph of Sect. 1.1.

References

  1. Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269–271 (1959)

    Article  MathSciNet  MATH  Google Scholar 

  2. Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)

    Article  Google Scholar 

  3. Scott, R.: Sparking life: notes on the performance capture sessions for the lord of the rings: the two towers. SIGGRAPH Comput. Graph. 37(4), 17–21 (2003)

    Article  Google Scholar 

  4. Silver, D.: Cooperative pathfinding. In: Artificial Intelligence and Interactive Digital Entertainment Conference (2005)

    Google Scholar 

  5. Pelechano, N., Malkawi, A.: Evacuation simulation models: challenges in modeling high rise building evacuation with cellular automata approaches. Autom. Constr. 17(4), 377–385 (2008)

    Article  Google Scholar 

  6. Svestka, P., Overmars, M.H.: Coordinated path planning for multiple robots. Robot. Auton. Syst. 23(3), 125–152 (1998)

    Article  Google Scholar 

  7. Domke, J., Hoefler, T., Matsuoka, S.: Routing on the dependency graph: a new approach to deadlock-free high-performance routing. In: Symposium on High-Performance Parallel and Distributed Computing (2016)

    Google Scholar 

  8. Yu, J., Rus, D.: Pebble motion on graphs with rotations: efficient feasibility tests and planning algorithms. In: Akin, H.L., Amato, N.M., Isler, V., Stappen, A.F. (eds.) Algorithmic Foundations of Robotics XI. STAR, vol. 107, pp. 729–746. Springer, Cham (2015). doi:10.1007/978-3-319-16595-0_42

    Google Scholar 

  9. Driscoll, J.R., Furst, M.L.: On the diameter of permutation groups. In: Symposium on Theory of Computing (1983)

    Google Scholar 

  10. Kornhauser, D., Miller, G., Spirakis, P.: Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. In: Symposium on Foundations of Computer Science (1984)

    Google Scholar 

  11. Johnson, W.W.: Notes on the “15” puzzle. Am. J. Math. 2(4), 397–404 (1879)

    Article  MathSciNet  MATH  Google Scholar 

  12. Wilson, R.M.: Graph puzzles, homotopy, and the alternating group. J. Comb. Theory, Ser. B 16(1), 86–96 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  13. Ratner, D., Warmuth, M.: The \(n^2-1\) puzzle and related relocation problems. J. Symb. Comput. 10(2), 111–137 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  14. Goldreich, O.: Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. Miscellanea on the Interplay Between Randomness and Computation. LNCS, vol. 6650, pp. 1–5. Springer, Heidelberg (2011). doi:10.1007/978-3-642-22670-0_1

    Chapter  Google Scholar 

  15. Kornhauser, D.: Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. Master’s thesis MIT/LCS/TR-320, Massachusetts Institute of Technology (1984)

    Google Scholar 

  16. Röger, G., Helmert, M.: Non-optimal multi-agent pathfinding is solved (since 1984). In: Symposium on Combinatorial Search (2012)

    Google Scholar 

  17. Jacobson, N.: Basic Algebra. Freeman, San Francisco (1974)

    MATH  Google Scholar 

Download references

Acknowledgements

We would like to thank the anonymous reviewers for their helpful comments. Klaus-Tycho Foerster is supported by the Danish Villum Foundation.

Author information

Authors and Affiliations

  1. ETH Zurich, 8092, Zurich, Switzerland

    Linus Groner, Torsten Hoefler, Michael Koenig, Sascha Schmid & Roger Wattenhofer

  2. Aalborg University, 9220, Aalborg, Denmark

    Klaus-Tycho Foerster

Authors
  1. Klaus-Tycho Foerster
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Linus Groner
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Torsten Hoefler
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Michael Koenig
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Sascha Schmid
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Roger Wattenhofer
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Linus Groner .

Editor information

Editors and Affiliations

  1. National Technical University of Athens, Zografou, Athens, Greece

    Dimitris Fotakis

  2. National Technical University of Athens, Zografou, Athens, Greece

    Aris Pagourtzis

  3. Université Paris-Dauphine, Paris, France

    Vangelis Th. Paschos

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Foerster, KT., Groner, L., Hoefler, T., Koenig, M., Schmid, S., Wattenhofer, R. (2017). Multi-agent Pathfinding with n Agents on Graphs with n Vertices: Combinatorial Classification and Tight Algorithmic Bounds. In: Fotakis, D., Pagourtzis, A., Paschos, V. (eds) Algorithms and Complexity. CIAC 2017. Lecture Notes in Computer Science(), vol 10236. Springer, Cham. https://doi.org/10.1007/978-3-319-57586-5_21

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-57586-5_21

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-57585-8

  • Online ISBN: 978-3-319-57586-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation