Efficient and asymptotically optimal kinodynamic motion planning

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 per- formed. 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 sub- sequent 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.Ph.D.Includes bibliographical reference