Multi-Robot Path Planning

Abstract

This chapter is devoted to a problem of path planning for multiple robots (Ryan, 2008; Surynek, 2010a). Consider a group of mobile robots that can move in some environment (for example in the 2-dimensional plane with obstacles). Each robot of the group is given an initial and a goal position in the environment. The question of our interest is how to determine a sequence of motions for each robot of the group such that all the robots reach their goal positions starting from the initial ones. Physical limitations must be respected by robots: robots must not collide with each other and they must avoid obstacles in the environment during their movements. The problem of multi-robot path planning is motivated by many practical tasks. Various problems of navigating a group of mobile robots can be formulated as multi-robot path planning. However, the primary motivations for the problem are tasks of moving certain entities within an environment with a limited free space. Hence, the formulation of the problem is not limited to the case where robots are actually represented by mobile robots. The constraint of limited free space represents a key aspect that makes the problem interesting and non-trivial. It is quite intuitive to see that the problem becomes easier with a lot of free space in the environment. The interaction between robots (which corresponds to the probability of collisions) is low in such a case. Thus, it is possible to plan movements of each robot relatively independently with respect to other robots. Then the problem reduces almost to the series of simple single source path finding (Cormen et al., 2001) for each robot; potentially with finding alternative paths if a collision still occurs. On the other hand, if there is limited free space in the environment the problem becomes harder. Consider the situation where the space occupied by robots is comparable to the free space or even the situation where robots occupy larger space than the space that remains unoccupied in the environment. The interaction between robots (that is, the probability of collisions) is so high in such a case that finding a path for each robot independently no longer works. Therefore, different methods must be used. One of the aims of this chapter is to explain solving methods for these cases. Notice, that it is desirable to reason about the case with limited free space since practical tasks typically has this property. Such real-life examples include rearranging of shipping containers in warehouses (a robot is represented by a shipping container – see Fig. 1) or coordination of vehicles in dense traffic (robot = vehicle). Additionally, our reasoning should not be limited to physical entities only. A robot may be represented by a virtual entity or by a piece of commodity too. Thus, many tasks such as planning of data transfer between communication