⎢
⎥
⎢
..
⎥
⎢
..
⎥
⎣
.
⎥
⎦
⎢
⎣
.
⎥
⎦
P
T
T
t− L, t/ t Ct
Pt− L, t/ t Ct
We also introduce component matrices of Mt as follows:
⎡ (
(
(
(
⎤
M 0,0)
0,1)
0,2)
0, L)
⎢ t
Mt
Mt
. . . Mt
⎢
⎥
⎢ (1,0)
(1,1)
(1,2)
(1, L)⎥
⎢ M
⎥
t
Mt
Mt
. . . Mt
⎢
⎥
⎢
⎥
(2,0)
(2,1)
(2,2)
(2, L)⎥
Mt = ⎢ M
⎢ t
Mt
Mt
. . . Mt
⎥ .
⎢
⎥
⎢ .
.
.
.
⎥
⎢ .
.
.
. .
.
⎥
⎣ .
.
.
.
.
⎥
⎦
(
(
(
(
M L,0)
L,1)
L,2)
L, L)
t
Mt
Mt
. . . Mt
Concerning Pt+1, we have
T
T
T
T
Pt+1 = A 1 M
+ T
T
+ H
t+1
t A 1 t+1
t+1 Jt Qt Jt
t+1
t+1 Rt+1 Ht+1
⎡
(
T
(
(
(
⎤
A 1
M 0,0)
A 1
M 0,0)
M 0,1)
M 0, L−1)
⎢ t+1 t
A 1 t+1
t+1
t
A 1 t+1 t
. . . A 1 t+1 t
⎢
⎥
⎢
(0,0)
T
(0,0)
(0,1)
(0, L−1)
⎥
⎢
M
⎥
t
A 1
M
t+1
t
Mt
. . .
Mt
⎢
⎥
⎥
= ⎢
(
T
(
(
(
⎢
M 1,0)
M 1,0)
1,1)
1, L−1)
⎥
⎢
t
A 1 t+1
t
Mt
. . .
Mt
⎥
⎢
.
.
.
.
⎥
⎢
.
.
.
. .
.
⎥
⎣
.
.
.
.
.
⎥
⎦
(
T
(
(
(
M L−1,0)
L−1,0)
L−1,1)
L−1, L−1)
t
A 1
M
t+1
t
Mt
. . . Mt
⎡
⎤
T
T+ H
T O O . . . O
⎢ t+1 QtTt+1
t+1 Rt+1 Ht+1
⎢
⎥
⎢
O
O O . . . O ⎥
⎢
⎥
⎥
+ ⎢
O
O O
⎢
. . . O ⎥ .
⎢
⎥
⎢
.
.
.
.
. ⎥
⎣
.
⎥
.
.. ..
. . .. ⎦
O
O O . . . O
The final part (iv) can be obtained from the last three equalities.
68
Discrete Time Systems
6. Conclusion
In this chapter, we considered discrete-time linear stochastic systems with unknown inputs
(or disturbances) and studied three types of smoothing problems for these systems. We
derived smoothing algorithms which are robust to unknown disturbances from the optimal
filter for stochastic systems with unknown inputs obtained in our previous papers. These
smoothing algorithms have similar recursive forms to the standard optimal filters and
smoothers. Moreover, since our algorithms reduce to those known smoothers derived from
the Kalman filter when unknown inputs disappear, these algorithms are consistent with the
known smoothing algorithms for systems without unknown inputs.
This work was partially supported by the Japan Society for Promotion of Science (JSPS) under
Grant-in-Aid for Scientific Research (C)-22540158.
7. References
Ackner, R. & Kailath, T. (1989a). Complementary models and smoothing, IEEE Trans.
Automatic Control, Vol. 34, pp. 963–969
Ackner, R. & Kailath, T. (1989b). Discrete-time complementary models and smoothing, Int. J.
Control, Vol. 49, pp. 1665–1682
Anderson, B. D. O. & Moore, J. B. (1979). Optimal Filtering, Prentice-Hall, Englewood Cliffs, NJ
Badawi, F. A.; Lindquist, A. & Pavon, M. (1979). A stochastic realization approach to the
smoothing problem, IEEE Trans. Automatic Control, Vol. 24, pp. 878–888
Bello, M. G.; Willsky, A. S. & Levy, B. C. (1989). Construction and applications of discrete-time
smoothing error models, Int. J. Control, Vol. 50, pp. 203–223
Bello, M. G.; Willsky, A. S.; Levy, B. C. & Castanon, D. A. (1986). Smoothing error dynamics
and their use in the solution of smoothing and mapping problems, IEEE Trans. Inform.
Theory, Vol. 32, pp. 483–495
Bryson, Jr., A. E. & Ho, Y. C. (1969). Applied Optimal Control, Blaisdell Publishing Company,
Waltham, Massachusetts
Caliskan, F.; Mukai, H.; Katz, N. & Tanikawa, A. (2003). Game estimators for air combat
games with unknown enemy inputs, Proc. American Control Conference, pp. 5381–5387,
Denver, Colorado
Chang, S. & Hsu, P. (1993). State estimation using general structured observers for linear
systems with unknown input, Proc. 2nd European Control Conference: ECC’93, pp.
1794–1799, Groningen, Holland
Chen, J. & Patton, R. J. (1996). Optimal filtering and robust fault diagnosis of stochastic systems
with unknown disturbances, IEE Proc. of Control Theory Applications, Vol. 143, No. 1,
pp. 31–36
Chen, J. & Patton, R. J. (1999). Robust Model-based Fault Diagnosis for Dynamic Systems, Kluwer
Academic Publishers, Norwell, Massachusetts
Chen, J.; Patton, R. J. & Zhang, H. -Y. (1996). Design of unknown input observers and robust
fault detection filters, Int. J. Control, Vol. 63, No. 1, pp. 85–105
Darouach, M.; Zasadzinski, M.; Bassang, O. A. & Nowakowski, S. (1995). Kalman filtering
with unknown inputs via optimal state estimation of singular systems, Int. J. Systems
Science, Vol. 26, pp. 2015–2028
New Smoothers for Discrete-time Linear Stochastic Systems with Unknown Disturbances
69
Darouach, M.; Zasadzinski, M. & Keller, J. Y. (1992). State estimation for discrete systems with
unknown inputs using state estimation of singular systems, Proc. American Control
Conference, pp. 3014–3015
Desai, U. B.; Weinert, H. L. & Yasypchuk, G. (1983). Discrete-time complementary models and
smoothing algorithms: The correlated case, IEEE Trans. Automatic Control, Vol. 28, pp.
536–539
Faurre, P.; Clerget, M. & Germain, F. (1979). Operateurs Rationnels Positifs, Dunod, Paris, France
Frank, P. M. (1990). Fault diagnosis in dynamic system using analytical and knowledge based
redundancy: a survey and some new results, Automatica, Vol. 26, No. 3, pp. 459–474
Hou, M. & Müller, P. C. (1993). Unknown input decoupled Kalman filter for time-varying
systems, Proc. 2nd European Control Conference: ECC’93, Groningen, Holland, pp.
2266–2270
Hou, M. & Müller, P. C. (1994). Disturbance decoupled observer design: a unified viewpoint,
IEEE Trans. Automatic Control, Vol. 39, No. 6, pp. 1338–1341
Hou, M. & R. J. Patton, R. J. (1998). Optimal filtering for systems with unknown inputs, IEEE
Trans. Automatic Control, Vol. 43, No. 3, pp. 445–449
Kailath, T. (1974). A view of three decades of linear filtering theory, IEEE Trans. Inform. Theory,
Vol. 20, No. 2, pp. 146–181
Kailath, T. (1975). Supplement to a survey to data smoothing, Automatica, Vol. 11, No. 11, pp.
109–111
Kailath, T. (1976). Lectures on Linear Least-Squares Estimation, Springer
Kailath, T.; Sayed, A. H. & Hassibi, B. (2000). Linear Estimation, Prentice Hall
Kalman, R. E. (1960). A new approach to linear filtering and prediction problems, in Trans.
ASME, J. Basic Eng. , Vol. 82D, No. 1, pp. 34–45
Kalman, R. E. (1963). New methods in Wiener filtering theory, Proc. of First Symp. Eng. Appl. of
Random Function Theory and Probability (J. L. Bogdanoff and F. Kozin, eds.), pp. 270-388,
Wiley
Katayama, T. (2000). Applied Kalman Filtering, New Edition, in Japanese, Asakura-Shoten,
Tokyo, Japan
Meditch, J. S. (1973). A survey of data smoothing for linear and nonlinear dynamic systems,
Automatica, Vol. 9, No. 2, pp. 151–162
Patton, R. J.; Frank, P. M. & Clark, R. N. (1996). Fault Diagnosis in Dynamic Systems: Theory and
Application, Prentice Hall
Sawada, Y. & Tanikawa, A. (2002). Optimal filtering and robust fault diagnosis of stochastic
systems with unknown inputs and colored observation noises, Proc. 5th IASTED Conf.
Decision and Control, pp. 149-154, Tsukuba, Japan
Tanikawa, A. (2006). On a smoother for discrete-time linear stochastic systems with unknown
disturbances, Int. J. Innovative Computing, Information and Control, Vol. 2, No. 5, pp.
907–916
Tanikawa, A. (2008). On new smoothing algorithms for discrete-time linear stochastic systems
with unknown disturbances, Int. J. Innovative Computing, Information and Control, Vol.
4, No. 1, pp. 15–24
Tanikawa, A. & Mukai, H. (2010). Minimum variance state estimators with disturbance
decoupling property for optimal filtering problems with unknown inputs and fault
detection (in preparation)
70
Discrete Time Systems
Tanikawa, A. & Sawada, Y. (2003). Minimum variance state estimators with disturbance
decoupling property for optimal filtering problems with unknown inputs, Proc. of
the 35th ISCIE Int. Symp. on Stochastic Systems Theory and Its Appl. , pp. 96-99, Ube,
Japan
Weinert, H. L. & Desai, U. B. (1981). On complementary models and fixed-interval smoothing,
IEEE Trans. Automatic Control, Vol. 26, pp. 863–867
5
On the Error Covariance Distribution for
Kalman Filters with Packet Dropouts
Eduardo Rohr, Damián Marelli, and Minyue Fu
University of Newcastle
Australia
1. Introduction
The fast development of network (particularly wireless) technology has encouraged its use
in control and signal processing applications. Under the control system’s perspective, this
new technology has imposed new challenges concerning how to deal with the effects of
quantisation, delays and loss of packets, leading to the development of a new networked
control theory Schenato et al. (2007). The study of state estimators, when measurements are
subject to random delays and losses, finds applications in both control and signal processing.
Most estimators are based on the well-known Kalman filter Anderson & Moore (1979). In
order to cope with network induced effects, the standard Kalman filter paradigm needs to
undergo certain modifications.
In the case of missing measurements, the update equation of the Kalman filter depends on
whether a measurement arrives or not. When a measurement is available, the filter performs
the standard update equation. On the other hand, if the measurement is missing, it must
produce open loop estimation, which as pointed out in Sinopoli et al. (2004), can be interpreted
as the standard update equation when the measurement noise is infinite. If the measurement
arrival event is modeled as a binary random variable, the estimator’s error covariance (EC)
becomes a random matrix. Studying the statistical properties of the EC is important to
assess the estimator’s performance. Additionally, a clear understanding of how the system’s
parameters and network delivery rates affect the EC, permits a better system design, where
the trade-off between conflicting interests must be evaluated.
Studies on how to compute the expected error covariance (EEC) can be dated back at least
to Faridani (1986), where upper and lower bounds for the EEC were obtained using a constant
gain on the estimator. In Sinopoli et al. (2004), the same upper bound was derived as the
limiting value of a recursive equation that computes a weighted average of the next possible
error covariances. A similar result which allows partial observation losses was presented
in Liu & Goldsmith (2004). In Dana et al. (2007); Schenato (2008), it is shown that a system in
which the sensor transmits state estimates instead of raw measurements will provide a better
error covariance. However, this scheme requires the use of more complex sensors. Most of
the available research work is concerned with the expected value of the EC, neglecting higher
order statistics. The problem of finding the complete distribution function of the EC has been
recently addressed in Shi et al. (2010).
72
Discrete Time Systems
This chapter investigates the behavior of the Kalman filter for discrete-time linear systems
whose output is intermittently sampled. To this end we model the measurement arrival event
as an independent identically distributed (i.i.d.) binary random variable. We introduce a
method to obtain lower and upper bounds for the cumulative distribution function (CDF) of
the EC. These bounds can be made arbitrarily tight, at the expense of increased computational
complexity. We then use these bounds to derive upper and lower bounds for the EEC.
2. Problem description
In this section we give an overview of the Kalman filtering problem in the presence of
randomly missing measurements. Consider the discrete-time linear system:
xt+1 = Axt + wt
(1)
yt
= Cxt + vt
where the state vector xt ∈ R n has initial condition x 0 ∼ N(0, P 0), y ∈ R p is the measurement, w ∼ N(0, Q) is the process noise and v ∼ N(0, R) is the measurement noise. The goal of the
Kalman filter is to obtain an estimate ˆ xt of the state xt, as well as providing an expression for
the covariance matrix Pt of the error ˜ xt = xt − ˆ xt.
We assume that the measurements yt are sent to the Kalman estimator through a network
subject to random packet losses. The scheme proposed in Schenato (2008) can be used to
deal with delayed measurements. Hence, without loss of generality, we assume that there is
no delay in the transmission. Let γt be a binary random variable describing the arrival of a
measurement at time t. We define that γt = 1 when yt was received at the estimator and γt = 0
otherwise. We also assume that γt is independent of γs whenever t = s. The probability to
receive a measurement is given by
λ = P( γt = 1).
(2)
Let ˆ xt| s denote the estimate of xt considering the available measurements up to time s. Let
˜ x
=
=
−
})(
−
}) }
t| s
xt − ˆ xt| s denote the estimation error and Σ t| s
E{( ˜ xt| s
E{ ˜ xt| s
˜ xt| s
E{ ˜ xt| s
denote its covariance matrix. If a measurement is received at time t (i.e., if γt = 1), the estimate
and its EC are recursively computed as follows:
ˆ x
=
+
t| t
ˆ xt| t−1 Kt( yt − Cxt)
(3)
Σ t| t = ( I − KtC)Σ t| t−1
(4)
ˆ x
=
t+1| t
A ˆ xt| t
(5)
Σ t+1| t = AΣ t| tA + Q,
(6)
with the Kalman gain Kt given by
Kt = Σ t| t−1 C ( CΣ t| t−1 C + Q)−1.
(7)
On the other hand, if a measurement is not received at time t (i.e., if γt = 0), then (3) and (4)
are replaced by
ˆ x
=
t| t
ˆ xt| t−1
(8)
On the Error Covariance Distribution for Kalman Filters with Packet Dropouts
73
Σ =
t| t
Σ t| t−1.
(9)
We will study the statistical properties of the EC Σ t| t−1. To simplify the notation, we define
Pt = Σ t| t−1. Then, the update equation of Pt can be written as follows:
Pt+1 =
Φ1( Pt), γ