Multiagent pathfinding routing is fixed parameter tractable below sum distances
Routing Multiple Agents Below the Sum of Distances
Data Structures and AlgorithmsDiscrete Mathematics
Summary
The problem studied is how to move many agents from their start points to end points in a network without bumping into each other. The authors focus on cases where the total time is less than the sum of shortest routes for each agent individually. They show that when considering both the number of agents and how much faster than the sum they want to be, the problem can be solved efficiently. Some parameter choices make the problem harder, but if all start and end points are different, it becomes easier. The authors also explain limits to how much the problem can be simplified.
What this means in practice
- •For robotics teams: Plan collision-free routes for multiple robots moving simultaneously in constrained spaces more efficiently when overall travel time is close to minimal.
- •For warehouse automation operators: Optimize simultaneous task scheduling of robotic agents in warehouses by exploiting parameter combinations that allow faster route planning below naive sequential totals.
A theory result. No direct application yet.
Authors
Matthias Bentert, Eduard Eiben, Fedor V. Fomin, Petr A. Golovach
Abstract
We study Transient Multiagent Pathfinding, a variant of the classical Multi-Agent Pathfinding problem in which a set of agents must be routed without collisions from designated start vertices to designated destination vertices in a graph. We analyze the problem within the above-and-below-guarantee paradigm of parameterized complexity. In particular, we consider the natural upper bound \(L\), given by the sum of the shortest-path distances between pairs of agents' terminals (corresponding to sequential routing of the agents). The parameterization is given by the gap \(ζ= L - λ\) between this bound and the target makespan \(λ\), together with the number \(k\) of agents. Our main result establishes fixed-parameter tractability for the combined parameter \(k + ζ\). Matching lower bounds show that parameterization by \(k\) alone is W[1]-hard, and that parameterization by \(ζ\) alone is W[1]-hard when terminals are not required to be distinct. On the positive side, if all terminals are distinct, the problem becomes fixed-parameter tractable when parameterized solely by \(ζ\). Finally, we show that Transient Multiagent Pathfinding is unlikely to admit a polynomial kernel when parameterized by \(k + ζ\). Together, our results provide an almost complete characterization of the parameterized complexity landscape of the problem for the considered parameters.