PaperlayerView exact revision on arXiv

Source-linked AI summary

A Theoretical Framework for Parallel Lifelong MAPF Using Group Decentralized Planning

Alex DeWeese, Jiaoyang Li, Guannan Qu

arXiv:2608.17928v1cs.MAcs.AIcs.RO

TL;DR

L-MAPF solvers such as RHCR offer strong solutions but incur computational costs that limit scalability. This paper theoretically motivates GD-RHCR, which plans spatially separated agent groups in parallel, achieving near-RHCR throughput with substantially lower planning cost.

  • Problem

    RHCR’s repeated MAPF solving incurs high computational cost, motivating a principled way to parallelize planning without sacrificing performance.

  • Method

    The paper models L-MAPF as a LI-MDP and uses group decentralized planning to partition agents by spatial interactions for parallel RHCR planning.

  • Results

    GD-RHCR stayed within ≈2% of RHCR throughput while achieving a 24.9x average improvement in plan time before RHCR collapse on one warehouse map.

  • Takeaways & Limitations

    GD-RHCR provides similar theoretical guarantees to RHCR and maintains strong performance at larger agent counts across varied maps.

  • Takeaways & Limitations

    Map topology can induce large groups, requiring all-at-once planning or fallback to PIBT when the group-size threshold is reached.

Abstract

from arXiv · show

In the Lifelong Multi-Agent Path Finding (L-MAPF) problem, agents must repeatedly move from one destination to another while avoiding obstacles and inter-agent collisions. Widely regarded as one of the highest-performing solutions to this problem is the Rolling-Horizon Collision Resolution (RHCR) framework. However, commensurate with its quality solutions, it incurs a computational cost that limits its applicability to even modest agent counts. In this paper, leveraging theoretical methods from the Locally Interdependent Multi-Agent MDP literature, we first theoretically prove the near-optimality of RHCR in a discounted MDP formulation of the L-MAPF problem. Then, we leverage these results to naturally motivate an extended framework called Group Decentralized RHCR (GD-RHCR) which incorporates a group decentralized structure that partitions agents based on a transitive communication scheme and plans for each partition of agents in parallel. We show that both RHCR and GD-RHCR achieve similar exponentially close to optimal guarantees, establishing a theoretical duality between the time based restrictions performed by vanilla RHCR and the additional space based partitioning performed by GD-RHCR. Lastly, we show that across varying maps, GD-RHCR is able to attain high throughput that scales into higher agent counts while maintaining a significantly lower per plan cost.

1 Introduction

This work develops a theoretically principled parallelization of RHCR for lifelong MAPF, targeting RHCR-level throughput with substantially lower computational cost. It establishes near-optimality guarantees for RHCR and similar guarantees for GD-RHCR, supported by empirical scaling results.

  • Problem setting: Lifelong MAPF repeatedly assigns agents new destinations while requiring high throughput and avoidance of obstacle and inter-agent collisions.This extends one-shot MAPF, which routes agents between fixed starts and destinations while avoiding obstacles and collisions.
  • Motivation: RHCR is a high-throughput solution, but repeatedly solving one-shot MAPF makes its computational cost grow exponentially, especially relative to PIBT.Even suboptimal Priority Based Search solvers can exhibit this computational explosion in RHCR.
  • Contributions: The paper develops GD-RHCR, a group-decentralized parallelization designed to preserve RHCR’s throughput while using a fraction of its compute cost.The approach partitions agents into groups and solves each group independently, enabling parallel replanning across groups.
  • Theoretical foundation of RHCR: RHCR is near-optimal in a discounted MDP formulation, with performance converging to optimal exponentially fast as the planning horizon increases.The worst-case bound is agnostic to the replanning window, providing theoretical motivation for that existing RHCR mechanism.
  • Group Decentralized RHCR: GD-RHCR satisfies theoretical guarantees similar to RHCR up to constant factors, yielding a duality between RHCR’s time restrictions and GD-RHCR’s distance-based group partitioning.The comparison is formalized through the framework’s cited theorems 3.1 and 6.1.
  • Experimental validation: 24.9x reduction in average plan time is achieved while matching RHCR before collapse, with up to a 57.7% throughput improvement against PIBT and collapsed RHCR.GD-RHCR also remains effective deeper into the large-agent range, where only PIBT can otherwise handle the counts.

