A practical algorithm for planning collision-free coordinated motion of multiple mobile robots

Abstract

When multiple mobile robots are working in the same environment, planning of collision-free coordinated motion is necessary; here, an algorithm for planning such a motion of two mobile robots, no matter how crude the constraints of obstacles are, is proposed. The situation is modeled as a Petri net, which is considered as a useful model for describing and analyzing a system in which it is possible for some events to occur concurrently but there are constraints on the concurrence. In the Petri net, all motion constraints of robots in their paths are arranged as its firing rules, and hence collision-free coordination between the robots can be easily planning by manipulation of the firing rules. The algorithm always finds a collision-free coordinated path of two robots if there actually exists such a path in the environment. Moreover, because the algorithm does not use any knowledge of movement of the robots, precise time-varying trajectory control is not required and realization of the coordination is easy. The algorithm works efficiently even in a complex environment, indebted to the generic properties of geographical quadtree modeling for the environment. The usefulness of the algorithm is shown by several simulations.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>