A fundamental task when designing physical multi-agent systems is pathfinding: how to move the agents from one location to another safely. While pathfinding for a single agent can be solved optimally in polynomial time, pathfinding for multiple agents is significantly more difficult. Nevertheless, recent years have shown tremendous progress in solving this problem in practice using a range of techniques following different algorithmic approaches.
In this tutorial we will cover existing approaches for solving the multi-agent pathfinding problem (MAPF), discuss the pros and cons of each approach, and outline current challenges and opportunities in the field. We will also give demo of systems for MAPF and robotic intra-logistics.
The target audience is anyone interested in planning for multiple agents. The attendees will walk away with information about the state-of-the-art in MAPF. The prerequisite knowledge for this tutorial is basic knowledge of heuristic search (best-first search, A*), SAT, and constraint satisfaction (all at the level of graduate AI course).
Multi-Agent Path Finding tutorial at AAMAS 2018 [web]
ASPRILO system [web]
- Introduction to Multi-agent pathfinding (MAPF)
- Problem formulation, variants, objectives
- Application areas
- Search-based solvers
- Incomplete solvers
- Complete but suboptimal solvers
- Optimal solvers
- Reduction-based solvers
- SAT encodings of MAPF
- CP encoding of MAPF
- MAPF Scenario (MAPF for Ozobots)
- ASPRILO system (an abstract benchmark environment for robotic intra-logistics)
- Open challenges, conclusion, discussion