Local Guidance for Configuration-Based Multi-Agent Pathfinding

AI summary

Overview

Research area: Multi-Agent Pathfinding (MAPF), specifically real-time, sub-optimal, configuration-based search — with a focus on a new form of "guidance" for heuristic planners.

Technical level: Advanced. The paper assumes familiarity with MAPF terminology (LaCAM, PIBT, configuration space, LNS, flowtime/sum-of-costs) and with the distinction between optimal and unbounded sub-optimal solvers.

Scope: The paper introduces local guidance — spatiotemporal congestion cues computed in the immediate vicinity of each agent — and integrates it into the LaCAM solver to improve solution quality while retaining real-time responsiveness.

What This Paper Is About

Existing MAPF "guidance" methods give planners congestion-avoidance information derived from a global view of the entire workspace and all agents, typically discarding time information. This paper asks whether the opposite works better: supplying each agent with a short-horizon, locally recomputed plan that explicitly captures where and when congestion occurs. The goal is to improve the quality of the initial solutions produced by LaCAM without blowing the real-time time budget.

Key Contributions

1. A local guidance concept. The authors define guidance that is recomputed around individual agents rather than globally, positioning it between coarse global guidance (which relaxes collision constraints) and full collision-free pathfinding (which is computationally demanding).

2. A windowed decoupled planning construction. They instantiate local guidance with a windowed planner (Algorithm 1) using a lexicographic cost that penalizes collisions, a default window of w = 20 and a collision penalty α = 3, solved by space-time A*.

3. A path-caching initialization scheme. Algorithm 2 bootstraps the guidance for configuration Q_k using the previous guidance Φ_{k-1}, shifting each agent's path by one timestep when the agent is where the prior guidance expected it to be. This lets the planner skip refinement iterations and saves significant time.

4. Compatibility and integration choices. The work shows how local guidance coexists with the swap technique (the guidance term is discarded and the PIBT preference reversed for swap situations), preserves LaCAM's completeness guarantee, accommodates an agent ordering sorted by previous-guidance collision counts, and can be combined with global guidance (LG+GG) via an added cost term δ(v).

Main Findings

• Large cost reductions on a congested maze. On maze-128-128-10 with 1,000 agents, guidance improved solution cost by 16.9% for global guidance (GG), 38.1% for local guidance (LG), and 38.4% for LG+GG, relative to unguided LaCAM (0.0%). In the most extreme case reported, LG reduced solution cost by 50% compared to original LaCAM.

• Local guidance beats global guidance overall. Across the benchmark maps, LG's cost reduction exceeded GG's with a few exceptions. GG was superior specifically on warehouse-20-40-10-2-1, where streamlining traffic flow in narrow corridors suppresses wasteful back-and-forth movement.

• Bottleneck areas are where LG shines. The maze-128-128-10 heatmaps show GG diversifying vertex usage in "area-A" but failing in "area-B," where most agents share a unique shortest start-goal path segment; LG smooths the flow there and discourages overuse of specific vertices.

• Overhead stays moderate. Although LG reconstructs guidance at every configuration generation, additional runtime remained within a few seconds in most cases even with 1,000 agents, and all LaCAM-based methods solved all tested instances within the 30 s limit.

• LG outperforms LNS2. LG delivered better solutions in less time than LNS2 in most scenarios. LNS2 failed on den312d when |A| ∈ {800, 1000}, whereas the LaCAM-based solvers solved all instances within 30 s.

• Combining both forms is best but marginally so. LG+GG inherits the strengths of each and yielded the best solution quality among all tested solvers, but the gain over LG alone was modest and came with the cost of computing both guidance types.

• Scalability holds. On warehouse-20-40-10-2-2 with up to 10,000 agents under a 300 s time limit, LG reduced solution cost by approximately 30% with moderate planning time, remaining significantly faster than both GG and LNS2, whose fast construction at this scale has been reported as challenging.

• Frequent ("live") updates matter. Updating guidance every two or three configuration generations instead of every generation could worsen performance relative to original LaCAM; updating every time with a smaller window was faster and produced higher-quality solutions.

• The path cache is essential. Using the cached previous guidance with one refinement iteration was the default; removing the cache (zero refinement) significantly dropped performance, while further refinement improved quality with diminishing returns and rising computation time.

• Agent ordering helps modestly. Sorting agents in descending order of collisions from the previous guidance improved performance across window sizes versus an unsorted order, but warehouse-10-20-10-2-1 was an exception, where narrow passages may induce oscillatory behavior under sorting. Runtime differences were negligible.

• Parameter trade-offs are real. Collision penalty α and window size w both affect quality and runtime with a sweet spot: overweighting collisions encourages overly conservative behavior, underweighting leaves congestion unmitigated, and enlarging the window helps only to a point.

• Better initial solutions pay off under anytime refinement. When LaCAM solutions were followed by LNS refinement (subsets of 1–30 agents, four concurrent LNS processes), densely populated scenarios showed large performance differences at the deadline, because smoothing highly interacting paths is hard. With fewer agents, LNS quickly refined solutions and final outcomes were similar.

• Comparison with lacam3. LG outperformed lacam3 in finding better initial solutions except on warehouse-type maps, leading to final solutions comparable to and sometimes superior to lacam3's, evaluated on 25 instances with 1,000 agents per map.

• Appendix heatmaps. On room-64-64-8 with 1,000 agents, cost improvements were 3.1% (GG), 31.5% (LG), and 30.8% (GG+LG); on warehouse-20-40-10-2-1 with 1,000 agents they were 33.3% (GG), 26.2% (LG), and 31.9% (GG+LG).

