Efficient Graph-based Environment Representation and Path Planning using Centroidal Voronoi Tessellation

Abstract

A scalable environment representation is important for a mobile robot when seeking appropriate paths in a large environment. A probabilistic roadmap (PRM) has an advantage of abstracting the traversable area information of a large environment because unoccupied regions and their connectivities are represented by several nodes and edges, respectively.In this thesis, we present an efficient graph-based environment representation for a mobile robot path planning by solving problems of the PRM. First, a centroidal Voronoi tessellation-based probabilistic roadmap (CVT-PRM) is proposed. The CVT-PRM is constructed by rearranging nodes using the node rearrangement method. It iteratively updates the positions of nodes using a concept of the centroidal Voronoi tessellation.The CVT-PRM covers traversable areas almost completely and divides them evenly, and the CVT-PRM-based path planner can search an appropriate path more promptly than a grid-based path planner. Second, a hierarchical roadmap (HRM) is proposed. The HRM has a multi-layered structure to represent traversable areas. In the HRM, a region-roadmap abstracts the topological relation of subegions in an environment, and a local-roadmap represents traversable areas in each subregion. The incremental construction process of the HRM expands the traversable area information by extracting new subregions when a mobile robot navigates unknown regions.An efficient path planning method is also proposed using the multi-layered structure of the HRM. The divide-and-conquer (DNC) method locally seeks an appropriate path to reduce search space. The HRM-based path planner with the DNC method can search an appropriate path more promptly than a PRM-based path planner because the search space size of the HRM-based planner is much smaller than that of the PRM-based planner. Last, the sampling-based retraction (SbR) is proposed. The SbR improves the safety of the initial path planning result by removing unsafe sections in the initial path. In the SbR, each waypoint is iteratively updated to maximize its clearance by indirectly modeling clearance around it using several random samples.