PaperlayerView exact revision on arXiv

Source-linked AI summary

MAPP: a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees

Ko-Hsin Cindy Wang, Adi Botea

arXiv:1401.3905v1cs.AI

TL;DR

Multi-agent path planning must balance centralized methods’ guarantees against decentralized methods’ scalability. The paper introduces MAPP, which identifies provably solvable units using tractable planning on undirected graphs. On game-grid benchmarks, MAPP solved 99.86% of units while retaining partial completeness and low-polynomial bounds, with longer solutions and slower speed than FAR when reusable data are available.

  • Problem

    Centralized planning has an exponentially large state space, while decentralized methods lack formal guarantees for completeness, runtime, and solution quality.

  • Method

    MAPP computes paths and alternate paths, identifies units in formally characterized completeness classes, and offers basic and extended versions with low-polynomial bounds.

  • Results

    99.86% of units were solved in attempt-all mode, compared with 81.87% for FAR and 77.84%–80.87% for WHCA* variants.

  • Takeaways & Limitations

    MAPP combines practical scalability with partial completeness and low-polynomial guarantees, while trading off speed and solution length against faster decentralized baselines.

  • Takeaways & Limitations

    MAPP’s solutions were longer than FAR’s and WHCA*’s, and unnecessary undo moves remain a target for improvement.

Abstract

from arXiv · show

Multi-agent path planning is a challenging problem with numerous real-life applications. Running a centralized search such as A* in the combined state space of all units is complete and cost-optimal, but scales poorly, as the state space size is exponential in the number of mobile units. Traditional decentralized approaches, such as FAR and WHCA*, are faster and more scalable, being based on problem decomposition. However, such methods are incomplete and provide no guarantees with respect to the running time or the solution quality. They are not necessarily able to tell in a reasonable time whether they would succeed in finding a solution to a given instance. We introduce MAPP, a tractable algorithm for multi-agent path planning on undirected graphs. We present a basic version and several extensions. They have low-polynomial worst-case upper bounds for the running time, the memory requirements, and the length of solutions. Even though all algorithmic versions are incomplete in the general case, each provides formal guarantees on problems it can solve. For each version, we discuss the algorithms completeness with respect to clearly defined subclasses of instances. Experiments were run on realistic game grid maps. MAPP solved 99.86% of all mobile units, which is 18--22% better than the percentage of FAR and WHCA*. MAPP marked 98.82% of all units as provably solvable during the first stage of plan computation. Parts of MAPPs computation can be re-used across instances on the same map. Speed-wise, MAPP is competitive or significantly faster than WHCA*, depending on whether MAPP performs all computations from scratch. When data that MAPP can re-use are preprocessed offline and readily available, MAPP is slower than the very fast FAR algorithm by a factor of 2.18 on average. MAPPs solutions are on average 20% longer than FARs solutions and 7--31% longer than WHCA*s solutions.

1. Introduction

MAPP addresses the scalability–guarantee trade-off in multi-agent path planning by combining tractable computation with formal, partial completeness guarantees. Its experiments show high solving rates, while exposing speed and solution-length trade-offs.

  • Motivation: Multi-agent path planning has an exponentially growing centralized state space, making complete and optimal search impractical as the number of units increases.The problem is NP-complete for bounded-move feasibility and makespan optimization.
  • Motivation: Existing decentralized methods scale better but provide no formal guarantees for solvability, running time, or solution quality.FAR and WHCA* decompose the problem into smaller searches but remain incomplete.
  • MAPP: MAPP identifies units guaranteed to be solved in low-polynomial time and defines completeness classes, including the SLIDABLE class for Basic MAPP.Extended versions enlarge the completeness range and improve solution length.
  • MAPP: A blank travels along alternate paths so blocked units can advance without runtime replanning.MAPP computes each unit’s path at the beginning and uses sliding-tile-puzzle-inspired blank movement to guarantee progress when applicable.
  • Evaluation: 99.86% of units were solved in attempt-all mode, versus 81.87% for FAR and 77.84%–80.87% for WHCA* variants.MAPP marked 98.82% of units as provably solvable during its first computation stage.
  • Evaluation: MAPP can reuse computation across instances, is competitive with or faster than WHCA*, but is 2.18× slower than FAR with reusable data and produces longer solutions.Solutions were 20% longer than FAR’s and 7%–31% longer than WHCA*’s; the paper also adds detailed enhancements, proofs, and empirical analysis.

