This thesis develops a low-cost grid-based path planner that intrinsically supports smooth, curved vehicle dynamics. There are many advantages to grid-based planners, including working natively in the digital space of most sensors, and efficiency in low dimensional space. However, discrete planners create jaggedness in most paths. Further, the dimensionality must be limited for efficiency, usually by limiting vehicle steering angles to a small finite set.

The algorithm presented here, Waypoint-A*, extends A* to produce low-cost curved trajectories, taking the dynamics of the vehicle into account explicitly post-planning. Considering the path generated by A* as composed of a set of waypoints, Waypoint-A* calculates the minimum-cost heading on a continuum, to direct the vehicle to the waypoint at the location resulting in the lowest total cost. Smoothness of these curves is invariant to terrain resolution and computation.