Past Events

PhD Defense

PhD Defense: Efficient and Asymptotically Optimal Kinodynamic Motion Planning


Download as iCal file

Friday, January 31, 2020, 03:00pm


Speaker: Zakary Littlefield

Location : 1 Spring Street (CAC), Room 403


Kostas Bekris (chair), Jingjin Yu, Abdeslam Boularias, Tim Barfoot (University of Toronto)

Event Type: PhD Defense

Abstract: This dissertation explores properties of motion planners that build tree data structures in a robot’s state space. Sampling-based tree planners are especially useful for planning for systems with significant dynamics, due to the inherent forward search that is performed. This is in contrast to roadmap planners that require a steering local planner in order to make a graph containing multiple possible paths. This dissertation explores a family of motion planners for systems with significant dynamics, where a steering local planner may be computationally expensive or may not exist. These planners focus on providing practical path quality guarantees without prohibitive computational costs. These planners can be considered successors of each other, in that each subsequent algorithm addresses some drawback of its predecessor. The first algorithm, Sparse-RRT, addresses a drawback of the RRT method by considering path quality during the tree construction process. Sparse-RRT is proven to be probabilistically complete under mild conditions for the first time here, albeit with a poor convergence rate. The second algorithm presented, SST, provides probabilistic completeness and asymptotic near-optimality properties that are provable, but at the cost of additional algorithmic overhead. SST is shown to improve the convergence rate compared to Sparse-RRT. The third algorithm, DIRT, incorporates learned lessons from these two algorithms and their shortcomings, incorporates task space heuristics to further improve runtime performance, and simplifies the parameters to more user-friendly ones. DIRT is also shown to be probabilistically complete and asymptotically near-optimal. Application areas explored using this family of algorithms include evaluation of distance functions for planning in belief space, manipulation in cluttered environments, and locomotion planning for an icosahedral tensegrity-based rover prototype that requires a physics engine to simulate its motions.


Department of Computer Science