Learn all about Multi-Agent Path Finding (MAPF)
P. Surynek, S. Kumar and S. Koenig. Multi-Agent Path Finding with Capacity Constraints. In Proceedings of the Advances in Artificial Intelligence - International Conference of the Italian Association for Artificial Intelligence (AI*IA), pages 235-249, 2019.
Abstract: In multi-agent path finding (MAPF), the task is to navigate agents from their starting positions to given individual goals. The problem takes place on an undirected graph whose vertices represent positions and whose edges define the topology. Agents can move along edges to neighboring vertices. In standard MAPF, the occupation of space by agents is modeled by a capacity constraint that permits at most one agent per vertex. We suggest an extension of MAPF in this paper that permits more than one agent per vertex. Propositional satisfiability (SAT) models for this extension of MAPF are studied. We focus on modeling capacity constraints in SAT-based formulations of MAPF and evaluation of the performance of these models. We extend two existing SAT-based formulations with vertex capacity constraints: MDD-SAT and SMT-CBS, where the former is an approach that builds the model in an eager way while the latter relies on the lazy construction of the model.