Complexity of planning for connected agents in a partially known environment

DOI10.1016/J.TCS.2022.11.015MaRDI QIDQ2680862zbMATH OpenOpenAlexFDO

Authors Arthur Queffelec, Ocan Sankur, François Schwarzentruber

Publication date 4 January 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2022.11.015

zbMATH Keywords

connectivitydecentralized planningimperfect knowledgemulti-agent planningmulti-agent path finding

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• The computational complexity of multi-agent pathfinding on directed graphs
• Implicitly Coordinated Multi-Agent Path Finding under Destination Uncertainty: Success Guarantees and Computational Complexity
• Multi-agent pathfinding with \(n\) agents on graphs with \(n\) vertices: combinatorial classification and tight algorithmic bounds
• Verification of agent navigation in partially-known environments
• Constrained motion planning and multi-agent path finding on directed graphs

Cites work

• scientific article; zbMATH DE number 432827 (Why is no real title available?)
• scientific article; zbMATH DE number 7297884 (Why is no real title available?)
• A concise introduction to decentralized POMDPs
• Algorithms for Omega-Regular Games with Imperfect Information
• Alternation
• Conflict-based search for optimal multi-agent pathfinding
• Implicitly Coordinated Multi-Agent Path Finding under Destination Uncertainty: Success Guarantees and Computational Complexity
• Lower bounds for multiplayer noncooperative games of incomplete information
• On the online multi-agent O-D \(k\)-Canadian traveler problem
• Relationships between nondeterministic and deterministic tape complexities
• Shortest paths without a map
• The Complexity of Decentralized Control of Markov Decision Processes
• The \(k\)-Canadian travelers problem with communication
• The computational complexity of propositional STRIPS planning

Cited in

(1)

• Constrained motion planning and multi-agent path finding on directed graphs

This page was built for publication: Complexity of planning for connected agents in a partially known environment

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