2. Related Work

Related work contrasts centralized methods that retain completeness or optimality with decentralized methods that improve scalability but sacrifice guarantees. Later approaches seek bounded-suboptimal compromises or exploit structured graph subclasses.

  • Centralized planning: Centralized A* searches the joint state space of all units, preserving completeness and optimality but requiring O(m^n) states.Most generated states are unpromising because they move some units farther from their goals.
  • Decentralized planning: LRA* plans independently and replans after collisions, sometimes reducing computation to O(mn), but it can create cycles and cannot prevent bottlenecks.Its behavior depends on collision-triggered runtime replanning.
  • Decentralized planning: Decentralized planning decomposes the problem and scales better, but commonly yields suboptimal solutions without completeness, runtime, or solution-length guarantees.WHCA* is an example using temporal-spatial reservations and windowed planning.
  • Bridging the trade-off: Recent work bridges tractability and completeness through bounded-suboptimal methods or complete planning on graphs with structures such as stacks, halls, cliques, and rings.These approaches exploit specific substructures rather than unrestricted graphs.
  • Bridging the trade-off: BIBOX was reported as fast with shorter solutions than a related pebble-coordination algorithm, but the authors observed rapidly growing runtime on much smaller graphs than their game maps.The comparison highlights scalability concerns for alternative complete approaches.

3. Problem Statement

The paper models multi-agent planning on undirected weighted graphs, with homogeneous units moving from distinct starts to distinct targets while avoiding fixed and mobile obstacles. Grid maps are used for clarity and experimentation, but MAPP’s definitions are not grid-specific.

  • Problem model: An instance consists of an undirected weighted graph and a non-empty collection of homogeneous mobile units with distinct start-target pairs.Each state records all unit positions at a given time.
  • Problem model: The objective is to move every unit from its start to its target while avoiding fixed and mobile obstacles.The model assumes one unit per graph node at a time.
  • Graph representation: Grid abstractions offer more path options for collision avoidance than sparse abstractions, so the experiments focus on grid maps.The examples use four-connected grids with cardinal moves only.
  • Graph representation: MAPP’s conditions and algorithmic definitions apply beyond regular grids under the stated graph-occupancy and edge-interference assumptions.Four-directional movement does not reduce completeness relative to eight-directional movement in the paper’s setting.

4. The SLIDABLE Class of Instances

The SLIDABLE class captures instances where Basic MAPP can guarantee progress using precomputed paths and alternate routes. Its conditions are polynomial-time verifiable and support formal completeness guarantees.

  • The SLIDABLE class: Basic MAPP is complete for a subclass of instances called SLIDABLE.An instance is SLIDABLE exactly when every unit is SLIDABLE.
  • The SLIDABLE class: A SLIDABLE unit has a path π(u) from its start to target satisfying the paper’s required conditions.The definition is based on the unit’s path sequence and associated alternate paths.
  • SLIDABLE conditions: Alternate connectivity requires an alternate path Ω_i between neighboring path locations that avoids the intervening location.Figure 2 illustrates such an alternate path.
  • SLIDABLE conditions: The initial blank condition requires the first path location to be unoccupied, while target isolation prevents other units’ paths or alternate paths from interfering with targets.These conditions constrain the initial configuration and interactions among planned routes.
  • Verification and algorithm: The three SLIDABLE conditions can be verified in polynomial time because the required A* searches explore state spaces linear in the number of graph nodes.Verification also identifies units that are guaranteed to be solved.
  • Verification and algorithm: MAPP computes paths and alternate paths, marks qualifying units as SLIDABLE, initializes the active set, and performs repositioning when needed.The algorithm overview lists these stages explicitly.

5. Basic MAPP

