Coordinated path planning for multiple robots

We present a new approach to the multi-robot path planning problem, where a number of robots are to change their positions through feasible motions in the same static environment. Rather than the usual decoupled planning, we use a coordinated approach. As a result we can show that the method is probabilistically complete, that is, any solvable problem will be solved within a finite amount of time. A data-structure storing multi-robot motion is built in two steps. First, a roadmap is constructed for just one robot. For this we use the probabilistic path planner, which guarantees that the approach can be easily applied to different robot types. In the second step, a number of these simple roadmaps are combined into a roadmap for the composite robot. This data-structure can be used for retrieving multi-robot paths. We have applied the method to car-like robots, and simulation results are presented which show that problems involving up to five car-like robots in complex environments are solved successfully in computation times in the order of seconds, after a preprocessing step (the construction of the data-structure) that consumes, at most, a few minutes. Such a preprocessing step however needs to be performed just once, for a given static environment. (C) 1998 Elsevier Science B.V.