Computing Optimal Motion Primitives for State Lattices

A set of motion primitives t-span a state lattice if, given a real number t greater or equal to one, any configuration in the lattice can be reached via a sequence of motion primitives whose cost is no more than t times the cost of the optimal path to that configuration. Determining the smallest set of t-spanning motion primitives allows for quick traversal of a state lattice in the context of robotic motion planning, while maintaining a t-factor adherence to the theoretically optimal path. Our previous research has shown that the problem of computing a minimal set of t-spanning motion primitives is, for a general lattice, NP-complete but that this is not true for a two dimensional any-angle Euclidean lattice. Our current research focuses on determining a set of criteria for a state lattice under which the problem can be computed efficiently. 

We are investigating a wide variety of applications for t-spanning primitives including determining a set of motion primitives for autonomous driving given human driving data and for robotic manipulators.

As a second component of this project, we are developing efficient methods for computing robot motions that can be used as primitives.  The key idea is to generate trajectories where the curvature, derivative of curvature, and angular jerk of the curve are all bounded.