Basic MAPP computes fixed individual paths and alternate paths, then coordinates units through ordered progression and repositioning steps. Its private zones, blank travel, and cycle-free progression guarantee termination and completeness on SLIDABLE instances.

  • 5. Basic MAPP: Basic MAPP is complete on SLIDABLE instances and uses a total ordering to remain deadlock-free and cycle-free.Lower-priority units cannot interfere with higher-priority units’ ability to advance.
  • 5.2 Path Computation: MAPP computes and caches a fixed path π(u) and alternate paths Ω for each unit during initial planning.The alternate-path conditions are enforced during modified A* search, and cached information can be reused across units and instances on the same map.
  • 5. Basic MAPP: A progression step advances active units toward their targets, while repositioning restores the advancing conditions after units are displaced.At least one active unit reaches its target during each progression step, so the active set shrinks until all units are solved.
  • 5.3 Progression: Private zones prevent lower-priority units from occupying locations needed by higher-priority units.The progression pseudocode either waits, moves directly, or brings a blank in front of a unit before it advances.
  • 5.3 Progression: Blank travel brings a vacant location to a unit’s front through alternate paths, potentially pushing another unit off its path as a side effect.The master unit can always bring a blank forward and is never pushed off its path.
  • 5.3 Progression: The master unit advances at every outer-loop iteration, at least one unit reaches its target per progression step, and Algorithm 2 generates no cycles.Reverse repositioning ensures subsequent progression steps start from a well-positioned state.

6. Worst-case and Best-case Analysis

MAPP has low-polynomial worst-case bounds whose exact forms depend on the alternate-path length parameter λ. When paths are optimal and require no blank travel, MAPP can produce optimal solutions with reduced search effort.

  • Worst-case bounds: λ measures the maximal length of alternate paths Ω and is often a small constant because alternate-path endpoints are close.The analysis also considers the worst case where λ grows linearly with m.
  • Worst-case bounds: O(nm) memory is required when λ is constant, increasing to O(nm^2) when λ grows linearly with m.The bound covers execution memory, including the progression-step move stack.
  • Worst-case bounds: O(n^2m) total travel distance and global-solution memory hold when λ is constant, increasing to O(n^2m^2) when λ grows linearly with m.The solution-length bound is expressed as total moves by all units.
  • Best-case analysis: MAPP computes optimal solutions when π paths are optimal and units reach targets without blank traveling.If the paths are disjoint, the solutions are also makespan optimal, and the search can require less effort than centralized A*.

7. Extending the Completeness Range

MAPP extends its completeness range by relaxing target isolation and alternate connectivity, then combining both extensions. These variants preserve tractability guarantees while providing formal completeness on broader, explicitly defined subclasses.

  • Completeness extensions: 70.57% of units satisfy all three Basic MAPP SLIDABLE conditions, while relaxing alternate connectivity or target isolation raises this to 87.06% or 85.05%.Relaxing blank availability changes the percentage only from 70.57% to 70.73%, so the other two conditions are more restrictive in this experiment.
  • 7.1 Relaxing Target Isolation: TI MAPP allows paths through foreign targets using a partial ordering that prevents cycles and prioritizes units consistently.Solved units cannot interfere with the remaining problem, and TI MAPP terminates.
  • 7.1 Relaxing Target Isolation: A greedy procedure removes units when necessary to keep the partial ordering cycle-free, guaranteeing solutions for the remaining TI-SLIDABLE units.The algorithm may identify many, often all, units as provably solvable even though it is not complete on the full TI-SLIDABLE class.
  • 7.2 Relaxing Alternate Connectivity: AC MAPP allows multiple paths to cross a single-width tunnel by generalizing blank travel with buffer zones.The extension addresses cases where alternate connectivity fails inside tunnels.
  • 7.2 Relaxing Alternate Connectivity: AC MAPP terminates and is complete on AC-SLIDABLE instances while preserving MAPP’s upper bounds.Its running time is O(n^2mτmax) or O(n^2mλ), depending on the larger tunnel or alternate-path length parameter.
  • 7.3 Combining Extensions: TI+AC MAPP combines both extensions and terminates, with each iteration solving at least one unit.Instances with targets inside single-width tunnels are excluded when their buffer capacity is zero.

8. Improving Solution Length