2 Related Works

Prior MAPF work contrasts theoretically guaranteed but computationally expensive solvers with fast greedy, learning-based, and grouped approaches. In lifelong MAPF, RHCR offers high-quality solutions at substantial cost, while LI-MDP theory motivates GD-RHCR’s group-decentralized structure and guarantees.

  • One-Shot MAPF: Theoretically guaranteed one-shot MAPF solvers, including CBS, ECBS, and EECBS, provide optimal or near-optimal solutions but can require high computation because MAPF is NP-hard.Greedy alternatives such as priority-based planning are faster but forgo theoretical near-optimality.
  • One-Shot MAPF: Ultra-fast PIBT-based methods and variants such as LaCAM scale well but may be suboptimal, while learning-based methods lack guarantees on performance loss from decentralization.Learning approaches use reinforcement or imitation learning and can obtain some parallelism through decentralization.
  • Lifelong MAPF: Lifelong MAPF largely separates slow, high-quality RHCR from fast, greedy PIBT, with PIBT variants often suffering deadlocks when the graph is not biconnected.RHCR converts one-shot MAPF solvers to lifelong planning but inherits substantial computational cost from one-shot MAPF’s NP-hardness.
  • Grouping in MAPF: Prior grouping methods accelerate MAPF through static map subregions or dynamically identified independent groups, while preserving completeness guarantees in the targeted algorithms.These approaches differ from the paper’s LI-MDP-motivated group-decentralized structure.
  • Locally Interdependent Multi-Agent MDP: LI-MDPs model discounted multi-agent systems with local interactions, and their transitive visibility-based group decentralization enables parallel planning with exponentially close-to-optimal guarantees.The framework provides insight into RHCR’s near-optimality and motivates GD-RHCR, which integrates the group-decentralized observability structure.

3 Motivation: Natural Extension to RHCR

RHCR reduces computation by replanning collision-free paths over a finite time horizon, motivating spatially partitioned parallel planning. Naive independent decentralization can cause delays, whereas group decentralization uses connected agent groups to preserve coordination.

  • RHCR: RHCR runs a one-shot solver for H steps, executes α ≤ H steps, then replans from current positions and remaining destinations.Replanning occurs at each t = kα, with the computed path followed during [kα, kα + α).
  • Motivation for Parallelization: Spatially ignoring interactions beyond distance V offers a natural parallelization analogue to RHCR’s temporal horizon H.The proposed motivation is to run the solver on agent groups in parallel while reducing computational requirements.
  • Failure of Naive Decentralization: Naive independent decentralization can require at least 2k timesteps when centralized coordination reaches goals in k steps.Agents lack communication and cannot move appropriately under the visibility-limited independent scheme.
  • Failure of Naive Decentralization: Increasing V in independent decentralization is not analogous to increasing H, which approaches the optimal solution as H →∞.The failure of independent coordination prevents spatial visibility from providing the same guarantee as a larger solver horizon.
  • Group Decentralized Setting: Group decentralization partitions agents into connected components of a visibility graph and plans each group independently.Agents are vertices, with edges connecting pairs within distance V.

4 Theory: LI-MDP Analysis of RHCR

The paper formulates L-MAPF as a discounted reward LI-MDP, enabling a near-optimality analysis of RHCR. LI-MDP theory also motivates group decentralization because agents in different groups cannot collide within a finite interaction horizon.

  • L-MAPF as LI-MDP: L-MAPF is modeled as a discounted multi-agent MDP with grid states, movement actions, sequential goals, and rewards for goal achievement and collision penalties.Discounting keeps rewards finite in the lifelong setting, while collision penalties are assumed larger in magnitude than goal rewards.
  • L-MAPF as LI-MDP: The resulting model fits the LI-MDP framework, whose theory provides both RHCR near-optimality guarantees and a group-decentralized policy structure.The formulation differs from LI-MDP only by a minor discrepancy concerning edge collisions.
  • Near Optimality of RHCR: RHCR’s suboptimality decreases exponentially as planning horizon H increases, aside from the solver’s ϵ-optimality error.The guarantee is independent of the replan window α, although smaller α can improve the value gap in practice.
  • Why group decentralized?: Group decentralization is motivated by the result that agents in different groups cannot collide within ⌊V/2⌋ steps, allowing them to be ignored during finite-horizon computation.This provides the intuition for planning groups separately while preserving near-optimality guarantees.

