Computer Science Colloquium

Planning Algorithms and Information Spaces

Steven M. LaValle
University of Illinois

Friday, October 20, 2006 11:30 AM
Room 1302 Warren Weaver Hall
251 Mercer Street
New York, NY 10012-1185

Colloquium Information:


Bud Mishra href="">, (212) 998-3464


These are exciting times for research on planning algorithms. After decades of development, motion planning algorithms have evolved to the point of widespread, reliable use in many applications, including the manufacturing industry, humanoid robotics, autonomous vehicle development, and computational biology. Basic path planning, the core of motion planning, is now very well understood; there are a variety of good algorithms, ranging from practical and efficient to theoretical and general.

Although there have been great successes, the most widely used formulation of motion planning is much too narrow because it neglects many important issues such as sensing, uncertainties, feedback, and differential constraints (kinematics, dynamics). We hope that the widespread success of basic motion planning can eventually be realized for a much broader class of problems. To achieve this, many basic challenges remain. I will provide some historical perspective and then spend most of the talk highlighting our work on planning in information spaces, which are the natural "configuration" spaces in which virtually all sensor-based planning problems live. The key to developing practical planning algorithms in contexts that have substantial uncertainty seems to lie in our ability to understand and reduce the information requirements and the corrsponding information spaces.

Related book: Planning Algorithms, S. M. LaValle, Cambridge Press, 2006. Free download at

top | contact