Kalman filter

from Wikipedia, the free encyclopedia

The Kalman filter (also Kalman-Bucy filter , Stratonovich-Kalman-Bucy filter or Kalman-Bucy-Stratonovich filter ) is a mathematical method for iterative estimation of system parameters on the basis of faulty observations. The filter is named after its discoverers Rudolf E. Kálmán , Richard S. Bucy and Ruslan L. Stratonovich , who independently discovered the process or made significant contributions to it.

The Kalman filter is used to estimate system variables that cannot be measured directly, while the errors in the measurements are optimally reduced. In the case of dynamic quantities, a mathematical model must be added to the filter as a constraint in order to take dynamic relationships between the system quantities into account. For example, equations of motion can help to precisely estimate changing positions and speeds together. The specialty of the filter introduced by Kálmán in 1960 is its special mathematical structure, which enables it to be used in real-time systems in various technical areas. These include u. a. the evaluation of radar signals or GNSS data to determine the position of moving objects ( tracking ), but also the use in ubiquitous electronic control loops in communication systems such as radio or mobile radio or in the control of electric bicycles.

Theoretical classification

In the context of mathematical estimation theory , the Kalman filter is also referred to as a Bayesian minimum variance estimator for linear stochastic systems in state space representation . In engineering, the Kalman filter is also referred to as the optimal filter for linear stochastic systems. See also Bayesian filter .

In contrast to the classic FIR and IIR filters of signal and time series analysis , the Kalman filter is based on state space modeling, in which an explicit distinction is made between the dynamics of the system state and the process of its measurement. In terms of its time behavior, it is an IIR filter with a delay stage.

Historical

Although almost identical procedures had previously been published by Thorvald N. Thiele and Peter Swerling, the filter was named after Rudolf E. Kálmán. At that time, more general non-linear filters by Ruslan L. Stratonovich already existed , which contain the Kalman filter and other linear filters as special cases. Also worth mentioning are preparatory work and joint publications by Kálmán and Richard S. Bucy, especially in the case of continuous-time dynamic systems. Therefore, the term Kalman-Bucy filter and occasionally Stratonovich-Kalman-Bucy filter is used in the specialist literature.

The first significant and successful use of the filter was carried out in Echtzeitnavigations- and control systems, as part of the Apollo program of NASA were developed under the direction of Stanley F. Schmidt.

There is now a wide range of Kalman filters for a wide variety of applications. In addition to the original formulation, these are the extended Kalman filter, the unscented Kalman filter, the information filter and a large number of numerically stable variants such as the root implementation or the Bierman-Thornton UD algorithm. The most widely used variant, however, is the phase control loop derived from control theory , which is used in many telecommunications devices.

Basics

Basic mathematical idea

The special feature that distinguishes the Kalman filter from simple filters such as the moving average and makes it significantly more efficient is the complete description of the estimated value using multi-dimensional normal distributions . These describe not only the probability distribution of possible values ​​around the most probable estimated values, but also the strength of the correlations between different estimation errors. If further measurements are added, the newly made and previous estimates are optimally combined with regard to their errors and correlations so that remaining errors are minimized as quickly as possible. In dynamic systems in which, in addition to the actual values, z. If, for example, speeds or accelerations are estimated, the Kalman filter also estimates correlations between these variables and uses this knowledge together with knowledge of the dynamic relationships for optimal error suppression. The filter status from estimated values, error estimates and correlations forms a kind of memory for all information obtained so far from past measured values. After each new measurement, the Kalman filter improves the estimated values ​​and provides new associated error estimates.

State space modeling

The state of a system is often understood to be the smallest set of determinants that fully describe the system. This is represented as part of the modeling in the form of a multidimensional vector X with a corresponding equation of motion , the so-called equation of state. This equation is often a difference equation , since in many cases the states are only of interest at certain times t k = t 0 + k · Δt with k as a natural number, separated from one another by fixed time intervals Δt . For the sake of a simple notation, it has become common practice to shorten the discrete points in time t k in equations as index k of the relevant quantity, t k-1 as index k-1 , etc. and so on. With this notation and for the special case considered by Kálmán one only linear interdependence of the states simplifies the equation of state to the linear difference equation

