{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/20748"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/20748","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Incremental geometric robot motion planning","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Barbehenn, Michael Tracy"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Hutchinson, Seth A."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:48:07Z","date_published":"2011-05-07T12:48:07Z","updated_at":"2026-07-22T22:25:16Z","subjects":["Computer Science"],"languages":["eng"],"rights":["Copyright 1996 Barbehenn, Michael Tracy"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9625112","(UMI)AAI9625112"],"render_values":[{"text":"AAI9625112","href":null,"code":true},{"text":"(UMI)AAI9625112","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/20748","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Hutchinson, Seth A."]},{"key":"dc:creator","label":"Author","values":["Barbehenn, Michael Tracy"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:48:07Z","10000-01-01","1996"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1996 Barbehenn, Michael Tracy"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9625112","(UMI)AAI9625112","http://hdl.handle.net/2142/20748"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2011-05-07T12:48:07Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9625112.pdf: 7024944 bytes, checksum: b23a5ce3cf9ff50cf8cb717b97563179 (MD5) Previous issue date: 1996","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:46:00Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:20:29-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Incremental geometric robot motion planning"]}]}],"canonical_facts":{"dc:contributor":["Hutchinson, Seth A."],"dc:creator":["Barbehenn, Michael Tracy"],"dc:date":["2011-05-07T12:48:07Z","10000-01-01","1996"],"dc:description":["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.","Made available in DSpace on 2011-05-07T12:48:07Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9625112.pdf: 7024944 bytes, checksum: b23a5ce3cf9ff50cf8cb717b97563179 (MD5) Previous issue date: 1996","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:46:00Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:20:29-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9625112","(UMI)AAI9625112","http://hdl.handle.net/2142/20748"],"dc:language":["eng"],"dc:rights":["Copyright 1996 Barbehenn, Michael Tracy"],"dc:subject":["Computer Science"],"dc:title":["Incremental geometric robot motion planning"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:16Z"}