New approach for determining optimal paths in a dynamic 2-D environment using monotone framed-octrees

This paper proposes a new approach for determining optimal obstacle-avoiding paths in a dynamic 2-D environment. The dynamic 2-D environment is first mapped to a static 3-D space-time workspace, represented by a monotone framed-octree (mf-octree). Based on interesting data structural and computational geometric techniques, our approach propagates a diamond-shaped path planning wave through the mf-octree in an accurate and efficient manner. In particular, for an obstacle-free leaf node F (called an mf-octant) of size n³ (containing O(n³) unit cells), we need to search only O(n²) unit cells to propagate the wave through F. Our approach is much more efficient than other commonly used cell-decomposition methods while achieving at least the same level of accuracy. To model the optimality of the paths, we use a general cost function that relates the movements through space and time. Thus, time-optimal and distance-optimal paths are special cases of optimal paths based on this cost function.