Automatic path planning for a mobile robot among obstacles of arbitrary shape

A novel and fast path-planning method for a mobile robot (MR) among objects of arbitrary shape is described. It comprises two phases. During the first phase, the graph including all possible collision-free paths from a top view of the environment is first obtained. During the second phase, the optimal path for the MR is then selected. For this, the proposed method uses both the fast distance transformation (FDT) and variations of some topological methods as thinning and skeletonization, to obtain the free space skeleton. Unlike conventional methods, the proposed approach is capable to include the MR and the target intrinsically in the path and, at the same time it obtains the collision-free path's graph, taking advantage of the topological concept of hole. We propose to use a logical operator over the FDT instead of the classical morphologic operators over the discrete array (erosion and dilation), to obtain a much faster algorithm. The optimal path (in terms of length) is next selected and smoothed by conventional algorithms. The resultant path is finally used a reference by the MR.