Planning with the Medial Axis
The medial axis is a geometric construct akin to the continuous Voronoi
diagram. It captures the topological information, including connectivity of a
space, but has lower dimension and maintains a maximal clearance from the
boundary. We are working on applying the medial axis to planning problems by
moving the robot along the medial axis or in its vicinity. In the case of
flexible surface, the deformation of the robot can be chosen to locally match
the shape of the medial axis, allowing us to plan through narrow and curved
passages. For rigid objects a heuristic is necessary to get a favorable
distribution of orientations in the neighborhood of the medial
axis.
We compute the medial axis in two dimensions with a generic sampling approach that utilizes some interesting properties of Delaunay triangulations. While this method is extensible to three dimensions, the sampling of the workspace becomes prohibitively difficult, and instead we use a tracing procedure. This procedure uses a point-to-obstacle distance function to enumerate a mesh approximating the medial axis. This algorithm is able to handle arbitrary triangle soups. Many 3D models are imported as polygon soups so algorithms that require some adjacency information are not generally as feasible.
For our 3 dimensional planner we use a very different method for
computing the medial axis. With only a point-obstacle distance
function we explore and construct the medial axis for arbitrary
polygonal input sets. We have been successful in planning for rigid
objects in three dimensions, and we are currently working on extending
the planner to deformable volumes in three dimensions. The image to
the right shows a medical application in which we compute an insertion
path for a pin (yellow) into an irregular cavity (green). Here is an
animation of our 2D planner at
work, as well as the 3D planner for a rigid object here and here (not gzipped).