Sampling and Searching Methods for Practical Motion Planning Algorithms
Time: September 17, 2007, 1pm - 2pm
Place: D344, LSRC
Speaker: Anna Yershova

Sampling and searching techniques have become highly successful tools in motion planning. Recent advances have influenced the development of efficient motion planners used in automated manufacturing, autonomous vehicles, mobile robotics, spacecraft navigation, computer graphics, and computational biology. Existing methods work well on many problems; however, they have weaknesses and limitations. In this talk I address the critical concerns not covered by the motion planning algorithms that are widespread in use today. These issues are: 1) the development of efficient nearest neighbor searching techniques for spaces arising in motion planning; 2) the development of guided sampling techniques for efficient exploration on such spaces; 3) the development of uniform sampling techniques to allow resolution completeness in sampling-based planning algorithms; 4) the synthesis of motion primitives for control systems, to allow rapid local motions to be generated in sampling-based planning algorithms. Addressing these core issues in motion planning does not only lead to a more fundamental understanding of the problem, but also to more efficient practical algorithms. Our experiments demonstrate several orders of magnitude running time improvement in some cases.