Kavraki Lab

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.