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

DOI10.1016/J.AUTOMATICA.2024.111593MaRDI QIDQ6566732zbMATH OpenFDO

Authors Luca Consolini, Marco Locatelli, Irene Saccani

Publication date 3 July 2024

Published in Automatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.AUTOMATICA.2024.111593

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Multi-agent systems (93A16)

Recommendations

• The computational complexity of multi-agent pathfinding on directed graphs
• Multi-agent pathfinding with \(n\) agents on graphs with \(n\) vertices: combinatorial classification and tight algorithmic bounds
• Solving multi-agent path finding on strongly biconnected digraphs
• Conflict-based search for optimal multi-agent pathfinding
• Complexity of planning for connected agents in a partially known environment

Cites work

• A linear-time algorithm for the feasibility of pebble motion on trees
• Conflict-based search for optimal multi-agent pathfinding
• Facets of the knapsack polytope
• Feasibility of motion planning on acyclic and strongly connected directed graphs
• Feasibility of Motion Planning on Directed Graphs
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Introduction to Discrete Event Systems
• Multi-color pebble motion on graphs
• On the complexity of paths avoiding forbidden pairs
• Push and rotate: a complete multi-agent pathfinding algorithm
• Supervisory control of discrete-event systems

Cited in

(3)

• Complexity of planning for connected agents in a partially known environment
• The computational complexity of multi-agent pathfinding on directed graphs
• Multi-agent pathfinding on strongly connected digraphs: feasibility and solution algorithms

This page was built for publication: Constrained motion planning and multi-agent path finding on directed graphs

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