.

The matrix F k-1 describes the transitions between temporally successive states X k-1 and X k . In addition to the actual dynamics expressed by the transition matrix F k-1 , the equation of state also models other external influences on the system. A distinction is made between deterministic, i.e. fully determinable, influences and those of a random nature. The deterministic component is represented by the acting disturbance u k-1 and its dynamics in the form of a matrix B k-1 ; the random, non-detectable components by a noise term, the stochastic quantity w k-1 . The temporally uncorrelated noise w k-1 follows a multi-dimensional normal distribution with expected value vector 0 and covariance matrix Q k-1 , in the usual short notation:

.

Due to the unpredictability of the noise term, the state vector also contains a certain amount of “randomness” and is therefore itself a stochastic variable, that is to say a random variable . The set of all state vectors form a special stochastic process , a Markov chain or a Markov model of the first order, i. H. the state at a point in time k depends only on the immediate predecessor in time at k-1 .

The process of observing the true system states X k , X k-1 , ... must reflect the characteristics of the observer or the measuring apparatus. This includes modelable distortions and the unpredictable measurement noise. In the case of the Kalman filter, the distortion is assumed to be linear and the noise to be uncorrelated in time and normally distributed. The corresponding modeling of the measurement process, the observation equation, reads

with the observation matrix H k and the white measurement noise

.

Dynamic noise w and measurement noise v should be independent of one another at all times .

The totality of the state equation and the observation equation is called a state space model. Due to the "hidden" or by a second stochastic process, the measurement covered Markov model is called in state space model also often by a hidden Markowmodell (English Hidden Markov Model ).

The filter problem

A measurement carried out in practice often only results in a single implementation z k of the normally distributed random variable Z k per point in time . The inverse problem now arises , namely being able to draw conclusions about the corresponding X 1 , X 2 , X 3 , X 4 , ... based on the information from a measurement series with the values z 1 , z 2 , z 3 , z 4 , ... Since the desired states remain normally distributed for all times due to the linearity of the model and the assumptions made for the noise terms w and v and a normal distribution is fully described by its mean value and covariance, the filter problem is limited to the estimation of these two determinants. A possible exact solution to this inverse problem is the discrete-time Kalman filter, a set of equations that is, the estimates for the mean value and the covariance of the state

based on the information extracted from the measurement series z k , z k-1 , z k-2 , ..., z 1 .

Often the task arises to solve the filter problem also for time-continuous systems. The difference equations of the state space model are converted into differential equations through a mathematical limit value formation . The equations of the time-continuous Kalman filter result from the time-discrete filter by using the same limit value formation. For this reason and for the sake of an understandable representation, only the equations of the time-discrete filter will be discussed below.

Equations

The estimation of the condition should be based on the knowledge of all previous observations whenever possible. A minimal estimation error is required, which should not be improved by the observations already made. For long series of measurements, the corresponding mathematical minimization problem quickly becomes unwieldy, since the entire series of measurements has to be evaluated for each estimate. The idea on which the Kalman filter is based is now to formulate the estimate at time t k as a linear combination of the previous estimate with the new measured value z k . This is possible because the estimate at time t k-1 contains the information from the measurement series z k-1 , z k-2 , ..., z 1 . This recursive formulation of the estimation problem allows an efficient numerical implementation.

Iterative and recursive algorithm

