Generalized Penetration Depth Computation

and Applications to Motion Planning

Liangjun Zhang1
Young J. Kim2
Gokul Varadhan1
Dinesh Manocha1

1 University of North Carolina at Chapel Hill

2  EWHA Womans University, Korea

Publications

  • A Fast and Practical Algorithm for Generalized Penetration Depth Computation, Liangjun Zhang, Young J. Kim, Dinesh Manocha, Robotics: Science and Systems Conference (RSS07), 2007
    Paper (PDF) (0.5M)   
  • Generalized Penetration Depth Computation, Liangjun Zhang, Young J. Kim, Gokul Varadhan, Dinesh Manocha, CAD (special issue on SPM06), Volume 39, Issue 8, Aug 2007, 625-638
    Paper
  • Generalized Penetration Depth Computation, Liangjun Zhang, Gokul Varadhan, Young J. Kim, Dinesh Manocha, ACM Solid and Physical Modeling Conference (SPM06), 2006, 173-184
    Paper (PDF, 4M)     SPM Presentation (4M)  
  • Efficient distance computation in configuration space, Liangjun Zhang, Young J. Kim, Dinesh Manocha, Computer Aided Geometric Design (special issue on SPM 07), Volume 25, Issue 7, Oct 2008,  489-502
    Paper
  • C-DIST: Efficient Distance Computation for Rigid and Articulated Models in Configuration Space, Liangjun Zhang, Young J. Kim, Dinesh Manocha, ACM Solid and Physical Modeling Conference (SPM07), 2007
    Project Webpage     Paper (PDF) (1.5M) 
  • A Simple Path Non-Existence Algorithm Using C-obstacle Query, Liangjun Zhang, Young J. Kim, Dinesh Manocha, The Seventh International Workshop on the Algorithmic Foundations of Robotics (WAFR), 2006
    Paper (PDF 1M)      WAFR Presentation (1.8M)
  • Fast C-obstacle Query Computation for Motion Planning, Liangjun Zhang, Young J. Kim, Gokul Varadhan, Dinesh Manocha, IEEE International Conference on Robotics and Automation (ICRA), 2006, 3035-3040
    Paper (PDF 1.4M)   ICRA Presentation (1.1M)
  • Research Project Summary
    Paper (PDF 0.7M)

Background

Penetration depth (PD) is a distance measure to quantify the extent of inter-penetration between two overlapping, closed, geometric objects. PD computation is important in a number of applications, including physically-based modeling, robot motion planning, virtual reality, haptic rendering and computer games.

Fig. 1: (a) shows the translational PD between two overlapping objects A and B. (b) shows that when both translational and rotational transformation are allowed, the amount of the motion to separate A from B is much smaller than when only translation is allowed in (a).

The Challenge

Most of the prior work on PD computation has been restricted to translational PD or PDt. The PDt between two overlapping objects is defined as the minimum translational distance needed to separate the two overlapping objects. Many good algorithms to estimate the PDt between convex and non-convex polyhedra are known. However, because PDt  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 inter-penetration as the generalized penetration depth or PDg.

  • A novel definition for PDg;
  • For convex models, we prove that their PDg is same as PDt;
  • Approximation lower bound and upper bound algorithms on PDg for non-convex models;
  • PDg based for C-obstacle query algorithm for complete motion planning and path non-existence problems.

Results of Generalized PD Computation

 

 

Video (33M)

We compute an upper bound on PDg 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 collision-free configuration, which yields an upper bound on PDg.

Fig. 3:  The comparison of PDg computation for the ‘spoon in cup’ example. LB(PDg):    Lower bound on PDg; UB1(PDg):  Upper bound by our containment optimization. UB2(PDg):  Trivial upper bound using the convex hulls. 

Tab. 1: Performance of various bounds computation on PDg

Application to Motion Planning

Our lower bound on PDg computation algorithm has been applied for motion planning to perform the C-obstacle query. Given a primitive in C-space, the C-obstacle query is formally defined as checking whether this primitive lies in C-obstacle space. Usually, the underlying query primitive is a cell.

 

In order to efficiently perform C-obstacle query for a cell, we compute the PDg 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 PDg is larger than the upper bound of the motion, we conclude that the cell fully lies in C-obstacle space.

 

The C-obstacle query is useful for cell decomposition based algorithms and other complete motion planning approaches, such as star-shaped 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 C-obstacle space and to avoid overly subdivision.

 

 

 

Video (7M)

Fig. 4:  An application of our C-obstacle query algorithm based on PDg for a complete motion planner – the star-shaped 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 star-shaped roadmap method took about 110s for this example and achieved about 2.4 times speedup.

 

 

 

Video (2M)

 

Fig. 5:  ‘2D puzzle’ example. (a) Our algorithm can report the path non-existence 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 collision-free path through a narrow passage among the obstacles. (c) shows intermediate configurations Am of the robot along the collision free path.

Related Work