Time Optimal Multi-Agent Path Planning on Graphs

For the problem of moving a set of agents on a connected graphto agent-specific goal locations, free of collisions, we propose a multiflow based integer linear programming (ILP) model that finds a time optimal solution. The resulting algorithm from our ILP model is complete and guarantees to yield true optimal solutions. Focusing on the time optimal formulation, we evaluate its performance, both as a stand alone algorithm and as a generic heuristic for quickly solving large problem instances. The computational results confirm the effectiveness of our method.