Multi-agent pathfinding with n agents on graphs with n vertices: combinatorial classification and tight algorithmic bounds

DOI10.1007/978-3-319-57586-5_21zbMATH Open1486.68129OpenAlexW2606892031MaRDI QIDQ5283371FDOQ5283371

Authors:

Publication date: 21 July 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-57586-5_21

Recommendations

• Push and rotate: a complete multi-agent pathfinding algorithm
• Conflict-based search for optimal multi-agent pathfinding
• scientific article; zbMATH DE number 5959974
• Solving multi-agent path finding on strongly biconnected digraphs
• Pairwise symmetry reasoning for multi-agent path finding search

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05)

Cites Work

• A note on two problems in connexion with graphs
• Title not available (Why is that?)
• Graph puzzles, homotopy, and the alternating group
• The \((n^ 2-1)\)-puzzle and related relocation problems
• Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard

Cited In (10)

• Push and rotate: a complete multi-agent pathfinding algorithm
• k-Agent Sufficiency for Multiagent Stochastic Physical Search Problems
• Constrained motion planning and multi-agent path finding on directed graphs
• Title not available (Why is that?)
• Reconfiguration of connected graph partitions
• Solving multi-agent path finding on strongly biconnected digraphs
• The computational complexity of multi-agent pathfinding on directed graphs
• The increasing cost tree search for optimal multi-agent pathfinding
• Implicitly Coordinated Multi-Agent Path Finding under Destination Uncertainty: Success Guarantees and Computational Complexity
• Token Swapping on Trees

This page was built for publication: Multi-agent pathfinding with \(n\) agents on graphs with \(n\) vertices: combinatorial classification and tight algorithmic bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5283371)