Ph.D Thesis 2007

Brendan Burns [1]

Exploiting Structure: A Guided Approach to Sampling-Based Robot Motion Planning [2]
[3]
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 vii 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 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.

Advisor: Oliver Brock [4]

back [5]