Files in this item
|(no description provided)|
|Title:||Incremental geometric robot motion planning|
|Author(s):||Barbehenn, Michael Tracy|
|Doctoral Committee Chair(s):||Hutchinson, Seth A.|
|Department / Program:||Computer Science|
|Degree Granting Institution:||University of Illinois at Urbana-Champaign|
|Abstract:||In this thesis we introduce the notion of incremental problems in geometric robot motion planning, and give incremental algorithms to solve these problems efficiently. In particular, we present incremental algorithms to compute an exact cell decomposition of the collision-free portion of the robot configuration space for a line segment robot moving freely in the plane amidst polygonal obstacles. After computing an initial decomposition of the collision-free portion of the robot configuration space, these algorithms maintain that decomposition as obstacles are moved between planning problems.
Typically, the cost to maintain the decomposition is much smaller than the cost to construct the initial decomposition. Because of this, the relative cost to perform a global search in the connectivity graph in the decomposition is high. Therefore the all-pairs shortest paths trees in the connectivity graph of the decomposition is incrementally maintained, which facilitates rapid access to solution paths without the need for search.
At the heart of the approach is a study of both the geometric and topological changes that occur to the collision-free portion of the robot configuration space when obstacles in the robot's environment are moved. We believe that this study provides insight into the more difficult problems of planning with multiple moving obstacles (outside the control of the robot) and planning with movable objects (that the robot manipulates). In particular, most past methods for these difficult problems use composite configuration spaces, which represent the simultaneous positions of all obstacles that may move. Since geometric robot motion planning is PSPACE-hard, these approaches do not scale. Instead, our approach leads to solutions for these more difficult problems that manipulate the much lower dimensional robot configuration space.
|Rights Information:||Copyright 1996 Barbehenn, Michael Tracy|
|Date Available in IDEALS:||2011-05-07|
|Identifier in Online Catalog:||AAI9625112|