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 discretization on the low weighted region speed up the overall process. The novel WQT-based cell decomposition method naturally provides such description of workspace.
The novel WQT-based path planning method and the related algorithms such as neighbor finding, antialiased path cost and path relaxation are described in detail. Also dynamic discrete events-based route evaluation method is shown for the selected path. This evaluation method is very effective to verify the route safeness if the workspace have some active agents that operate dynamically with some interactive events. Finally, an integrated framework for the path planning is implemented in the weight workspace. The complete map of the workspace including the risk costs as well as obstacle locations is assumed to be known a priori.
