Source-linked AI summary
PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning
Guillaume Sartoretti, Justin Kerr, Yunfei Shi, Glenn Wagner, T. K. Satish Kumar, Sven Koenig, Howie Choset
TL;DR
Large-scale MAPF remains difficult because centralized planners scale poorly as robot teams grow, while real deployments require online planning under uncertainty. PRIMAL combines reinforcement learning with expert imitation to train decentralized, partially observable policies, achieving near-perfect success for teams up to 1024 agents in a large obstacle-free world and supporting hybrid factory-robot experiments.
Problem
MAPF planners face growing coordination complexity and poor scalability beyond a few hundred agents, despite requirements for large-scale robot deployment.
Method
PRIMAL combines distributed reinforcement learning and imitation learning from the centralized ODrM* planner to train decentralized policies using local information without explicit communication.
Results
PRIMAL can handle teams up to 1024 agents with a near-perfect success rate in a 160 × 160 world without obstacles, and was demonstrated with physical and simulated factory robots.
Takeaways & Limitations
The learned policy scales across team sizes and world dimensions while enabling online decentralized path planning from local information.
Abstract
from arXiv · showhide
Multi-agent path finding (MAPF) is an essential component of many large-scale, real-world robot deployments, from aerial swarms to warehouse automation. However, despite the community's continued efforts, most state-of-the-art MAPF planners still rely on centralized planning and scale poorly past a few hundred agents. Such planning approaches are maladapted to real-world deployments, where noise and uncertainty often require paths be recomputed online, which is impossible when planning times are in seconds to minutes. We present PRIMAL, a novel framework for MAPF that combines reinforcement and imitation learning to teach fully-decentralized policies, where agents reactively plan paths online in a partially-observable world while exhibiting implicit coordination. This framework extends our previous work on distributed learning of collaborative policies by introducing demonstrations of an expert MAPF planner during training, as well as careful reward shaping and environment sampling. Once learned, the resulting policy can be copied onto any number of agents and naturally scales to different team sizes and world dimensions. We present results on randomized worlds with up to 1024 agents and compare success rates against state-of-the-art MAPF planners. Finally, we experimentally validate the learned policies in a hybrid simulation of a factory mockup, involving both real-world and simulated robots.
I. INTRODUCTION
MAPF must coordinate increasingly large robot teams despite rapidly growing planning complexity. PRIMAL addresses this challenge with decentralized, partially observable policies that combine reinforcement and imitation learning.
- Motivation: MAPF planning becomes more difficult as robot deployments grow to thousands of agents, while optimal planners currently handle only several hundred.Coupled planners face exponential growth in planning complexity, motivating decoupled and dynamically coupled alternatives.
- Motivation: Reactive planners can produce deadlocks and livelocks in environments with narrow features.These failures arise in factory-like settings where many agents must compute collision-free paths.
- Approach: PRIMAL combines reinforcement learning with imitation learning from an expert centralized MAPF planner to train decentralized policies.Agents learn a common policy that plans online from local observations without explicit communication.
- Approach: The learned policy supports implicit coordination in partially observable worlds and can be copied onto any number of agents.Dynamically coupled planners instead expand their search spaces only as necessary during planning.
- Evaluation: The paper evaluates PRIMAL across varying team sizes, world sizes, and obstacle densities against state-of-the-art MAPF planners.The paper also reports an experimental scenario involving physical and simulated robots in a factory mockup.
B. Multi-Agent Reinforcement Learning (MARL)
Decentralized multi-agent learning must avoid combinatorial state-action growth and coordinate agents without relying on full observability or explicit communication. PRIMAL uses expert imitation, reward design, and challenge sampling to learn cooperative local policies.
- Challenges: Joint multi-agent learning suffers from combinatorial state-action growth that can require impractical amounts of training data.Decentralized policies address this scaling issue but must still incorporate cooperation during training.
- Challenges: Many existing approaches use centralized learning or explicit communication, whereas prior work learned a common policy without communication under full observability.Predicting other agents’ actions also tends to scale poorly as team size increases.
- PRIMAL: PRIMAL uses imitation learning from the centralized ODrM* planner to teach coordination without explicit communication in a partially observable world.The resulting policy executes from locally gathered information and is described as robust to agent failures or additions.
- PRIMAL: The framework combines this imitation strategy with a carefully crafted reward structure and sampled training challenges.These design choices target cooperative behavior while retaining decentralized execution.
III. POLICY REPRESENTATION
PRIMAL represents each agent’s policy for a partially observable gridworld using local spatial channels plus persistent goal information. Agents choose discrete movement actions, with training and testing procedures handling invalid moves explicitly.
- Observation Space: Each agent observes a limited 10 × 10 field of view centered on itself in a partially observable discrete gridworld.The fixed field of view reduces neural-network input size and can support generalization across world sizes.
- Observation Space: Agents always receive a unit vector toward their goal and its Euclidean distance, even when the goal lies outside the field of view.This supplements the local spatial observation with persistent goal information.
- Observation Space: Observations encode obstacles, other agents, the agent’s goal when visible, and observable agents’ goals in separate binary channels.Obstacles are added outside world boundaries when agents are near an edge.
- Action Space: The action space contains four cardinal moves and staying still, while training samples only valid actions and adds a validity-learning loss.The authors report more stable training than using negative rewards for invalid moves.
- Action Space: During testing, an invalid action becomes a stay-still action, and fully trained agents rarely select invalid moves.This behavior indicates that the policy learns the valid action set for each state.
C. Reward Structure
The reward structure combines goal-directed incentives, collision penalties, exploration support, and auxiliary training losses to guide stable cooperative learning.
- Reward design: Agents are penalized for each timestep they are not resting on goal, encouraging rapid goal attainment.Staying still is penalized slightly more than moving to encourage exploration.
- Reward design: Collisions receive a −2 reward, while completing an episode when all agents reach their goals simultaneously receives +20.Actions are filtered for validity during training, but simultaneous moves can still produce collisions.
- Policy representation: The policy network maps local observations and goal information to actions using convolutional processing and recurrent memory.The network includes convolutional layers, max-pooling, and an LSTM.
- Training losses: Value learning uses discounted returns, while policy learning bootstraps an advantage estimate and adds entropy regularization.The entropy weight is σH = 0.01 in practice.
- Training losses: Auxiliary blocking and invalid-move losses help guide and stabilize training.The blocking output predicts whether an agent is blocking others, and the validity loss discourages selecting invalid moves.
IV. LEARNING
The framework learns MAPF policies through distributed reinforcement learning augmented with imitation learning from expert demonstrations.
- Learning framework: PRIMAL adds an imitation-learning module so agents can learn from demonstrations of an expert MAPF planner.The reinforcement-learning component builds on prior distributed learning for multiple agents in shared environments.
- Learning framework: The resulting training framework targets implicit coordination among decentralized agents.Agents learn behaviors through the combined reinforcement- and imitation-learning setup.
- Learning framework: The learning process is distributed across agents operating in shared environments.This preserves the framework’s decentralized training orientation.
A. Coordination Learning
Coordination learning addresses selfish decentralized behavior by combining a blocking penalty, expert demonstrations, and targeted training environments.
- Coordination challenge: Selfish policies can leave agents on their goals while blocking other agents from reaching theirs.This failure is especially problematic in dense environments with many narrow passages.
- Coordination challenge: Limited fields of view and large environments invalidate several existing techniques for addressing multi-agent selfishness.Credit assignment can be confusing when agents cannot observe the source of a penalty.
- Coordination approach: The framework uses a blocking penalty, expert demonstrations, and tailored random environments exposing agents to difficult cluttered scenarios.The authors report that omitting any of the three methods causes unstable learning or a worse policy.
1) Blocking Penalty:
The blocking mechanism penalizes agents that obstruct others and combines this reward signal with expert-guided hybrid training.
- Blocking Penalty: Agents receive a sharp penalty of −2 for staying on goal while preventing another agent from reaching its goal.The penalty encourages agents to leave goals when remaining there obstructs team progress.
- Blocking Penalty: An agent is classified as blocking when removing another agent shortens its A∗ path by more than 10 steps.The blocking output predicts this condition to explain the additional penalty during training.
- Combining RL and IL: Each episode is randomly assigned to reinforcement-learning or imitation-learning training.Expert demonstrations are generated dynamically using a centralized planner.
- Combining RL and IL: The expert planner coordinates agents during imitation learning, providing demonstrations of coordinated behavior.The agents learn to imitate the centralized planner while retaining individual policy copies with shared weights.
- Combining RL and IL: Without demonstrations, learning is slower and converges to a significantly worse solution.Changing the imitation-learning proportion between 10% and 50% had little observed effect on trained-policy performance.
3) Environment Sampling:
Training environments are sampled to expose agents more often to situations requiring coordination. The sampling favors smaller, denser worlds because uniform sampling produces too few agent-agent interactions.
- Environment sizes and obstacle densities are randomized at the start of each episode.Uniform sampling was found insufficient for exposing coordination-relevant situations.
- Smaller, denser environments force more frequent agent-agent interactions during training.The sampling distribution favors these environments to encourage collaborative behavior.
B. Training Details
PRIMAL is evaluated against centralized and decoupled MAPF planners across varied world sizes, obstacle densities, and team sizes. Its performance is strongest in sparse environments and can degrade in dense or larger settings, while training components improve convergence.
- PRIMAL is compared with CBS, ODrM*, and ORCA across world sizes from 10 to 160 and teams from 4 to 1024 agents.The comparison varies obstacle density from 0 to 0.3, while PRIMAL uses only partial observability.
- Removing environment sampling, blocking penalties, or imitation learning causes convergence to a worse solution or unstable learning.The complete training procedure includes all three methods.
- PRIMAL performs extremely well at low obstacle densities but is easily outperformed in dense environments requiring joint actions.Dense cases may require drastic path changes that decentralized reactive behavior does not handle as well.
- PRIMAL paths are sometimes more than twice as long as those of other planners, partly because the planners permit movements excluded by PRIMAL’s MAPF definition.PRIMAL’s agents generally reach their goals effectively except for a few laggards.
- In a 160 × 160 obstacle-free world, PRIMAL handles teams up to 1024 agents with a near-perfect success rate.Centralized planners struggle as the joint configuration space grows with team size.
- PRIMAL remains above 60% success for 512 agents in a medium-sized, low-density world, while the other planners perform poorly.Its success rate begins decreasing earlier than that of the other planners in this scenario.
B. Experimental Validation
Experimental validation combines simulated and physical robots in a factory mockup and compares planner success across three obstacle scenarios. PRIMAL performs best in obstacle-free settings, slightly better in low-density settings, and worse in dense settings.
- The factory mockup includes two physical robots operating alongside two, then three, simulated robots.All robots plan their next actions online using the decentralized approach.
- Fig. 6 compares planner success rates in obstacle-free, low-obstacle-density, and high-obstacle-density scenarios.PRIMAL outperforms all planners in the obstacle-free world, slightly outperforms them in low-density worlds, and is strongly outperformed in dense worlds.
- Fig. 7 shows overhead and side views of the mockup alongside obstacles, robots, goals, and current moves.Obstacles are black solids, robots blue circles, goals blue squares, and current moves green squares.
- Planning time per step and per agent is below 0.1s on a standard GPU and below 0.2s on a CPU.The hybrid deployment demonstrates online operation in the factory mockup.
VI. CONCLUSION
PRIMAL combines distributed reinforcement learning with imitation learning from a centralized expert while giving agents only local information. Experiments show scalability across team and world sizes, strong performance in low-density settings, and deployment with physical and simulated robots, while factory-like structured environments remain future work.
- PRIMAL combines distributed reinforcement learning and imitation learning from a centralized expert planner.
- PRIMAL scales across team sizes, world sizes, and obstacle densities despite giving agents only local information about the world.
- In low obstacle-density environments, PRIMAL matches or outperforms state-of-the-art MAPF planners that access the whole system state.
- A factory mockup deployment with physical and simulated robots demonstrates an online, local-information-based decentralized MAPF approach.
- Future work targets factory-like environments containing sparse regions and highly structured areas such as corridors and aisles.