Skip to main content
Complete and Scalable Multi-Robot Planning in Tunnel Environments
Proceeings of the First IFAC Workshop on Multi-Vehicle Systems
  • Mike Peasgood, University of Waterloo
  • John McPhee, University of Waterloo
  • Christopher M. Clark, University of Waterloo
Publication Date

This paper addresses the challenging problem of finding collision-free trajectories for many robots moving to individual goals within a common environment. Most popular algorithms for multi-robot planning manage the complexity of the problem by planning trajectories for robots sequentially; such decoupled methods may fail to find a solution even if one exists. In contrast, this paper describes a multi-phase approach to the planning problem that guarantees a solution by creating and maintaining obstacle-free paths through the environment as required for each robot to reach its goal. Using a topological graph and spanning tree representation of a tunnel or corridor environment, the multi-phase planner is capable of planning trajectories for up to r = L-1 robots, where the spanning tree includes L leaves. Monte Carlo simulations in a large environment with varying number of robots demonstrate that the algorithm can solve planning problems requiring complex coordination of many robots that cannot be solved with a decoupled approach, and is scalable with complexity linear in the number of robots.

Publisher statement
The definitive version is available at
Citation Information
Mike Peasgood, John McPhee and Christopher M. Clark. "Complete and Scalable Multi-Robot Planning in Tunnel Environments" Proceeings of the First IFAC Workshop on Multi-Vehicle Systems (2006)
Available at: