Exploiting structure: A guided approach to sampling-based robot motion planning

2007 2007

Other formats: Order a copy

Abstract (summary)

Robots already impact the way we understand our world and live our lives. However, their impact and use is limited by the skills they possess. Currently deployed autonomous robots lack the manipulation skills possessed by humans. To achieve general autonomy and applicability in the real world, robots must possess such skills. Autonomous manipulation requires algorithms that rapidly and reliably compute collision-free motion for robotic limbs with many degrees of freedom. Unfortunately, adequate algorithms for this task do not currently exist. Though there are many dimensions of the real-world planning task that require further research. A central problem of reliable real-world planning is that planners must rely on incomplete and inaccurate information about the world in which they are planning. The motion planning problem has exponential complexity in the robot's degrees of freedom. Consequently, the most successful planning algorithms use incomplete information obtained via sampling a subset of all possible movements. Additionally, real-world robots generally obtain information about the state of their environment through lasers, cameras and other sensors. The information obtained from these sensors contains noise and error. Thus the planner's incomplete information about the world is possibly inaccurate as well. Despite such limited information, a planner must be capable of quickly generating collision free motions to facilitate general purpose autonomous robots.

This thesis proposes a new utility-guided framework for motion planning that can reliably compute collision-free motions with the efficiency required for real-world planning. The utility-guided approach begins with the observation there is regularity in space of possible motions available to a robot. Further, certain motions are more crucial than others for computing collision free paths. Together these observations form structure in the robot's space of possible movements. This structure provides a guide for the planner's exploration of possible motions. Because a complete understanding of this structure is computationally intractable, the utility-guided framework incrementally develops an approximate model discovered by past exploration. This model of the structure is used to select explorations that maximally benefit the planner. Information provided by each exploration improves the planner's approximation. The process of incremental improvement and further guided exploration iterates until an adequate model of configuration space is constructed. Discovering and exploiting structure in a robot's configuration space enables a utility-guided planner to achieve the performance and reliability required by real-world motion planning.

This thesis describes applications of the utility-guided motion-planning framework to multi-query sampling-based roadmap and random-tree motion planning. Additionally, the utility-guided framework is extended to develop a planner that can successfully plan despite inaccuracies in its perception of the environment and to guide further sensing to reduce uncertainty and maximally improve the utility of the path.

Indexing (details)

Computer science
0771: Robots
0984: Computer science
Identifier / keyword
Applied sciences; Motion planning; Robot motion
Exploiting structure: A guided approach to sampling-based robot motion planning
Burns, Brendan
Number of pages
Publication year
Degree date
School code
DAI-B 68/07, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
Brock, Oliver
University of Massachusetts Amherst
Computer Science
University location
United States -- Massachusetts
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.