A Computational Technique for Free Space Localization in 3-D Multiresolution Probabilistic Environment Models

Probabilistic modeling of two-dimensional or three- dimensional (2-D or 3-D) objects and working environments as quadtrees and octrees encoded with multiple resolutions represents a new trend with numerous applications in computer vision and robotics. The development of neighbor-finding techniques adapted to these tree structures appears as a critical issue for such models to be used properly, especially for path planning and collision avoidance where free space localization is essential. In this paper, a generic neighbor-finding framework that is based on a recursive addressing scheme directly operating on a hierarchical tree structure without the need for preprocessing of raw occupancy measurements generated by range-sensing devices is presented. Neighboring cell addresses are processed in a way similar to basic arithmetic operations with carry given a displacement direction and the address of a starting cell. Neighboring rule sets are derived for a quadtree and extended to an octree. Special cases resulting from multiresolution maps are handled, while the algorithm complexity is kept low to ensure good performances. The approach is developed and validated in the context of collision avoidance for autonomous robotics