This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/20748
Description
Title
Incremental geometric robot motion planning
Author(s)
Barbehenn, Michael Tracy
Issue Date
1996
Doctoral Committee Chair(s)
Hutchinson, Seth A.
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