5 Our Method: Group Decentralized RHCR

GD-RHCR partitions agents into connected groups, selectively replans them through lazy evaluation, coordinates groups with soft constraints, and uses fast secondary solvers for congestion. This design reduces per-iteration computation while supporting heterogeneous solvers across groups.

  • Group Decentralized: GD-RHCR identifies connected components at each timestep to form agent groups, using shortest-path distances and union-find to exploit map topology.Near obstacles, longer shortest paths can cause groups to break into smaller partitions.
  • Lazy Evaluation: Lazy evaluation dynamically determines which groups replan, staggering evaluations and reducing per-iteration computational load compared to RHCR.Groups initially plan in parallel with horizon H, then reuse shared plans until reevaluation is needed.
  • Soft Constraints: Soft constraints penalize collisions with other groups’ previous plans during lower-level search, while lazy evaluation limits the staleness of those trajectories.Only plans of groups currently planning are stale at a given time.
  • Soft Constraints: csoft must remain relatively small because large penalties increase lower-level computation, while hard constraints csoft = ∞ may eliminate solutions.Hard constraints can effectively give agents in other groups higher priority than the group being planned.
  • Secondary Solver: When a group reaches Kthreshold, GD-RHCR immediately invokes a fast secondary solver to decongest it, allowing the primary solver to route other groups.Unlike RHCR’s timeout-triggered fallback, GD-RHCR treats the secondary solver as an integrated part of the algorithm, so greater congestion can speed execution.
  • Flexible choice of solvers: The framework supports heterogeneous solvers across groups, enabling modular solver choices that exploit different group structures.The implementation uses a specific (SOLV ER, SOLV ER2) pair, but the framework permits different algorithms for different groups.

6 Theory: Near Optimality of GD-RHCR

Under a simplified discounted-MDP analysis, GD-RHCR is theoretically justified through a duality between spatial group restrictions and temporal replanning restrictions. The analysis also motivates parallel group decentralization and lazy evaluation alongside RHCR’s replanning window.

  • Assumptions: The theoretical analysis models L-MAPF as a discounted MDP and assumes Kthreshold = ∞ and csoft = 0, omitting the secondary solver.In practice, csoft is expected to be small, and estimating out-of-view agents often does not change the overall guarantee.
  • Theorem 6.1: Theorem 6.1 analyzes GD-RHCR trajectories generated from state s with horizon H when SOLVER produces an ϵ-optimal finite-horizon policy.The value V GD(s) is defined as the expected sum of discounted rewards along the resulting trajectory.
  • Space–time duality: The exponent min(⌊V/2⌋+ 1, H) captures the duality between GD-RHCR’s space restriction and RHCR’s time restriction.The group scheme ignores agents beyond distance V, while agents in different groups cannot collide within ⌊V/2⌋ timesteps.
  • Space–time duality: When H = ⌊V/2⌋+ 1, planning groups in parallel has no consequence on the solution and improves computational efficiency.This follows from the Dependence Time Lemma’s guarantee that agents in different groups cannot collide within ⌊V/2⌋ timesteps.
  • Theoretical motivation: The theory motivates GD-RHCR’s group-decentralized parallelization and lazy evaluation in the same way that it theoretically motivates RHCR’s replan window α.Thus, the analysis supports both the parallel group structure and the lazy evaluation scheme.

7 Simulations

