Multi-agent pathfinding on strongly connected digraphs: feasibility and solution algorithms

DOI10.1016/J.ARTINT.2025.104372MaRDI QIDQ6933243zbMATH OpenFDO

Authors Luca Consolini, Marco Locatelli, Bernhard Nebel, Irene Saccani

Publication date 5 September 2025

Published in Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

strongly connected digraphmulti-agent pathfinding

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Agent technology and artificial intelligence (68T42)

Cites work

• A linear-time algorithm for the feasibility of pebble motion on trees
• A stabilizing algorithm for finding biconnected components
• Complexity of token swapping and its variants
• Conflict-based search for optimal multi-agent pathfinding
• Constrained motion planning and multi-agent path finding on directed graphs
• Feasibility of Motion Planning on Directed Graphs
• Feasibility of motion planning on acyclic and strongly connected directed graphs
• Multi-color pebble motion on graphs
• Optimal pebble motion on a tree
• Push and rotate: a complete multi-agent pathfinding algorithm
• Solving multi-agent path finding on strongly biconnected digraphs

This page was built for publication: Multi-agent pathfinding on strongly connected digraphs: feasibility and solution algorithms

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