Octree-based hierarchial distance maps for collision detection

Discretized distance maps have been used in robotics for path planning and efficient collision detection applications in static environments. (1) However, they have been used at the finest level of resolution, thereby making them memory intensive. In this article, we propose an octree-based hierarchical representation for discretized distance maps, called Octree Distance Maps (ODM), and show its use in efficient collision detection. To the best of our knowledge, ours is the first work to consider the use of hierarchical distance maps for collision detection. ODM representation achieves an advantageous compromise between array-based distance maps and ordinary octrees. Compared to the former, ODM requires a fraction of the memory at the expense of somewhat slower collision detection. Compared to the latter, ODM requires slightly more memory but provides a significant improvement in collision detection. ODM is similar to the quadtree distance transforms used in image representation(2) but differs significantly in various aspects of distance representation and its use in collision detection since the main motivation behind ODM is efficient collision detection instead of image representation. We then present algorithms for (1) creating an ODM from an octree, and (2) for efficient collision detection based on an ODM. Extensive experiments are then presented and compared with octree-based collision detection. Our experimental results quantify the advantageous compromise achieved by ODM representation. (C) 1997 John Wiley & Sons, Inc.