Proceedings of t h e American Control Conference

Albuquerque, New Mexico J u n e 1997

0-7803-3832-4/97/$10.000 1997 AACC
A Non-divergent Estimation Algorithm in the Presence of Unknown
Correlations
Simon J. Julier & Jeffrey K. Uhlmann
The Robotics Research Group, Advanced Information Technology,
Department of Engineering Science, Code 5580,
The University of Oxford, The Naval Research Laboratory,
Oxford, OX1 3PJ, UK Washington DC 20375-5320, USA
sijuQrobots.ox.ac.uk uhlmannQait.nrl.navy.mil

ABSTRACT In a number of applications including map building [4],

This paper addresses the problem of estimation when the decentralised estimation with arbitrary network topolo-
cross-correlation in the errors between different random gies and weather forecasting [6], the process model could
variables are unknown. A new data fusion algorithm, the use thousands of states. Maintaining a full covariance
Covariance Intersection Algorithm(CI), is presented. It matrix is impractical and approximations must be made.
is proved that this algorithm yields consistent estimates Often the correlations are assumed to be of a particular
irrespective of the actual correlations. This property is form (such as independence), which eliminates a signific-
illustrated in an application of decentralised estimation ant degree of the computational load.
where it is impossible to consistently use a Kalman filter.
When there are unknown correlations it is possible, by
Keywords- Data fusion, decentralised networks, fil- judicious “tuning”, to develop filters which are consistent
tering, Kalman filter, map building, matrix inequal-
under certain circumstances. However, this is achieved
ities, nonlinear filtering. at the compromise of rigour, optimality and does not
guarantee that the estimate is consistent. Indeed, if
one simply treats the observation noise as constant and
I. INTRODUCTION changes the process noise covariance matrix (a standard
The fundamental requirement of an estimator is that filter tuning practice), the filter is guaranteed t o diverge.
it is able to fuse information from a number of noise-
In this paper a new and completely general method
corrupted sources t o make consistent inferences about
for fusing the information from two random variables
the state of a system. Arguably the most important es-
is described. Called the Covariance Intersection Al-
timator is the Kalman filter, which assumes that each
gorithm(CI), it forms an estimate from the convex com-
information source can be expressed as a random vari-
bination of the means and covariances of the two input
able with a known mean, covariance and cross correl-
variables. The a1gorith.m yields consistent estimates for
ation with the other sources. Providing these statist-
any degree of correlation between the two inputs vari-
ics are known perfectly, the filter is rigorous and yields
ables, and the formulation includes of a degree of free-
minimum mean squared error estimates of the system
dom which allows the update to be optimised with re-
state. In many situations the actual statistics are not
spect to different cost functions (such as the trace or de-
known perfectly but, providing the information sources
terminant). To demonstrate the practical benefits of the
are independent, it is possible to “over estimate” the stat-
algorithm, it is applied to the problem of decentralised
istics and suboptimal filtering can be performed [ 3 , 5 ] .
data fusion.
However, in many important situations it is impossible
to guarantee that the noise sources are independent and
might, in fact, be highly correlated. There are two main
reasons. First, the noises which act on the physical sys- 11. PROBLEM
STATEMENT
tem are correlated. Second, the system might be per-
We consider the problem that two pieces of information,
turbed by independent noises, but the implemented filter
labelled A and B , are to be fused together to yield an
is an approximation.
output C. This is a general type of data fusion problem
The first cause of unknown correlations is lack of know- - A and B could be two different sensor measurements,
ledge of the true system. For example, the observation or A could be a prediction from a system model and
noises of a suite of navigation sensors mounted on the B could be sensor information. The input sources are
same vehicle might be correlated with one another by vir- corrupted by noise, and so they are random variables, a
tue of vehicle motion, but this correlation has not been and b respectively. We assume that the true statistics
identified. There can also be correlations through time. of these variables are unknown. The only information
For example, a process model might consistently under which is available are consistent estimates of the means
predict the value of a parameter, leading to a biased pre- and covariances of each of these variables. We define
diction. consistency as follows. The assumed means and covari-
ances of a and b are ii a.nd b. The deviations of A and B
A - A
The second cause of correlations arise when it only pos- about these assumed means are 5 = a - ii and b = b - b.
sible to approximate the full filter for the actual system. In general, these deviations are not zero mean, and the
2369
mean squared error and cross correlations are P this is the locus of points {p : pTP-'p = c} where
c is a constant) P a a l P b b and P,, for all choices of P a b ,
P,, always lies within the intersection of Pa, and P b b .
Fig. 1 illustrates this for a number of different choices of
Pab.
The actual values are not known, but rather are approx-
imated by the values P a , and Pbb. These approxima-
1
tions are consistent if I

