PaperlayerView exact revision on arXiv

Source-linked AI summary

PRIMAL2: Pathfinding via Reinforcement and Imitation Multi-Agent Learning -- Lifelong

Mehul Damani, Zhiyao Luo, Emerson Wenzel, Guillaume Sartoretti

arXiv:2010.08184v3cs.RO

TL;DR

LMAPF requires agents to repeatedly pursue changing goals while coordinating in dense, structured environments, where frequent replanning is difficult for existing approaches. PRIMAL2 learns fully decentralized policies from local observations, predicted neighbor movements, coordination conventions, and imitation learning. Experiments show competitive performance, improved results over PRIMAL, and scaling to 2048 agents with rapid online planning.

  • Problem

    LMAPF requires repeated online replanning and substantial coordination in dense, structured environments, challenging existing coupled and decoupled approaches.

  • Method

    PRIMAL2 is a distributed reinforcement learning framework using local observations, predicted neighbor movements, learned conventions, and centralized-planner imitation to train decentralized policies.

  • Results

    PRIMAL2 surpasses PRIMAL in constrained settings, performs comparably to state-of-the-art planners across scenarios, and scales to teams of 2048 agents.

  • Takeaways & Limitations

    Learned conventions support implicit coordination in larger teams while PRIMAL2 retains rapid online replanning and decentralized operation.

Abstract

from arXiv · show

Multi-agent path finding (MAPF) is an indispensable component of large-scale robot deployments in numerous domains ranging from airport management to warehouse automation. In particular, this work addresses lifelong MAPF (LMAPF) - an online variant of the problem where agents are immediately assigned a new goal upon reaching their current one - in dense and highly structured environments, typical of real-world warehouse operations. Effectively solving LMAPF in such environments requires expensive coordination between agents as well as frequent replanning abilities, a daunting task for existing coupled and decoupled approaches alike. With the purpose of achieving considerable agent coordination without any compromise on reactivity and scalability, we introduce PRIMAL2, a distributed reinforcement learning framework for LMAPF where agents learn fully decentralized policies to reactively plan paths online in a partially observable world. We extend our previous work, which was effective in low-density sparsely occupied worlds, to highly structured and constrained worlds by identifying behaviors and conventions which improve implicit agent coordination, and enable their learning through the construction of a novel local agent observation and various training aids. We present extensive results of PRIMAL2 in both MAPF and LMAPF environments and compare its performance to state-of-the-art planners in terms of makespan and throughput. We show that PRIMAL2 significantly surpasses our previous work and performs comparably to these baselines, while allowing real-time re-planning and scaling up to 2048 agents.

I. INTRODUCTION

LMAPF extends MAPF to dynamic settings where agents repeatedly receive goals and must replan online. PRIMAL2 extends PRIMAL with decentralized coordination mechanisms for dense, structured environments and performs competitively while scaling to large teams.

  • LMAPF repeatedly assigns agents new goals, requiring reactive online path computation and frequent replanning.Its performance is measured by throughput, the average number of targets reached per unit time.
  • PRIMAL2 extends distributed reinforcement learning from one-shot MAPF to lifelong MAPF in dense, structured warehouse-like environments.The framework remains fully decentralized and relies on local interactions only.
  • The approach combines learned movement conventions, rich local observations, predicted neighbor movements, and imitation learning from a centralized planner.A new distributed training implementation reduces training time from 10 days to about 12 hours.
  • Simulations with up to 2048 agents show coordinated maneuvers without explicit communication and performance comparable to state-of-the-art planners in multiple scenarios.PRIMAL2 also significantly surpasses the previous PRIMAL work in these structured environments.

II. PRIOR WORKS

Prior MAPF planners trade scalability against solution quality or coordination: coupled methods incur exponential joint-space costs, while decentralized learning methods can struggle in dense structured worlds or with large teams.

  • Coupled planners search a high-dimensional joint space for complete or bounded-suboptimal paths, but computational cost scales exponentially with agent count.
  • Decoupled planners plan in each agent’s lower-dimensional space and adjust paths to avoid collisions.
  • PRIMAL introduced fully decentralized reactive policies that scale to large teams but perform poorly in densely occupied structured worlds requiring substantial coordination.
  • Communication-learning methods using graph neural networks address constrained environments but often have poor scalability to larger teams.
  • A common LMAPF strategy repeatedly invokes one-shot MAPF planners, causing replanning time to grow exponentially and recomputing paths for unaffected agents.

III. PROBLEM FORMULATION

