Efficient global penetration depth computation for articulated models

Abstract

We present an algorithm for computing the global penetration depth between an articulated model and an obstacle or between the distinctive links of an articulated model. In so doing, we use a formulation of penetration depth derived in configuration space. We first compute an approximation of the boundary of the obstacle regions using a support vector machine in a learning stage. Then, we employ a nearest neighbor search to perform a runtime query for penetration depth. The computational complexity of the runtime query depends on the number of support vectors, and its computational time varies from 0.03 to 3 milliseconds in our benchmarks. We can guarantee that the configuration realizing the penetration depth is penetration free, and the algorithm can handle general articulated models. We tested our algorithm in robot motion planning and grasping simulations using many high degree of freedom (DOF) articulated models. Our algorithm is the first to efficiently compute global penetration depth for high-DOF articulated models.