Multi-agent Path Finding: Algorithmic and Learning-based Solutions

Authors

Yakovlev K.

Annotation

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. The Multi-Agent Path Finding (MAPF) formalism provides a fundamental abstraction for this problem, enabling the development of algorithms with strong theoretical guarantees. Heuristic search has been highly successful in this domain, producing optimal or bounded-suboptimal solutions with proven guarantees. Rule-based solvers and optimization techniques have also proven to be effective tools to tackle MAPF by providing high-quality solutions within a much lower computational budget. Still, most of the modern search-based and rule-based MAPF solvers intrinsically assume that the multi-agent system is controlled in a centralized fashion and it is not trivial to adapt them to real-world constraints like partial observability and limited communication. This is where ML-based approaches may come on stage and overcome the limitations of conventional planning-based methods. This talk explores how heuristic search may be integrated with machine learning (i.e. deep reinforcement learning, imitation learning, transformers, large-scale learning) to create new generation of (decentralized) MAPF solvers.