Pa, - P a a L 01
(1) 0.6
Pbb -Pbb 2 0.
0.4
Note that the cross-correlation matrix between the ran- 0.2
dom variables, P a b , is unknown and will not, in general,
be 0. 0

-0.2
This definition conforms t o the standard definition of
-0.4
consistency used in [3]. The problem is t o fuse the in-
formation from a and b together to yield a new estimate -0.6

{E, P,,} which minimises some form of cost function but -0.8
guarantees consistency:
I
-1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1
P,, - P c c 2 0
A
Fig. 1: The shape of the updated covariance ellipse,
where E = c - C and P,, = E [ E T .] The variances of P,, and Pbb are the solid ellipses.
Different values of P,, which arise from different
The most common data fusion algorithms compute a lin- choices of P,b are shown as dashed ellipses.
ear combination of the means, and then analytically de- This interpretation suggests the following approach: if
termine the covariance of the result. Although this is P,, lies within the intersection of P a , and P b b for any
optimal approach when the statistics are known, it leads possible choice of P a b , then an update strategy which
to problems when there is uncertainty in the cross cor- finds a P,, which encloses the intersection region must be
relations. The Kalman filter, for example, uses a linear consistent even if there is n o knowledge about P a b [7,8].
update rule of the form The tighter the updated covariance encloses the intersec-
tion region, the greater the amount of information which
= Was f Wb6 (3)
can be used.
and calculates the covariance as
The intersection is characterised by the convex combina-
Pcc =waPaawz +W a P a b W : tion of the covariances, and the Covariance Intersection
(4)
+WbPbaWz + WbPbbWr.
algorithm is

wa and W b are chosen to minimise the trace of Pee. P&l = WP;; + (1- w)P;l (5)
However, this calculation uses the assumed values of the
covariances. The true covariance is
P,-,lE = WP;;. + (1 - w)P,'b (6)

P C c =WaPaaWLf +W , P a b W F where w E [0,1]. In Appendix A it is proved that this