The paper evaluates one-shot and lifelong pathfinding in structured 2D grid worlds with obstacles, corridors, and agent-goal dynamics. One-shot episodes end when agents reach unique goals, while lifelong episodes continuously assign new goals.

  • A. Environment Setup: The environments are 2D discrete 4-connected grids where agents, goals, and obstacles occupy individual cells.Agents can move cardinally or wait at each timestep.
  • A. Environment Setup: Structured worlds use moderate-to-high obstacle densities and long corridors generated by a parameterized maze algorithm.
  • A. Environment Setup: Corridors are illustrated as dead-ends, two-endpoint passages, and T-junctions formed by combining three corridors.
  • A. Environment Setup: The one-shot variant supports comparisons of solution quality with centralized baselines, although the paper focuses on lifelong MAPF.
  • B. One-shot MAPF: In one-shot MAPF, each agent receives a unique goal, disappears upon arrival, and frees its occupied cell for other agents.The episode terminates when all agents reach their goals.

C. Lifelong MAPF

LMAPF is an online task in which agents know only their current goals and receive new ones upon arrival. PRIMAL2 uses local observations enriched with goal, path, corridor, and predicted-neighbor information for decentralized replanning.

  • C. Lifelong MAPF: LMAPF agents receive new randomly assigned goals only after reaching their current goals and may operate indefinitely or for a fixed horizon.New goals are constrained to lie a minimum Euclidean distance from the current goal.
  • C. Lifelong MAPF: The LMAPF objective is throughput, defined as the average number of targets reached per unit time.
  • Each agent observes a limited local square field of view, approximately 11×11, reflecting partial observability and supporting generalization across world sizes.
  • The observation includes obstacle, agent, goal, own-goal, path-length, and predicted-neighbor maps plus goal direction and distance values.
  • Corridor maps encode endpoint orientation through ∆X and ∆Y and indicate whether another agent blocks an endpoint.The blocking map marks an endpoint when an agent inside the corridor is moving toward that exit.

B. Action Space

PRIMAL2 combines discrete grid-world actions with A3C, value and policy-gradient objectives, entropy-based exploration, and supervised validity learning. Its network processes local observations and goal information before recurrent policy generation.

  • Action space: Agents choose among five actions: four cardinal moves or staying still, while invalid moves and convention-breaking actions are excluded during training.Validity includes avoiding obstacles, agents, and predefined corridor-navigation violations.
  • Learning objectives: A supervised valid-action loss is preferred over reward-based learning because validity does not depend on the preceding trajectory.The authors report that this avoids delayed and unfavorable convergence when learning valid actions.
  • Learning objectives: A3C trains the network with value, actor, and validity losses combined through manually tuned weights.The value output matches discounted cumulative returns, while the validity loss reduces the likelihood of invalid moves.
  • Network structure: Local observation channels are processed convolutionally, goal features through a fully connected layer, and their combination through fully connected layers and an LSTM.A residual shortcut connects the output of the concatenated processing pathway.
  • Learning objectives: Entropy regularization encourages exploration and discourages premature convergence, with σH = 0.01 used in practice.The actor loss also uses an advantage estimate obtained by bootstrapping from the critic’s value function.

V. LEARNING

The learning section introduces the methods used to obtain implicit coordination and train the decentralized agents.

  • Learning: The section details methods for achieving implicit agent coordination and the associated training process.

A. Coordination Learning

Dense, constrained environments make coordination necessary, but decentralized agents must learn it implicitly with limited environmental information and no direct control over others. PRIMAL2 addresses this through convention learning, imitation learning, and episode randomization.

  • Motivation: High traffic in constrained worlds creates situations where decentralized agents need implicit coordination despite limited information and no direct control over other agents.Centralized planners can coordinate explicitly in the joint space, whereas decentralized policies must learn coordination.
  • Approach: PRIMAL2 uses convention learning, centralized-planner demonstrations, and broad environment sampling to teach coordination and improve policy robustness.These techniques are respectively called Convention Learning, Imitation Learning, and Episode Randomization.

1) Convention Learning:

PRIMAL2 teaches decentralized agents corridor conventions and supplements reinforcement learning with centralized-planner demonstrations. These aids target deadlock avoidance, coordinated movement, and higher-quality paths in constrained environments.

  • Convention Learning: Agents improve corridor navigation by following shared conventions that break symmetries, including avoiding entry against opposing traffic and avoiding abrupt reversals.Abrupt reversal is permitted when a deadlock exists; otherwise it is generally non-optimal.
  • Convention Learning: Pure policy gradients struggle to learn these conventions because agents tend toward selfish policies and rewards do not effectively reinforce them.
  • Convention Learning: The supervised validity loss teaches agents to avoid convention-violating actions, producing a near-perfect valid rate of > 99.5%.Valid rate measures the fraction of selected actions that are valid.
  • Imitation Learning: Imitation learning uses centralized near-optimal planners to instill coordination behavior that decentralized reinforcement learning finds difficult to acquire.The training maintains an RL-to-IL episode ratio close to 50%.
  • Imitation Learning: Expert demonstrations come from ODrM* with inflation ε = 2 and train the policy using behavior cloning.
  • Imitation Learning: For LMAPF training, ODrM* combines multiple one-shot instances and is called whenever at least one agent reaches its goal and replanning is required.

3) Environment Randomization:

