OCTREE-BASED HIERARCHICAL 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 o ctree-based hierarchical representation for discretized distance maps, called Octree Distance Maps (ODM), and show its use in efficient coll ision detection. To the best of our knowledge, ours is the first work to consider the use of hierarchical distance maps for collision detect ion. ODM representation achieves an advantageous compromise between ar ray-based distance maps and ordinary octrees. Compared to the former, ODM requires a fraction of the memory at the expense of somewhat slowe r collision detection. Compared to the latter, ODM requires slightly m ore memory but provides a significant improvement in collision detecti on. ODM is similar to the quadtree distance transforms used in image r epresentation(2) but differs significantly in various aspects of dista nce representation and its use in collision detection since the main m otivation behind ODM is efficient collision detection instead of image representation. We then present algorithms for (1) creating an ODM fr om an octree, and (2) for efficient collision detection based on an OD M. Extensive experiments are then presented and compared with octree-b ased collision detection. Our experimental results quantify the advant ageous compromise achieved by ODM representation. (C) 1997 John Wiley & Sons, Inc.