When it isn’t crashing into trash cans, Savage Solder uses a combination of several sensors to form accurate estimates about where it is in the world. This series describes the sensors and techniques that it uses to identify where it is in the world, providing data that is useful for the driving and cone tracking subsystems.

Principles

First, why does the car need to know where it is? Several other subsystems in Savage Solder rely on having accurate estimates of where the car is, measured in different ways. First, when driving to try and find a cone, it follows a path surveyed by GPS. In that case, the driving algorithm needs to know where the car is relative to the pre-surveyed path in order to select the appropriate steering and throttle commands. Here, absolute accuracy is most useful. We rely on surveyed paths to avoid obstacles, and the driving algorithm is relatively insensitive to position estimates that move around as GPS measurements change.

When moving in proximity to cones, the car needs a locally stable coordinate system in order to identify where the cone is relative to the car itself. For this, an estimate that is smooth is most important, as the car’s position relative to a cone can only change in a continuous manner.

For both of these cases, the localization subsystem on Savage Solder takes measurements from various sensors, and produces an estimate of the current position of the car. This estimate is updated on a regular basis, and fed to each other subsystem which needs to know where the car is.

Estimation

At the top level, Savage Solder uses a total-state unscented Kalman filter to incorporate measurements and produce localization estimates. Kalman filters are a class of algorithms which, given a series of noisy measurements of a system, estimate what the internal state variables the system are. In the localization problem, the noisy measurements are things like a GPS reading, a gyroscope measurement, or the value from an odometer, while the estimated state is perhaps the latitude and longitude of the vehicle along with its heading, heading rate and speed.

The Unscented Kalman filter is just one type of estimation algorithm. Traditionally, a designer would select it over other non-linear estimators when higher accuracy is required. As compared to estimators like the Extended Kalman Filter, it achieves this higher accuracy through an increase in computational cost.

For Savage Solder, our PC based computer platform has power to spare, so we chose the unscented Kalman filter (UKF) for a different reason. We used the UKF because it only requires numerical system models. Most non-linear Kalman filters, like the EKF, require analytical derivations of the partial derivatives of the system and measurement functions. These can be involved to create. When you want to change your design, and modify the estimated states or measurement variables, the process is slow and error prone. The UKF only requires a numerical definition of the system and measurement functions themselves. Because of this, we can experiment with different filter structures much more rapidly.

Next Installment

In the next installment, I’ll look in more detail at the measurements we use, and the states that we estimate.