webmaster: Sven Koenig

Learn all about Multi-Agent Path Finding (MAPF)


Pavel Surynek. Sum of Costs Optimal Multi-Agent Path Finding with Continuous Time via Satisfiability Modulo Theories. In Proceedings of the International Symposium on Combinatorial Search (SoCS), pages 200-202, 2021.

Abstract: Multi-agent path finding with continuous movements and time (denoted MAPFR) is addressed. The task is to navigate agents that move smoothly between predefined positions to their individual goals so that they do not collide. Recently a novel solving approach for obtaining makespan optimal so- lutions called SMT-CCBS based on satisfiability modulo theories (SMT) has been introduced. We extend the approach further towards the sum-of-costs objective which is a more challenging case in the yes/no SMT environment due to more complex calculation of the objective.

Download the paper in pdf.

(last updated in 2022)