Methodology in Plain English

MAPF here means moving many agents on a graph from starts to goals, one step at a time, without two agents occupying the same vertex or swapping vertices in a single step. Solution quality is measured by flowtime (sum-of-costs). LaCAM searches over configurations — the simultaneous positions of all agents — treating MAPF as single-agent pathfinding on a graph of configurations, using depth-first search with lazy successor generation. That successor generation uses a configuration generator; PIBT is the usual choice, and it works by ranking each agent's candidate moves according to a preference list.

The researchers change what goes into that preference list. Before PIBT runs, they build a short "guidance path" for each agent using a general template (Algorithm 1) that plans ahead only w timesteps — typically 5 to 20 — using space-time A*. The cost is lexicographic: first a stage cost that counts steps and adds a penalty α (= 3) for each collision with other agents' guidance paths, then a terminal cost of shortest-path distance to the goal. This encourages paths that stay near the goal direction but collide less with neighbors within the short horizon. The resulting guidance is fed into PIBT as an extra leading term in the scoring function, so agents prefer their guidance path's next step.

Because planning agents sequentially is unfair — the first agent faces few constraints, the last faces many — the authors iterate the planning a few times (empirically twice is enough), and they reuse the previous configuration's guidance shifted by one timestep to approximate the first iteration cheaply. They also sort agents by how many collisions they had in the previous guidance. Local guidance can be layered on top of global guidance (SUO-based, precomputed, time-independent paths) by adding a distance-to-global-path term to the cost. The formal overhead is O(mn(w|E| + w|V| log(w|V|))) for m iterations over n agents, which with m = 1 and grid-like graphs reduces to O(nw|V| log(w|V|)), plus O(nw) for initialization.

Experiments used the "random" scenarios of the MAPF benchmark (25 instances per map and agent count, up to 1,000 agents), a laptop with an Intel Ultra 9 185H and 62 GB RAM, and a 30 s planner time limit unless noted. Comparisons covered LaCAM, GG, LG, LG+GG, and LNS2. Figure 3's instance-wise panel drew 644 instances across five agent scales {200, 400, 600, 800, 1000}, five instances per setting from 32 different grids, with flowtime normalized by a trivial lower bound of the sum of shortest start-goal distances.

Why This Matters

Research impact. The paper reframes the guidance design space: instead of an all-or-nothing choice between coarse global guidance and expensive exact pathfinding, it shows a middle ground exists and is empirically strong. It establishes what the authors describe as a new Pareto frontier for real-time MAPF, and it argues that anytime MAPF pipelines should invest more time in finding better initial solutions in dense settings rather than relying solely on refinement.

Real-world applications.

• Warehouse and logistics robotics fleets, where hundreds of robots share narrow aisles (the paper evaluates exactly this setting, with warehouse-20-40-10-2-1 and warehouse-20-40-10-2-2 maps).
• Autonomous vehicle coordination in confined or structured environments such as intersections, parking structures, and ports.
• Drone swarm routing where dense traffic causes hovering waiting times.
• Automated container terminals and factory-floor AGV systems where congestion directly translates to lost throughput.

Industry relevance. Local guidance is easy to implement (it reuses a widely occurring windowed decoupled planning template), requires no offline data collection or prior preparation, and is released as open-source code at https://github.com/allegorywrite/lg_lacam. The funding note — a gift from Murata Machinery, Ltd. — points to direct industrial interest in material-handling automation. The trade-off analysis (a few seconds of overhead for substantial cost reduction) is the kind of explicit accounting practitioners need.

Future Directions

1. Better integration of global and local guidance. LG+GG was best but only modestly better than LG alone, at the cost of computing both. The authors state that developing more effective integration remains an important direction.

2. Extending beyond LaCAM. The paper argues the concept deserves research effort "not limited to LaCAM," since the construction template appears across many MAPF algorithms.

3. Lifelong MAPF. One direct application named by the authors is lifelong (continuously re-tasked) MAPF, where PIBT has proven effective for building strong planners.

4. Understanding the warehouse exception. GG outperformed LG on warehouse-type maps due to narrow-corridor traffic flow and oscillatory behavior under agent sorting; a principled way to handle corridor-heavy topologies is left open.

Target Audience

MAPF researchers and graduate students working on scalable sub-optimal planning, practitioners building large robot-fleet coordinators (warehouse, logistics, material handling), and anyone already familiar with PIBT, LaCAM, or LNS-based anytime solvers who wants to improve initial solution quality without sacrificing real-time responsiveness. Readers seeking beginner-level introductions to MAPF will find the preliminaries terse; the paper is best suited to those who already know the field's standard algorithms and benchmark suites.

Authors’ abstract

Guidance is an emerging concept that improves the empirical performance of real-time, sub-optimal multi-agent pathfinding (MAPF) methods. It offers additional information to MAPF algorithms to mitigate congestion on a global scale by considering the collective behavior of all agents across the entire workspace. This global perspective helps reduce agents' waiting times, thereby improving overall coordination efficiency. In contrast, this study explores an alternative approach: providing local guidance in the vicinity of each agent. While such localized methods involve recomputation as agents move and may appear computationally demanding, we empirically demonstrate that supplying informative spatiotemporal cues to the planner can significantly improve solution quality without exceeding a moderate time budget. When applied to LaCAM, a leading configuration-based solver, this form of guidance establishes a new performance frontier for MAPF.