Training randomizes world geometry and agent configurations to expose PRIMAL2 to diverse navigation and coordination conditions. Distributed reinforcement and imitation learning accelerates policy training through parallel workers.

  • Environment Randomization: World size, obstacle density, and typical corridor length are uniformly randomized at each episode’s start.World sizes range from 10 to 70, obstacle densities from 20% to 70%, and corridor lengths from 3 to 21.
  • Environment Randomization: Agent, obstacle, and goal positions are randomized while ensuring every agent can reach its goal and narrow corridors initially contain at most one agent.Goals are at least 2 cells from their agents in practice.
  • Training Setup: Training uses γ = 0.95 and 256-step episodes, while imitation-learning episodes last 64 steps because repeated ODrM* calls are costly.Updates occur at episode end and when an agent reaches its goal.
  • Distributed Training: Ray distributes learning across nine asynchronous nodes, with four computing imitation-learning gradients and five running pure reinforcement-learning episodes.Each node contains an LMAPF environment with eight learning agents and sends gradients to a master node.
  • Distributed Training: Training lasts around 10 hours and converges within 35k episodes, nearly 10x fewer episodes and 24x shorter training time than the previous work.

VI. RESULTS

The evaluation compares PRIMAL2 with centralized and decentralized planners across systematically varied team sizes and structured environments. PRIMAL2 surpasses centralized planners at larger scales, improves over PRIMAL, and retains a limitation in path quality and looping behavior.

  • Evaluation Setup: Experiments vary team sizes, world sizes, densities, and corridor lengths, averaging 50 tests per feasible parameter combination.All planners encounter identical scenarios, with makespan and success rate as primary metrics.
  • One-Shot MAPF Results: PRIMAL2 outperforms centralized planners when team sizes exceed 128 agents, after centralized performance drops sharply with joint-space growth.For smaller teams, centralized planners slightly outperform PRIMAL2 under the standard 100% success metric.
  • One-Shot MAPF Results: PRIMAL2 outperforms PRIMAL in both moderate and large team sizes.
  • Limitations: A few agents often enter undesirable loops, causing the 100% success rate to decline with team size while the 95% metric remains nearly constant.The authors identify centralized correction of this behavior as future work.
  • Plan Quality: PRIMAL2 trajectories are 25%-50% longer than ODrM* for teams up to 32 agents and 75%-125% longer for teams between 64 and 256 agents.ODrM* cannot generate solutions for 512 agents and above, preventing path-suboptimality estimates at the largest scales.

B. LMAPF Results

PRIMAL2 provides fast decentralized replanning for LMAPF and remains effective as teams and environments become larger and more constrained. Windowed-PBS can achieve higher throughput in some settings, but PRIMAL2 scales further with substantially lower planning time, while learned conventions improve large-team performance.

  • Evaluation setup: LMAPF evaluates planners by throughput while requiring frequent online replanning as agents receive new goals.The experiments use a 60-second timeout for each replanning instance.
  • Planner comparison: Windowed-PBS marginally outperforms PRIMAL2 in many scenarios up to 512 agents, but its replanning times exceed PRIMAL2’s by well over an order of magnitude for moderate and large teams.Windowed-PBS also begins timing out in some 1024-agent episodes, whereas PRIMAL2 generally replans in under a second in a decentralized manner.
  • Planner comparison: PRIMAL2 outperforms PRIMAL in larger teams and constrained worlds with long corridors, despite equivalent performance in low-density worlds with short corridors.The reported improvement is attributed to the additional coordination-learning techniques introduced in PRIMAL2.
  • MovingAI benchmarks: On MovingAI maze and warehouse benchmarks, centralized planners often lead for small and moderate teams, but windowed-PBS times out at large team sizes while PRIMAL2 remains adequate at 2048 agents.In warehouse maps, PRIMAL2 performs on par with windowed-PBS and ODrM* for small teams, while windowed-PBS performs better for moderate teams.
  • Ablation study: PRIMAL2 surpasses variants without convention learning by around 10% for larger teams, whereas the three planners perform near-identically up to 64 agents.The comparison includes a second variant that also removes corridor-information channels from the observation.

VII. CONCLUSION

PRIMAL2 is a distributed reinforcement-learning framework for lifelong MAPF in highly constrained worlds, using decentralized online planning and learned conventions for implicit coordination. It achieves effective throughput comparable to centralized planners while scaling to 2048 agents, and the authors identify several directions for improving coordination further.

  • VII. CONCLUSION: PRIMAL2 uses wholly decentralized online path planning based on local information and learned conventions for coordinated joint maneuvers.The conventions break movement symmetries and organize agent behavior without explicit communication.
  • VII. CONCLUSION: PRIMAL2 scales to 2048 agents while producing throughput comparable to centralized planners in both one-shot MAPF and LMAPF.The conclusion reports successful online path planning for both problem settings.
  • VII. CONCLUSION: Future work targets stronger implicit coordination through recurrent architectures, systematic RL-to-IL ratio studies, and recent off-policy learning methods.
Loading 2010.08184v3…