Presents a geometry-based approach for multiple mobile robot motion coordination. The problem is to coordinate the motions of several robots moving along fixed independent paths to avoid mutual collisions. The proposed algorithm is based on a bounding box representation of the obstacles in the so-called coordination diagram. The algorithm is resolution-complete but it is shown to be complete for a large class of inputs. Despite the exponential dependency of the coordination problem, the algorithm efficiently solves problems involving up to ten robots in worst-case situations and more than 100 robots in practical ones.

The paper presents a geometric algorithm dealing with collision checking in the framework of multiple mobile robot coordination. We consider that several mobile robots have planned their own collision-free path by taking into account the obstacles, but ignoring the presence of other robots. We first compute the domain swept by each robot when moving along its path - such a domain is called a trace. Then the algorithm computes the coordination configurations for one robot with respect to the others, i.e. the configurations along the path where the robot enters the traces of the other robots or exits from them. This information may be exploited to coordinate the motions of all the robots.

Several schemes have been proposed in the path planning literature to plan collision-free and feasible trajectories for nonholonomic mobile robots. A classical scheme is the two-step approach which consists in first computing a collision-free holonomic path, and then in transforming this path by a sequence of feasible ones. The quality of the solution and the computational cost of the second step depend on the shape of the holonomic path. In this paper, we introduce a nonholonomic cost of the geometric path to be approximated and we propose a configuration space structuring that allows us to compute an holonomic path minimizing at best the nonholonomic cost. The algorithms have been implemented and we present simulation results which illustrate the efficacy of the planner to produce good solutions with respect to the nonholonomic constraints of a mobile robot.