Generalized Penetration Depth Computation and Applications to
Motion Planning ^{2 } Publications
BackgroundPenetration depth (PD) is a distance measure to quantify the extent of interpenetration between two overlapping, closed, geometric objects. PD computation is important in a number of applications, including physicallybased modeling, robot motion planning, virtual reality, haptic rendering and computer games.
The ChallengeMost of the prior work on PD computation has been restricted to translational PD or PD^{t}. The PD^{t} between two overlapping objects is defined as the minimum translational distance needed to separate the two overlapping objects. Many good algorithms to estimate the PD^{t} between convex and nonconvex polyhedra are known. However, because PD^{t} does not take into account the rotational motion, it is not sufficient for many applications, such as motion planning and physically based modeling. Highlights of our approach We take into account the translational and rotational motion to describe the extent of two intersecting objects and refer to that extent of interpenetration as the generalized penetration depth or PD^{g}.
Results of Generalized PD Computation
We compute an upper bound on PD^{g} based containment optimization using linear programming.
Fig. 2: In the left column, the ‘spoon’ collides with the ‘cup’ at t=0, 0.5, and 1. The right column shows for every t the corresponding collisionfree configuration, which yields an upper bound on PD^{g}.
Fig. 3: The comparison of PD^{g}^{ }computation for the ‘spoon in cup’ example. LB(PD^{g}): Lower bound on PD^{g}; UB_{1}(PD^{g}): Upper bound by our containment optimization. UB_{2}(PD^{g}): Trivial upper bound using the convex hulls.
Tab. 1: Performance of various bounds computation on PD^{g} Application to Motion Planning Our lower bound on PD^{g} computation algorithm has been applied for motion planning to perform the Cobstacle query. Given a primitive in Cspace, the Cobstacle query is formally defined as checking whether this primitive lies in Cobstacle space. Usually, the underlying query primitive is a cell.
In order to efficiently perform Cobstacle query for a cell, we compute the PD^{g} by setting its configuration as the center of the cell. Then we compare it with the maximal motion that the robot can undergo when its configuration is confined within this cell. If the lower bound of PD^{g} is larger than the upper bound of the motion, we conclude that the cell fully lies in Cobstacle space.
The Cobstacle query is useful for cell decomposition based algorithms and other complete motion planning approaches, such as starshaped roadmap (Fig. 4). Given that the time and space complexity of these methods grows quickly with the level of subdivision, it is important to identify cells that lie in Cobstacle space and to avoid overly subdivision.
Fig. 4: An application of our Cobstacle query algorithm based on PD^{g}^{ }for a complete motion planner – the starshaped roadmap method. The robot Gear needs to move from initial configuration A to goal configuration A’ by translating and rotating within the shaded rectangular 2D region. We show the robot's intermediate configurations for the found path. The improved starshaped roadmap method took about 110s for this example and achieved about 2.4 times speedup.
Fig. 5: ‘2D puzzle’ example. (a) Our algorithm can report the path nonexistence for the problem to move A to A0 in 7.898s. (b) is a modified version of (a) without the obstacle B3. Our algorithm can find a collisionfree path through a narrow passage among the obstacles. (c) shows intermediate configurations Am of the robot along the collision free path. Related Work
