Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology
Foivos Fioravantes, Dušan Knop, Jan Matyáš Křištan, Nikolaos Melissinos, Michal Opler
Abstract
In the Multiagent Path Finding (MAPF for short) problem, we focus on efficiently finding non-colliding paths for a set of k agents on a given graph G, where each agent seeks a path from its source vertex to a target. An important measure of the quality of the solution is the length of the proposed schedule l, that is, the length of a longest path (including the waiting time). In this work, we propose a systematic study under the parameterized complexity framework. The hardness results we provide align with many heuristics used for this problem, whose running time could potentially be improved based on our Fixed-Parameter Tractability (FPT) results. We show that MAPF is W[1]-hard with respect to k (even if k is combined with the maximum degree of the input graph). The problem remains NP-hard in planar graphs even if the maximum degree and the makespan l are fixed constants. On the positive side, we show an FPT algorithm for k+l. As we continue, the structure of G comes into play. We give an FPT algorithm for parameter k plus the diameter of the graph G. The MAPF problem is W[1]-hard for cliquewidth of G plus l while it is FPT for treewidth of G plus l.
BibTeX
@article{Fioravantes_Knop_Křištan_Melissinos_Opler_2024, title={Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology}, volume={38}, url={https://ojs.aaai.org/index.php/AAAI/article/view/29686}, DOI={10.1609/aaai.v38i16.29686}, abstractNote={In the Multiagent Path Finding (MAPF for short) problem, we focus on efficiently finding non-colliding paths for a set of k agents on a given graph G, where each agent seeks a path from its source vertex to a target.
An important measure of the quality of the solution is the length of the proposed schedule l, that is, the length of a longest path (including the waiting time).
In this work, we propose a systematic study under the parameterized complexity framework. The hardness results we provide align with many heuristics used for this problem, whose running time could potentially be improved based on our Fixed-Parameter Tractability (FPT) results. We show that MAPF is W[1]-hard with respect to k (even if k is combined with the maximum degree of the input graph).
The problem remains NP-hard in planar graphs even if the maximum degree and the makespan l are fixed constants.
On the positive side, we show an FPT algorithm for k+l. As we continue, the structure of G comes into play.
We give an FPT algorithm for parameter k plus the diameter of the graph G.
The MAPF problem is W[1]-hard for cliquewidth of G plus l while it is FPT for treewidth of G plus l.}, number={16}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Fioravantes, Foivos and Knop, Dušan and Křištan, Jan Matyáš and Melissinos, Nikolaos and Opler, Michal}, year={2024}, month={Mar.}, pages={17380-17388} }