Across MAPD and random-navigation simulations, GD-RHCR maintains near-RHCR throughput over a broad range while substantially reducing planning cost. Its advantage is greatest on maps whose topology induces smaller groups, whereas large groups, sparse obstacles, or PIBT deadlocks limit the improvement.

  • Simulation outcomes: GD-RHCR stays within ≈2% of RHCR throughput while achieving a 24.9x average plan-time improvement on warehouse-10-20-10-2-1 before RHCR collapses.Across several maps, GD-RHCR maintains near-RHCR performance before RHCR collapses.
  • Simulation outcomes: GD-RHCR reduces per-step plan time because only subsets of agents plan simultaneously, while parallelism further reduces the time for concurrently evaluating agents.The average plan-time metric uses the maximum completion time across parallel groups for GD-RHCR.
  • Simulation outcomes: Group-based planning extends RHCR’s effective range by restricting plans to small groups and using PIBT immediately for groups exceeding Kthreshold.This allows other smaller groups to continue planning and produces a more graceful transition to PIBT as fallback.
  • Simulation outcomes: +57.7% throughput improvement over collapsed RHCR / PIBT occurs for GD-RHCR at k = 800 on warehouse-10-20-10-2-1.At k = 1000, improvements are 12.6% on warehouse-10-20-10-2-2 and 9.66% on sortation-1.
  • Topology influences performance: Topology-driven smaller groups create the largest GD-RHCR advantage, while small or less obstacle-dense maps induce large groups and reduce the benefit.Large groups must be planned together or use the PIBT fallback when Kthreshold is reached.
  • Topology influences performance: Non-biconnected maps can cause PIBT deadlocks, reducing GD-RHCR performance when it relies on PIBT before RHCR would.On these maps, GD-RHCR can hit Kthreshold early and speed up computationally as agent counts increase.

8 Conclusion and Future Work · A MAPF as LI-MDP

The paper grounds RHCR in the LI-MDP framework and introduces GD-RHCR, which offers similar guarantees while scaling empirically to larger agent counts. Future work includes integrating group decentralization with learning-based and parallel MAPF methods, while the LI-MDP formulation models local interactions and collision penalties.

  • 8 Conclusion and Future Work: RHCR receives a theoretical grounding from LI-MDP analysis, motivating GD-RHCR with similar guarantees and strong empirical performance at larger agent counts.The comparison spans many maps and reports GD-RHCR performing well over RHCR.
  • 8 Conclusion and Future Work: Group decentralization is proposed as a flexible direction for integrating learning-based methods and parallelizing alternatives such as PIBT.The paper characterizes group decentralization as relatively new within the MAPF community.
  • 8 Conclusion and Future Work: The framework also enables different algorithms to operate in different locations or settings, opening additional research directions.This capability is presented as a simple setup created by the work.
  • A MAPF as LI-MDP: The LI-MDP appendix formally defines the framework and shows how the paper’s MAPF MDP formulation fits within it.The appendix introduces this connection after defining the LI-MDP components.
  • A MAPF as LI-MDP: Each agent has a metric-space state, optional internal state, arbitrary actions, and independent environment transitions constrained to movement of at most one space.The agent state is represented as S_i = (X, Y_i), and transitions are restricted by the distance metric.
  • A MAPF as LI-MDP: LI-MDP rewards combine single-agent incentives with pairwise local rewards that vanish beyond dependence radius R.The formulation permits i = j for single-agent rewards and uses r_i,j for interactions between agents.
  • A MAPF as LI-MDP: The MAPF model matches LI-MDP structure through individual movement, single-agent goals, and interdependent collision penalties, with edge collisions requiring interactions beyond R = 0.Vertex collisions correspond to R = 0, while edge collisions involve agents one step apart.

B Proofs · B.1 RHCR · B.2 Group Decentralized RHCR