update equation is consistent in the sense given by Equa-
f W b P b a W z +W b P b b W r .
tion 2 for all choices of Pab and w .
In the simple case when the assumed and actual vari-
The free parameter w manipulates the weights which are
ables are uncorrelated ( P a b = P a b = 0) the consistency
assigned to a and b. Different choices of w can be used
of a and b are sufficient to ensure that Equation 4 yields
to optimise the update with respect t o different per-
a consistent update[3]. However, when P a b # 0, it is dif-
formance criteria such as minimising the trace or the
ficult to guarantee a consistent update. These problems
determinant of P,,. Cost functions which are convex
motivate the development of the Covariance Intersection
with respect to w have only one distinct optimum in the
algorithm, which is described next.
range 0 5 w 5 1. Virtually any optimisation strategy
111. THECOVARIANCE INTERSECTION ALGORITHM can be used, ranging from Newton-Raphson t o sophistic-
ated semidefinite and convex programming [9] techniques
The Covariance Intersection Algorithm (CI) is a data fu- which can minimise almost any norm. When combining
sion algorithm which takes a convex combination of the large numbers of estimates, efficient algorithms such as
means and covariances in the information (inverse covari- the public domain SPDSOL software [l]are available.
ance) space. The intuition behind this approach arises
from a geometric interpretation of Equation 4. If one The next section demonstrates the application of CI to
plots out the covariance ellipses (for a covariance matrix decentralised estimation.

2370
 IV. EXAMPLE APPLICATION: DECENTRALISED the body with different levels of accuracy (see Table 1)
ESTIMATION and each node maintains its own estimates and has its
own filter. The nodes propagate their estimates amongst
This section illustrates the application of CI to decent-
one another.
ralised estimating systems. These systems consist of a
network of autonomous nodes which communicate in-
formation between one another. 1 Node I Measures I Variance1

6v0
Node 2

Node 3
Node 4
Table 1: The sensors for each node.
We use the following notation. Let f (i . 1 j) be the es-
timate at time i conditioned on all measurements up to
and including time step j. P (i I j) is the corresponding,
Fig. 2: The network layout. estimated covariance.

A decentralised data fusion system is a collection of Each node consists of: a single sensor, a Kalman filter,
processing nodes; connected by communication links and a mechanism for propagating and combining its own
(Fig. 2 ) , in which none of the nodes has knowledge about estimate with those of the other nodes. The first step in
the overall network topology. Rather, each node only the operation of each node is to predict what the future
contains information about its connection to other ad- state of the system will be given the current estimate.
jacent nodes. Each node performs a specific comput- The prediction for the ith node is given by
ing task-using information from nodes with with it is
linked, but there is no “central” node that controls the
network. There are many attractive properties of such i i + 1I k ) F i i ( k I k )
(IC L-
decentralised systems[2], including robustness (if nodes
fail the performance of the system degrades gracefully
Pi (IC + 1 I IC) := FPi (IC + 1 I k ) FT + GGTo;.
rather than completely fails) and flexibility (additional
nodes can be readily introduced and removed). Inform- The update from the prediction to the estimate for each
ation from distributed sources propagates through the node is a two step process. First, each node updates
network so that each node obtains the data relevant to with local sensor information to give the partial estim-
its own processing task. Estimating the position of a + + +
ate ff ( k 1 I IC 1) and Pf (IC 1 I k 1). These es- +
vehicle, for example, might combine acceleration estim- timates are then propagated between the nodes, and are
ates from nodes measuring wheel speed, from laser gyros, incorporated to yield ithe final estimates.
and from pressure sensors on the accelerator pedal. If
each independent node provides the mean and covariance Updating with local sensor information can be achieved
of its estimate of acceleration, then it is straightforward using a standard Kalman filter since the observation
to fuse the estimates to obtain a better filtered estimate. noise is independent. If Ri is the observation noise co-
If some nodes share an unknown amount of redundant variance on the ith sensor, and Hi is the observation
information, and hence correlated errors, then the fusion matrix, then the partial estimates are
step cannot assume independence. +
~ i ( k 1) = ~i ( k + 1) - Hiki (IC + 1 I IC)
The problems of correlated noise and the utility of CI
Si( k + 1)= Hipi ( k + 1 I k ) H F + Ri
can be illustrated by considering a the following specific Wi ( k + 1) = Pi (IC + 1 I k ) HTSil (IC + 1)
application: to estimate the motion of a body which ex- +
ff (IC 1 I k + 1) = fi ( k + 1 I k )
periences random jerks (derivative of acceleration). The
dynamics of the motion of the moving body are:
+ wi (k + 1)Vi@ + 1)
Pf ( k + 1 I k + 1) = P i & + 1 I k ) - wi ( k + 1)
x (IC + 1) = Fx ( k ) + G v ( k ) (7) x si (IC + 1)WT ( k 3- 1).
where

