Motion planning is concerned with computing obstacle-avoiding motion for objects in an environment populated with obstacles (e.g., robot manipulators on an assembly line or drug molecules inside the binding cavity of a protein). It has applications in areas as disparate as robotics, computational biology, animation, and medical surgery planning. The key difficulty in designing general motion planning algorithms lies in the number of degrees of freedom (dofs) that an object has.
In this talk, I will present efficient randomized algorithms for computing obstacle-avoiding motion for objects with many dofs in complex geometric environments. I will show extensions of the basic algorithms to deal with kinematic and dynamic motion constraints, as well as moving obstacles in the environment. The generality and efficiency of these algorithms make them useful in applications such as robotics and computer animation. Using insights gained from randomized motion planning, we developed Stochastic Roadmap Simulation (SRS), a new framework for simulating and analyzing molecular motion. SRS simultaneously examines many molecular motion pathways encoded compactly in a graph and thus achieves tremendous improvement in computational efficiency, compared with classic techniques such as the Monte Carlo method.