Charles Explorer logo
🇬🇧

Scheduling Models for Multi-Agent Path Finding

Publication at Faculty of Mathematics and Physics |
2017

Abstract

Multi-agent path finding (MAPF) deals with the problem of finding a colli- sion 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.