The computational complexity of multi-agent pathfinding on directed graphs

DOI10.1016/J.ARTINT.2023.104063MaRDI QIDQ6494349

Bernhard Nebel

Publication date: 30 April 2024

Published in: Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

computational complexitymulti-agent pathfindingpebble motion on graphsMAPFpermutation group theorycooperative pathfindingdiMAPFmotion planning on graphs

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Feasibility of motion planning on acyclic and strongly connected directed graphs
• Graph puzzles, homotopy, and the alternating group
• Implicitly Coordinated Multi-Agent Path Finding under Destination Uncertainty: Success Guarantees and Computational Complexity
• Feasibility of Motion Planning on Directed Graphs
• Solving Multi-agent Path Finding on Strongly Biconnected Digraphs
• Reducibility among Combinatorial Problems
• Digraphs

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