SUMMARY

This work considers the application of motion primitives to path planning and obstacle avoidance problems in which the system is subject to significant parametric and/or initial condition uncertainty. In such problems, optimal path planning is achieved by minimizing the expected value of a cost function subject to probabilistic (chance) constraints on vehicle-obstacle collisions. The Koopman operator provides an efficient means to compute these expected values. A generalization of motion primitives that leverages this Koopman approach is devised, and the resulting planning problem is cast as a chance-constrained Markov Decision Process (CCMDP). One way to obtain single-query solutions to CCMDPs is by searching the And/Or hypergraph representing the state-action space of the system. An induced heuristic for state-action pairs is described that can be rapidly computed by leveraging the properties of motion primitives; its value can be used to prioritize AND nodes for more efficient search. Shared symmetry in constraints and dynamics is leveraged to move almost all computation necessary to enforce convex polytope constraints offline. The key bottleneck is identified as the expected value calculation, which is a high dimensional integral. One way to accelerate such calculations is through the use of a "sparse" numerical integration scheme. A method is described for obtaining maximally sparse numerical integration schemes for use with hypergraph search algorithms. The approach formulates a mixed-integer linear program that is tailored to the specific structure of the hypergraph on which chance-constrained motion primitive planning problems are solved. Finally, the effectiveness of Monte Carlo Tree Search and Lazy constraint enforcement is investigated.