Discrete Time Systems by Mario A. Jordan and Jorge L. Bustamante - HTML preview

PLEASE NOTE: This is an HTML preview only and some elements such as links or page numbers may be incorrect.
Download the book in PDF, ePub, Kindle for a complete version.

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;

index-32_1.png

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