Parameterized Algorithms for Multiagent Pathfinding on Trees

Abstract

The classical Multiagent Pathfinding problem has been extensively studied not only within the artificial intelligence research community, but also by scholars in the areas of theoretical computer science and computational geometry. The problem asks for a minimum-makespan schedule that routes k agents (or robots) from their starting points to their destinations in a graph, while avoiding collisions, and is known to be NP-hard even on the fundamental class of trees. In this article we present two fixed parameter algorithms parameterized by k: the first yields a collision-free schedule on trees whose makespan deviates from the optimum by at most an additive polynomial function of k, and the second solves Multiagent Pathfinding optimally on the class of irreducible trees, i.e., trees with no vertices of degree 2. Both results rely on novel tools and insights into the properties of optimal schedules.