Source-linked AI summary
Searching with Consistent Prioritization for Multi-Agent Path Finding
Hang Ma, Daniel Harabor, Peter J. Stuckey, Jiaoyang Li, Sven Koenig
TL;DR
Prioritized MAPF is efficient but fixed priority choices can produce poor solutions or miss solvable instances, while general guarantees remain limited. This paper systematically searches partial priority orderings with CBSw/P and PBS, develops theoretical characterizations, and reports near-optimal, efficient solutions with strong scalability and broader success than standard prioritized planning.
Problem
Existing prioritized MAPF algorithms rely on a fixed total priority ordering chosen a priori, which can produce poor solutions or fail on solvable instances.
Method
The paper combines a theoretical framework with CBSw/P and PBS, which systematically and lazily search priority orderings to resolve conflicts.
Results
The methods compute near-optimal, efficient solutions, find solutions missed by standard prioritized planning, and PBS solves well-formed instances with 600 agents in less than a minute.
Takeaways & Limitations
Systematic ordering search broadens the practical usefulness of prioritized planning while exposing its completeness and optimality limitations.
Takeaways & Limitations
Prioritized planning remains incomplete in general, including for P-solvable instances under an arbitrary given ordering.
Abstract
from arXiv · showhide
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.
Introduction
MAPF coordinates multiple agents along collision-free paths, but existing prioritized methods commit to a fixed ordering that can produce poor solutions or fail on solvable instances. The paper systematically searches priority orderings through two new algorithms and reports strong solution quality, efficiency, and scalability.
- Motivation: MAPF plans collision-free paths for multiple agents from specified starts to targets on a graph.Solution quality is measured by flowtime or makespan, and optimal MAPF is NP-hard.
- Motivation: Existing prioritized algorithms use a predefined total priority ordering, which can yield poor-quality solutions or fail on solvable instances.A different total ordering may produce a higher-quality solution or enable solvability.
- Approach: The paper develops a theoretical framework for prioritized planning and two algorithms that systematically explore good priority orderings.CBSw/P uses lazy best-first search over total orderings, while PBS uses lazy depth-first search and can accept a partial ordering.
- Results: The new methods compute near-optimal solutions, improve efficiency relative to CBS variants, solve many instances missed by standard prioritized planning, and scale to 600 agents in under a minute.PBS remains near-optimal and efficient beyond 100 agents and solves well-formed instances with 600 agents in less than a minute.
Problem Definition
MAPF is formalized on a connected undirected graph with agents that move or wait over discrete time. A solution assigns each agent a path satisfying its start, target, and collision-avoidance requirements.
- Instance model: MAPF uses a connected undirected graph and assigns each agent a unique start vertex and target vertex.Agents move to adjacent vertices or wait at discrete time steps.
- Plans and paths: A plan contains one path per agent, beginning at its start and remaining at its target after arrival.Each agent’s arrival time is the earliest time it reaches and stops at its target.
- Collision constraints: Solutions must avoid vertex collisions and edge collisions between agents.Vertex collisions share a vertex at the same time; edge collisions traverse the same edge in opposite directions simultaneously.
- Objective: Flowtime is the sum of all agents’ arrival times.The formal objective is represented as the sum over agents of T_i.
Prioritized Planning
Prioritized planning plans agents sequentially under priority constraints, making efficiency attractive but leaving outcomes dependent on the ordering. The examples illustrate that solvability and optimality can vary sharply across orderings and instance classes.
- Mechanism: Prioritized planning computes individually optimal paths sequentially, treating higher-priority paths as dynamic obstacles for lower-priority agents.The method generalizes fixed total ordering to partial ordering, where a_i has higher priority than a_j iff i ≺ j.
- Guarantees and trade-offs: Prioritized planning is efficient but offers no completeness or optimality guarantees in general.Its central practical challenge is choosing a good priority ordering because bad choices can lower solution quality or cause failure.
- Ordering sensitivity: A P-solvable instance may be solvable only under a specific ordering, as Figure 2 permits only {1 ≺2}.This demonstrates that solvability can depend on the exact total priority ordering.
- Ordering sensitivity: Some instances are not solvable with any fixed priority ordering, as shown in Figure 1.The paper identifies such instances as not P-solvable.
- Instance classes: Well-formed instances are P-solvable for any total ordering, whereas OP-solvable instances may still lack a prioritized-planning solution under a fixed ordering.Well-formed instances allow agents to wait indefinitely at their starts and targets without blocking others.
- Priority assignment: Priority assignment can be arbitrary, heuristic-based, or dynamically determined to resolve collisions on the fly.Examples include target-distance heuristics, preferred path types, and temporary priorities when agents reach an impasse.
Theoretical Results
Theoretical results characterize when prioritized planning is complete or optimal and show that fixed priority orderings can fundamentally restrict MAPF solutions. Well-formed instances guarantee completeness, but broader solvable classes may require specific orderings, path choices, or even inconsistent priorities.
- Prioritized planning with an arbitrary priority ordering is incomplete for MAPF in general.
- Optimality: The only flowtime- or makespan-optimal solution in some instances is inconsistent with every fixed priority ordering.
- P-solvable instances: P-solvable instances may have solutions consistent with only one total priority ordering, and prioritized planning is incomplete for this class under any given ordering.
- Well-formed instances: Well-formed instances are complete under every total priority ordering because agents can wait at starts until higher-priority agents reach targets.
- Optimality: Prioritized planning is generally suboptimal for flowtime and makespan, even on P-solvable instances.
- OP-solvable instances: Some OP-solvable instances require the correct total ordering and correct path tie-breaking; an alternative individually optimal path can create a deadlock.
Conflict-Based Search with Priorities
CBSw/P extends conflict-based search by storing and incrementally extending priority orderings while resolving collisions through constraint-tree search.
- Conflict-Based Search with Priorities: CBSw/P stores a priority ordering in every constraint-tree node and generates children whose orderings extend the parent ordering.Priority orderings retain previously imposed relations between agents.
- Conflict-Based Search with Priorities: The root node has no constraints or priority ordering, contains independently optimal paths, and is assigned their summed arrival time.The root is inserted into OPEN for best-first expansion.
- Conflict-Based Search with Priorities: CBSw/P expands the lowest-cost node and returns its plan when collision-free; otherwise, it branches on the agents involved in a selected collision.Each generated child adds an agent-specific constraint and may add the corresponding priority relation.
- Conflict-Based Search with Priorities: For each viable child, CBSw/P updates the colliding agent’s path with a low-level search and recomputes the plan cost before reinserting the node.The low-level search is space-time A* and respects constraints relevant to the replanned agent.
Priority-Based Search
PBS searches priority orderings dynamically with depth-first backtracking, updating paths to respect higher-priority agents until it finds a collision-free plan or exhausts alternatives.
- Priority-Based Search: PBS builds a priority tree through depth-first search, greedily choosing which colliding agent receives higher priority and backtracking when a branch has no solution.It introduces ordered pairs only when agents collide.
- Priority-Based Search: PBS removes a node from the stack and returns its plan if collision-free; otherwise, it creates children by constraining each agent involved in the first collision.Child nodes add the corresponding higher-priority relation and are explored in cost order.
- Priority-Based Search: The root uses an initial priority ordering, empty by default, and computes individually optimal paths for all agents before high-level search begins.With an empty initial ordering, the root update succeeds for every agent.
- Priority-Based Search: UpdatePlan uses a topological ordering and low-level searches to recompute paths that avoid all higher-priority agents while preserving the partial ordering.A failed low-level search causes the branch to be rejected.
Experiments
Experiments compare CBSw/P and PBS with CBS and fixed or randomized priority-ordering variants on grid and game-map instances, evaluating success, runtime, solution quality, and search effort.
- Experimental setup: CBSw/P, PBS, and fixed-ordering variants are compared with CBS, using obstacle-grid and game-map benchmarks under a one-minute per-instance limit.Variants include FIX, LH, SH, and RND, which represent fixed heuristics and repeated random orderings.
- 20×20 grids: PBS and RND solve nearly all grid instances, whereas fixed-ordering variants often fail; on hard instances with more than 70 agents and 10% obstacles, failures or timeouts remain.SH has the lowest success rates among fixed-ordering PBS variants because higher-priority agents can block lower-priority agents.
- 20×20 grids: CBSw/P almost always finds optimal solutions, while PBS remains within 4% of optimal and FIX is more than 5% worse, often substantially worse.The comparison uses flowtime divided by optimal flowtime computed by CBS.
- 20×20 grids: PBS is nearly indistinguishable from SH, better than RND, which is better than FIX, which is better than LH, while PBS performs more low-level expansions because it explores more orderings.Runtime follows low-level expansions because most runtime is spent in low-level searches.
- Game maps: On brc202d and lak503d, PBS has higher success rates than FIX, CBS, and CBSw/P, remains close to FIX in runtime, and is almost always nearly optimal.On well-formed variants, CBSw/P and CBS are nearly indistinguishable in success rates and runtimes.
- Game maps: PBS scales to 600 agents on brc202d(WF) without reaching the runtime limit.The scalability test used the well-formed brc202d benchmark.
Conclusions
The paper addresses prioritized planning by combining a theoretical framework for its limits with two systematic algorithms that lazily search priority orderings.
- Conclusions: CBSw/P and PBS search for good priority orderings by imposing relations only between colliding agents and exploring orderings systematically.CBSw/P uses best-first search, whereas PBS uses depth-first search.