A new algorithm and simulation for computing optimal paths in a dynamic and weighted 2-D environment
Bin Xu, D.Z. Chen, Robert J. Szczerba · 2002
Presents a new method for determining optimal paths in a weighted and dynamic 2D environment, together with some simulation results. After mapping the dynamic and weighted 2D environment onto a static 3D space-time workspace, we represent the 3D workspace by a weighted and framed octree (wf-octree), and find optimal paths in the weighted and dynamic 2D environment by propagating a diamond-shaped path planning wave in the 3D workspace through the uniformly weighted leaf nodes of the wf-octree. A wave propagation heap is introduced to control the process of the wave propagation. Based on interesting data-structural and computational geometric techniques, our approach propagates the path-planning wave through each uniformly-weighted and framed octant efficiently. Our approach guarantees the optimality of the resulting paths without requiring the entire static 3D space-time workspace to be searched. Therefore, it is much more efficient than other commonly-used cell decomposition methods such as the grid-based ones, while it achieves at least the same accuracy as other cell decomposition methods. The distance we compute is based on the L/sub 1/ or L/sub /spl infin// metric.