Sampling-Based Motion Planning with Differential Constraints

Kinodynamic and nonholonomic planning problems have differential constraints which restrict admissible velocities and accelerations of robotic systems. Since these differential constraints are ignored in the path planning process, solutions from classical decoupled methods could be either inexecutable or inefficient. Motion planning with differential constraints (MPD), which directly considers differential constraints, provides a promising direction to calculate reliable and efficient solutions. A large amount of recent efforts on MPD have been devoted to various sampling-based algorithms, which iteratively build search graphs using sampled states and controls to construct solutions. This thesis addresses several issues in analysis and design of these sampling-based MPD algorithms. In algorithm analysis, resolution completeness of sampling-based path planning algorithms is extended to sampling-based MPD algorithms and the first quantitative sufficient conditions are provided. The analysis is based on the relationship between the reachability graph, which is an intrinsic graph representation of a given problem, and the search graph, which is built incrementally by the algorithm. Because of control space sampling, state space sampling, and other complications in algorithms, there exist mismatches between these two graphs. If there is a path that encodes a solution in the reachability graph, a resolution complete MPD algorithm must construct a solution path that encodes the solution or its approximation in the search graph in finite time. In algorithm design, a symmetry-based gap reduction algorithm is designed and combined with sampling-based methods to solve the gap problem in their solution paths. Gaps are discontinuities between trajectories associated with edges in the search graph and could cause these methods to take enormous or even infinite time to return a high quality solution trajectory whose final state is in a small neighborhood of a goal state. The proposed method quickly obtains high quality solutions using the gap reduction algorithm to minimize big gaps in solution path candidates. The minimization is greatly accelerated using symmetry of the system to avoid computationally expensive numerical integration. Secondly, a heuristic is designed to solve metric sensitivity of RRT-based MPD methods, which means that, under differential constraints, RRT-based methods have difficulties in escaping local minima when the given metric provides a poor approximation of the true cost-to-go. Instead of designing a computationally expensive and system-specific metric, the heuristic is obtained by collecting collision information in the planning process and assigning a real value to each node in the search graph. A node with a higher value means that the number of trajectories from the state of the node that have been detected in collision is larger. Local minima are more likely to be avoided when nodes with smaller values are given higher probability to be extended