Before too long, we will be relieved of the burden of long-distance driving. Given the desired destination and access to a mapping system, electronic control and navigation algorithms will select the best route and control the autonomous vehicle, constantly monitoring and adjusting its direction and speed of travel. The origins of the methods used for autonomous navigation lie in the early 1960s, when the space race triggered by the Russian launch of Sputnik I was raging.
In 1960 Rudolph Kalman published a paper describing an algorithm that was particularly suited to the needs of space research. It provided an almost ideal method to calculate the velocity changes for mid-course corrections during lunar missions.
The discovery of Kalman's filter by Nasa was fortuitous. Kalman presented his work at the Ames Research Center, and its relevance to space research was immediately grasped. Its first major application was for guidance of the Apollo lunar mission.
The system for Apollo needed to run on small space-borne computers. It had to be highly efficient in guiding the spacecraft through injection to a trajectory around the Moon and back to Earth. The spacecraft location could be measured by on-board observations and by radar detection from Earth.
But observational data are incomplete, intermittent and inaccurate: errors are inevitable. The idea of the Kalman filter is to combine the best estimate of the current position and speed with new observations to produce a better estimate. Occasional mid-course corrections, required to keep the mission on target, could then be calculated.
Kalman originally developed his filter for linear problems. The lunar navigation problem is highly non-linear. When the Nasa scientists combined Kalman’s linear filter with the perturbation methods already under study at Ames, they produced a solution – the extended Kalman filter – for the nonlinear navigation problem. Numerical instability problems were overcome by an improved formulation, the square root filter. This method was used with success in the Apollo programme and in many subsequent programmes, including navigation and guidance of the Space Shuttle.
On the road again
To operate an autonomous vehicle (AV), GPS signals are used to determine its location. A high-fidelity mapping system is also essential. Raw observations must be converted to determine the state of the AV – that is, its position, speed and direction of travel. Radar and laser echoes are used to analyse the immediate neighbourhood of the AV so as to anticipate hazards.
The aim of the system is to iteratively update the AV state without recalculation from scratch. One of the most powerful algorithms for controlling AVs is the Kalman filter. Its recursive least-squares minimisation algorithm comprises two stages.
In the prediction stage, the dynamical laws of motion are used to predict the state a short time ahead, based on the current estimated position. In the update stage, new measurement data are combined with the predicted state to obtain a better estimate of state and uncertainty.
Information on the current state the location and speed of the AV is projected a short time ahead to predict a future state, perhaps one second later. The level of accuracy of this prediction is also estimated. New observational data are then combined with the predicted state to calculate a better estimate of it. This alternating prediction-correction cycle is repeated.
The predicted state and observations are weighted according to their confidence levels to optimise the estimates of position and speed. At each stage, the steering angle and throttle and brake settings needed to keep the vehicle on course are applied.
Peter Lynch is emeritus professor at the UCD school of mathematics and statistics. He blogs at thatsmaths.com