The computational complexity of multi-agent pathfinding on directed graphs

DOI10.1016/J.ARTINT.2023.104063MaRDI QIDQ6494349zbMATH OpenFDO

Authors Bernhard Nebel

Publication date 30 April 2024

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.ARTINT.2023.104063

zbMATH Keywords

computational complexitycooperative pathfindingdiMAPFMAPFmotion planning on graphsmulti-agent pathfindingpebble motion on graphspermutation group theory

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Recommendations

• Solving multi-agent path finding on strongly biconnected digraphs
• Constrained motion planning and multi-agent path finding on directed graphs
• Multi-agent pathfinding with \(n\) agents on graphs with \(n\) vertices: combinatorial classification and tight algorithmic bounds
• On the complexity of optimal parallel cooperative path-finding
• Push and rotate: a complete multi-agent pathfinding algorithm

Cites work

• Digraphs
• Exploiting subgraph structure in multi-robot path planning
• Feasibility of motion planning on acyclic and strongly connected directed graphs
• Feasibility of Motion Planning on Directed Graphs
• Graph puzzles, homotopy, and the alternating group
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3223737 (Why is no real title available?)
• Implicitly Coordinated Multi-Agent Path Finding under Destination Uncertainty: Success Guarantees and Computational Complexity
• Reducibility among combinatorial problems
• Solving multi-agent path finding on strongly biconnected digraphs

Cited in

(2)

• Complexity of planning for connected agents in a partially known environment
• Constrained motion planning and multi-agent path finding on directed graphs

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: The computational complexity of multi-agent pathfinding on directed graphs

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