2-D Path planning for weighted-regions by weighted-quadtree method

Abstract

Path planning is one of the most important research areas of robotics, operations research, artificial intelligence and other optimization fields. Much research has been focused on developing theories and algorithms needed for the planning of a path. Most of approaches posit a binary view of the environment, either traversable or impassable, and find the non-colliding shortest path based on the Euclidean-distance metrics. However, a real workspace is an environment which consists of many different media, such as terrains, hazard regions, threats, obstacles and etc.. It is natural to allow a path to pass through them at extra costs. The extra costs are represented by the weights that means the ``cost per unit distance`` of moving through that particular region. In this weighted environment, the shortest path of Euclidean-distance metrics does not imply the least cost path. If we assign the weight as infinity or 1 depending on the existence of obstacles or not, the path planning in the weighted workspace becomes the binary workspace. Therefore path planning in the weighted workspace is a generalized shortest path problem. Until recently, efficient methods representing the weighted regions and the feasible path planning algorithms in the weighted workspace are not yet sufficiently developed. In this thesis, our novel weighted quadtree (WQT) as a new representation method and a path planning approach based on the weighted quadtree are described. The WQT is a hierarchical multiresolution cell decomposition technique. All leaves of the tree have a restricted cost and each leaf has a different area depending on the weight of that area. Without loss of generality, the most important heuristics for the space representation for the path planning is to avoid excess details and spending time on the parts of the space that does not affect the planning operation. The more weighted risk cost region is, the more detail path planning is required for more safety. The coarse d...