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

Abstract

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.

arXiv comment\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 (5)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning
• Deep Q-learning from Demonstrations
• Reinforcement and Imitation Learning for Diverse Visuomotor Skills
• Flatland-RL : Multi-Agent Reinforcement Learning on Trains

Cited by in corpus (17)

• Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding
• 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
• Graph-Based Multi-Robot Path Finding and Planning
• Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities
• Multi-Robot Coordination and Layout Design for Automated Warehousing
• UAV-assisted Internet of Vehicles: A Framework Empowered by Reinforcement Learning and Blockchain
• Blockchain-based Crowdsourced Deep Reinforcement Learning as a Service
• Adaptive Target Localization under Uncertainty using Multi-Agent Deep Reinforcement Learning with Knowledge Transfer
• Flatland Competition 2020: MAPF and MARL for Efficient Train Coordination on a Grid World
• Blockchain-assisted Demonstration Cloning for Multi-Agent Deep Reinforcement Learning
• Optimizing Crowd-Aware Multi-Agent Path Finding through Local Communication with Graph Neural Networks
• SIGMA: Sheaf-Informed Geometric Multi-Agent Pathfinding
• Expected $1.x$-Makespan-Optimal MAPF on Grids in Low-Poly Time
• Reinforcement Learning Aided Sequential Optimization for Unsignalized Intersection Management of Robot Traffic
• Destination-to-Chutes Task Mapping Optimization for Multi-Robot Coordination in Robotic Sorting Systems
• A traffic management system for large and heterogeneous vehicles in narrow industrial environments