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 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 [TM214 or search for “thatsmaths” at irishtimes.com].
To the Moon and Back
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 work by NASA was fortuitous. Kalman presented his work at the Ames Research Center and its relevance to space research was immediately grasped. The first major application of Kalman filtering 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 program and in many subsequent programs, 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 can be used to analyse the immediate neighbourhood of the AV so as to anticipate hazards.
Kalman filter combines an uncertain prediction of position (blue) with imperfect observational data (red) to produce an optimal solution together with its uncertainty (magenta).
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 minimization algorithm comprises two stages. In the prediction stage, the dynamical laws of motion are used to pedict 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 optimize the estimates of position and speed. At each stage, the steering angle and throttle and break settings needed to keep the vehicle on course are applied.
Sources
Brooks, C.G., J. M. Grimwood and L. S. Swenson, 1979: Chariots for Apollo: A History of Manned Lunar Spacecraft. The NASA History Series (NASA SP-4205), National Aeronautics and Space Administration.
Web tutorial on Kalman Filter: https://www.kalmanfilter.net/
* * * * *
That’s Maths II: A Ton of Wonders
by Peter Lynch now available.
Full details and links to suppliers at
http://logicpress.ie/2020-3/
>> Review in The Irish Times <<
* * * * *
ThatsMaths 