|Volume 21 Issue 12 - Publication Date: 1 December 2002
|A Framework for Real-Time Path
Planning in Changing Environments
|Peter Leven and Seth
Hutchinson Electrical and computer Engineering, The Beckman Institute,
University of Illinois, Urbana, IL 61801
|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, thus facilitating
real-time planning. 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.
|In this paper, we first discuss
the construction of the roadmap, including how random samples of the configuration
space are generated using an importance sampling approach and how these
samples are connected to form the roadmap. We then discuss the mapping from
the workspace to the configuration space roadmap, explaining how the mapping
is generated and how it can be encoded ef- ficiently using compression schemes
that exploit redundancy in the mapping. We then introduce quantitative robustness
measures and show how these can be used to enhance the robustness of the
roadmap to changes in the environment. Finally, we evaluate an implementation
of our approach for serial-link manipulators with up to 20 joints.