April 11, 2003 - Seth Hutchinson

Real-time Path Planning in Changing Environments

Location: Shaffer 3
Time: 11:00 am


We present a new method for generating collision-free paths for robots operating in changing environments. Our approach is closely related to recent probabilistic roadmap approaches. These planners use preprocessing and query stages, and are aimed at planning many times in the same environment. In contrast, our preprocessing stage creates a representation of the configuration space that can be easily modified in real time to account for changes in the environment. As with previous approaches, we begin by constructing a graph that represents a roadmap in the configuration space, but we do not construct this graph for a specific workspace. Instead, we construct the graph for an obstacle-free workspace, and encode the mapping from workspace cells to nodes and arcs in the graph. When the environment changes, this mapping is used to make the appropriate modifications to the graph, and plans can be generated by searching the modified graph.

As part of our presentation, we discuss the construction of the roadmap, including how samples of the configuration space may be generated and how to connect the samples to form the roadmap. We then discuss the mapping from the workspace to the roadmap, explaining efficient techniques for its generation and representation. We continue with some robustness measures and how these may be used to enhance the robustness of the roadmap. We then present an extension of our method for mobile robots. Finally, we evaluate an implementation of our approach for serial-link manipulators with up to 20 joints.


Seth Hutchinson received his Ph. D. from Purdue University in West Lafayette, Indiana in 1988. He spent 1989 as a Visiting Assistant Professor of Electrical Engineering at Purdue University. In 1990 Dr. Hutchinson joined the faculty at the University of Illinois in Urbana-Champaign, where he is currently an Associate Professor in the Department of Electrical and Computer Engineering, the Coordinated Science Laboratory, and the Beckman Institute for Advanced Science and Technology.

Dr. Hutchinson is currently a senior editor of the {it IEEE Transactions on Robotics and Automation}. In 1996 he was a guest editor for a special section of the {it Transactions} devoted to the topic of visual servo control, and in 1994 he was co-chair of an IEEE Workshop on Visual Servoing. In 1996 and 1998 he co-authored papers that were finalists for the King-Sun Fu Memorial Best Transactions Paper Award. He was co-chair of IEEE Robotics and Automation Society Technical Committee on Computer and Robot Vision from 1992 to 1996, and has served on the program committees for more than thirty conferences related to robotics and computer vision. He has published more than 100 papers on the topics of robotics and computer vision.


Greg Hager