Compilation approaches to multi-agent path finding

Abstract

Multi-agent path finding (MAPF) deals with the problems of moving a set of agents from their origins to their destinations in a (directed or undirected) graph. A more widely studied group of problems, frequently called cooperative path finding (CPF), requires agents not to use the same arc and the same vertex at the same time. This talk is about much less studied problem of multiple-origin-multiple-destination (MOMD) path finding, where the agents are required to share as many arcs as possible in their paths.

The objective of MOMD is minimising the sum of costs of used arcs. We will present declarative models for the MOMD problem that can be compiled to SAT or to MIP to solve the problem. In the second part we will discuss how the declarative model can be modified to solve the CPF problem. The models are implemented in a novel declarative programming language Picat.