PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning

Abstract

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.

\c{opyright} 20XX IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works

References in corpus (6)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• Prioritized Experience Replay
• Learning to Communicate with Deep Multi-Agent Reinforcement Learning
• Leveraging Demonstrations for Deep Reinforcement Learning on Robotics Problems with Sparse Rewards
• Counterfactual Multi-Agent Policy Gradients
• Reinforcement Learning from Imperfect Demonstrations

Cited by in corpus (34)

• PRIMAL2: Pathfinding via Reinforcement and Imitation Multi-Agent Learning -- Lifelong
• Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding
• CL-MAPF: Multi-Agent Path Finding for Car-Like Robots with Kinematic and Spatiotemporal Constraints
• GLAS: Global-to-Local Safe Autonomy Synthesis for Multi-Robot Motion Planning with End-to-End Learning
• Collaborative Target Search with a Visual Drone Swarm: An Adaptive Curriculum Embedded Multistage Reinforcement Learning Approach
• Learning Team-Based Navigation: A Review of Deep Reinforcement Learning Techniques for Multi-Agent Pathfinding
• SACHA: Soft Actor-Critic with Heuristic-Based Attention for Partially Observable Multi-Agent Path Finding
• Graph-Based Multi-Robot Path Finding and Planning
• NavFormer: A Transformer Architecture for Robot Target-Driven Navigation in Unknown and Dynamic Environments
• DeepRacer: Educational Autonomous Racing Platform for Experimentation with Sim2Real Reinforcement Learning
• Learning Connectivity-Maximizing Network Configurations
• Flatland-RL : Multi-Agent Reinforcement Learning on Trains
• MAPPER: Multi-Agent Path Planning with Evolutionary Reinforcement Learning in Mixed Dynamic Environments
• An Energy-Optimal Framework for Assignment and Trajectory Generation in Teams of Autonomous Agents
• Adaptive Target Localization under Uncertainty using Multi-Agent Deep Reinforcement Learning with Knowledge Transfer
• Blockchain-assisted Demonstration Cloning for Multi-Agent Deep Reinforcement Learning
• Distributed Heuristic Multi-Agent Path Finding with Communication
• Optimizing Crowd-Aware Multi-Agent Path Finding through Local Communication with Graph Neural Networks
• Multi Agent Navigation in Unconstrained Environments using a Centralized Attention based Graphical Neural Network Controller
• Learning to Resolve Conflicts for Multi-Agent Path Finding with Conflict-Based Search
• Multi-agent navigation based on deep reinforcement learning and traditional pathfinding algorithm
• Learning to Plan Optimally with Flow-based Motion Planner
• Parallelised Diffeomorphic Sampling-based Motion Planning
• SIGMA: Sheaf-Informed Geometric Multi-Agent Pathfinding
• Rapidly-exploring Random Forest: Adaptively Exploits Local Structure with Generalised Multi-Trees Motion Planning
• Subdimensional Expansion Using Attention-Based Learning For Multi-Agent Path Finding
• Rapid Replanning in Consecutive Pick-and-Place Tasks with Lazy Experience Graph
• Expected $1.x$-Makespan-Optimal MAPF on Grids in Low-Poly Time
• Topological Navigation Graph Framework
• MA-DV2F: A Multi-Agent Navigation Framework using Dynamic Velocity Vector Field
• AB-Mapper: Attention and BicNet Based Multi-agent Path Finding for Dynamic Crowded Environment
• PC2P: Multi-Agent Path Finding via Personalized-Enhanced Communication and Crowd Perception
• MORPH: Self-Organising Multi-Robot Task Allocation via Neuroplasticity-Inspired Adaptive Topology
• Combining Propositional Logic Based Decision Diagrams with Decision Making in Urban Systems