Time Optimal Multi-Agent Path Planning on Graphs

Significant progress has been made in the area of multiagent path finding/planning in the past decade (Silver 2005; van den Berg et al. 2009; Standley 2010; Luna and Bekris 2011; Wang and Botea 2011). In this work, we introduce a multi-agent path planning problem similar to that of (Standley (a) (b) (c) 2010) and aim at maximizing parallelism among the agents. That is, we seek a feasible plan that minimizes the Figure 1: a) A simple graph G. b) A gadget for splitting time it takes the last agent to reach its goal. To solve the an undirected edge through time steps.