A tutorial at AAMAS 2018, July 10, 2018, Stockholm, Sweden (Location: K23, 8:30 – 12:30)

Multi-Agent Pathfinding

by Roman Barták and Roni Stern

Tutorial Description:

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. While the problem is NP hard, modern multi-agent pathfinding algorithms can find optimal paths for more than 100 agents in less than 5 minutes. This is in contrast to the more general multi-agent planning problem, which can rarely be solved optimally for more than 10 agents. In this tutorial we will cover existing approaches for solving the multi-agent pathfinding problem, 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 prerequisite knowledge for this tutorial is basic knowledge of heuristic search (best-first search, A*). .

  

Tutorial Syllabus:

  • Introduction to Multi-agent pathfinding (MAPF)
    • Problem variants
    • Objective functions
    • Applications.
  • Search-based solvers
    • Incomplete solvers
    • Complete but suboptimal solvers
    • Optimal solvers
  • Reduction-based solvers
    • SAT encodings of MAPF
    • CP encodings of MAPF
  • From Planning to execution
    • The gap between planning and execution in MAPF
    • Current approaches
  • Open challenges and conclusion

 

 

About the Authors

roman
 Roman Barták works as a full professor and a researcher at Charles University, Prague (Czech Republic), where he leads Constraint Satisfaction and Optimization Research Group. His research work focuses on techniques of constraint satisfaction and modeling and their application to planning, scheduling, and other areas.
roni

Roni Stern is a senior lecturer in the department of Software and Information Systems Engineering at Ben Gurion University (Israel). His main research interests are heuristic search, automated diagnosis, single and multi-agent automated planning. He is also interested in applications of AI to health care. He is also serving as the current president of SoCS.