Complete and scalable multi-robot planning in tunnel environments
Multivehicle Systems, Volume # 1 | Part# 1
Mike Peasgood; John McPhee; Christopher Clark
Digital Object Identifier (DOI)
mobile robots,efficient algorithms,path planning,trajectory planning
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.
 Bennewitz, M., W. Burgard and S. Thrun (2001). Optimizing schedules for prioritized path planning of multi-robot systems. In: Proc. IEEE Int. Conf. on Robotics and Automation . pp. 271-276.  Clark, C., S. Rock and J. C. Latombe (2003). Motion planning for multi-robot systems using dynamic robot networks. In: Proc. IEEE Int. Conf. on Robotics and Automation. pp. 4222 -4227.  Erdmann, Michael and Tomas Lozano-Perez (1987). On multiple moving objects. Algorithmica 2, 477-521.  Ge, S. S. and Y. J. Cui (1997). Dynamic motion planning for mobile robots using potential field method. Autonomous Robots 13(3), 207- 222.  Guo, Y. and L. Parker (2002). A distributed and optimal motion planning approach for multiple mobile robots. In: Proc. IEEE Int. Conf. on Robotics and Automation. pp. 2612- 2619.  Latombe, J. C. (1991). Robot Motion Planning. Kluwer Academic Publishers.  LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.  Lumelsky, V. J. and K. R. Harinarayan (1997). Decentralized motion planning for multiple mobile robots: The cocktail party model. Autonomous Robots 4(1), 121-135.  Svestka, P. and M. Overmars (1998). Coordinated path planning for multiple robots. Robotics and Autonomous Systems 23, 125-152.