Source-linked AI summary
Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding
Keisuke Okumura, Manao Machida, Xavier Défago, Yasumasa Tamura
TL;DR
MAPF becomes difficult to solve online and iteratively for applications with hundreds of agents because optimal approaches are computationally intensive. This paper presents PIBT, a scalable sub-optimal algorithm using adaptive prioritization and local movement planning; it guarantees finite-time reachability under stated graph conditions and produces acceptable solutions quickly, including in large and iterative warehouse scenarios.
Problem
MAPF must be solved online and iteratively for applications with hundreds of agents, while offline compute-intensive optimal approaches are difficult to use within realistic timeframes.
Method
PIBT is a sub-optimal iterative MAPF algorithm that uses priority inheritance with backtracking to coordinate adjacent movements through local agent interactions.
Results
PIBT guarantees finite-time reachability on graphs where every pair of adjacent nodes belongs to a simple cycle and promptly produces acceptable solutions for large and iterative MAPF instances.
Takeaways & Limitations
PIBT provides practical, scalable MAPF planning for online and lifelong settings, including scenarios with hundreds or thousands of agents and real-robot execution.
Takeaways & Limitations
PIBT+ does not guarantee better solutions or faster planning than its complement solver, and dense situations can degrade solution quality when the complement solver is used.
Abstract
from arXiv · showhide
In the Multi-Agent Path Finding (MAPF) problem, a set of agents moving on a graph must reach their own respective destinations without inter-agent collisions. In practical MAPF applications such as navigation in automated warehouses, where occasionally there are hundreds or more agents, MAPF must be solved iteratively online on a lifelong basis. Such scenarios rule out simple adaptations of offline compute-intensive optimal approaches; and scalable sub-optimal algorithms are hence appealing for such settings. Ideal algorithms are scalable, applicable to iterative scenarios, and output plausible solutions in predictable computation time. For the aforementioned purpose, this study presents Priority Inheritance with Backtracking (PIBT), a novel sub-optimal algorithm to solve MAPF iteratively. PIBT relies on an adaptive prioritization scheme to focus on the adjacent movements of multiple agents; hence it can be applied to several domains. We prove that, regardless of their number, all agents are guaranteed to reach their destination within finite time when the environment is a graph such that all pairs of adjacent nodes belong to a simple cycle (e.g., biconnected). Experimental results covering various scenarios, including a demonstration with real robots, reveal the benefits of the proposed method. Even with hundreds of agents, PIBT yields acceptable solutions almost immediately and can solve large instances that other established MAPF methods cannot. In addition, PIBT outperforms an existing approach on an iterative scenario of conveying packages in an automated warehouse in both runtime and solution quality.
1 Introduction
MAPF requires collision-free paths for multiple agents, but offline optimal planning becomes impractical at scale. PIBT addresses iterative scenarios with adaptive local prioritization, theoretical reachability under graph conditions, and fast empirical performance.
- Motivation: MAPF seeks collision-free paths to individual destinations, but its optimization is computationally intractable as the number of agents grows.The search space grows exponentially with the number of agents.
- Motivation: Online lifelong applications repeatedly update plans as agents receive new goals, making compute-intensive optimal approaches difficult to use with hundreds of agents.Automated warehouse package delivery is given as a motivating example.
- Theory: PIBT guarantees finite-time reachability on graphs where every pair of adjacent nodes belongs to a simple cycle, including biconnected graphs.The guarantee concerns each agent reaching its destination, not necessarily all agents reaching their goals simultaneously.
- Theory: PIBT requires O(|A| · (∆(G) + F + log |A|)) time per timestep and can use constant-time distance evaluation with preprocessing.Planning repeats one-timestep decisions until termination.
- Evaluation: PIBT returns acceptable solutions quickly with hundreds or more agents, solves a 43,151-vertex grid instance with 1,000 agents within 5 seconds, and outperforms an existing MAPD approach in runtime and quality.The reported average sub-optimality for the grid instance remains below 1.5.
- Method: PIBT uses adaptive priority inheritance and backtracking to coordinate adjacent movements of multiple agents during iterative planning.A lower-priority agent temporarily inherits a higher-priority agent’s priority when it impedes that agent, while backtracking helps avoid waiting deadlocks.
2 Related Work
Related MAPF work spans optimal, sub-optimal, complete, incomplete, centralized, decentralized, and learning-based approaches. The paper positions PIBT among inexpensive prioritized and rule-based methods for large online and lifelong settings.
- 2.1 Basis of Multi-Agent Path Finding (MAPF): MAPF assigns collision-free paths on graphs, with discrete synchronized actions in which agents move to adjacent nodes or wait.MAPF is NP-hard under various optimization criteria, including restricted graph classes and approximation thresholds.
- 2.1 Basis of Multi-Agent Path Finding (MAPF): Complete algorithms must report either collision-free paths ending at agents’ destinations or the absence of such a set of paths.Completeness is defined by guaranteeing this outcome when a solution does or does not exist.
- 2.2 Algorithms: Search-based approaches jointly search among agents and can be complete and optimal, while bounded sub-optimal variants target larger instances.Examples include conflict-based search and operator-decomposition methods.
- 2.2 Algorithms: Compiling-based approaches reduce MAPF to SAT, integer linear programming, or answer set programming and are described as complete and optimal.These methods translate path finding into established computational problem formulations.
- 2.2 Algorithms: Rule-based approaches move agents step-by-step using ad hoc rules; they are sub-optimal but often complete for particular problem instances.Examples include BIBOX and push and swap/rotate.
- 2.2 Algorithms: Learning-based approaches use machine learning to imitate expert behavior but are described as suboptimal and incomplete, without theoretical guarantees.The paper identifies prioritized and rule-based approaches as promising for online and lifelong scenarios with hundreds or more agents.
- 2.2 Algorithms: Prioritized planning sequentially plans agents’ paths in a decoupled manner, making it computationally inexpensive but generally neither complete nor optimal.Priority ordering is central, and variants include iterative decentralized implementations.
- 2.2 Algorithms: PIBT combines safe push-like operations with dynamic priorities and backtracking, without requiring an operational equivalent of swap.It was partly influenced by push and swap/rotate, which otherwise moves only one agent or pair at a time.
3 Problem Definition
The paper defines MAPF as collision-free multi-agent movement on graphs and MAPD as an online variant with task assignment and pickup-to-delivery execution.
- MAPF: Agents may move to adjacent nodes or wait, while avoiding vertex conflicts and swap conflicts.
- MAPF: MAPF assigns each agent a collision-free path from its initial location to its destination, with all agents reaching goals at a common timestep.
- MAPD: MAPD introduces a stream of pickup-delivery tasks that can arrive over time and are assigned only to free agents.
- MAPD: An assigned agent must visit each task’s pickup and delivery locations in order before becoming free again.
- MAPD: MAPD seeks to complete all tasks quickly, using service time and makespan as objective functions.
4 Priority Inheritance with Backtracking (PIBT)
PIBT performs repeated one-timestep prioritized planning, combining adaptive priority inheritance with backtracking to assign collision-free next locations.
- Top-level procedure: PIBT updates agent priorities each timestep and assigns next locations sequentially in decreasing priority order.
- Priority inheritance: When a lower-priority agent blocks a higher-priority agent, it temporarily inherits the higher priority to force resolution of the conflict.
- Backtracking: Priority inheritance alone can leave agents stuck, so PIBT adds backtracking that propagates valid or invalid outcomes through recursive requests.
- Recursive procedure: Combining priority inheritance and backtracking assigns every agent a next location without collisions.
- Recursive procedure: Each agent considers its current node and neighboring nodes, ordered by increasing distance to its goal, while avoiding vertex and swap conflicts.
4.3 Theoretical Analysis
The analysis proves reachability and gives per-timestep complexity bounds, while identifying graph conditions and conventional-MAPF limitations.
- Reachability: Lemma 1 shows that the highest-priority agent receives its nearest desired neighboring node whenever a suitable simple cycle exists.
- Reachability: Theorem 1 guarantees conflict-free paths and a goal-reaching timestep t ≤ diam(G) · |A| when every adjacent-node pair lies on a simple cycle.
- Reachability: Reachability does not guarantee simultaneous goal occupancy, so PIBT is incomplete for conventional one-shot MAPF.
- Failure cases: Without the graph condition, agents may remain permanently stationary and PIBT can report failure after reaching a predefined makespan limit.
- Complexity analysis: O(|A| · (∆(G) + F + lg |A|)) is PIBT’s time complexity for one timestep.
- Complexity analysis: With precomputed goal-distance tables, complexity becomes O(|A| · (∆(G) lg ∆(G) + lg |A|)).
- Complexity analysis: The low complexity supports large instances, anytime planning, and predictable runtime for real-time planning.
4.4 Application to Specific Problems
The paper adapts PIBT to one-shot MAPF through a complement solver and to lifelong MAPD through task-aware prioritization, with completeness guarantees under stated conditions.
- Application to MAPF: PIBT+ runs PIBT for Tmin timesteps to move agents toward their goals, then invokes a complement MAPF solver from the resulting configuration.
- Application to MAPF: PIBT+ is complete on undirected graphs when its complement solver satisfies the required completeness conditions.
- Application to MAPF: PIBT+ does not guarantee a better solution or faster planning than using the complement solver initially, and its added costs depend on Tmin.
- Application to MAPD: Task-assigned agents receive higher priority than free agents, and assigned agents retain priority until completing their tasks.
- Application to MAPD: For MAPD, each timestep assigns available tasks and uses PIBT to plan the agents’ next locations.
- Application to MAPD: Algorithm 3 is complete for MAPD when every pair of adjacent nodes belongs to a simple cycle.
- Application to MAPD: Compared with TP, PIBT does not require non-task endpoints and applies across a wider range of settings satisfying the graph condition.
4.5 Decentralized Online Planning
PIBT supports online decentralized planning through repeated single-timestep actions, local interactions, and information propagation. Interacting groups can plan in parallel, while communication is linear in the number of agents per timestep.
- Online planning: PIBT performs online planning by repeating single-timestep planning and movement actions.
- Information propagation: Priority inheritance and backtracking are implemented through propagated information between interacting agents.
- Parallel local planning: Agents in different interaction groups cannot affect one another, so their path planning and negotiation can occur in parallel.
- Parallel local planning: PIBT can use local interactions with direct communication between nearby agents and multi-hop communication across an interaction group.
- Communication: O(|A|) communication is required per timestep because each agent invokes PIBT at most once and sends at most one backtracking message.
4.6 Without Rotations
PIBT can be adapted to prohibit rotations, which may be difficult for physical robots to execute reliably. Under biconnectivity and fewer agents than nodes, the adapted algorithm produces conflict-free, rotation-free paths with a finite reachability bound.
- Motivation: Rotations may be difficult to realize in physical environments because of synchronization problems.
- Rotation-free planning: A rotation is a cyclic one-timestep movement of adjacent agents, and rotation-free paths contain no such movement.
- Rotation-free planning: PIBT avoids rotations by skipping candidate nodes that would create them during next-timestep planning.
- Rotation-free planning: The rotation-free variant outputs paths without rotations.
- Guarantee: Under biconnectivity and |A| < |V|, every agent reaches its goal by timestep t ≤ diam(G) · |A| along conflict-free, rotation-free paths.
- Scope: The rotation-free reachability theorem is restricted to biconnected graphs, unlike the original reachability theorem.
5 Evaluation
PIBT is evaluated as a fast, scalable MAPF solver across benchmark, stress-test, MAPD, and robot settings. It produces acceptable solutions quickly, while its quality and completeness depend on environmental and density conditions.
- Evaluation setup: PIBT was tested across MAPF, MAPD, agent-count stress tests, and a real-robot demonstration.The evaluation used a laptop implementation and compared PIBT with prioritized, rule-based, search-based, optimal, and compiling-based solvers.
- MAPF results: PIBT solves large instances orders of magnitude faster than established solvers.The reported advantage is attributed to its small time complexity.
- MAPF results: PIBT provides acceptable sum-of-costs and makespan quality in sparse settings but does not guarantee solution quality generally.Pure rule-based solvers often fail the makespan limit, while prioritized planning supports PIBT’s solution quality.
- MAPF limitations: PIBT can fail at the makespan limit when agents need simultaneous goal occupancy or when adjacent-node cycles are absent.These failures occur especially with many agents in small maps.
- MAPF results: PIBT+ raises success rates by using a complement solver, but its solution quality can degrade in dense situations.In the reported experiment, PIBT+ used PS+, whose lower quality affected dense random-32-32-20 instances.
- MAPD results: In MAPD, PIBT significantly outperforms TP in runtime and is comparable to or better than TP in service time and makespan.The paper attributes the result partly to PIBT moving free agents toward pickup locations instead of evacuating them to non-task endpoints.
- Stress test: PIBT requires around 10 milliseconds per timestep even with 10,000 agents on an ordinary laptop.The scores follow an almost linear trend with the number of agents.
6 Conclusion
The paper concludes that PIBT is a scalable iterative MAPF algorithm with practical performance across large, lifelong, and robotic settings. It also identifies asynchronous agent motion as an important direction for future work.
- Conclusion: PIBT uses simple prioritization to solve MAPF iteratively and can be applied to online and lifelong settings.The conclusion connects this design with applications across several domains.
- Conclusion: PIBT(+) promptly solves large MAPF instances, while PIBT outperforms current solutions for pickup and delivery.The conclusion also reports real-time planning with thousands of agents and a real-robot execution.
- Future directions: Asynchronous agent movement remains outside the traditional synchronized MAPF assumption and requires further consideration.The paper identifies this gap as a future research direction for more practical environments.
A MAPF Results
The appendix figures summarize the complete MAPF experimental results reported for Section 5.1.
- MAPF results: Figures 11 and 12 summarize all MAPF experiment results from Section 5.1.
B PIBT in Extremely Dense Situations
In extremely dense situations, PIBT was evaluated on graphs satisfying the reachability condition, with results depending on agent density and tie-break strategy. The experiments show fast solving in many instances, while tie-break choices affect both success and solution quality.
- Results: Most extremely dense instances were solved within 5 ms, although some reached the makespan limit and failed.Solution qualities worsened as the number of agents increased because many agents could not follow shortest paths.
- Results: PIBT solved all 64-agent fully occupied instances but sometimes failed with 50 agents because of random tie-breaking.The experiments used 25 instances for each agent count on the empty-8-8 map.
- Tie-break strategy: Candidate nodes were ordered by goal distance, agent presence, and random values when earlier rules produced ties.The agent-presence rule was intended to avoid unnecessary priority inheritance.
- Tie-break strategy: Removing the agent-presence tie-break led to success in all tested instances regardless of agent count in the reported dense settings.The same trend was observed on a 16 × 16 empty grid, although the authors identify further investigation as beyond the paper.
- Scope and comparison: The reported tie-break discussion does not apply when the graph fails PIBT’s reachability condition, while rule-2 usually improves sum-of-costs.Table 3 compares normal PIBT with a random variant without rule-2 on den520d using averages of upper bounds with 95% confidence intervals.