Proximity Queries between Convex Objects:
An Interior Point Approach for Implicit Surfaces
Download the paper,
icra06.pdf.
Authors:
Srinivas Akella
Department of Computer Science
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
sakella at cs.rpi.edu
Nilanjan Chakraborty
Department of Computer Science
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
chakrn2 at cs.rpi.edu
John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj at rpi.edu
Jufeng Peng
Burlington Northern Santa Fe Railway
jufeng.peng at bnsf.com
Proceedings of
ICRA2006,
the 2006 IEEE International Conference on
Robotics and Automation,
Orlando, Florida, May 2006,
pages 1910-1916.
The proceedings are for sale
here.
September 2005.
Abstract:
In this paper, we present an interior point approach
to exact distance computation between convex objects
represented as intersections of implicit surfaces. The implicit
surfaces considered include planes (polyhedra), quadrics,
and generalizations of quadrics including superquadrics and
hyperquadrics, as well as intersections of these surfaces. Exact
distance computation algorithms are particularly important
for applications involving objects that make contact, such
as in dynamics simulations and in contact point prediction
for dextrous manipulation. They can also be used in the
narrow phase of hierarchical collision detection. In contrast
to geometric approaches developed for polyhedral objects,
we formulate the distance computation problem as a convex
optimization problem; this optimization formulation has been
previously described for polyhedral objects. We demonstrate
that for general convex objects represented as implicit surfaces,
interior point approaches are reasonably fast and in
some cases, owing to their global convergence properties, are
the only provably good choice for solving proximity query
problems. We use a primal-dual interior point algorithm that
solves the KKT conditions resulting from the convex programming
formulation. We present preliminary implementation
results, including distance computation between deforming
superquadrics, to demonstrate the merit of the interior point
approach.
Download the paper,
icra06.pdf.
Return to my list of papers.