F= 61 AT AT2/2
AT ] AT316
and G = 1 1 : / 2 ] .
We examine three strategies for combining the informa-
tion from the other nodes: (i) the nodes are unconnected,
and so no information flows between them; (ii) a nGve
approach, in which the information from the different
v(k) is an uncorrelated, zero-mean Gaussian noise with nodes is assumed to be independent and (iii) a Covari-
variance U: = 10 and the length of the time step AT = ance Intersection-based approach.
0.1s.
A . Unconnected Nodes
The tracking system uses four nodes which are shown in When the nodes are unconnected, no information flows
Fig. 2 . Each node measures different quantities about from the other nodes. Therefore, the final estimate is

2371
equal t o the partial estimate:
k(k+lIk+l)
P(k+lIk+l)
= Xzf(k+lIk+l),
= Pzf(k+lIk+l) :::L-
/ '0 10 20 30
,

40 50 €0 70 80 90 100

Fig. 3 shows the estimated covariance and mean squared

error estimate (calculated over 100 Monte Carlo runs) in '"I " " " . ' ' I
estimating x,x and x for node 1. As can be seen, the
filter is consistent, and its covariance is a true reflection l---/I:l

of the actual errors in the system. 0

0 10 20 30 40 50 60 70 80 90 100

Although node 1 appears to behave acceptably, this is

not the case for nodes 2 and 3. The reason is that these
nodes measure velocity and acceleration respectively, but
they do not have access to absolute position measure-
ments. Therefore, the position is unobservable for both
nodes, and the velocity is unobservable for node 3. (See
Table 2). Fig. 4: The results for node 1 with the naive
implementation. On the scale of the plots, the
estimated covariances for x(k) and x(k) are not
visible.
0.6
I The independence assumption is the crudest (and least
accurate) which can be made, and there is scope for re-
finement. One important modification would be to use
0 10 20 30 40 50 €0 70 80 90 100
channel fiZters[2]which maintain correlation information
between adjacent nodes. However, these filters only en-
..
3 sure consistent performance when the network has a tree
2 structure, because there is only a single route which in-
formation can take in flowing between different nodes.
The network shown here is a cycle, and there are mul-
tiple routes. As shown in [2],under this situation it is
impossible to consistently use a Kalman filter which only
has knowledge of local connections. Correlation inform-
ation about the entire network is required, undermining
the advantages of a decentralised system.

Fig. 3: The results for node 1 with disconnected

nodes. The estimated covariance for each state is a C. Covariance Intersection Approach
dashed line, whereas the root mean squared error is
the solid line. The final approach is to use the CI Algorithm t o combine
Because the variances on these nodes increase without the information from the different nodes. Fig. 5 shows
bound, it is desirable t o propagate the information the behaviour of node 1. As can be seen the estimates
between the different nodes. are consistent despite the correlation between the estim-
ates. In fact the variance is slightly over estimated. This
B. Naive Approach is because the CI algorithm exploits n o correlation in-
The naive approach is to use the Kalman filter to fuse formation at all.
the information from the different nodes under the as-
sumption that the estimates from the different nodes Table 2 compares the performance of the unconnected
are independent. The final estimates are given by up- and CI connected system for all four nodes. The vari-
dating the partial estimate with the estimate from each ance at time step 100 for each node is shown. As can be
node using the Kalman filter under the assumptions of seen, all of the nodes have reached steady state in the CI
independent noise. This corresponds to H = I and network, and in most cases the variances on the estimates
R=P:(k+l lk+l). are smaller than those in the disconnected case. There
are two exceptions: the variances on x(k) in node 1 and
The result of this naive approach is shown in Fig. 4. As %(k) on node 3 have increased slightly. These are due
can be seen, the filter diverges extremely rapidly. This to the fact that the CI update minimises the determin-
is due to the fact that the estimates from the differ- ant of the covariance matrix. Although the variances in
ent nodes are correlated. Not only is the process noise these individual states have increased slightly, they have
common to all nodes, but the estimates are correlated been accompanied by large reductions in the variances
through previous information flows which have propag- of the other states, significantly reducing the overall un-
ated between the different nodes. certainty in the estimates.

