Determining conditional shortest paths in an unknown 3-D environment using framed-octrees

A conditional shortest path is a collision-free path of shortest distance which is computed from environmental information which is known at a given time. Based on the techniques of computational geometry, this paper proposes a novel cell decomposition approach for finding conditional shortest paths, in either the L₁ or L_∞ metric, through an unknown 3D environment. The proposed based on a new data structure called the framed-octree, compute a distance transform using a spherical path planning wave. The proposed methods combine together the accuracy of 3D grid-based path planning techniques with the efficiency of octree-based techniques, hence having the advantages of both kinds of techniques and avoiding their disadvantages