Matej Husár, Jiří Švancara, Roman Barták

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

Introduction

On path selection for reduction-based solving of multi-agent pathfinding using graph pruning. Optimize Multi-Agent Pathfinding (MAPF) reduction-based solving using advanced graph pruning and innovative path selection strategies. Improves efficiency for makespan-optimal plans.

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.

Review

This paper addresses a fundamental challenge in Multi-Agent Pathfinding (MAPF): the limitations of reduction-based algorithms when applied to larger problem instances, even with a sparse number of agents. It effectively sets the stage by contrasting the strengths of search-based and reduction-based methods, highlighting that while the latter excel in smaller, conflict-rich environments, they struggle with scale. The authors build upon prior work that introduced a subgraph pruning method, which aims to reduce instance size by leveraging agent-specific shortest paths, but acknowledge a key limitation in the original study: the random selection of these initial shortest routes. The core novelty of this work lies in its systematic re-evaluation and improvement of the path selection strategy for this subgraph pruning method. The authors move beyond random shortest path selection, proposing and experimentally comparing several more deliberate approaches. A particularly insightful and innovative contribution is the recognition that for makespan optimality, not all agents are strictly bound to their individual shortest paths. This understanding paves the way for a novel strategy where some agents may be assigned slightly longer paths if it demonstrably helps in reducing the total number of interactions and conflicts within the multi-agent system, thereby simplifying the overall problem for the reduction solver. The reported experimental results clearly indicate the efficacy of this innovative approach. The strategy of allowing longer paths to mitigate interactions is shown to perform significantly better than any method strictly adhering to individual shortest paths. This finding represents a significant step forward in bridging the performance gap for reduction-based MAPF algorithms in larger instances, potentially enabling them to compete more effectively with search-based methods in a broader range of scenarios. The work demonstrates a sophisticated understanding of the underlying problem structure and offers a practical, high-impact solution for enhancing computational efficiency in this complex domain.

Full Text

Comments

You need to be logged in to post a comment.