In the algorithmic implementation, the system state is first initialized with an a priori estimate and the first correction is carried out with the observations. Subsequently, in each further time step k> 0, the prediction and correction are carried out, which alternately propagate the system state over time and correct it with new observations.

 Initialization ( t 0
 

 

Prediction ( t k> 0 )
 

 


Correction ( t k≥0 )
 

 
 

Variables and dimensions

New observations that are available at time t k .
Observation matrix, which maps the n values ​​of the system state to the m observations, so that .
Transition matrix, from the time the system state t k-1 according to the time t k propagated z. B. using equations of motion.
Deterministic disorder.
Dynamics of the deterministic disturbance and projection on the system state.
Process noise, describes additional uncertainties due to modeling errors or changing conditions, usually as a diagonal matrix.
Measurement noise covariance matrix. The matrix can also be non-diagonal when there is correlated noise. However, the noise must not be time-correlated, otherwise the estimated variances are too small, which can lead to inaccurate predictions or even to numerical destabilization. In such cases, the disturbance variable should be added to the system state as an additional component to be estimated, or the covariances should be expanded by suitable terms.
Kalman gain matrix for projecting the residuals onto the correction of the system state.
System state at time t k , which was derived from the state of the previous point in time t k-1 , before the application of the new observations (a priori).
Covariance matrix of the errors from , before application of the new observations (a priori).
System status after applying the new observations (a-posteriori).
Covariance matrix of the errors from after applying the new observations (a-posteriori).

is the number of system status values , the number of measured values ​​and the number of disturbance variables. The dimensions are not necessarily constant, but may be different in each time step , and .

Prediction

In the first step of the filtering process, the previous estimate is subjected to the state dynamics in order to obtain a prediction for the current point in time. For the mean value results

and for the covariance

.

The indexing notation k | k-1 expresses for the state at time t k the conditionality of the estimate by the previous state k-1 . The superscript T denotes the transposed matrix .

correction

The predictions are then corrected with the new information from the current measured value and result in the estimates sought

such as

with the auxiliary variables innovation

,

Residual covariance

and the associated Kalman matrix

.

The auxiliary variable innovation describes how precisely the predicted mean value can describe the current measured value using the observation equation. For a bad prediction, the associated innovation will be big, for an accurate prediction it will be small. Corresponding corrections must then be large or only small. The correction to be made can therefore be seen as proportional to the size of the innovation . In addition, innovations of measured values ​​that are afflicted with greater uncertainty than their estimates should be included in the correction with less weight than those for which the opposite is the case. These properties to be demanded are met by the Kalman matrix as the desired proportionality factor. This becomes from the equivalent wording

can be seen, which, in the context of this rather intuitive approach and thus in a highly simplified manner, can be viewed as the required ratio of the uncertainties of the predictions P k to the associated measurement uncertainties R k . In many cases, the elements of the Kalman matrix can be calculated analytically, that is to say before the start of the estimation process, or at least approximately determined. In less time-critical applications, the Kalman matrix is ​​also estimated; H. recalculated again and again from the current forecast of the covariance during the estimation process.

The exact derivation and justification of the prediction and correction equations usually takes place in the context of probabilistic considerations using Bayes' theorem .

Notes on the continuous time Kalman filter

In the case of continuous time, one no longer speaks of a recursive formulation and also of a predictor-correction structure. Rather, you are dealing with a set of differential equations that describe the estimates of mean and covariance. In order to be able to make statements about the estimate at a certain point in time, the above-mentioned differential equations must be solved. Due to a non-linear term in the covariance equation , the so-called Matrix-Riccati equation , an exact solution and thus an optimal estimate is only possible in a few cases.

initialization

One often uses for the initial estimate

with the identity matrix I and a suitable variance .

properties

As can be seen from the correction equation, the estimate of the mean value depends in a linear manner on the observation, the Kalman filter is therefore a linear filter. As the length of the measurement series increases, the estimates for mean and variance approximate the actual values ​​as precisely as required. In statistical jargon, one speaks of an unbiased and consistent estimator with minimal variance . Because of these estimation properties, which here correspond to a minimization of the mean square error , the Kalman filter is an optimal linear filter. Even generalized nonlinear filters do not provide better results for the linear state space model with normally distributed variables considered here. In contrast to other (recursive) linear estimators, which also minimize error squares, the Kalman filter also allows problems with correlated noise components to be dealt with, as are often encountered in practice.

Applicability and extensions

The prerequisites made when deriving the Kalman filter can often only be approximately fulfilled in practice. In many cases, the exact structure of the linear equation of state and observation is unknown or too extensive to be computationally manageable within the framework of the Kalman filter. The user must therefore restrict the model classes to be used. The associated inaccuracies often lead to a divergent behavior of the filter that deviates from the optimum. Therefore, before use, investigations into the dependence of the estimation results on the modeling errors (and their compensation) are necessary as part of a sensitivity analysis .

The rounding errors caused by the use of digital computing technology lead to a further limitation of the estimation quality . Analogous to the model inaccuracies, these can lead to a drastic divergence of the Kalman filter. This can be remedied by algebraic reformulations ( factorizations ) of the covariance matrices, but at the cost of increased computational effort. The best-known numerically stable variants of the Kalman filter are the root implementation according to Potter et al. and their refinement in the form of the Bierman-Thornton UD algorithm.

In addition to these problems, the Kalman filter cannot be used in many cases because it is limited to linear state space models. Even simple tasks in navigation technology or the important topic of parameter estimation always lead to non-linear state or observation equations. This can be remedied, for example, by non-linear extensions of the Kalman filter such as the Extended Kalman Filter (EKF) developed in the 1960s or the newer Unscented Kalman Filter (UKF). These Kalman filter variants approximate the non-linear problem with a linear one, with the EKF using analytical techniques and the UKF using statistical techniques. In the sense of uncomplicated usage, these extensions are often abbreviated as Kalman filters, since they also have a recursive and a predictor-corrector structure. In contrast to the simple Kalman filter, the Kalman matrix is ​​now a random variable and must be estimated during the entire filter use, which in turn increases the demands on the technology.

Since the emergence of high-performance digital computing technology, most demanding non-linear filter problems have been treated by simulations ( sequential Monte Carlo methods ) or other approximation methods (quadrature filters, Gaussian filters, projection filters).

Sample applications

The Kalman filter is probably the most widely used algorithm for state estimation of linear and non-linear systems today.

  • The Kalman filter has found widespread use in inertial navigation, for example in aircraft: During flight, an inertial measuring unit measures accelerations and rotation rates of the aircraft at high frequencies in order to enable short-term navigation . Further sensors, in particular satellite-based position determination (e.g. GPS ), provide support data. These different measurements must be linked (“merged”) in order to guarantee the best possible estimate of the current position and orientation.
  • Tracking processes and thus the Kalman filter as a typical representative of a tracking filter are increasingly playing a role in the automotive sector. Safety or comfort applications that are based on systems that recognize the surroundings are dependent on reliable information (e.g. position, speed) regarding the objects in their surroundings. In autonomous land vehicles , Kalman filters are used to reduce the noise from lidar and radar devices .
  • Another type of Kalman filter that is also often used, the PLL filter , has now found widespread use in radios, two-way radios, computers and in almost all other types of video and communication devices.
  • In macroeconomics , Kalman filters are used to estimate dynamic-stochastic general equilibrium models ( DSGE models ).
  • In meteorology , they are used for data assimilation when determining the initial state in numerical weather forecasting.

See also

literature

In addition to the articles published by Kálmán and Bucy, there is a large number of other, mainly supplementary and in-depth literature that approach the topic from a mathematical as well as an engineering perspective. An overview of the most important publications is given below.

German-language literature

  • Karl Brammer, Gerhard Siffling: Kalman-Bucy filter: deterministic observation and stochastic filtering . Oldenbourg, Munich / Vienna 1994, ISBN 3-486-22779-3 .
  • Phil Kim: Kalman filters for beginners: with Matlab examples . CreateSpace Independent Publishing Platform, 2016, ISBN 978-1-5027-2378-9 .
  • Reiner Marchthaler, Sebastian Dingler: Kalman filter: Introduction to state estimation and its application for embedded systems . Springer Vieweg, Berlin 2017, ISBN 978-3-658-16727-1 .
  • Jan Wendel: Integrated navigation systems: sensor data fusion, GPS and inertial navigation . Oldenbourg, 2007, ISBN 978-3-486-58160-7 .

English-language literature

  • Analytical Sciences Corp-Technical: Applied Optimal Estimation . Ed .: A. Gelb. 16th edition. MIT Press, Cambridge 2001, ISBN 0-262-57048-3 .
  • Yaakov Bar-Shalom, X. Rong Li, Thiagalingam Kirubarajan: Estimation with Applications to Tracking and Navigation: Theory Algorithms and Software . Wiley & Sons, New York 2001, ISBN 0-471-41655-X .
  • Richard S. Bucy, BG Williams: Lectures on Discrete Time Filtering . Signal processing and digital filtering. Springer-Verlag, New York 1994, ISBN 0-387-94198-3 .
  • Mohinder S. Grewal, Angus P. Andrews: Kalman Filtering Theory and Practice . Prentice-Hall, Upper Saddle River 1993, ISBN 0-13-211335-X .
  • Dan Simon: Optimal State Estimation: Kalman, H Infinity, and Nonlinear Approaches . Wiley-Interscience, Hoboken 2006, ISBN 0-471-70858-5 .
  • Robert Groover Brown, Patrick YC Hwang: Introduction to Random Signals and Applied Kalman Filtering . Wiley & Sons, New York 1997, ISBN 0-471-12839-2 .

Web links

Individual evidence

  1. ^ RE Kalman: A New Approach to Linear Filtering and Prediction Problems (=  Transaction of the ASME, Journal of Basic Engineering ). 1960, p. 35–45 ( unc.edu [PDF; accessed March 24, 2017]).
  2. Steffen L. Lauritzen: Thiele: Pioneer in Statistics. ( Memento of October 13, 2008 on the Internet Archive ) Oxford University Press , 2002, ISBN 0-19-850972-3 .
  3. ^ RL Stratonovich: Optimum nonlinear systems which bring about a separation of a signal with constant parameters from noise . Radiofizika, 1959, 2: 6, pp. 892-901.
  4. ^ RL Stratonovich: Application of the Markov processes theory to optimal filtering . Radio Engineering and Electronic Physics, 1960, 5:11, pp. 1-19.
  5. Simon J. Julier, Jeffrey K. Uhlmann and HF Durant-Whyte: A new approach for filtering nonlinear systems . Proceedings of the 1995 American Control Conference, 1995, pp. 1628-1632.
  6. Simon J. Julier and Jeffrey K. Uhlmann: A new extension of the Kalman filter to nonlinear systems . In: Int. Symp. Aerospace / Defense Sensing, Simul. and controls . 1997.
  7. JE Potter and RG Stern: Statistical filtering of space navigation measurements . Proc. of AIAA, Guidance and Control Conf, 1963.
  8. Jump up ↑ GJ Bierman and CL Thornton: Numerical Comparison of Kalman Filter Algorithms: Orbit Determination Case Study . Automatica 13, 23, 1977.
  9. A. Patapoutian: On phase-locked loops and Kalman filters . IEEE Transactions on Communications, Volume 47, Issue 5, May 1999, pages 670-672.
  10. Gelb et al .: Applied Optimal Estimation . The MIT Press, 2001, p. 119 ff.
  11. RH Shumway, DE Olsen and LJ Levy: Estimation and Tests of Hypotheses for the Initial Mean and Covariance in the Kalman Filter Model . Commun. Stat. Theory Meth, 1981.
  12. A good overview and detailed explanations can be found for example in Least-Squares estimation: from Gauss to Kalman by HW Sorenson (IEEE Spectrum, Vol. 7, pages 63-68, July 1970).

Remarks

  1. The use of language for the term state space model is not uniform in the literature. In control engineering, it means the mere modeling of the state dynamics, in time series analysis, on the other hand, the totality of state and observation equations is referred to as a state space model.
  2. An exact formulation by means of an explicit consideration of the matrix elements should be omitted for reasons of space and clarity. More details can be found in Gelb et al .: Applied Optimal Estimation .