In the Multiagent Path Finding 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).
We propose a systematic algorithmic study of this problem under the parameterized complexity framework.
We present a plethora of hardness results, which align with many heuristics used for this problem, whose running time could potentially be improved based on our fixed-parameter tractability results. In particular, we show that an exact solution to MAPF cannot be computed efficiently, unless P=NP, even if we consider very restrictive settings such as a bounded k, bounded l, or networks with star-like topologies (bounded vertex cover number) or even trees with 11 leaves. On the positive side, we present efficient algorithms for instances with bounded k + l, k plus the diameter of the graph G, or networks with highly centralized topologies (bounded distance to clique). This parameter is significant as it mirrors real-world
networks. In such environments, a bunch of central hubs (e.g., processing areas) are connected to only a few peripheral nodes.
These results were obtained by collaborating with Dušan Knop, Jan Matyáš Křišťan, Nikolaos Melissinos, Michal Opler and Tung Anh Vu, and were presented in AAAI’24 and AAAI’25.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne