Solving Multiagent Path Finding on Highly Centralized Networks
Authors: Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan, Nikolaos Melissinos, Michal Opler, Tung Anh Vu
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our goal is to design exact algorithms that are guaranteed to return an optimum solution. In view of the computational hardness of the MAPF problem, this is not possible in the general case. But what if we consider restricted instances? Can we identify characteristics, henceforth called parameters, whose exploitation leads to efficient algorithms? This is exactly the question that is in the core of the parameterized analysis that has recently been initiated for this problem (Eiben, Ganian, and Kanj 2023; Fioravantes et al. 2024a). The first two parameters that one would hope could be exploited are the number of agents k and the makespan ℓ, i.e., the total length of the schedule; these are exactly the two natural parameters of the MAPF problem. Unfortunately, the results of Fioravantes et al. (2024a) indicate that it is highly unlikely for either of these two parameters to be sufficient on their own. Thus, we turn towards structural parameters of the problem. Both (Eiben, Ganian, and Kanj 2023) and (Fioravantes et al. 2024a) provide a plethora of infeasibility results for many topologies which we could expect to come up in practical applications. Indeed, the MAPF problem remains NP-complete even when the input graph is a tree, or is planar and the makespan is at most 3. Our final result, which is the main algorithmic contribution of this paper, is an efficient algorithm that solves MAPFCC on graphs of bounded distance to clique. |
| Researcher Affiliation | Academia | 1Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague, Czech Republic 2Computer Science Institute, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic |
| Pseudocode | No | The algorithm has 4 steps. 1. We prove that if I admits a feasible solution, then the makespan of any optimum solution of I is bounded by a computable function of dc. 2. We create a new instance K = G , A , s 0, t of MAPF such that: G is an induced subgraph of G with a number of vertices that is bounded by a computable function of dc. V (G ) M. A A1 is selected appropriately. If I admits a feasible solution s1, . . . , sm then K admits a feasible solution s 1, . . . , s m such that |s i(A ) M| = |si(A) M| |A| |Q|. 3. We compute an optimum solution s 1, . . . , s m of K such that |s i(A ) M| |A| |Q| (if such a solution exists). This is done in FPT time parameterized by dc leveraging that V (G ) is bounded by a computable function of dc. 4. We extend the optimum solution s 1, . . . , s m of K into an optimum solution s1, . . . , sm of I. This is done by creating consecutive matchings between the positions of the agents of A \ A during the round i [m 1] {0} and the empty positions in Q during the round i + 1, i.e., Q \ s i+1(A ). |
| Open Source Code | No | The paper mentions "The full version of our work is available in (Fioravantes et al. 2024b). ar Xiv:2412.09433." which is a link to an arXiv preprint, not an explicit statement or link to open-source code for the methodology. No other mention of code availability is found. |
| Open Datasets | No | The paper is theoretical, focusing on algorithmic contributions and complexity analysis of the Multiagent Path Finding (MAPF) problem on various graph topologies. It does not conduct experiments using specific datasets and therefore does not provide concrete access information for any open datasets. |
| Dataset Splits | No | The paper is theoretical, focusing on algorithmic contributions and complexity analysis of the Multiagent Path Finding (MAPF) problem. It does not involve experimental evaluation on datasets, thus no dataset splits are provided. |
| Hardware Specification | No | The paper presents theoretical results concerning algorithm complexity and parameterized analysis. It does not describe any experimental setup or hardware specifications used for running experiments. |
| Software Dependencies | No | The paper describes theoretical algorithms and complexity analysis. It does not present any implementations or experiments that would require specific software dependencies or their version numbers. |
| Experiment Setup | No | The paper is theoretical, focusing on algorithmic contributions and complexity analysis of the Multiagent Path Finding (MAPF) problem. It does not describe any experimental setup, hyperparameters, or training configurations. |