New cell decomposition techniques for planning optimal paths
Robert J. Szczerba, Danny Z. Chen, J.J. Uhran · 1996
Planning optimal paths between distinct locations in an environment scattered with obstacles is an important problem in many areas of research. One commonly used method for generating such optimal paths is through cell decomposition techniques, in which an environment is subdivided into cells and is searched with heuristic searching algorithms. Previous cell decomposition approaches using grids, quadtrees, and/or octrees have been unable to generate both accurate and efficient solutions to several classical path planning problems. Through the development of new framed-subspace data structures and applying computational geometry techniques, we present accurate and efficient solutions to a number of important path planning problems. In particular, we develop algorithms for finding optimal paths in both 2-D and 3-D environments scattered with static and dynamic obstacles, weighted regions, and/or multiple, dynamic goals. We solve these problems in the context of a variety of optimality metrics and problem constraints. Our techniques represent a significant improvement in efficiency and accuracy over what could previously be achieved with traditional approaches in this area.