2372
 Since P a b is not known the actual value of this term
cannot be calculated. CI implicitly calculates an upper
bound of this quantity. Substituting the actual mean
squared error into Equation 2, pre- and post-multiplying
both sides by P;' and collecting terms, the consistency
condition becomes
4
I
p-1 - #2p-'-aa PaaP:: - w(1 - w)P;:PabPG1
cc (8)
-#(I - w ) P ~ l P b a P , - , ' - (1 -w)2PE1Pb/,PG1 2 0.
It is possible to find an upper bound on P
:; which can
be expressed using P,,, P b b , Pa, and P b b . From the
Fig. 5 : The results for node 1 using CI. consistency condition for a,

pa, - P a a L 0
or, by pre- and post-multiplying by Pi:,
;;R? 2 P;:PaaP;:
A similar condition exists for b and, by substituting these
results in Equation 5 ,
P
:; = + (1 - w)PG'
UP,-,'

2 wP;paaP;; + (1- W ) P , - d P b b P G ' .

Table 2: The variances at time step 100 for the Substituting this lower bound into Equation 8 leads to
unconnected (UN) and Covariance intersected (CI)
nodes. A * denotes the state is diverging and does not w(l - U) (P;:PaaP;: - P;:Pa/,P;l
have a finite steady-state value. -PG1-dpbaPz: + PG'PbbPk') 2 0 .
V. CONCLUSIONS or
This paper has described a new method for combining w ( l - ~ ) E[{P;iii-Phlb} {P;;i-p,-$bjT] 20.
the information of random variables with an unknown
degree of cross-correlation, the Covariance Intersection
Algorithm. Using the convex combination of the means
and covariances of the variables, it is able to yield a con- Clearly, the inequality must hold for all choices of P , b
sistent estimate irrespective of the correlation between and w E [0, 11.
the prior information. This algorithm has been demon-
REFERENCES
strated in the context of a decentralised system, where
it is able to produce substantial benefits. The Kalman S . Boyd and S. Wu. Sdpsol: User's guide. SDPSOL: A
filter, on the other hand, is unable to even operate con- Parser/Solver for Semidefinite Programs with Matrix Struc-
sistently. ture, November 1995.
S . Grime and H. Durrant-Whyte. Data fusion in decentralized
networks. Control Eng. Practice, 2 , 1994.
A PROOF
OF CONSISTENCY A. H. Jazwinski. Stochastic Processes and Filtering Theory.
Academic Press, 1970
This appendix proves that Covariance Intersection yields J. Leonard. Directed Sonar Sensing for Mobile Robot Naviga-
tion. Kluwer Academic Press, 1991.
a consistent estimate for any value of w and P G b provid-
P. S . Maybeck. Stochastic Models, Estimation, and Control,
ing that a and b are consistent. volume 1. Academic Press, 1979.
R. Todling and S. E. Cohn. Suboptimal schemes fcw atmo-
The CI algorithm calculates its mean using Equation 6. spheric data assimilation based on the kalman filter. Montly
The actual error in this estimate is Weather Review, pages 2530-2557, November 1994.
Jeffrey K. Uhlmann. Dynamic Map Building and Localiza-
tion: New Theoretical Foundations. P h D thesis, University of
2 = P,, {wP;:H 4- (1 - w)PGlb}. Oxford, 1995.
Jeffrey K . Uhlmann. General d a t a fusion for estimates with
unknown cross covariances. Proceedings of the SPIE Aerosense
Conference, 2755, 4/1996.
By taking outer products and expectations, the actual L. Vandenberghe and S. Boyd. Semidefinite programming.
mean squared error which is committed by using Equa- SIAM Review, March 1996.

2373