Constrained Voronoi diagram and its application to autonomous mobile robot path planning

摘要

In this work the problem of mobile robot path planning in known static environments is investigated. A new environment representation based on the concept of Voronoi diagram, called constrained Voronoi diagram, is introduced. In general, conventional environment representation is by modelling obstacles as polygons. The input to the constrained Voronoi algorithm is the vertex location of polygonal obstacles. By modelling obstacles with more points, the constrained Voronoi diagram approaches the skeleton of the free space. This structure has inherent properties to achieve maximal clearance paths in O(n) time complexity (where n is the number of obstacle vertex points). Depending on type of the environment (i.e., cluttered with obstacles or sparsely populated), different types of paths are desired. The combination of constrained Voronoi diagram and its dual the triangulation diagram, is analyzed to determine the type of the environment. Based on the type of the environment, either a maximum clearance or a path with a specified clearance is generated. An environment can have a mixture of different type regions. The paths for this type of an environment is partitioned and is modified for the particular region. Finally, a path smoothing algorithm is used to minimize the number of turns.