AAAI Publications, Workshops at the Twenty-Sixth AAAI Conference on Artificial Intelligence

Font Size: 
Time Optimal Multi-Agent Path Planning on Graphs
Jingjin Yu, Steven M. LaValle

Last modified: 2012-07-15


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.


multiagent systems, path planning, network flow

Full Text: PDF