Center for Advanced Intelligence Project

Mr. Pavel Surynek (Czech Technical University): SAT-based Multi-Agent Path Finding

Abstract:
Multi-agent Path Finding (MAPF) became an area of growing research interest.
At the core of this research area, numerous diverse techniques were developed
in the past 10 years for optimally solving MAPF under various objectives such
as the sum-of-costs. One of the major streams of development are optimal
solving algorithms based on the reduction to propositional satisfiability (SAT).
In this talk I will survey these techniques, while putting them into the wider
context of the MAPF research. I will also provide theoretical and experimental
comparisons that show pros and cons of the SAT-based approach in contrast to
other search-based techniques. The talk is addressed to the general computer
science audience. No prior knowledge is needed.

Bio:
Pavel Surynek is an associate professor at the Faculty of Information Technology, Czech
Technical University in Prague. He obtained his Ph.D. (2008) and M.Sc. (2004) in artificial
intelligence and theoretical computer science at Charles University in Prague. Prior to joining the
Czech Technical University he held the position of research scientist at AIST in Tokyo, the
assistant professor position at Charles University, and the position of JSPS fellow at
Kobe University. His research interests include multi-agent path finding (MAPF), satisfiability
(SAT), and heuristic search.