Skip to Main Content
 

Global Search Box

 
 
 
 

ETD Abstract Container

Abstract Header

Sampling-based Motion Planning Algorithms: Analysis and Development

Wedge, Nathan Alexander

Abstract Details

2011, Doctor of Philosophy, Case Western Reserve University, EECS - Electrical Engineering.

Robotic motion planning, which concerns the computation of paths and controls that drive an autonomous agent from one configuration to another, is quickly becoming a vitally important field of research as its applications diversify and become increasingly public. Many algorithms have been proposed to deal with this central problem; sampling-based approaches like the Rapidly-exploring Random Tree (RRT) and Probabilistic Roadmap Method (PRM) planners are among the most successful. Still, these algorithms are not fully understood and suffer from pathologically poorly-performing instances resulting from the contributions of random sampling and qualitative obstacle features like narrow passages. The large means and variances that result from these issues continue to motivate the development of new algorithms and adaptations to increase consistency and to allow more difficult problems to be solved.

This research examines these performance issues with a focus on the Rapidly-exploring Random Tree (RRT) planner. Fundamental analysis establishes that the interaction of its Voronoi bias with particular obstacle features can compromise its efficacy and illustrates the types of distributions on its performance that result. It further provides guidance on the types of problems amenable to solutions by the algorithm and on the use of its alternative EXTEND and CONNECT heuristics and step size parameter. Observations from this analysis prompt an investigation of the use of restart strategies to manage issues of both scaling in computation and exploratory missteps. In turn, their impact provides a foundation for the introduction of a novel algorithm, the Path-length Annexed Random Tree (PART) planner, that directs its exploration on a local basis. This algorithm and its environment-adaptive successor, the Adaptive PART (APART) planner, demonstrate competitive performance on instructive examples and dramatic improvements on difficult benchmarks, while also supplementing their utility with the output of a connected roadmap.

Michael Branicky, PhD (Committee Chair)
M. Cenk Çavuşoğlu, PhD (Committee Member)
Wyatt Newman, PhD (Committee Member)
Soumya Ray, PhD (Committee Member)
172 p.

Recommended Citations

Citations

  • Wedge, N. A. (2011). Sampling-based Motion Planning Algorithms: Analysis and Development [Doctoral dissertation, Case Western Reserve University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=case1301502703

    APA Style (7th edition)

  • Wedge, Nathan. Sampling-based Motion Planning Algorithms: Analysis and Development. 2011. Case Western Reserve University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=case1301502703.

    MLA Style (8th edition)

  • Wedge, Nathan. "Sampling-based Motion Planning Algorithms: Analysis and Development." Doctoral dissertation, Case Western Reserve University, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=case1301502703

    Chicago Manual of Style (17th edition)