one nodes having the same biggest metric, anyone of these nodes can be taken as the desired
estimate.
Real-time Recursive State Estimation for Nonlinear
Discrete Dynamic Systems with Gaussian or non-Gaussian Noise
13
F
( )
a
(
w k )
1
n
m
F
( a)
x(0)
Eq. (3)
GS
Eq. (3)
Determine initial admissible
quantization levels and
discard non-admissible
Calculate the state quantization
initial quantization levels
levels at time k by Eq. (6 ). Then,
determine admissible quantization
levels and discad non-admissible
quantization levels
If the number of
admissible quantization
Then
levels =0
Z(k)
Else
If the number of
k=k+1
admissible quantization
levels =0
Then
Calculate the metrics of
admissible initial quantization
Unit
levels by Eq. (13)
Else
Delay
Calculate metrics of admissible
Calculate
quantization levels at time k by
the mean
Eq. (14)
Estimate of the initial state is
the mean value of the state if this
Consider only MN admissible
mean value satisfies the
quantization levels with the
constrains, otherwise, the initial
biggest metrics at time k if the
node with biggest metric
number of admissible
quantization levels is greater
MN
than MN; otherwise, all
admissible quantization levels
decide that there do not
exist any estimates satisfying the
Estimate of state at
constraints for given n, m, GS and
time k is the admissible
MN; and use the DF with different
quantization level with the
n, m, GS, or MN
biggest metric
Fig. 3. Flowchart of the DF
14
Discrete Time Systems
300
DF
SIR
250
ASIR
200
150
100
Average Filtering Errors
50
00
20
40
60
80
100
Time
Fig. 4. Average Filtering Errors for Eqs. (18) and (19)
6. Simulations
In this section, Monte Carlo simulation results of two examples are given. More examples are
presented in (Demirba¸s, 2010). The first example is given by
State Model
x( k + 1) = x( k)[1 +
k
cos(0.8 x( k) + 2 w( k))] + w( k)
(18)
k + 1
Observation Model
z( k) =
6 x( k)
+ v( k),
(19)
1 + x 2( k)
where the random variables x(0), w( k), and v( k) are independent Gaussian random variables
with means 6, 0, 0 and variances 13, 20, 15 respectively. It was assumed that there did not
exist any constraints imposed on state estimates. The state model of Eq. (18) is an highly
nonlinear function of the disturbance noise w( k). The extended Kalman filter (EKF) and the
grid-based approaches may not be used for the state estimation of this example, since the
EKF assumes a linear disturbance noise in the state model and the grid based approaches
assumes the availability of the state transition density p( x( k) |x( k − 1)) which may not readily
calculated (Arulampalam et al., 2002; Ristic et al., 2004). States of this example were estimated
by using the DF, the sampling importance resampling (SIR) particle filter (which is sometimes
called the bootstrap filter, and auxiliary sampling importance resampling (ASIR) particle filter
(Arulampalam et al., 2002; Gordon et al., 1993). Average absolute filtering and prediction
errors are sketched in Figs. 4 and 5 for 2000 runs each of which consists of 100 iterations.
These estimation errors were obtained by using the SIR and ASIR particle filters with 1000
particles and the DF for which the random variables x(0) and w( k) were approximated by the
approximate random variables with 3 possible values (which are given in Section 3); the gate
size ( GS) and MN were taken as 0.1 and 8 respectively. The average filtering and prediction
errors per one estimation (one iteration) were 33.8445, 45.6377, 71.5145 and 34.0660, 45.4395,
Real-time Recursive State Estimation for Nonlinear
Discrete Dynamic Systems with Gaussian or non-Gaussian Noise
15
300
DF
SIR
250
ASIR
200
150
100
Average Prediction Errors
50
00
20
40
60
80
100
Time
Fig. 5. Average Prediction Errors for Eqs. (18) and (19)
70.2305 respectively. A typical run with 100 iteration took 0.0818, 0.2753, 0.3936 seconds for
the DF, SIR and ASIR particle filters, respectively. The DF clearly performs better than both
the SIR and ASIR particle filter. Moreover, the DF is much faster than both the SIR and ASIR
particle filters with 1000 particles.
The second example is described by
State Model
x( k + 1) = x( k)[1 +
k
cos(0.8 x( k))] + w( k)
(20)
k + 1
Observation Model
z( k) =
6 x( k)
+ v( k),
(21)
1 + x 2( k)
where the random variables x(0), w( k),and v( k) are independent Gaussian random variables
with means 3, 0, 0 and variances 8, 9, 9 respectively. It was assumed that there did not
exist any constraints imposed on state estimates. Average absolute filtering and prediction
errors are sketched in Figs. 6 and 7 for 2000 runs each of which consists of 200 iterations.
These estimation errors were obtained by using the SIR and ASIR particle filters with 1000
particles and the DF for which the random variables x(0) and w( k) were approximated by the
approximate random variables with 3 possible values (which are given in Section 3); the gate
size ( GS) and MN were taken as 0.1 and 4 respectively. The average filtering and prediction
errors per one estimation (one iteration) were 38.4913, 61.5432, 48.4791 and 38.5817, 61.4818,
48.5088 respectively. A typical run with 200 iteration took 0.0939, 0.5562, 0.8317 seconds for
the DF, SIR and ASIR particle filters, respectively. The state model of the second example is
a linear function of the disturbance noise. Hence, the extended Kalman filter (EKF) was also
used for state estimation, but the EKF estimation errors quickly diverged, hence, the EKF state
estimation errors are not sketched. The DF clearly performs better than the EKF, SIR and ASIR
particle filters and also the DF is much faster than both the SIR and ASIR particle filters with
1000 particles for the second example.
16
Discrete Time Systems
140
DF
SIR
120
ASIR
100
80
60
40
Average Filtering Errors
20
00
50
100
150
200
Time
Fig. 6. Average Filtering Errors for Eqs. (20) and (21)
140
DF
SIR
120
ASIR
100
80
60
40
Average Prediction Errors
20
00
50
100
150
200
Time
Fig. 7. Average Prediction Errors for Eqs. (20) and (21)
The performance of the DF is determined by the possible values ( n and m) of the approximate
discrete random disturbance noise and approximate discrete initial state, gate size ( GS),
maximum number ( MN) of considered state quantization levels at each iteration. As GS goes
to zero and the parameters n, m, and MN approach infinity, the approximate models of Eq.
(6) and (7) approach the models of Eqs. (1) and (2), hence, the DF approaches an optimum
estimation scheme, but the implementation complexity of the DF exponentially increases with
time k. The parameters n, m, GS, MN which yield the best performance for given models
are determined by Monte Carlo simulations for available hardware speed and storage. For
given nonlinear models: the performances of the DF, EKF, particle filters, and others must
be compared by Monte Carlo simulations with available hardware speed and storage. The
estimation scheme yielding the best performance should be used. The EKF is surely much
Real-time Recursive State Estimation for Nonlinear
Discrete Dynamic Systems with Gaussian or non-Gaussian Noise
17
faster than both the DF and particle filters. The speed of the DF is based upon the parameters
n, m, GS, MN; whereas the speeds of particle filters depend upon the number of particles
used.
7. Conclutions
Presented is a real-time (online) recusive state filtering and prediction scheme for nonlinear
discrete dynamic systems with Gaussian or non-Gaussian disturbance and observation noises.
This scheme, referred to as the DF, is recently proposed in (Demirba¸s, 2010). The DF is very
suitable for state estimation of nonlinear dynamic systems under either missing observations
or constraints imposed on state estimates. The DF is much more general than grid based
estimation approaches. This is based upon discrete noise approximation, state quantization,
and a suboptimum implementation of multiple hypothesis testing , whereas particle filters
are based upon sequential Monte Carlo Methods. The models of the DF is as general as
the models of particle filters, whereas the models of the extended Kalman filter (EKF) are
linear functions of the disturbance and observation noises. The DF uses state models only to
calculate transition probabilities from gates to gates. Hence, if these transition probabilities
are known or can be estimated, state models are not needed for estimation with the DF,
whereas state models are needed for both the EKF and particle filters. The performance
and implementation complexity of the DF depend upon the gate size ( GS), numbers n and
m of possible values of approximate discrete disturbance noise and approximate discrete
initial state, and maximum number ( MN) of considered quantization levels at each iteration
of the DF; whereas the performances and implementation complexities of particle filters
depend upon numbers of particles used. The implementation complexity of the DF increases
with a smaller value of GS, bigger values of n, m, and MN. These yield more accurate
approximations of state and observation models; whereas the implementation complexities
of particle filters increase with larger numbers of particles, which yield better approximations
of conditional densities. Surely, the EKF is the simplest one to implement. The parameters
( GS, n, m, MN) for which the DF yields the best performance for a real-time problem should
be determined by Monte Carlo simulations. As GS → 0, n → ∞, m → ∞,and MN → ∞;
the DF approaches the optimum one in the average overall error probability sense, but its
implementation complexity exponentially increases with time. The performances of the DF,
particle filters, EKF are all model-dependent. Hence, for a real-time problem with available
hardware speed and storage; the DF, particle filters, and EKF (if applicable) should all be
tested by Monte Carlo simulations, and the one which yields the best results should be used.
The implementation complexity of the DF increases with the dimensions of multidimensional
systems, as in the particle filters.
8. References
Arulampalam, M.S.; Maskell, S.; Gordon, N.; and Clapp, T. (2002), A tutorial on particle filters
for online nonlinear/non-Gaussian bayesian tracking. IEEE Transactions on Signal
Processing, Vol.50, pp. 174-188.
Daum, F.E. (2005). Nonlinear Filters: Beyond the Kalman Filter, IEEE A&E Systems Magazine,
Vol. 20, No. 8, Part 2, pp. 57-69
Demirba¸s K. (1982), New Smoothing Algorithms for Dynamic Systems with or without
Interference, The NATO AGARDograph Advances in the Techniques and Technology of
Applications of Nonlinear Filters and Kalman Filters, C.T. Leonde, (Ed.), AGARD, No.
256, pp. 19-1/66
18
Discrete Time Systems
Demirba¸s, K. (1984). Information Theoretic Smoothing Algorithms for Dynamic Systems with
or without Interference, Advances in Control and Dynamic Systems, C.T. Leonde, (Ed.),
Volume XXI, pp. 175-295, Academic Press, New York
Demirba¸s, K.; Leondes, C.T. (1985), Optimum decoding based smoothing algorithm for
dynamic systems, The International Journal of Systems Science, Vol.16, No. 8, pp.
951-966
Demirba¸s, K.; Leondes, C.T. (1986). A Suboptimum decoding based smoothing algorithm for
dynamic Systems with or without interference, The International Journal of Systems
Science, Vol.17, No.3, pp. 479-497.
Demirba¸s, K. (1988). Maneuvering target tracking with hypothesis testing, I.E.E.E. Transactions
on Aerospace and Electronic Systems, Vol.23, No.6, pp. 757-766.
Demirba¸s, K. (1989). Manoeuvring-target Tracking with the Viterbi Algorithm in the Presence
of Interference, the IEE Proceedings-PartF, Communication, Radar and Signal Processing,
Vol. 136, No. 6, pp. 262-268
Demirba¸s, K. (1990), Nonlinear State Smoothing and Filtering in Blocks for Dynamic Systems
with Missing Observation, The International Journal of Systems Science, Vol. 21, No. 6,
pp. 1135-1144
Demirba¸s, K. (2007), A state prediction scheme for discrete time nonlinear dynamic systems,
the international journal of general systems, Vol. 36, No. 5, pp. 501-511
Demirba¸s, K. (2010). A new real-time suboptimum filtering and prediction scheme for general
nonlinear discrete dynamic systems with Gaussian or non-Gaussian noise, to appear
in the international journal of Systems Science, DOI: 10.1080/00207721003653682, first
published in www.informaworld.com on 08 September 2010.
Doucet, A.; De Freitas, J.F.G.; and Gordon, N.J. (2001), An introduction to sequential Monte
Carlo methods, in Sequential Monte Carlo Methods in Practice, A. Doucet, J.F.G de
Freitas, and N.J.Gordon (Eds.), Springer-Verlag, New York
Forney, G.D. (1973). The Viterbi algorihm, Proceedings of the IEEE, Vol. 61, pp. 268-278
Gordon, N.; Salmond, D.; Smith, A.F.M. (1993). Novel approach to nonlinear and
non-Gaussian Bayesian state estimation. Proceedings of the Institute of Electrical
Engineering F, Vol.140, pp. 107-113
Kalman, R.E. (1960). A new approach to linear filtering and prediction problems, Trans. ASME,
Journal of Basic Engineering, Vol. 82, pp. 35-45.
Kalman, R.E.; Busy R.S. (1960). New Results in Linear Filtering and Prediction Theory, Trans.
ASME, Journal of Basic Engineering, Series D, Vol. 83, pp. 95-108
Kee, R.J.; Irwin, G.W. (1994). Investigation of trellis based filters for tracking, IEE Proceedings
Radar, Sonar and Navigation, Vol. 141, No.1 pp. 9-18.
Julier S. J.; Uhlmann J. K. (2004). Unscented Filtering and Nonlinear Estimation Proceedings of
the IEEE, 92, pp. 401-422
Ristic B., Arulampalam S.; Gordon N. (2004). Beyond the Kalman Filter: Particle Filters for
Tracking Applications , Artech House, London
Sage, A.P.; Melsa, J.L. (1971). Estimation Theory with Applications to Communications and Control,
McGraw-Hill, New York
Van Trees, H. L. (2001). Detection, Estimation and Modulation: Part I. Detection, Estimation, and
Linesr Modulation Theory, Jhon Wiley and Sons, Inc., New York, ISBN 0-471-09517-6
Weber, C. L. (1968), Elements of Detection and Signal Design, McGraw-Hill, New York
2
Observers Design for a Class of Lipschitz
Discrete-Time Systems with Time-Delay
Ali Zemouche and Mohamed Boutayeb
Centre de Recherche en Automatique de Nancy, CRAN UMR 7039 CNRS,
Nancy-Université, 54400 Cosnes et Romain
France
1. Introduction
The observer design problem for nonlinear time-delay systems becomes more and
more a subject of research in constant evolution Germani et al. (2002), Germani &
Pepe (2004), Aggoune et al. (1999), Raff & Allgöwer (2006), Trinh et al. (2004), Xu et al.
(2004), Zemouche et al. (2006), Zemouche et al. (2007). Indeed, time-delay is frequently
encountered in various practical systems, such as chemical engineering systems, neural
networks and population dynamic model. One of the recent application of time-delay is
the synchronization and information recovery in chaotic communication systems Cherrier
et al. (2005). In fact, the time-delay is added in a suitable way to the chaotic system in the
goal to increase the complexity of the chaotic behavior and then to enhance the security of
communication systems. On the other hand, contrary to nonlinear continuous-time systems,
little attention has been paid toward discrete-time nonlinear systems with time-delay. We
refer the readers to the few existing references Lu & Ho (2004a) and Lu & Ho (2004b), where
the authors investigated the problem of robust H∞ observer design for a class of Lipschitz
time-delay systems with uncertain parameters in the discrete-time case. Their method show
the stability of the state of the system and the estimation error simultaneously.
This chapter deals with observer design for a class of Lipschitz nonlinear discrete-time
systems with time-delay. The main result lies in the use of a new structure of the proposed
observer inspired from Fan & Arcak (2003).
Using a Lyapunov-Krasovskii functional, a
new nonrestrictive synthesis condition is obtained. This condition, expressed in term of
LMI, contains more degree of freedom than those proposed by the approaches available in
literature. Indeed, these last use a simple Luenberger observer which can be derived from the
general form of the observer proposed in this paper by neglecting some observer gains.
An extension of the presented result to H∞ performance analysis is given in the goal to
take into account the noise which affects the considered system. A more general LMI is
established. The last section is devoted to systems with differentiable nonlinearities. In
this case, based on the use of the Differential Mean Value Theorem (DMVT), less restrictive
synthesis conditions are proposed.
Notations : The following notations will be used throughout this chapter.
•
. is the usual Euclidean norm;
20
Discrete Time Systems
• ( ) is used for the blocks induced by symmetry;
• AT represents the transposed matrix of A;
• Ir represents the identity matrix of dimension r;
• for a square matrix S, S > 0 ( S < 0) means that this matrix is positive definite (negative
definite);
• zt( k) represents the vector x( k − t) for all z;
1
2
• The notation x s =
∑∞
is the s norm of the vector x ∈ R s. The set s is
2
k=0 x( k) 2
2
2
defined by
s =
< +∞
2
x ∈ R s :
x s
.
2
2. Problem formulation and observer synthesis
In this section, we introduce the class of nonlinear systems to be studied, the proposed state
observer and the observer synthesis conditions.
2.1 Problem formulation
Consider the class of systems described in a detailed forme by the following equations :
x( k + 1) = Ax( k) + Adxd( k) + B f Hx( k), Hdxd( k)
(1a)
y( k) = Cx( k)
(1b)
x( k) = x 0( k), for k = −d, ..., 0
(1c)
where the constant matrices A, Ad, B, C, H and Hd are of appropriate dimensions.
The function