Toward Real-Time Motion Planning in Changing Environments

摘要

We present a new method for generating collisionfree paths for robots operating in changing environ­ ments. Our approach is closely related to recent prob­ abilistic roadmap approaches. These planners use pre­ processing and query stages, and are aimed at plan­ ning many times in the same environment. In con­ trast, 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 spe­ cific 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.