A tutorial at AAAI 2019, Monday, January 28, 2019, Honolulu, USA (Location: South Pacific 1, 8:30 – 12:30)

Multi-Agent Pathfinding: Models, Solvers, and Systems

by Roman Barták, Philipp Obermeier, Torsten Schaub, Tran Cao Son, 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.

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

Some links:
- Multi-Agent Path Finding tutorial at AAMAS 2018 [web]
- ASPRILO system [web]

  

Tutorial Syllabus:

  • 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
  • Demos
    • MAPF Scenario (MAPF for Ozobots)
    • ASPRILO system (an abstract benchmark environment for robotic intra-logistics)
  • Open challenges, conclusion, discussion

 

 

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. obermeier Philipp Obermeier is a doctoral student in the Knowledge-Based Systems group at the University of Potsdam, Germany. His scientific interests are centered around Answer Set Programming (ASP) and declarative languages for dynamic domains. schaub Torsten Schaub is a professor at the University of Potsdam, Germany. His current research focus lies on Answer set programming and materializes at potassco.org, the home of the open source project Potassco bundling software for Answer Set Programming.
 
tran
 Tran Cao Son is a full Professor at New Mexico State University, USA. His main research interests are centered around theoretical issues and practical applications of knowledge representation and reasoning such as aggregates in answer set programming, planning with preferences and incomplete information, multi-agent systems, and reasoning about actions and changes

 

 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.