» Download Article

Authors
Mike Peasgood; John McPhee; Christopher Clark

Digital Object Identifier (DOI)
10.3182/20061002-2-BR-4906.00006

Page Numbers:
26-31

Index Terms
mobile robots,efficient algorithms,path planning,trajectory planning

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.

References

[1] 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.
[2] 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.
[3] Erdmann, Michael and Tomas Lozano-Perez
    (1987). On multiple moving objects. Algorithmica
     2, 477-521.
[4] Ge, S. S. and Y. J. Cui (1997). Dynamic motion
    planning for mobile robots using potential
    field method. Autonomous Robots 13(3), 207-
    222.
[5] 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.
[6] Latombe, J. C. (1991). Robot Motion Planning.
    Kluwer Academic Publishers.
[7] LaValle, S. M. (2006). Planning Algorithms. Cambridge
     University Press.
[8] 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.
[9] Svestka, P. and M. Overmars (1998). Coordinated
    path planning for multiple robots. Robotics
    and Autonomous Systems 23, 125-152.