Navigation of a car-like mobile robot using a decomposition of the environment in convex cells

A method for rapidly computing the possible maneuvers of car-like robots within convex polygonal cells is presented. In a convex polygonal cell, maneuvering can be completely handled with geometric reasoning, and, since only a few boundary configurations have to be checked to avoid collision, the method allows precise computation of the maneuvers without using the whole configuration space. General environments are then described by means of a graph connecting overlapping convex cells. To find a path to a goal, the graph is searched to determine the cells that have to be traversed. Intermediate configurations are then computed inside the intersection of each pair of adjacent cells. Finally, the trajectories generated inside each cell are assembled to produce global collision-free paths in complex environments