On Path Selection for Reduction-Based Solving of Multi-Agent Pathfinding Using Graph Pruning

Abstract

Multi-agent pathfinding is the task of navigating a set of mobile agents in a shared environment such that they avoid collisions. Finding an optimal solution in terms of the length of the plan is known to be a computationally hard problem (NP-Hard). In general, there are two schools of optimal algorithms: search-based and reduction-based. While search-based algorithms excel in solving large maps where few conflicts can be expected, reduction-based algorithms excel in smaller instances even when agents interact often. However, the reduction-based approaches lag behind in large instances, even with few agents. To mitigate this, a subgraph pruning method was introduced to prune unnecessary vertices to decrease the size of the instance. The pruning is based on the shortest paths for each agent. In the original study, the authors randomly selected the shortest routes. In this study, we replicate the overall approach while selecting the initial shortest path with more care. We provide several approaches for selecting one of the possible shortest paths and experimentally compare them. We note that when the makespan optimal plan is needed, not all agents are required to use the shortest path, as only the longest path dictates the makespan. Using this observation, we also introduce an approach that selects longer paths for some agents if it helps to reduce the total number of interactions between agents. We provide an experimental comparison of all proposed approaches and show that the latter performs significantly better, in most cases outperforming any approach that strictly selects only the shortest path.