"Sketch"-based motion planning

This work aimed to create a path planner for car-like nonholonomic vehicles. The planner "constructs" a solution by stringing together a sequence of known "motion sketches", or parts thereof, into a trajectory that satisfies all global constraints. Sketches are rough motion outlines, possibly parametrized, and have a corresponding controller capable of then executing that particular motion. This is meant to be a local planner, hence one of its inputs is a rough, kinematic path plan, which it will then attempt to roughly follow, system dynamics permitting.

Algorithm operation can be summarized as:

• try to advance along suggested global path as far as possible using a single sketch in its repertoire
• repeat until either goal reached or until cannot advance further from current point using any of the sketches
• in the latter case, backtrack and use alternate sketches at earlier point, ones that do not advance as far but possibly give more freedom later on
• once goal reached in this fashion, smooth out any discontinuities between sketch endpoints

Images: upper-left shows a sample "motion sketch repertoire" for a car, while at bottom we see a sample intermediate (i.e., unsmoothed) solution; right hand side shows different solutions.