Multi-Robot Path Planning: Heuristic Search Meets Reinforcement Learning

Abstract

Coordinating a team of mobile robots that simultaneously move and accomplish tasks in a shared environment (e.g., wheeled robots in a warehouse, driverless cars in a parking lot, etc.) is a challenging problem that comes in different flavors. One of the most widely studied abstractions of this problem is known as Multi-Agent Path Finding (MAPF), which adopts several simplifying assumptions regarding how the agents move, communicate, and observe the environment. Heuristic search is a widely used technique to obtain high-quality MAPF solutions (i.e., optimal or bounded-optimal solutions). Nowadays, numerous search-based MAPF solvers exist that provide strong theoretical guarantees on the completeness and optimality of the resultant solutions. However, they often need to scale better with the number of agents. To mitigate this issue and to lift several other restrictions typically adopted by conventional search-based MAPF solvers, decentralized, learning-based approaches to MAPF recently came on stage. They utilize the power of modern deep learning, reinforcement learning, imitation learning, etc., to obtain decision-making policies that do not require a centralized controller, work well under partial observability and limited communication, and thus can be more suited to large-scale real-world robotic applications despite the lack of strong theoretical guarantees.In this tutorial, we propose to overview the core problem of multi-robot pathfinding and summarize recent progress in learning-based and hybrid solvers. Our objective is to give a holistic perspective covering theoretical background, practical algorithms, and software tools needed to create modern learnable MAPF solvers. Our target audience is anyone interested in coordinating multiple mobile robots. As the tutorial involves demo sessions with (some) coding in Python, basic knowledge of this language is beneficial.