Files in this item



application/pdf9625112.pdf (7MB)Restricted to U of Illinois
(no description provided)PDF


Title:Incremental geometric robot motion planning
Author(s):Barbehenn, Michael Tracy
Doctoral Committee Chair(s):Hutchinson, Seth A.
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
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.
Issue Date:1996
Rights Information:Copyright 1996 Barbehenn, Michael Tracy
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9625112
OCLC Identifier:(UMI)AAI9625112

This item appears in the following Collection(s)

Item Statistics