The proofs analyze RHCR through finite-horizon value extensions and establish the corresponding GD-RHCR analysis using transitive agent partitions, dependence-time separation, and lazy replanning. The GD-RHCR proof accounts for within-group collisions directly and cross-group interactions after groups can interact, then compares the resulting value with the optimum.

  • B.1 RHCR: The RHCR proof represents its discounted value by repeatedly taking rewards for α timesteps from finite-horizon policies and subtracting the remaining discounted value.RHCR computes a finite-horizon optimal policy at each replan window α and repeatedly applies only the first α timesteps.
  • B.1 RHCR: The analysis extends an arbitrary finite-horizon policy trajectory across successive α-length windows before comparing RHCR with the optimal stationary policy.The extension completes the trajectory within each repeated horizon and supports the final comparison to π∗.
  • B.2 Group Decentralized RHCR: GD-RHCR partitions agents into sets Z(s) formed by transitive grouped-decentralized connections.The proof assumes csoft = 0 and Kthreshold = ∞.
  • B.2 Group Decentralized RHCR: The Dependence Time Lemma states that agents in different partitions cannot have vertex or edge collisions within ⌊V/2⌋ steps.The geometric argument uses the fact that agents in separate groups cannot interact within the dependence-time bound, including edge collisions.
  • B.2 Group Decentralized RHCR: The GD-RHCR value decomposition separates interactions within a partition from interactions with agents outside that partition.The notation i →p′ denotes agent i’s interactions, or collisions, with agents in p′.
  • B.2 Group Decentralized RHCR: When lazy evaluation triggers, GD-RHCR removes the remaining trajectory and introduces new plans for each group, accounting for cross-group collisions when agents enter one another’s groups.The trajectory expression uses an indicator for lazy evaluation and the group associated with the previous plan.
  • B.2 Group Decentralized RHCR: The GD-RHCR extension initially includes only collisions among agents in the same group, while cross-group residual terms are deferred beyond the dependence-time bound.The proof introduces an indicator for terms occurring after ⌊V/2⌋ iterations and then compares the resulting value function with V∗(s).

B.3 Abalations … Advantage of Lower Fallback

The ablations show that tighter visibility and soft-constraint settings can degrade performance by triggering thresholds or group timeouts. Throughput remains comparatively robust to increasing K on the studied map because topology and PIBT fallback decongest larger groups.

  • B.3 Abalations: Ablation simulations were conducted on warehouse-10-20-10-2-1, with outcomes reported in Figure 5.
  • B.3 Abalations: With Kthreshold = 20, lower visibility causes the algorithm to hit the threshold sooner, degrading performance.
  • Advantage of Smaller Visibilities: Without the threshold, RHCR viewed as GD-RHCR with V = ∞ has throughput close to RHCR before collapse on most maps, except smaller 32x32 maps.
  • Advantage of Smaller Soft Constraints: Increasing csoft rapidly worsens computation time, lowering throughput when groups begin to time out.
  • Advantage of Lower Fallback: Throughput is relatively agnostic to increasing K in Kthreshold = min(0.1k, K) on the studied map.
  • Advantage of Lower Fallback: The map topology forms smaller groups, while PIBT fallback decongests larger groups and lets GD-RHCR route into the large-agent range.

C Simulation Times

GD-RHCR generally achieves at least a 2x wall-time improvement over RHCR before RHCR collapse, while fallback behavior can make the advantage exponentially larger. Exceptions are linked to small maps and scheduling or core-contention effects, whereas large groups can trigger faster PIBT fallback execution.

  • Wall Times Are Faster: At least 2x wall-time improvement is achieved by GD-RHCR over RHCR before RHCR collapse, aside from anomalous maps.Including RHCR’s post-collapse region can make the improvement ratio exponentially large as RHCR’s timeout increases; beyond collapse, RHCR only runs PIBT fallback.
  • Wall Times Are Faster: Smaller 32x32 random and room maps are anomalous, while warehouse-10-20-10-2-2 has RHCR-like wall time mainly because of scheduling issues and core contention.The discrepancy between scaled planning time and wall time exposes these scheduling effects.
  • Fallback Means Faster Wall Times: GD-RHCR’s computation time can drop significantly when it relies more on SOLVER2 (PIBT), including on random-32-32-20 and room-32-32-var1.For larger agent counts, groups join, become large, and immediately enter PIBT, reducing wall time.

D Group Statistics

Group statistics show that average group counts generally rise and then decline as agent numbers increase, while denser agent populations produce larger groups. Maps where GD-RHCR approaches PIBT throughput exhibit comparatively few groups.

  • Group Statistics: Average group counts generally increase and then trend downward as the number of agents grows across most maps.The reported trend is attributed to changing agent density and group formation.
  • Group Statistics: Higher agent density tends to produce larger groups, reflected by the increasing average group size.The passage explains this as agents forming larger groups as map density increases.
  • Group Statistics: Sortation-2, random-32-32-20, and room-32-32-var1 show GD-RHCR throughput near PIBT alongside low average group counts.These examples are explicitly identified as maps where GD-RHCR had throughput near PIBT.
Loading 2608.17928v1…