A Hierarchical Orthogonal Space Approach to Three-Dimensional Path Planning

A methodology tor three-dimensional collision-free path planning by which planning is done in the three-dimensional orthogonal two-dimensional projections of a three-dimensional environment is presented. Collision checking is done in each of the three orthogonal twodimensional subspaces using primitive path segments. A hierarchical-path search method is used to speed up the search process. This approach forms basis for spatial planning in environments where no a priori knowledge is assumed. The three orthogonal two-dimensional projections can be readily obtained from three orthogonal cameras in simple environments.