MAPP improves solution length by replacing overly strong global checking with counting-based repositioning, while preserving well-positioned states and completeness guarantees. The enhanced RC MAPP stops undoing moves under conditions that prevent interference and is proven to end every repositioning step well positioned.

  • Motivation: Global checking guarantees a well-positioned state but can create many unnecessary undo moves.It checks the advancing condition for all active units after each undo move.
  • Repositioning with counting: Repositioning with counting balances global and local checking to reduce unnecessary moves while retaining the guarantee of reaching a well-positioned state.Undo moves stop when the unit is advancing, cannot interfere with future undo moves, and satisfies additional safety conditions.
  • Repositioning with counting: Counters c(l) are reset at each progression step, initialized by occupancy, incremented on visits, and decremented when undo moves leave a location.These counters support deciding when further undo moves are unnecessary.
  • Counting guarantees: If c(l) = 0, no unit will pass through l during the remainder of the current repositioning step.For an active unit at pos(u), c(pos(u)) = 1 also means that no other unit will pass through its position later in that step.
  • RC MAPP: RC MAPP introduces counting-based repositioning to eliminate many useless undo moves.Each active unit stops undoing moves when the conditions in Definition 33 are satisfied.
  • Guarantees: Every RC MAPP repositioning step ends in a well-positioned state, and using RC in TI+AC MAPP does not negatively affect completeness.The well-positioned state guarantees that active units have their advancing condition satisfied.

9. Experimental Results

Experiments show that MAPP’s relaxations substantially expand solvability and scalability, while preprocessing improves runtime; the resulting plans are generally longer than competitors’ plans.

  • Experimental setup: MAPP compares four versions—Basic, TI, AC, and TI+AC—using success ratio, defined as the percentage of solved units.Repositioning with counting is excluded because it affects solution length rather than success ratio.
  • Scalability as Percentage of Solved Units: TI MAPP achieves a success ratio of at least 93% across all unit counts on 7 maps, while narrow corridors and tunnels remain challenging on 3 maps.Basic MAPP’s success ratio often falls below 50% as unit counts increase on four challenging maps.
  • Scalability as Percentage of Solved Units: 98.82% of all units are solved by TI+AC MAPP, compared with 81.87% by FAR and 77.84% or 80.87% by WHCA* with or without diagonals.With 2,000 units, FAR solves as few as 17.5%, while WHCA* solves as few as 16.7% without diagonals and 12.3% with diagonals.
  • Scalability when Attempting to Solve All Units: Attempt-all increases MAPP’s solved-unit percentage from 98.82% to 99.86% and raises fully solved instances from 34% to 84.5%.The large instance-level gain occurs because failed instances often contain only one or two unsolved units.
  • Comparing Total Distance with FAR and WHCA*(8,1): MAPP’s travel distance is 7% longer than WHCA* without diagonals and 20% longer than FAR on average, while remaining 31% longer than diagonal WHCA* on average.Across comparisons, MAPP’s distance ranges from shorter to substantially longer than competing methods.
  • Comparing Total Distance with FAR and WHCA*(8,1): MAPP can still make unnecessary undo moves, each of which counts twice in final solution length, motivating further plan-length improvements.Repositioning with counting eliminates many unnecessary undo moves but does not remove them all.
  • Running Time Analysis: Offline reusable data reduce MAPP’s speed gap to FAR to a factor of 2.18 and make MAPP 4.8–5.2 times faster than WHCA* on average.When computed from scratch, MAPP is comparable to WHCA* but about 10 times slower than FAR; search, especially Ω-path search, dominates runtime.

10. Conclusion

MAPP addresses the trade-off between centralized methods’ scalability limits and decentralized methods’ lack of guarantees by combining practical scalability with formal, low-polynomial bounds. Empirically, it solved substantially more units than FAR and WHCA*, while accepting longer solutions and some speed trade-offs.

  • 10. Conclusion: 98.82% of units were provably solvable, while 99.86% were solved in attempt-all mode, compared with 81.87% for FAR and 77.84% and 80.87% for WHCA*.The attempt-all version solved 13–26% more instances than the benchmark algorithms.
  • 10. Conclusion: MAPP combines formal completeness and upper-bound guarantees with scalability and practical efficiency.Its guarantees cover completeness, runtime, memory, and solution length within supported instance classes.
  • 10. Conclusion: MAPP’s speed was significantly better than WHCA* and 2.18 times slower than FAR on average when alternate paths were available.With all computations from scratch, MAPP’s speed was comparable to WHCA*.
  • 10. Conclusion: MAPP’s solutions were on average 20% longer than FAR’s and 7–31% longer than WHCA*’s solutions.The paper identifies unnecessary undo moves as one source of excess solution length.
  • 10. Conclusion: Future work targets faster computation, better solutions, broader instance coverage, additional quality measures, and heterogeneous units.Proposed extensions include relaxing further SLIDABLE conditions and supporting units with different sizes and speeds.
Loading 1401.3905v1…