Source-linked AI summary
Lifelong Multi-Agent Path Finding in Large-Scale Warehouses
Jiaoyang Li, Andrew Tinka, Scott Kiesel, Joseph W. Durham, T. K. Satish Kumar, Sven Koenig
TL;DR
Lifelong MAPF requires agents to avoid collisions while continually receiving new goals, as in large-scale warehouses. The paper proposes RHCR, which repeatedly solves bounded-horizon Windowed MAPF instances, and reports high-throughput solutions for up to 1,000 agents while outperforming existing work. RHCR does not guarantee completeness or optimality and prioritizes throughput when the two objectives conflict.
Problem
Lifelong MAPF extends collision-free path finding to agents that are constantly assigned new goal locations in applications such as automated warehouses.
Method
RHCR decomposes lifelong MAPF into Windowed MAPF instances, replanning every h timesteps and resolving collisions only within a bounded horizon w ≥ h.
Results
RHCR outperforms existing work and produces high-throughput solutions for up to 1,000 agents in simulated warehouse instances.
Takeaways & Limitations
RHCR generates pliable plans for continually arriving goals and applies across general graphs with user-specified replanning frequency.
Takeaways & Limitations
RHCR does not guarantee completeness or optimality, and the paper prioritizes throughput when throughput and completeness compete.
Abstract
from arXiv · showhide
Multi-Agent Path Finding (MAPF) is the problem of moving a team of agents to their goal locations without collisions. In this paper, we study the lifelong variant of MAPF, where agents are constantly engaged with new goal locations, such as in large-scale automated warehouses. We propose a new framework Rolling-Horizon Collision Resolution (RHCR) for solving lifelong MAPF by decomposing the problem into a sequence of Windowed MAPF instances, where a Windowed MAPF solver resolves collisions among the paths of the agents only within a bounded time horizon and ignores collisions beyond it. RHCR is particularly well suited to generating pliable plans that adapt to continually arriving new goal locations. We empirically evaluate RHCR with a variety of MAPF solvers and show that it can produce high-quality solutions for up to 1,000 agents (= 38.9\% of the empty cells on the map) for simulated warehouse instances, significantly outperforming existing work.
1 Introduction
Lifelong MAPF extends collision-free path finding to settings where agents repeatedly receive new goals. RHCR addresses this online setting by replanning over bounded horizons and achieves strong scalability and throughput.
- Motivation: Lifelong MAPF keeps agents moving toward newly assigned goals instead of stopping after reaching one destination.This variant models ongoing operation in applications such as automated warehouses.
- Prior approaches: Prior approaches either solve lifelong MAPF offline, replan all agents every timestep, or replan only agents that have reached new goals.These strategies differ in scalability, replanning scope, and assumptions about the environment.
- RHCR framework: RHCR decomposes lifelong MAPF into Windowed MAPF instances, replanning every h timesteps while resolving collisions only through a user-specified horizon w ≥ h.The framework interleaves planning and execution and supports agents receiving goal sequences within an episode.
- RHCR framework: Bounded-horizon resolution keeps agents engaged and produces pliable plans that can adapt as new goal locations arrive.Resolving collisions beyond the active horizon is often unnecessary because later paths may change.
- Evaluation: 1,000 agents (= 38.9% of the empty cells on the map) were handled in simulated warehouse instances, while RHCR outperformed existing work.Across the evaluated solvers, bounded horizons achieved similar throughput to full horizons with significantly smaller runtime.
2 Background
The paper situates lifelong MAPF among established MAPF solvers and three prior solution strategies. It motivates bounded-horizon planning as a way to reduce computation while preserving solution quality and online flexibility.
- MAPF solvers: MAPF research includes rule-based, prioritized, compilation-based, A*-based, and dedicated search-based solvers.The paper presents four representative solvers for later evaluation or discussion.
- MAPF solvers: CBS is complete and optimal, whereas ECBS is complete and bounded-suboptimal through focal search.ECBS trades exact optimality for a user-specified bound on solution cost.
- MAPF solvers: CA* uses fixed priorities and is fast in practice but can be suboptimal or incomplete; PBS combines priority-based planning with CBS-like high-level search.PBS improves over many prioritized-planning variants in solution quality, according to the paper.
- Lifelong MAPF: Prior lifelong MAPF methods differ in offline knowledge, replanning frequency, scalability, and structural assumptions on the map.Method (1) has limited scalability, Method (2) replans all agents frequently, and Method (3) requires additional map structure for completeness.
- Bounded-horizon planning: Bounded-horizon planning reduces runtime as the horizon shrinks, while RHCR is reported to retain agents’ activity and decrease solution quality only slightly.The paper contrasts this behavior with WHCA* for regular MAPF, which generates longer paths as its horizon decreases.
3 Problem Definition
The problem is defined on a graph with online goal assignments and collision-free movement under discrete-time actions. The objective is to maximize throughput while treating task assignment and execution as external interfaces.
- Problem setting: The environment is a graph G = (V, E), with vertices as locations, edges as neighboring connections, and m agents having initial locations.The system operates online without knowing all goal locations in advance.
- Dynamics and collisions: Agents may move to a neighboring location or wait at each discrete timestep, with both actions lasting one unit of time.A collision includes shared-location occupancy or opposite-direction traversal of the same edge.
- Objective: The planner must produce collision-free paths and maximize throughput, defined as average goal locations visited per timestep.The set of collision-free paths for all agents is called a MAPF plan.
- System boundary: Goal assignment is handled by an external task assigner, allowing the path-planning system to remain applicable across different domains.The paper notes that domain-specific task assignment can be combined hierarchically with the domain-independent planner.
- Execution assumption: The framework assumes drive units execute MAPF plans perfectly, while post-processing can account for their kinematic constraints.The paper identifies robust execution methods as a way to convert plans into executable commands.
4 Rolling-Horizon Collision Resolution
RHCR repeatedly replans Windowed MAPF episodes, assigning ordered goal sequences and resolving collisions only within a bounded horizon. Its deadlock-avoidance mechanism can expand that horizon when progress is insufficient, but throughput and completeness may compete.
- Rolling-Horizon Collision Resolution: RHCR replans every h timesteps and resolves collisions only through time horizon w, with w ≥ h.The agents then execute the generated paths for h timesteps before the next episode.
- Rolling-Horizon Collision Resolution: Each Windowed MAPF episode updates agent starts, extends goal sequences until their lower-bound travel time reaches h, then plans collision-free paths for the first w timesteps.Visited goals are removed after agents execute h timesteps along the generated paths.
- Windowed MAPF Solvers: Windowed MAPF modifies regular MAPF by requiring paths to visit ordered goal sequences while ignoring collisions beyond the first w timesteps.This bounded-horizon design assumes shortest-path motion beyond the collision-resolution horizon.
- A* for a Goal Location Sequence: The low-level search generalizes Multi-Label A* by tracking how many ordered goals each path has visited and testing completion after the full sequence.This accounts for spatio-temporal dependencies between path segments that simple concatenation can miss.
- Behavior of RHCR: Resolving collisions over a longer horizon does not necessarily improve solutions, whereas too small a horizon may create deadlocks that block agents from reaching goals.The paper reports cases where smaller horizons achieve higher throughput and gives a corridor example producing a deadlock.
- Avoiding Deadlocks: RHCR can enlarge w using a progress potential P(w), but its deadlock-avoidance mechanism remains incomplete because throughput and completeness can conflict.The paper therefore focuses on throughput rather than completeness.
5 Empirical Results
RHCR is evaluated across warehouse settings, MAPF solvers, and horizon strategies, showing higher throughput or improved scalability with bounded horizons while dynamic horizons add runtime overhead.
- Evaluation setup: RHCR is evaluated with Windowed MAPF solvers based on CBS, ECBS, CA*, and PBS, alongside holding-endpoints and reserving-dummy-path baselines.The implementation uses SIPP or Soft Conflict SIPP as low-level solvers for the corresponding methods.
- Fulfillment warehouse application: In fulfillment warehouses, RHCR outperforms reserving dummy paths, which outperform holding endpoints in throughput.The comparison uses a 33 × 46 grid with 16% obstacles, PBS for all methods, and RHCR parameters w = 20 and h = 5.
- Fulfillment warehouse application: RHCR is slower per solver run because competing methods usually replan for fewer than 5 agents, despite their lower overall applicability and throughput.The competing methods also replan at every timestep and are not applicable to all maps.
- Dynamic bounded horizons: PBS with w = ∞ solves instances only up to 700 agents, whereas PBS with w = 5 solves instances up to at least 1,000 agents.Small horizons therefore yield scalability with respect to the number of agents in the reported experiments.
- Dynamic bounded horizons: Dynamic horizon selection uses an average horizon of 9.97 timesteps and achieves throughput 2.10 and runtime 0.35s, while fixed horizons incur lower runtime.With fixed w = 5, throughput is 1.72 and runtime 0.07s; with w = 10, throughput is 2.02 and runtime 0.17s.
6 Conclusions
The paper concludes that RHCR provides a flexible framework for lifelong MAPF, adapting plans to arriving goals while scaling to large agent populations. It identifies automatic horizon adjustment, parallel planning, and incremental search as future directions.
- Conclusions: RHCR decomposes lifelong MAPF into Windowed MAPF instances and empirically succeeds on fulfillment warehouse and sorting-center maps.The framework does not guarantee completeness or optimality.
- Conclusions: RHCR scales to 1,000 agents while producing high-throughput solutions and applies to general graphs with user-specified replanning frequency.Its plans adapt to continually arriving goal locations without anticipating all future goals.
- Future work: Future work includes automatically adjusting w to congestion and planning budgets, grouping agents for parallel planning, and reusing search effort incrementally.These directions are presented as avenues for extending RHCR.