Abstract

Over the past several years, techniques have been developed for generating, manipulating and characterizing objects in quadtree and octree data organizations [Jackins and Tanimoto 1980, Samet 1981, Schneir 1981, Udupa 1982 and Yau 1983]. An important but less studied application of the octree and related data structures is to model 3d space not 3d objects. That is, the working environment of a robot can be modeled by placing objects in the various cells of an octree data structure which models the encompassing 3d space. This slight but important variation on object modeling is crucial in robotic applications where it is necessary not only to model object size and shape but object position and the voids between objects so that movements can be planned. A modified octree approach has been described which increases storage efficiency and allows planning of robotic arm movement [Lozano-Perez 1981]. The hextree model generalizes the octree concept to 4 dimensions so that objects moving in the environment can be modeled. This enables a robot system to predict (and thus avoid) collisions of objects in the environment including arms and manipulators under its control and external moving objects over which it has no direct control. Since the entire environment in space and time is modeled, paths for manipulator movement can be planned which avoid both stationary and moving objects.

© 1985 Optical Society of America