Tutorials

Abstract: A fundamental task when designing physical (robots) or virtual (games) 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.

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).

Outline of the structure:

Part I: Introduction to Multi-agent pathfinding (MAPF)

     - Problem formulation, variants, objectives

Part II: Search-based solvers

     - Incomplete solvers

     - Optimal solvers

Part III: Reduction-based solvers

     - SAT encodings of MAPF

     - CP encodings of MAPF

Part IV: Beyond classical MAPF

     - MAPF on robots

     - On-line problems

Part V: Open challenges, conclusion, discussion

Biography: Roman Barták is a professor of Computer Science at Charles University (Prague). He coordinates the graduate program Artificial Intelligence and doctoral program Theoretical Computer Science and Artificial Intelligence. His research area is Artificial Intelligence, in particular automated planning and scheduling, constraint satisfaction, and knowledge representation. He is actively doing research in the area of multi-agent path finding (https://dblp.uni-trier.de/pid/04/5344.html). He is an EurAI Fellow, and a senior member of AAAI and ACM.

Roman Barták is teaching university courses at Charles University, Prague for more than 20 years (http://ktiml.mff.cuni.cz/~bartak/_new_web/teaching-courses.html).

He gave many tutorials at summer schools, including ESSLLI, NASLLI, and ESSAI, and at international conferences such as IJCAI, AAAI, AAMAS, and ICAPS (http://ktiml.mff.cuni.cz/~bartak/_new_web/teaching-tutorials.html). Videos from recent tutorials are available at the above web.