Driving · 2026-10-14

Reinforcement Learning for Large-Scale Lifelong Multi-Agent Path Finding with Shared Spatial Fields

Jean Seong Bjorn Choe

arXiv:2610.18186PDF

AI-assisted summary based on the paper. Consult the linked source for methods and limitations. Benchmark numbers appear after editor verification.

TL;DR

The authors propose an end-to-end average-reward RL policy for lifelong multi-agent path finding that computes a shared spatial field over the map once per timestep, then uses a goal-conditioned route operator and a destination allocation (Sinkhorn) step to decide agent movements. Trained without planner demonstrations or an online planner, it transfers to larger unseen layouts and populations, matching or exceeding best baselines across six 10,000-agent layouts while running in under 10 ms per step.

Why it matters

Large-scale lifelong MAPF needs fast per-step decisions under changing traffic and across varied layouts/populations. The method reuses computation across agents via a shared spatial field and uses differentiable route reweighting plus entropy-regularized allocation to train directly from throughput, enabling deployment without retraining on larger unseen layouts and different agent populations.

Method

  • CNN computes a shared spatial field Φt over the map once per timestep from an aggregate state; outputs are scores for movement and waiting.
  • Goal-conditioned route operator: uses soft shortest-path reference and learned field-derived gains, reweights KL-regularized route continuations of fixed depth H, then returns next-move probabilities.
  • Destination allocation: one-step assignment using entropy-regularized affinities from next-move probabilities and a Sinkhorn-based update to account for competing demand for cells; trained end-to-end with average-reward RL on throughput.
Abstract (from arXiv)

Large-scale applications of lifelong multi-agent path finding (LMAPF) call for computationally inexpensive movement decisions under changing traffic conditions and across varied layouts. We propose a navigation policy in which a convolutional network computes a shared spatial field over the map once per timestep and a compact goal-conditioned operator derives agents' movement preferences. The complete policy is trained end-to-end using average-reward reinforcement learning with throughput as the reward, without planner demonstrations or a separate online path planner. For structured and unstructured layouts, we train one policy per class on mixtures of small maps and deploy each without retraining on larger, unseen layouts and agent populations. Across six layouts with 10000 agents, our policies achieve throughput comparable to or higher than the strongest evaluated baselines. The proposed method has an average execution time below 10 ms per step, more than an order of magnitude faster than several established planners.

Related papers

Publication record

Bibliographic evidence describes where and when a record appeared. It does not validate scientific claims.

First public release: 2026-10-13 · Indexed by Pub-AI: 2026-10-14 UTC

preprint

Reinforcement Learning for Large-Scale Lifelong Multi-Agent Path Finding with Shared Spatial Fields

Jean Seong Bjorn Choe

Preprint posted: 2026-10-13 · Original record ↗

arxiv
2610.18186
Explicit source versions (1)
  • v1 · 2026-10-13
  1. Preprint available

    Source date: 2026-10-13 · First detected: 2026-10-25 UTC · Historical baseline

    Source evidence (1)
Abstract · arxiv

Large-scale applications of lifelong multi-agent path finding (LMAPF) call for computationally inexpensive movement decisions under changing traffic conditions and across varied layouts. We propose a navigation policy in which a convolutional network computes a shared spatial field over the map once per timestep and a compact goal-conditioned operator derives agents' movement preferences. The complete policy is trained end-to-end using average-reward reinforcement learning with throughput as the reward, without planner demonstrations or a separate online path planner. For structured and unstructured layouts, we train one policy per class on mixtures of small maps and deploy each without retraining on larger, unseen layouts and agent populations. Across six layouts with 10000 agents, our policies achieve throughput comparable to or higher than the strongest evaluated baselines. The proposed method has an average execution time below 10 ms per step, more than an order of magnitude faster than several established planners.