Get ready, get set, race! Position and orientation data for autonomous navigation

GPS World, Sept, 2006 by William "Red" Whittaker, Louis Nastro

Position estimation is critical to map fusion and map fusion is critical to the robustness of the navigation system, enabling the latter to cope with sensor failures and missing data. To use the data from the various sensor-processing algorithms, we needed to combine it into a composite world model (either implicitly or explicitly).

Sensor fusion generates a composite map using a weighted average of each of the input maps, each registered using position estimation. Each of the processing algorithms specifies a confidence for the output map it generates. The fusion algorithm then combines the maps with these weightings to generate the composite expected cost map. This design allows the sensor processing algorithms to adjust their contribution to the composite map if they recognize that they are performing poorly. In practice, a set of static weights, based on a heuristic sense of confidence in the algorithm's ability to accurately assess the safety of terrain, worked well. With calibrated sensors, and with good position data, this approach produces usable composite terrain models. FIGURE 3 shows various input maps and the resulting, fused composite map.

Planning and Driving

Pure pursuit tracking means following a predetermined path set by the team and based on data provided by DARPA prior to race time. It uses POS LV data in conjunction with the vehicle's drive-by-wire system--integrated electronically assisted control devices that actuate hydraulics, servos, and other steering management components without the use of mechanical linkages. Pure pursuit tracking ensures waypoints are reached within the programmed speed/time parameters. Accurate path tracking depends on vehicle position and dynamics. The pure pursuit path tracking algorithm uses the information provided by the POS, which ensures that the maximum speed and curve apex trajectory is within the constraints of the vehicle's performance so as to not allow it to skid or veer off course. Unprocessed DARPA waypoints produce straight path segments through the entire course, including through corners. By detailing the curve apex trajectory, we can achieve maximum speed into and out of the corner, as well as a safer path. Given the number of curves in the course, this time saving is significant.

Trajectory planning algorithms attempt to find an optimal path from a starting point to a goal point. Many approaches have been developed to solve various planning problems. The most popular are deterministic, heuristic-based algorithms, and randomized algorithms. Some work has been done to set speeds and curvatures reactively. In general, the search space for a mobile robot is large, so search is computationally expensive. Deterministic searches typically sample the search space at a resolution that allows for a fast search, but decreases efficiency of solutions. Randomized algorithms do not sample the search space, but tend to generate somewhat random trajectories.

In the Grand Challenge, a prescribed route consisting of a centerline with a set of bounds was provided to teams just before race time. Although the bounds and centerline were only intended to simply keep vehicles near terrain that DARPA desired the vehicles to traverse, we made use of this information to significantly improve planning speeds.