ACS6124 Multisensor and Decision Systems Part I: Multisensor Systems
Lecture 7: Dynamic Sensor Fusion
George Konstantopoulos g.konstantopoulos@sheffield.ac.uk
Automatic Control and Systems Engineering The University of Sheffield
(lecture notes produced by Dr. Inaki Esnaola and Prof. Visakan Kadirkamanathan)
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Target Tracking
Example: Vehicle tracking, pedestrian surveillance, incipient fault monitoring
Target object position and velocity are: st , vt .
The object motion can be described by constant velocity model:
The sensor measurement is the position (e.g., camera) with sampling interval ∆t.
sk yk= 1 0 v +ek
k
ek is sensor measurement noise, k is the sampling instant.
The state space model is suitably discretised as:
sk+1 1 ∆t sk 0.5∆t2
s ̇t 0 1 st 0 v ̇ = 0 0 v + w
ttt wt is the random acceleration noise term.
v = 0 1 v + ∆t wk k+1 k
Target tracking is now a state estimation problem – Kalman filter.
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Dynamical Signal Model
A simple signal model which allows correlation between samples is given by the following dynamical or state model:
Definition of First Order Gauss-Markov Process
A first order Gauss-Markov process if given by
xt =axt−1+wt fort≥0
where wt ∼ N(0,σw2 ), x0 ∼ N(μx ,σx2), and x0 is independent of wt for all t ≥ 0. Description of parameters:
wt is the driving term or excitation disturbance: xt can be viewed as the output of a linear time-invariant system driven by wt .
In control literature the system is the plant and wt is the plant noise
The state of the system at time t0 and the inputs {wt}t≥t0 determine the output
of the system for t ≥ t0, i.e. {xt }t≥t0 Stability of the process requires |a| ≤ 1
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Scalar Dynamical Signal Model
Recall the first order Gauss-Markov model:
xt =axt−1+wt fort≥0
Consider the observation model given by:
yt = xt + vt
where
wt ∼ N(0,σw2 ), vt ∼ N(0,σv2), x0 ∼ N(μx ,σx2) (derivation assuming μx = 0) Assumethatx0,wt,andvt areallindependent
Aim of Kalman Filter:
MMSE estimator of xt based on observations y1,y2,··· ,yt (filtering) Estimation xˆt written as a function of xˆt−1 (recursive)
Note that the estimate is given by xˆt =△ xˆt|k =f(y1,y2,…,yk) Optimality criterion: Bayesian MSE given by
BMSExˆt|t=Ext −xˆt|t2 where the expectation is taken with respect to Py1 ,y2 ,··· ,yt ,xt
The MMSE estimate based on observation y = [y1,y2,··· ,yt ] is given by xˆ =E[x |y ,y ,···,y ]=Σx yΣ−1y
t|t t12 t tyy since xt and y1,y2,··· ,yt are jointly Gaussian.
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Scalar Kalman Filter
Innovation is the part of the observation that is uncorrelated with the previous observations (error is orthogonal to observation):
y ̃ t = y t − yˆ t | t − 1
Notice that yt−1 = [y1,y2,··· ,yt−1] and y ̃t together contain the same information
as yt since yt can be recovered as
y t = y ̃ t + yˆ t | t − 1
t−1
= y ̃ t + ∑ a k y k
k=1
where {ak } are the optimal MMSE weighting coefficients
Therefore
xˆt|t =E[xt|yt−1,y ̃t] and because yt−1 and y ̃t are uncorrelated
xˆt|t =E[xt|yt−1]+E[xt|y ̃t]
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Scalar Kalman Filter
Recall:
Evaluating xˆt|t−1 yields
xˆt|t =E[xt|yt−1]+E[xt|y ̃t]
xˆ t | t − 1
xˆt|t−1 = E[xt |yt−1]
= E[axt −1 + wt |yt −1 ]
=E[axt−1|yt−1]+E[wt|yt−1]=axˆt−1|t−1
=0
This results in
xˆt|t =axˆt−1|t−1+E[xt|y ̃t]
Evaluating E[xt |y ̃t ] consists on computing MMSE estimator of xt given y ̃t .
Because of linearity and zero mean assumption: E[xt|y ̃t]=Kty ̃t =Kt yt −yˆt|t−1
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Scalar Kalman Filter
Recall:
with Kt computed from definition of MMSE estimator for jointly Gaussian xt and
E[xt|y ̃t]=Kty ̃t =Kt yt −yˆt|t−1 K t = E [ x t y ̃ t ]
y ̃t , that is:
Notice that since yt = xt + vt and using the linearity of expectation
Therefore
In summary:
E [ y ̃ t 2 ]
yˆt|t−1 = xˆt|t−1 +vˆt|t−1 = xˆt|t−1
=0
E [ x t | y ̃ t ] = K t y t − xˆ t | t − 1
xˆt|t =E[xt|yt−1]+E[xt|y ̃t]
= a xˆ t − 1 | t − 1 + K t y t − xˆ t | t − 1 = a xˆ t − 1 | t − 1 + K t y t − xˆ t | t − 1
Evaluation of Kt remains
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Scalar Kalman Filter
Recall:
Kt = E[xty ̃t] = E[xt(yt −xˆt|t−1)] E[y ̃t2] E[(yt −xˆt|t−1)2]
Evaluation of numerator of Kt :
E[xt(yt −xˆt|t−1)]=E[xty ̃t]
= E[xt y ̃t ] − E[(xˆt |t −1 )y ̃t ]
=0 =E[(xt −xˆt|t−1)y ̃t]
= E[(xt −xˆt|t−1)(yt −xˆt|t−1)] E[(yt −xˆt|t−1)2]=E[(xt −xˆt|t−1+vt)2]
=E[(xt −xˆt|t−1)2]+E[vt2]+2E[(xt −xˆt|t−1)vt)]
Evaluation of denominator of Kt :
= E[(xt −xˆt|t−1)2]+σv2
=0
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Scalar Kalman Filter
Therefore
K t = E [ x t y ̃ t ] E [ y ̃ t 2 ]
= E[(xt −xˆt|t−1)(yt −xˆt|t−1)] E[(xt −xˆt|t−1)2]+σv2
= E[(xt −xˆt|t−1)2] E[(xt −xˆt|t−1)2]+σv2
Noting that E[(xt −xˆt|t−1)2] is the MSE of estimating xt given y1,y2,…,yt−1 and
denoting it by Pt|t−1 yields
Operating the MSE terms the following two properties can be verified:
Pt|t−1 = a2Pt−1|t−1 +σw2 Pt|t =(1−Kt)Pt|t−1
Kt = Pt|t−1
P t | t − 1 + σ v2
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Scalar Kalman Filter
Scalar Kalman Filtering Procedure
INITIALIZATION: xˆ 0 | 0 = μ x
P 0 | 0 = σ x2 PROCEDURE:
1
2
3
4
5
Prediction:
Minimum Prediction MSE:
xˆt|t−1 = axˆt−1|t−1 Pt|t−1 = a2Pt−1|t−1 +σw2
Kalman Gain:
Pt|t−1
σ v2 + P t | t − 1
Correction:
Minimum MSE:
xˆt|t = xˆt|t−1 +Kt yt −xˆt|t−1 Pt|t =(1−Kt)Pt|t−1
Kt =
ACS6124 Multisensor and Decision Systems
G. Konstantopoulos
Properties of Scalar Kalman Filter
The Kalman filter extends the sequential MMSE estimator to the case where the signal model is dynamic
No matrix inversion is required: Low complexity implementation Kalman filter is a time varying filter:
xˆt|t = axˆt−1|t−1 +Kt yt −axˆt−1|t−1 = ( 1 − K t ) a xˆ t − 1 | t − 1 + K t y t
This is a first order recursive filter with time-varying coefficients
MSE and Kalman gain are independent of the data: Offline computation Prediction step increases the error and correction stage decreases error:
evolution of error is non-monotonic
The Kalman filter is optimal in that it minimizes the Bayesian MSE for each estimator xˆt . When the Gaussian assumptions in the dynamic model do not hold: optimal linear MMSE estimator.
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Vector Kalman Filter
Consider a signal x ∈ Rm that evolves according to a Gauss-Markov model: xt =Axt−1+Bwt fort≥0
where
wt is independent from sample to sample: E[wt w⊤k ] = 0 for t ̸= k ,
wt ∼N(0,Σw)
The initial state is x0 ∼ N(μx,Σx) and independent of ut The observation is given by where
yt = Hxt + vt for t ≥ 0
Ht ∈ Rn×m is the observation matrix (can be time-varying)
vt ∼ N(0, Σv ) is the noise vector independent from sample to sample Aim:Tosequentiallyestimatext basedony1,y2,···,yt,i.e.,
xˆt|t =E[xt|y1,y2,···,yt]
MSE Matrices (Rm×m):
Pt|t−1 = E[(xt −xˆt|t−1)(xt −xˆt|t−1)⊤] Pt|t =E[(xt −xˆt|t)(xt −xˆt|t)⊤]
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Vector Kalman Filter
Vector Kalman Filtering Procedure
INITIALIZATION:
xˆ 0 | 0 = μ x
P0|0 = Σx PROCEDURE:
1
2
3
4
5
Prediction:
Minimum Prediction MSE Matrix:
xˆt|t−1 = Axˆt−1|t−1
Pt|t−1 = APt−1|t−1A⊤ +BΣwB⊤
Kalman Gain Matrix (Matrix Inversion Required):
Correction:
Minimum MSE:
yt −Htxˆt|t−1
Pt|t =(I−KtHt)Pt|t−1
ACS6124 Multisensor and Decision Systems
K =P H⊤Σv+HP H⊤−1
t
t|t−1 t
xˆt|t =xˆt|t−1+Kt
t t|t−1 t
G. Konstantopoulos
Properties of Vector Kalman Filter
All properties of the scalar case hold for the vector case with the exception of the need of matrix inversion
More efficient implementation: Information form
Extension to time-varying At , Bt , Σw,t and Σv,t : Replace by static
counterparts in the recursion. Extended Kalman Filter:
The Kalman Filter (KF) is a recursive linear estimator for a continuous state that evolves over time on the basis of periodic observations of the state. Optimality:
If signal and noise are jointly Gaussian: KF is optimal MMSE estimator If signal and noise are not jointly Gaussian: KF is the optimal LMMSE estimator
Suitability for Multisensor systems:
Explicit description of signal and observation allows inclusion of wide
range of sensor models
Statistical measure of uncertainty makes it possible to quantitatively evaluate the role of each sensor in the overall system performance Recursive structure allows simple and efficient implementation
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Multi-Sensor Kalman Filter
A set of S sensors is used for observing a dynamical system
All sensors units are observing the same system: Dynamical random process is common to all sensors
Observation yi,n with i = 1,2,··· ,S obtained by sensor i at time n is given by:
yi,n = Hi,nxn +zi,n
where
Hi,n ∈ Rm×p is the observation matrix for sensor i at time n (time-varying) zi ,n ∼ N(0, Σzi zi ) is the noise vector independent from sample to sample: zi,n =zi
Assumptions:
Hi,n ∈ Rm×p is the assumed time invariant: Hi,n = Hi for i = 1,2,…,S
Observation noise from different sensors is uncorrelated: E[zj zi ] = 0 for i ̸= j
All sensors units are observing the same system: xn is the same for all
i = 1,2,…,S
How do we extend the Kalman Filter implementation to large and complex system?
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Multi-Sensor Kalman Filter
Dynamical System
y,n z
H + Mission Control Center 1
xn = Axn + Bun
H2 + Mission Control Center 2
FUSION CENTER
xön n = E x|y,y2,…,yS
y2,n z2
HS + yS,n zS
Mission Control Center S
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Centralised v Decentralised Fusion Architectures
Centralised Sensor Fusion
Centralised architectures assume that a single processor performs the entire data fusion process.
Incurs high communication load and reliability concerns.
Decentralised Sensor Fusion
Each nodes process sensor data locally, validates them, and uses the observations to update its estimates.
Nodes communicates their estimates information to other similar nodes that are then used locally in the other nodes to update their local estimate.
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
The Group-Sensor Method
Combine all observation in a single compound group sensor model The problem formulation is equivalent to a vector Kalman filter
Combining all observations yields:
y ̃ n = H ̃ n x n + ̃z n Group observations: y ̃n = yT yT . . . yT T
where
Group observation matrix: H ̃i,n = HT1,n HT2,n,…,HT T
Group observation noise: ̃zn = zT zT . . . zT T
Covariance of group noise:
1,n 2,n S,n
12S
Σz1z1 0···0
0 Σz2z2 ··· 0 Σ ̃z ̃z= . . . .
. . .. . 0 0 ··· ΣzSzS
Advantages and Limitations:
The computational complexity of computing the Kalman Gain Matrix, the Correction, and the Minimum MSE grows with the number of sensors S. Straightforward approach when the number of sensors is small but problematic in higher dimensions
S,n
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
The Sequential-Sensor Method
Each observation treated as an independent, sequential update to the estimate
Observations are combined at Scan Fusion Center For each observation compute:
Kalman Gain Matrix
Minimum MSE Matrix
Each sensor model is considered individually:
Dimension of Kalman Gain Matrix and Minimum MSE matrix does not change with S
Computation of a new Kalman Gain Matrix and Minimum MSE matrix for each sensor
Procedure:
It is assumed that each sensor makes an observation synchronously at each time step
Establish an ordering of the S sensors:
Ordered measurements: {yo1,n,yo2,n,··· ,yoS,n}
Sensor k generates estimate based on its own measurement and the estimations produced by sensors before in the ordering:
xˆo = Exˆn|yo ,xˆo ,xˆo ,…,xˆo = f yo ,xˆo ,xˆo ,…,xˆo k,n k,n 1,n 2,n k,n k,n 1,n 2,n k,n
Advantages and Limitations:
Size of the matrix inversion in Kalman Gain Matrix Computation does not increase
No need to wait for all observations to get an estimate
The complexity of the procedure grows with the dimension S
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
The Sequential-Sensor Method
Dynamical System
H + z
Observation 1
H2 + z2
Observation 2
yo,n
Kalman Filter 1
xöo,n
Kalman Filter 2
xöo2,n xöoS ,n
Kalman Filter S
Scan Fusion Center
xöo,n
y2o,n
xöo2,n
xn = Axn + Bun
HS + zS
Observation S
ySo,n
xöoS,n
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Track-to-Track Fusion
Track Fusion Center combines the estimates from different local sensor sites In track-to-track fusion algorithms, local sensor sites generate local track
estimates using a local Kalman filter
Local tracks are communicated to a Track Fusion Center that combines them to
generate a Global Track Estimate
When global estimate is communicated back to local sensor sites: feedback
configuration
Advantages and Limitations:
Local estimates are available at local sensors
Reduced communication requirements: local estimate contains less information than raw data from observations
Robustness to sensor failure
Complexity of the system is increased
Scalability: Extension to large networks is feasible Computational burden can be balanced across the network
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Track-to-Track Fusion
Straightforward (sloppy) fusion
xˆn|n = Pn|n =
S
Pn|n ∑P−1 xˆi,n|n (Global Estimate)
(Global MSE)
i,n|n i=1
S −1 ∑ P−1
i,n|n i=1
where
This methods ignores the correlation between different estimates Weights can be tuned to consider the correlation between estimates
xˆi,n|n is the local estimate at local sensor i
P−1 is the local minimum MSE at local sensor i i ,n|n
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Track-to-Track Fusion
Dynamical System
y,n
Local Tracker 1
xö,n
y2,n Local Tracker 2
xö2,n
Track-To-Track Fusion Algorithm
xön n Mn n
xn = Axn + Bun
yS,n
Local Tracker 2
xöS,n
Track Fusion Center
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Model-based Change Detection
The decision rules investigated can be summarised as:
Detection problems considered have reduced to computing a residual st . Residual signal is then processed (aggregated, match filtered).
Processed residual is checked against a threshold for change detection.
Dynamic systems have structure in their behaviour that have more variety than the simpler measurement model.
The challenge is to find a suitable residual signal.
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Dynamical model representation
The state space dynamical system representation is one form: xt+1 = Axt +But +Gwt
yt = Hxt + Jvt
wt , vt ∼ N(0, I), (i.e. Normally distributed noise and disturbance with zero mean
and unit covariance)
Fault Type 1: Additive Fault
The additive fault can be represented as:
xt+1 = Axt +But +Eft +Gwt
yt =Hxt +Dft +Jvt
ft is the fault signal.
Fault Type II: Multiplicative Fault Changes in system matrices G,J. Fault Type III: Spectral Fault Changes in system matrices A,B,H.
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Kalman Filtering based Change Detection
Recall from Kalman filter equations, the prediction error and the term in the gain:
z = y − H xˆ , R = Σ + H P H ⊤ t t t t|t−1 t v,t t t|t−1 t
zt is called the “innovation” or “residual”:
When the system is unchanged or normal,
zt ∼N(0,Rt)
Any changes will result in deviation of statistical properties that can be detected.
Additive sensor faults will lead to a mean value shift in the residual. For single sensor systems, et is a scalar, and if we form:
zt
st=√Rt ∼N(0,1)
Standard detectors such as CUSUM can be used with this residual.
Kalman filter is popularly used in fault detection of dynamic systems.
Kalman filter can be used as state and fault parameter estimator for change detection.
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Observer Based Change Detection
The function of an observer is to estimate states.
Observer estimation error is guaranteed to converge to zero if system is unchanged.
Identity Observer
The system dynamic model is as follows:
xt+1 = Axt +But +Eft +Gwt
The observer is:
yt =Hxt +Dft +Jvt
xˆt+1 = Axˆt +But +Lzt z t = y t − yˆ t
yˆ t = H xˆ t
Design observer gain L such that (A − LH) should have eigenvalues inside the unit circle.
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Observer Based Change Detection
Residual Function
For fault detection, we need a residual signal. Choose:
r t = z t = y t − yˆ t
=H(xt −xˆt)+Dft +Jwt
= Het +Dft +Jwt
where et = xt − xˆt , the state estimation error. If et → 0, then rt contains a noisy fault signal. State Estimation Dynamics
e t + 1 = x t + 1 − xˆ t + 1
= Aet +Eft +Gwt −Lzt
=Aet +Eft +Gwt −L(Het +Dft +Jwt) = (A−LH)et +(E−LD)ft +(G−LJ)wt
et will not go to zero even when ft = 0 since wt in the error dynamics. et will still be zero mean random signal and hence rt will be zero mean.
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Parameter Estimation based Change Detection
State space representation assumes known model parameters.
For unknown dynamical systems, a parameter estimation approach is required.
Take the example of a simplified suspension system:
An equivalent discrete time model is:
my ̈ = u − ky − cy ̇
yt = a1yt−1 +a2yt−2 +b1ut−1 +b2ut−2 +et = φ t θ + et
where e(t) represents the noise and disturbances φt = [yt−1 yt−2 ut−1 ut−2]
θ =[a1 a2 b1 b2]⊤
Note that θ = f(m,c,k) is the parameter vector.
ObservationsD1:T={y1,u1,y2,u2,…,yt,ut}.
Estimate the discrete-time model parameters using System Identification methods
⇒ y ̈+cy ̇+ky=1u mmm
(e.g. least squares).
θˆ 1 , θˆ 2 , . . . , θˆ t
We may not be able to map θ back to the physical parameters uniquely (which is an implication of fault isolation).
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems
Parameter Estimation based Change Detection
Fault Type 3: Spectral Fault
Decision rule: ∥st ∥2 < δ then decide H0
2
The decision rule ∥st ∥2 = θˆt − θ 0 is
a scalarised two-sided test.
It is equivalent to partitioning the parameter space by forming a hyperspherical region.
More general multivariate decision rules can be used to partition parameter space.
Model:- yt = φ⊤t (θ +∆)+et Let the parameter estimate at time t be θˆt .
Let the nominal parameters of the system be θ0.
Choose the residual signal to be:
s t = θˆ t − θ 0
G. Konstantopoulos
ACS6124 Multisensor and Decision Systems