mapf.info

webmaster: Sven Koenig

Learn all about Multi-Agent Path Finding (MAPF)

AAAI-22 Tutorial on Recent Advances in Multi-Agent Path Finding

by Jiaoyang Li, Daniel Harabor, Sven Koenig and Ariel Felner

Tutorial Description:

Navigating a team of agents through a shared environment is an important problem for many existing and emerging application areas. Examples include warehouse logistics, mail sortation, autonomous intersection management, and the coordination of drone swarms. In each of these settings, practitioners must tackle a challenging combinatorial problem known as Multi-Agent Path Finding (MAPF). Studies on this topic appear often in the literature of Artificial Intelligence and in the proceedings of flagship conferences, such as AAAI. These works are also of interest to researchers in adjacent areas, such as Robotics and Discrete Optimisation.

In this tutorial, we propose to overview the core MAPF problem and to summarise recent progress in this fast-moving research area. Our objective is to give a holistic perspective that covers theoretical foundations as well as practical algorithms: for planning, execution, and handling a variety of operational issues that commonly arise in practice. Our target audience is anyone interested in planning for and coordination of multiple agents. The tutorial will particularly benefit people who are interested in MAPF and its many applications.

Tutorial Syllabus:

  1. MAPF Overview (slides)
    • Overview of multi-agent coordination and planning applications
    • The underlying MAPF problem
    • Complexity results for MAPF in different scenarios
    • Issues that arise when applying MAPF in practice
  2. Planning (slides-part-1, slides-part-2)
    • Approaches for finding optimal, bounded-suboptimal, and unbounded-suboptimal MAPF plans
    • Joint-space planning A* and its improvements
    • Decomposition with conflict-based search
    • Constraints for conflict resolution
    • Heuristics for node section
  3. Execution (slides)
    • Considering the kinematics of agents
    • Dealing with failures during the planning phase
    • Dealing with failures during the execution phase
  4. Scalability (slides-part-1, slides-part-2)
    • Trade-off between scalability and solution quality
    • Bounded-suboptimal algorithms
    • Rule-based algorithms
    • Large neighborhood search
  5. Summary and Opportunities (slides)

Authors:

Jiaoyang Li is a Ph.D. student in computer science at the University of Southern California. She received a Bachelor’s degree in automation from Tsinghua University in 2017. Her research focuses on developing efficient planning algorithms for large-scale multi-agent coordination problems. See more information about her at https://jiaoyangli.me/.

Daniel Harabor is a Senior Lecturer at Monash University. His research interests include single and multi-agent pathfinding, with applications for games and robotics. For more information please visit https://harabor.net/daniel.

Sven Koenig is a professor of computer science at the University of Southern California. Most of his research centers around planning techniques for single agents (such as robots) and multi-agent systems. Additional information on him can be found at http://idm-lab.org.

Ariel Felner is a professor of computer science at Ben-Gurion University, Israel. He is interested in all aspects of Heuristic Search: Algorithms, Heuristics and Applications. Multi-agent pathfinding has been at the core of his research for more than a decade. Additional information on him can be found at https://felner.wixsite.com/home.


(last updated in 2022)