Dan Halperin
Let R be a robot (a body or a collection of bodies hinged together) moving in an environment cluttered with obstacles. The basic motion planning problem is: Given start and (desired) goal positions for R, decide whether R can move from start to goal without colliding with the obstacles nor with itself, and if so plan such a collision-free motion. The motion planning problem has been intensively studied for several decades, with many extensions and variants. We review milestone results in this study, describing how the perception of what is difficult in motion planning has changed over the years.
We then address two extreme settings and describe tools we have developed to cope with them in practice: (i) The case of a very large number of degrees of freedom (dofs), as arises in macromolecular-motion simulation. Here we describe tools to expedite the computation and improve the quality of paths produced by sampling-based methods. (ii) Planning motion along tight passages, namely with zero or near-zero clearance from the obstacles(for very few dofs though), such as arise for example in mechanical assembly planning. Here we describe complete solutions based on recent developments in CGAL, the Computational Geometry Algorithms Library.
Joint work with Angela Enosh, Efi Fogel, and Barak Raveh.