Searching with Consistent Prioritization for Multi-Agent Path Finding
This addresses the challenge of efficient path planning for multiple agents, offering improvements over rule-of-thumb heuristics in robotics or logistics, though it is incremental in advancing prioritized planning methods.
The paper tackles the problem of Multi-Agent Path Finding (MAPF) by introducing a novel search framework that explores partial priority orderings instead of fixed total orderings, achieving state-of-the-art solution qualities and success rates with similar runtimes to existing algorithms.
We study prioritized planning for Multi-Agent Path Finding (MAPF). Existing prioritized MAPF algorithms depend on rule-of-thumb heuristics and random assignment to determine a fixed total priority ordering of all agents a priori. We instead explore the space of all possible partial priority orderings as part of a novel systematic and conflict-driven combinatorial search framework. In a variety of empirical comparisons, we demonstrate state-of-the-art solution qualities and success rates, often with similar runtimes to existing algorithms. We also develop new theoretical results that explore the limitations of prioritized planning, in terms of completeness and optimality, for the first time.