Last week, Dr. Steven M. LaValle, a Professor of Computer Science at The University of Illinois at Urbana-Champaign, presented as part of Georgia Tech’s Robotics and Intelligent Machines (RIM) Seminar Series. This was the second is a series of eight seminars spanning the Fall 2006 semester and I had the pleasure of attending and hear him speak.

Dr. LaValle structured his lecture around his new book, Planning Algorithms, which is available for free download here. He describes the book by saying:

This book presents a unified treatment of many different kinds of planning algorithms. The subject lies at the crossroads between robotics, control theory, artificial intelligence, algorithms, and computer graphics. The particular subjects covered include motion planning, discrete planning, planning under uncertainty, sensor-based planning, visibility, decision-theoretic planning, game theory, information spaces, reinforcement learning, nonlinear systems, trajectory planning, nonholonomic planning, and kinodynamic planning.

While he was there to present his entire book, he chose to focus on three areas of overlap between mechanical engineering, electrical engineering, and computer science which present “great potential for impact”: motion planning with differential constraints, feedback motion planning, and information spaces.

Basics: As with any term used by different groups of people, motion planning can describe several scenarios in the fields of robotics, control theory, and artificial intelligence. However, a basic definition is designing a set of steps to move from one location or configuration to some other location or configuration while avoiding any obstacles.

Motion planning with differential constraints considers the kinematic and dynamic constraints of the robot. For example, a robot that can only move forward and turn left and right. Another example is a robotic arm that can only accelerate/decelerate its joints within some bounded range. These constraints are then “factored in” to the design of a planning algorithm.

Feedback motion planning simply means the addition of feedback (usually from sensors) to the algorithm to account for unpredictability of future states. This feedback is either done explicitly by developing a model “that explicitly account[s] for the possible ways that the actual future state can drift away from the planned future state”, or implicitly by developing a “model of state transitions [which] indicates that no uncertainty is possible; however, a feedback plan is constructed to ensure that [the algorithm] knows which action to apply, just in case it happens to be in some unexpected state during execution.” (pgs 369-370)

An information space is the set of observation history, action history, and initial conditions of a system. It is a way of saying, “I know I started at point x, I know I traveled y distance where I saw an obstacle z distance in front of me, then I traveled m distance where I saw an obstacle n distance in front of me, etc.” The information space may be used to solve the task directly without ever requiring a state estimator.

Those last two areas rely heavily on information from sensors and Dr. LaValle’s discussion promoted a “sensor centric” view of problem solving. His attitude is that algorithms should base planning decisions on input from the sensors and not on a predefined map. In other words, “use what you see to guide you and not what is on a map that someone gave you.”

Dr. LaValle’s book is the required text for UIUC’s CS 498 Introduction to Planning Algorithms, which he teaches.

To comment on the style of his lecture, I found it very in depth for only 50 minutes of speaking. His approximately 80 slides were very well organized and showed what his mouth was saying. He didn’t simply retype his speech for everyone to read. Time constraints limited him to, I’m guessing, 70% of his presentation, yet he didn’t lose the audience by jumping ahead several slides. I hope he is as good a lecturer to his students as he is to a room full of strangers.

Resources:
Dr. LaValle’s academic website
Planning Algorithms textbook
CS 498 class website
Wikipedia: navigation problem
Robotics and Intelligent Machines @ Georgia Tech

Seminar Series Poster

(I wrote this to summarize my notes from Dr. LaValle’s lecture and my small amount of follow up reading of his text, to gain insight into the University of Illinois’ ME/EE/CS research, and to spark interest in future RIM seminars.)