Publication

R. Bartak, J. Svancara and M. Vlk. Scheduling Models for Multi-Agent Path Finding. In Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), pages 189-200, 2017.

Abstract: Multi-agent path finding (MAPF) deals with the problem of finding a collision free path for a set of agents. The agents are located at nodes of a directed graph, they can move over the arcs, and each agent has its own destination node. It is not possible for two agents to be at the same node at the same time. This paper suggests to model the MAPF problem using scheduling techniques, namely, nodes are seen as unary resources. We present three models of the problem. One model is motivated by network flows, another model uses classical unary resource constraints together with path constraints, and the last model works with optional activities. We compare the efficiency of models experimentally.

Download the paper in pdf.