Complete and Scalable Multi-Robot Planning in Tunnel Environments

Mike Peasgood, University of Waterloo
John McPhee, University of Waterloo
Christopher M. Clark, University of Waterloo

Article comments

Copyright © 2006 IFAC. The definitive version is available at http://www.ifac-papersonline.net/Detailed/29806.html.

NOTE: At the time of publication, the author Christopher Clark was not yet affiliated with Cal Poly.

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.