Skip to main content
Presentation
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
10-2-2006
Abstract

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.

Disciplines
Publisher statement
The definitive version is available at http://www.ifac-papersonline.net/Detailed/29806.html.
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: http://works.bepress.com/cmclark/23/