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.

DISCRETE TIME SYSTEMS

Edited by Mario A. Jordán

and Jorge L. Bustamante

Discrete Time Systems

Edited by Mario A. Jordán and Jorge L. Bustamante

Published by InTech

Janeza Trdine 9, 51000 Rijeka, Croatia

Copyright © 2011 InTech

All chapters are Open Access articles distributed under the Creative Commons

Non Commercial Share Alike Attribution 3.0 license, which permits to copy,

distribute, transmit, and adapt the work in any medium, so long as the original

work is properly cited. After this work has been published by InTech, authors

have the right to republish it, in whole or part, in any publication of which they

are the author, and to make other personal use of the work. Any republication,

referencing or personal use of the work must explicitly identify the original source.

Statements and opinions expressed in the chapters are these of the individual contributors

and not necessarily those of the editors or publisher. No responsibility is accepted

for the accuracy of information contained in the published articles. The publisher

assumes no responsibility for any damage or injury to persons or property arising out

of the use of any materials, instructions, methods or ideas contained in the book.

Publishing Process Manager Ivana Lorkovic

Technical Editor Teodora Smiljanic

Cover Designer Martina Sirotic

Image Copyright Emelyano, 2010. Used under license from Shutterstock.com

First published March, 2011

Printed in India

A free online edition of this book is available at www.intechopen.com

Additional hard copies can be obtained from orders@intechweb.org

Discrete Time Systems, Edited by Mario A. Jordán and Jorge L. Bustamante

p. cm.

ISBN 978-953-307-200-5

free online editions of InTech

Books and Journals can be found at

www.intechopen.com

Contents

Preface IX

Part 1

Discrete-Time Filtering 1

Chapter 1

Real-time Recursive State Estimation

for Nonlinear Discrete Dynamic Systems

with Gaussian or non-Gaussian Noise 3

Kerim Demirbaş

Chapter 2

Observers Design for a Class of Lipschitz

Discrete-Time Systems with Time-Delay 19

Ali Zemouche and Mohamed Boutayeb

Chapter 3

Distributed Fusion Prediction for Mixed

Continuous-Discrete Linear Systems 39

Ha-ryong Song, Moon-gu Jeon and Vladimir Shin

Chapter 4

New Smoothers for Discrete-time Linear

Stochastic Systems with Unknown Disturbances 53

Akio Tanikawa

Chapter 5

On the Error Covariance Distribution

for Kalman Filters with Packet Dropouts 71

Eduardo Rohr Damián Marelli, and Minyue Fu

Chapter 6

Kalman Filtering for Discrete Time Uncertain Systems 93

Rodrigo Souto, João Ishihara and Geovany Borges

Part 2

Discrete-Time Fixed Control 109

Chapter 7

Stochastic Optimal Tracking with Preview

for Linear Discrete Time Markovian Jump Systems 111

Gou Nakura

Chapter 8

The Design of a Discrete Time Model Following

Control System for Nonlinear Descriptor System 131

Shigenori Okubo and Shujing Wu

VI

Contents

Chapter 9

Output Feedback Control of Discrete-time

LTI Systems: Scaling LMI Approaches 141

Jun Xu

Chapter 10

Discrete Time Mixed LQR/HControl Problems 159

Xiaojie Xu

Chapter 11

Robust Control Design of Uncertain

Discrete-Time Systems with Delays 179

Jun Yoneyama, Yuzu Uchida and Shusaku Nishikawa

Chapter 12

Quadratic D Stabilizable Satisfactory Fault-tolerant

Control with Constraints of Consistent Indices

for Satellite Attitude Control Systems 195

Han Xiaodong and Zhang Dengfeng

Part 3

Discrete-Time Adaptive Control 205

Chapter 13

Discrete-Time Adaptive Predictive Control

with Asymptotic Output Tracking 207

Chenguang Yang and Hongbin Ma

Chapter 14

Decentralized Adaptive Control

of Discrete-Time Multi-Agent Systems 229

Hongbin Ma, Chenguang Yang and Mengyin Fu

Chapter 15

A General Approach to Discrete-Time

Adaptive Control Systems with Perturbed

Measures for Complex Dynamics - Case Study:

Unmanned Underwater Vehicles 255

Mario Alberto Jordán and Jorge Luis Bustamante

Part 4

Stability Problems 281

Chapter 16

Stability Criterion and Stabilization

of Linear Discrete-time System

with Multiple Time Varying Delay 283

Xie Wei

Chapter 17

Uncertain Discrete-Time Systems with Delayed

State: Robust Stabilization with Performance

Specification via LMI Formulations 295

Valter J. S. Leite, Michelle F. F. Castro, André F. Caldeira,

Márcio F. Miranda and Eduardo N. Gonçalves

Chapter 18

Stability Analysis of Grey Discrete Time

Time-Delay Systems: A Sufficient Condition 327

Wen-Jye Shyr and Chao-Hsing Hsu

Contents

VII

Chapter 19

Stability and L2 Gain Analysis of Switched Linear

Discrete-Time Descriptor Systems 337

Guisheng Zhai

Chapter 20

Robust Stabilization for a Class of Uncertain

Discrete-time Switched Linear Systems 351

Songlin Chen, Yu Yao and Xiaoguan Di

Part 5

Miscellaneous Applications 361

Chapter 21

Half-overlap Subchannel Filtered MultiTone

Modulation and Its Implementation 363

Pavel Silhavy and Ondrej Krajsa

Chapter 22

Adaptive Step-size Order Statistic LMS-based

Time-domain Equalisation in Discrete

Multitone Systems 383

Suchada Sitjongsataporn and Peerapol Yuvapoositanon

Chapter 23

Discrete-Time Dynamic Image-Segmentation System 405

Ken’ichi Fujimoto, Mio Kobayashi and Tetsuya Yoshinaga

Chapter 24

Fuzzy Logic Based Interactive Multiple Model

Fault Diagnosis for PEM Fuel Cell Systems 425

Yan Zhou, Dongli Wang, Jianxun Li, Lingzhi Yi and Huixian Huang

Chapter 25

Discrete Time Systems with Event-Based Dynamics:

Recent Developments in Analysis

and Synthesis Methods 447

Edgar Delgado-Eckert, Johann Reger and Klaus Schmidt

Chapter 26

Discrete Deterministic and Stochastic Dynamical

Systems with Delay - Applications 477

Mihaela Neamţu and Dumitru Opriş

Chapter 27

Multidimensional Dynamics:

From Simple to Complicated 505

Kang-Ling Liao, Chih-Wen Shih and Jui-Pin Tseng

Preface

Discrete-Time Systems comprehend an important and broad research fi eld. The con-

solidation of digital-based computational means in the present, pushes a technological

tool into the fi eld with a tremendous impact in areas like Control, Signal Processing,

Communications, System Modelling and related Applications. This fact has enabled

numerous contributions and developments which are either genuinely original as

discrete-time systems or are mirrors from their counterparts of previously existing

continuous-time systems.

This book att empts to give a scope of the present state-of-the-art in the area of Discrete-

Time Systems from selected international research groups which were specially con-

voked to give expressions to their expertise in the fi eld.

The works are presented in a uniform framework and with a formal mathematical

context.

In order to facilitate the scope and global comprehension of the book, the chapters were

grouped conveniently in sections according to their affi

nity in 5 signifi cant areas.

The fi rst group focuses the problem of Filtering that encloses above all designs of State

Observers, Estimators, Predictors and Smoothers. It comprises Chapters 1 to 6.

The second group is dedicated to the design of Fixed Control Systems (Chapters 7 to

12). Herein it appears designs for Tracking Control, Fault-Tolerant Control, Robust Con-

trol, and designs using LMI- and mixed LQR/Hoo techniques.

The third group includes Adaptive Control Systems (Chapter 13 to 15) oriented to the

specialities of Predictive, Decentralized and Perturbed Control Systems.

The fourth group collects works that address Stability Problems (Chapter 16 to 20).

They involve for instance Uncertain Systems with Multiple and Time-Varying Delays

and Switched Linear Systems.

Finally, the fi ft h group concerns miscellaneous applications (Chapter 21 to 27). They

cover topics in Multitone Modulation and Equalisation, Image Processing, Fault Diag-

nosis, Event-Based Dynamics and Analysis of Deterministic/Stochastic and Multidi-

mensional Dynamics.

X

Preface

We think that the contribution in the book, which does not have the intention to be

all-embracing, enlarges the fi eld of the Discrete-Time Systems with signifi cation in the

present state-of-the-art. Despite the vertiginous advance in the fi eld, we think also that

the topics described here allow us also to look through some main tendencies in the

next years in the research area.

Mario A. Jordán and Jorge L. Bustamante

IADO-CCT-CONICET

Dep. of Electrical Eng. and Computers

National University of the South

Argentina

Part 1

Discrete-Time Filtering

1

Real-time Recursive State Estimation for

Nonlinear Discrete Dynamic Systems with

Gaussian or non-Gaussian Noise

Kerim Demirba¸s

Department of Electrical and Electronics Engineering

Middle East Technical University

Inonu Bulvari, 06531 Ankara

Turkey

1. Introduction

Many systems in the real world are more accurately described by nonlinear models. Since

the original work of Kalman (Kalman, 1960; Kalman & Busy, 1961), which introduces the

Kalman filter for linear models, extensive research has been going on state estimation

of nonlinear models; but there do not yet exist any optimum estimation approaches for

all nonlinear models, except for certain classes of nonlinear models; on the other hand,

different suboptimum nonlinear estimation approaches have been proposed in the literature

(Daum, 2005). These suboptimum approaches produce estimates by using some sorts of

approximations for nonlinear models. The performances and implementation complexities

of these suboptimum approaches surely depend upon the types of approximations which

are used for nonlinear models. Model approximation errors are an important parameter

which affects the performances of suboptimum estimation approaches. The performance of a

nonlinear suboptimum estimation approach is better than the other estimation approaches for

specific models considered, that is, the performance of a suboptimum estimation approach is

model-dependent.

The most commonly used recursive nonlinear estimation approaches are the extended

Kalman filter (EKF) and particle filters. The EKF linearizes nonlinear models by Taylor

series expansion (Sage & Melsa, 1971) and the unscented Kalman filter (UKF) approximates

a posteriori densities by a set of weighted and deterministically chosen points (Julier, 2004).

Particle filters approximates a posterior densities by a large set of weighted and randomly

selected points (called particles) in the state space (Arulampalam et al., 2002; Doucet et al.,

2001; Ristic et al., 2004). In the nonlinear estimation approaches proposed in (Demirba¸s,

1982; 1984; Demirba¸s & Leondes, 1985; 1986; Demirba¸s, 1988; 1989; 1990; 2007; 2010): the

disturbance noise and initial state are first approximated by a discrete noise and a discrete

initial state whose distribution functions the best approximate the distribution functions of the

disturbance noise and initial state, states are quantized, and then multiple hypothesis testing

is used for state estimation; whereas Grid-based approaches approximate a posteriori densities

by discrete densities, which are determined by predefined gates (cells) in the predefined state

space; if the state space is not finite in extent, then the state space necessitates some truncation

of the state space; and grid-based estimation approaches assume the availability of the state

4

Discrete Time Systems

transition density p( x( k) |x( k − 1)), which may not easily be calculated for state models with

nonlinear disturbance noise (Arulampalam et al., 2002; Ristic et al., 2004). The Demirba¸s

estimation approaches are more general than grid-based approaches since 1) the state space

need not to be truncated, 2) the state transition density is not needed, 3) state models can be

any nonlinear functions of the disturbance noise.

This chapter presents an online recursive nonlinear state filtering and prediction scheme for

nonlinear dynamic systems. This scheme is recently proposed in (Demirba¸s, 2010) and is

referred to as the DF throughout this chapter. The DF is very suitable for state estimation of

nonlinear dynamic systems under either missing observations or constraints imposed on state

estimates. There exist many nonlinear dynamic systems for which the DF outperforms the

extended Kalman filter (EKF), sampling importance resampling (SIR) particle filter (which is

sometimes called the bootstrap filter), and auxiliary sampling importance resampling (ASIR)

particle filter. Section 2 states the estimation problem. Section 3 first discusses discrete noises

which approximate the disturbance noise and initial state, and then presents approximate

state and observation models. Section 4 discusses optimum state estimation of approximate

dynamic models. Section 5 presents the DF. Section 6 yields simulation results of two

examples for which the DF outperforms the EKF, SIR, and ASIR particle filters. Section 7

concludes the chapter.

2. Problem statement

This section defines state estimation problem for nonlinear discrete dynamic systems. These

dynamic systems are described by

State Model

x( k + 1) = f ( k, x( k), w( k))

(1)

Observation Model

z( k) = g( k, x( k), v( k)),

(2)

where k stands for the discrete time index; f : R xR mxR n → R m is the state transition function; R m is the m-dimensional Euclidean space; w( k) R n is the disturbance noise vector at time k; x( k) R m is the state vector at time k; g : R xR mxR p → R r is the observation function; v( k) R p is the observation noise vector at time k; z( k) R r is the observation vector at time k; x(0), w( k), and v( k) are all assumed to be independent with known distribution functions.

Moreover, it is assumed that there exist some constraints imposed on state estimates. The DF

recursively yields a predicted value ˆ x( k|k − 1) of the state x( k) given the observation sequence

from time one to time k − 1, that is, Zk− 1 Δ

= {z(1), z(2), . . . , z( k − 1) }; and a filtered value

ˆ x( k|k) of the state x( k) given the observation sequence from time one to time k, that is, Zk.

Estimation is accomplished by first approximating the disturbance noise and initial state with

discrete random noises, quantizing the state, that is, representing the state model with a time

varying state machine, and an online suboptimum implementation of multiple hypothesis

testing.

3. Approximation

This section first discusses an approximate discrete random vector which approximates a

random vector, and then presents approximate models of nonlinear dynamic systems.

Real-time Recursive State Estimation for Nonlinear

Discrete Dynamic Systems with Gaussian or non-Gaussian Noise

5

3.1 Approximate discrete random noise

In this subsection: an approximate discrete random vector with n possible values of a

random vector is defined; approximate discrete random vectors are used to approximate

the disturbance noise and initial state throughout the chapter; moreover, a set of equations

which must be satisfied by an approximate discrete random variable with n possible values

of an absolutely continuous random variable is given (Demirba¸s, 1982; 1984; 2010); finally, the

approximate discrete random variables of a Gaussian random variable are tabulated.

Let w be an m-dimensional random vector. An approximate discrete random vector with n

possible values of w, denoted by wd, is defined as an m-dimensional discrete random vector

with n possible values whose distribution function the best approximates the distribution

function of w over the distribution functions of all m-dimensional discrete random vectors

with n possible values, that is

w

1

d = min

{

[ Fy( a) − Fw( a)]2 da}

(3)

y D

R n

where D is the set of all m-dimensional discrete random vectors with n possible values, Fy( a)

is the distribution function of the discrete random vector y, Fw( a) is the distribution function

of the random vector w, and R m is the m-dimensional Euclidean space. An approximate

discrete random vector wd is, in general, numerically, offline-calculated, stored and then used

for estimation. The possible values of wd are denoted by wd 1, wd 2, ...., and wdn ; and the

occurrence probability of the possible value wdi is denoted by Pw , that is

di

Δ

Pw = Prob{w

di

d = wdi }.

(4)

where Prob{wd(0) = wdi} is the occurrence probability of wdi.

Let us now consider the case that w is an absolutely continuous random variable. Then, wd is

an approximate discrete random variable with n possible values whose distribution function

the best approximates the distribution function Fw( a) of w over the distribution functions of

all discrete random variables with n possible values, that is

w

1

d = min

{J( Fy( a)) }

y D

in which the distribution error function (the objective function) J( Fy( a)) is defined by

J( Fy( a)) Δ

=

[ Fy( a) − Fw( a)]2 da

R

where D is the set of all discrete random variables with n possible values, Fy( a) is the

distribution function of the discrete random variable y, Fw( a) is the distribution function of the

absolutely continuous random variable w, and R is the real line. Let the distribution function

Fy( a) of a discrete random variable y be given by

⎨0 if a < y 1

Fy( a) Δ

= ⎩ Fy if y

i

i ≤ a < yi+1, i = 1, 2, . . . , n − 1

1

if a ≥ yn.

Then the distribution error function J( Fy( a)) can be written as

y

n− 1

1

yi+1

J( Fy( a)) =

F 2

[ Fy − Fw( a)]2 da +

[1 − Fw( a)]2 da.

w( a) da +

i

i=1 yi

yn

6

Discrete Time Systems

Let the distribution function Fw ( a) of an approximate discrete random variable w

d

d be

⎨0

if a < wd 1

Fw ( a) Δ

= F

if w

d

wdi

di ≤ a < wdi+1, i = 1, 2, . . . , n − 1

1

if a ≥ wdn.

It can readily be shown that the distribution function Fw ( a) of the approximate discrete

d

random variable wd must satisfy the set of equations given by

Fw =2 F

d 1

w( wd 1);

Fw + F

=2 F

di

wdi+1

w( wdi+1), i = 1, 2, . . . , n − 2;

(5)

1 + Fw

=2 F

dn− 1

w( wdn);

wdi+1

Fw [ w

F

di

di+1 − wdi]=

w( a) da, i = 1, 2, . . . , n − 1.

wdi

The values wd 1, wd 2, ..., wdn, Fw , F , ..., F

satisfying the set of Eqs. (5) determine the

d 1

wd 2

wdn

distribution function of wd. These values can be, in general, obtained by numerically solving

Eqs. (5). Then the possible values of the approximate discrete random variable wd become

wd 1, wd 2, ..., and wdn ; and the occurrence probabilities of these possible values are obtained

by

Fw

if i = 1

d 1

Pw =

F

− F

if i = 2, 3, . . . , n − 1

di

wdi

wdi− 1

1 − Fw

if i = n.

dn

where Pw = Prob{w

di

d = wdi }, which is the occurrence probability of wdi.

Let y be a Gaussian random variable with zero mean and unit variance. An approximate

discrete random variable yd with n possible values was numerically calculated for different

n’s by using the set of Eqs.

(5).

The possible values yd 1, yd 2, ..., ydn of yd and the

occurrence probabilities Py , P , ..., P

of these possible values are given in Table 1, where

d 1

yd 2

ydn

Δ

Py

= Prob{y

di

d = ydi }.

As an example, the possible values of an approximate discrete

random variable with 3 possible values of a Gaussian random variable with zero mean and

unit variance are -1.005, 0.0, and 1.005; and the occurrence probabilities of these possible

values are 0.315, 0.370, and 0.315, respectively. Let w be a Gaussian random variable with

mean E{w} and variance σ 2. This random variable can be expressed as w = + E{w}.

Hence, the possible values of an approximate discrete random variable of w are given by

wdi = ydiσ + E{w}, where i = 1, 2, 3, ..., n; and the occurrence probability of the possible value

wdi is the same as the occurrence probability of ydi, which is given in Table 1.

3.2 Approximate models

For state estimation, the state and observation models of Eqs. (1)and (2) are approximated by

the time varying finite state model and approximate observation model which are given by

Finite State Model

xq( k + 1) = Q( f ( k, xq( k), wd( k)))

(6)

Approximate Observation Model

z( k) = g( k, xq( k), v( k)),

(7)

Real-time Recursive State Estimation for Nonlinear

Discrete Dynamic Systems with Gaussian or non-Gaussian Noise

7

n

yd 1

yd 2

yd 3

yd 4

yd 5

yd 6

yd 7

yd 8

yd 9 yd 10

Py

P

P

P

P

P

P

P

P

P

d 1

yd 2

yd 3

yd 4

yd 5

yd 6

yd 7

yd 8

yd 9

yd 10

1 0.000

1.000

2 -0.675 0.675

0.500 0.500

3 -1.005 0.0

1.005

0.315 0.370 0.315

4 -1.218 -0.355 0.355 1.218

0.223 0.277 0.277 0.223

5 -1.377 -0.592 0.0

0.592 1.377

0.169 0.216 0.230 0.216 0.169

6 -1.499 -0.768 -0.242 0.242 0.768 1.499

0.134 0.175 0.191 0.191 0.175 0.134

7 -1.603 -0.908 -0.424 0.0

0.424 0.908 1.603

0.110 0.145 0.162 0.166 0.162 0.145 0.110

8 -1.690 -1.023 -0.569 -0.184 0.184 0.569 1.023 1.690

0.092 0.124 0.139 0.145 0.145 0.139 0.124 0.092

9 -1.764 -1.120 -0.690 -0.332

0

0.332 0.690 1.120 1.764

0.079 0.106 0.121 0.129 0.130 0.129 0.121 0.106 0.079

10 -1.818 -1.199 -0.789 -0.453 -0.148 0.148 0.453 0.789 1.199 1.818

0.069 0.093 0.106 0.114 0.118 0.118 0.114 0.106 0.093 0.069

Table 1. Approximate Discrete Random Variables the best Approximating the Gaussian

Random Variable with Zero Mean and Unit Variance

where wd( k) is an approximate discrete random vector with, say, n possible values of the

disturbance noise vector w( k); this approximate vector is pre(offline)-calculated, stored and

then used for estimation to calculate quantization levels at time k + 1; the possible values of

wd( k) are denoted by wd 1( k), wd 2( k), ...., and wdn( k) ; Q : R m → R m is a quantizer which first divides the m-dimensional Euclidean space into nonoverlapping generalized rectangles

(called gates) such that the union of all rectangles is the m-dimensional Euclidean space, and

then assigns to each rectangle the center point of the rectangle, Fig. 1 (Demirba¸s, 1982; 1984;

2010); xq( k), k > 0, is the quantized state vector at time k and its quantization levels, whose

number is (say) mk, are denoted by xq 1( k), xq 2( k), ...., and xqm ( k). The quantization levels k

of xq( k + 1) are calculated by substituting xq( k) = xqi( k) ( i = 1, 2, . . . , mk) for xq( k) and wd( k) = wdj( k) ( j = 1, 2, . . . , n) for wd( k) in the finite state model of Eq. (6). As an example, let the quantization level xqi( k) in the gate Gi be mapped into the gate Gj by the lth-possible

value wdl( k) of wd( k), then, x( k + 1) is quantized to xqj( k + 1), Fig. 1. One should note that the approximate models of Eqs. (6) and (7) approach the models of Eqs. (1) and (2) as the gate

sizes ( GS) 0 and n → ∞. An optimum state estimation of the models of Eqs. (6) and (7) is

discussed in the next section.

4. Optimum state estimation

This section discuses an optimum estimation of the models of Eqs. (6) and (7) by using

multiple hypothesis testing.

On the average overall error probability sense, optimum

estimation of states of the models of Eqs. (6) and (7) is done as follows: Finite state model

8

Discrete Time Systems

x ( k)

qi

G

m

R

i

f ( k, x ( k), w ( k)) (

x k )

1

qi

di

x( k )

1

Gj

(

Q (

x k ))

1 x ( k )

1

qj

x ( k )

1

qj

Fig. 1. Quantization of States

of Eq. (6) is represented by a trellis diagram from time 0 to time k (Demirba¸s, 1982; 1984;

Demirba¸s & Leondes, 1985; Demirba¸s, 2007). The nodes at time j of this trellis diagram

represent the quantization levels of the state x( j). The branches of the trellis diagram represent

the transitions between quantization levels. There exist, in general, many paths through this

trellis diagram. Let Hi denote the ith path (sometimes called the ith hypothesis) through the

trellis diagram. Let xiq( j) be the node (quantization level) through which the path Hi passes

at time j. The estimation problem is to select a path (sometimes called the estimator path)

through the trellis diagram such that the average overall error probability is minimized for

decision (selection). The node at time k along this estimator path will be the desired estimate

of the state x( k). In Detection Theory (Van Trees, 2001; Weber, 1968): it is well-known that the

optimum decision rule which minimizes the average overall error probability is given by

Select Hn as the estimator path i f M( Hn) ≥ M( Hl) f or all l = n,

(8)

where M( Hn) is called the metric of the path M( Hn) and is defined by

M( Hn) Δ

= ln {p( Hn) Prob{observation sequence | Hn}},

(9)

where ln stands for the natural logarithm, p( Hn) is the occurrence probability (or the a

priori probability) of the path Hn, and Prob{observation sequence | Hn} is the conditional

probability of the observation sequence given that the actual values of the states are equal

to the quantization levels along the path Hn. If the inequality in the optimum decision rule

becomes an equality for an observation sequence, anyone of the paths satisfying the equality

can be chosen as the estimator path, which is a path having the biggest metric.

It follows, from the assumption that samples of the observation noise are independent, that

Prob{observation sequence | Hn} can be expressed as

k

Prob{observation sequence | Hn} = ∏ λ( z( j) | xnq( j))

(10)

j=1

Real-time Recursive State Estimation for Nonlinear

Discrete Dynamic Systems with Gaussian or non-Gaussian Noise

9

where

λ( z( j) |xnq)( j)) Δ= 1

if z(j) is neither available nor used for estimation

(11)

p( z( j) |xnq( j))

if z(j) is available and used for estimation,

in which, p( z( j) |xnq( j)) is the conditional density function of z( j) given that the actual value of state is equal to xnq( j), that is, x( j) = xnq( j); and this density function is calculated by using the observation model of Eq. (2).

It also follows, from the assumption that all samples of the disturbance noise and the initial

state are independent, that the a priori probability of Hn can be expressed as

k

p( Hn) = Prob{xq(0) = xnq(0) } T( xnq( j − 1) → xnq( j)),

(12)

j=1

where Prob{xq(0) = xnq(0) } is the occurrence probability of the initial node (or quantization

level) xnq(0), and T( xnq( j − 1) → xnq( j)) is the transition probability from the quantization

level xnq( j − 1) to the quantization level xnq( j)), that is, T( xjq( i − 1) → xnq( j)) Δ

= Prob{xq( j) =

xnq( j) |xq( j − 1) = xnq( j − 1) }, which is the probability that xnq( j − 1) is mapped to xnq( j) by the finite state model of Eq. (6) with possible values of wd( j − 1). Since the transition from

xnq( j − 1) to xnq( j) is determined by possible values of wd( j − 1), this transition probability is the sum of occurrence probabilities of all possible values of wd( j − 1) which map xnq( j − 1) to

xnq( j).

The estimation problem is to find the estimator path, which is the path having the biggest

metric through the trellis diagram. This is accomplished by the Viterbi Algorithm (Demirba¸s,

1982; 1984; 1989; Forney, 1973); which systematically searches all paths through the trellis

diagram. The number of quantization levels of the finite state model, in general, increases

exponentially with time k. As a result, the implementation complexity of this approach

increases exponentially with time k (Demirba¸s, 1982; 1984; Demirba¸s & Leondes, 1985;

Demirba¸s, 2007). In order to overcome this obstacle, a block-by-block suboptimum estimation

scheme was proposed in (Demirba¸s, 1982; 1984; Demirba¸s & Leondes, 1986; Demirba¸s, 1988;

1989; 1990). In this estimation scheme: observation sequence was divided into blocks of

constant length. Each block was initialized by the final state estimate from the last block. The

initialization of each block with only a single quantization level (node), that is, the reduction

of the trellis diagram to one node at the end of each block, results in state estimate divergence

for long observation sequences, i.e., large time k, even though the implementation complexity

of the proposed scheme does not increase with time (Kee & Irwin, 1994). The online and

recursive state estimation scheme which is recently proposed in (Demirba¸s, 2010) prevents

state estimate divergence caused by one state initialization of each block for the block-by-block

estimation. This recently proposed estimation scheme, referred to as the DF throughout

this chapter, first prunes all paths going through the nodes which do not satisfy constraints

imposed on estimates and then assigns a metric to each node (or quantization level) in the

trellis diagram. Furthermore, at each time (step, or iteration), the number of considered state

quantization levels (nodes) is limited by a selected positive integer MN, which stands for

the maximum number of quantization levels considered through the trellis diagram; in other

words , MN nodes having the biggest metrics are kept through the trellis diagram and all the

paths going through the other nodes are pruned. Hence, the implementation complexity of

the DF does not increase with time. The number MN is one of the parameters determining

the implementation complexity and the performance of the DF.

10

Discrete Time Systems

5. Online state estimation

This section first yields some definitions, and then presents the DF.

5.1 Definitions

Admissible initial state quantization level : a possible value xqi(0) Δ

= xdi(0) of an

approximate discrete random vector xq(0) Δ

= xd(0) of the initial state vector x(0) is said

to be an admissible quantization level of the initial state vector (or an admissible initial

state quantization level) if this possible value satisfies the constraints imposed on the state

estimates. Obviously, if there do not exist any constraints imposed on the state estimates,

then all possible values of the approximate discrete random vector xq(0) are admissible.

Metric of an admissible initial state quantization level: the natural logarithm of the

occurrence probability of an admissible initial quantization level xqi(0) is referred to as the

metric of this admissible initial quantization level. This metric is denoted by M( xqi(0)), that

is

M( xqi(0)) Δ

= ln {Prob{xq(0) = xqi(0) }}.

(13)

where Prob{xq(0) = xqi(0) } is the occurrence probability of xqi(0).

Admissible state quantization level at time k: a quantization level xqi( k) of a state vector

x( k), where k ≥ 1, is called an admissible quantization level of the state (or an admissible

state quantization level) at time k if this quantization level satisfies the constraints imposed

on the state estimates. Surely, if there do not exist any constraints imposed on the state

estimates, then all the quantization levels of the state vector x( k), which are calculated by Eq.

(6), are admissible.

Maximum number of considered state quantization levels at each time: MN stands for the

maximum number of admissible state quantization levels which are considered at each time

(step or iteration) of the DF. MN is a preselected positive integer. A bigger value of MN yields

better performance, but increases implementation complexity of the DF.

Metric of an admissible quantization level (or node) at time k, where k ≥ 1: the metric of an

admissible quantization level xqj( k), denoted by M( xqj( k)), is defined by

M( xqj( k)) Δ

=max {M( xqn( k − 1)) + ln[ T( xqn( k − 1) → xqj( k))] }

n

+ ln[ λ( z( k) |xqj( k))],

(14)

where the maximization is taken over all considered state quantization levels at time k − 1

which are mapped to the quantization level xqj( k) by the possible values of wd( k − 1); ln

stands for the natural logarithm; T( xqn( k − 1) → xqj( k)) is the transition probability from

xqi( k − 1) to xqj( k) is given by

T( xqi( k − 1) → xqj( k)) = ∑ Prob{wd( k − 1) = wdn( k − 1) },

(15)

n

where Prob{wd( k − 1) = wdn( k − 1) } is the occurrence probability of wdn( k − 1) and the summation is taken over all possible values of wd( k − 1) which maps xqi( k − 1) to xqj( k); in

Real-time Recursive State Estimation for Nonlinear

Discrete Dynamic Systems with Gaussian or non-Gaussian Noise

11

other words, the summation is taken over all possible values of wd( k − 1) such that

Q( f ( k − 1, xqi( k − 1), wdn( k − 1))) = xqj( k);

(16)

and

λ( z( k) |xqj( k)) Δ= 1

if z(j) is neither available nor used for estimation

(17)

p( z( k) |xqj( k))

if z(j) is available and used for estimation,

in which, p( z( k) |xqj( k)) is the conditional density function of z( k) given that the actual value of state x( k) = xqj( k), and this density function is calculated by using the observation model

of Eq. (2).

5.2 Estimation scheme (DF)

A flowchart of the DF is given in Fig. 3 for given Fw( k)( a), Fx(0)( a), MN, n, m , and GS; where Fw( k)( a) and Fx(0)( a) are the distribution functions of w( k) and x(0) respectively, n and m are the numbers of possible values of approximate random vectors of w( k) and x(0) respectively;

GS is the gate size; and z( k) is the observation at time k. The parameters MN, n, m , and GS determine the implementation complexity and performance of the DF. The number of

possible values of the approximate disturbance noise wd( k) is assumed to be the same, n , for

all iterations, i.e., for all k. The filtered value ˆ x( k|k) and predicted value ˆ x( k|k − 1) of the state

x( k) are recursively determined by considering only MN admissible state quantization levels

with the biggest metrics and discarding other quantization levels at each recursive step (each

iteration or time) of the DF. Recursive steps of the DF is described below.

Initial Step (Step 0): an approximate discrete random vector xd(0) with m possible values of

the initial state x(0) is offline calculated by Eq. (3). The possible values of this approximate

random vector are defined as the initial state quantization levels (nodes). These initial state

Δ

quantization levels are denoted by xq 1(0), xq 2(0), ..., and xqm(0), where x

=

qi(0)

xdi(0) ( i =

1 2 ... m). Admissible initial state quantization levels, which satisfy the constraints imposed

on state estimates, are determined and the other initial quantization levels are discarded. If

the number of admissible initial quantization levels is zero, then the number, m, of possible

values of the approximate initial random vector xd(0) is increased and the initial step of the

DF is repeated from the beginning; otherwise, the metrics of admissible initial quantization

levels are calculated by Eq. (13). The admissible initial state quantization levels (represented

by xq 1(0), xq 2(0), ..., and xqN (0)) and their metrics are considered in order to calculate state

0

quantization levels and their metrics at time k = 1. These considered quantization levels are

denoted by nodes (at time 0) on the first row (or column) of two rows (or columns) trellis

diagram at the first step k = 1 of the DF, Fig. 2.

State estimate at time 0 : if the mean value of x(0) satisfies constraints imposed on state estimates

such as the case that there do not exist any estimate constraints , then this mean value is taken

as both ˆ x(0 | 0) and ˆ x(0 | 0 1); otherwise, the admissible initial state quantization level (node)

with the biggest metric is taken as both the filtered value ˆ x(0 | 0) and predicted value ˆ x(0 | 0 1)

of the state x(0), given no observation.

Recursive Step (Step k): An approximate discrete disturbance noise vector wd( k − 1) with

n possible values of the disturbance noise w( k − 1) is offline obtained by Eq. (3). The

quantization levels of the state vector at time k are calculated by using the finite state model

of Eq. (6) with all the considered quantization levels (or nodes) xq 1( k − 1), xq 2( k − 1) ...

xqN ( k − 1) at time k − 1; and all possible values w

k− 1

d 1( k − 1), wd 2( k − 1), ..., wdn( k − 1)

of the approximate discrete disturbance noise vector wd( k − 1) . That is, substituting the

12

Discrete Time Systems

x ( k )

1

1

q

x ( k )

1

x

( k )

1

qi

qNk 1

x ( k )

x ( k )

x ( k )

x

( k)

q 1

q 3

qj

qNk

Fig. 2. Two Row Trellis Diagram of Admissible State Quantization Levels

considered state quantization levels xqi( k − 1) ( i = 1, 2, . . . , Nk− 1) for xq( k − 1) and the

possible values wd( k − 1) = wdj( k − 1) ( j = 1, 2, . . . , n) for wd( k − 1) in the finite state model of Eq. (6), the quantization levels of the state at time k are calculated (generated). The

admissible quantization levels at time k, which satisfy constraints imposed on state estimates,

are determined and non-admissible state quantization levels are discarded. If the number

of admissible state quantization levels at time k is zero, then a larger n, MN or smaller GS

is taken and the recursive step at time k of the DF is repeated from the beginning; otherwise,

the metrics of all admissible state quantization levels at time k are calculated by using Eq.

(14). If the number of admissible state quantization levels at time k is greater than MN, then

only MN admissible state quantization levels with biggest metrics, otherwise, all admissible

state quantization levels with their metrics are considered for the next step of the DF. The

considered admissible quantization levels (denoted by xq 1( k), xq 2( k), ..., xqN ( k)) and their

k

metrics are used to calculate the state quantization levels and their metrics at time k + 1. The

considered state quantization levels at time k are represented by the nodes on the second row

(or column) of two rows (or columns) trellis diagram at the recursive step k and on the first row

(or column) of two rows (or columns) trellis diagram at the recursive step k + 1, Fig. 2; where

the subscript Nk, which is the number of considered nodes at the end of Recursive step k, is less

than or equal to MN; and the transition from a node at time k − 1, say xqi( k − 1), to a node at

time k , say xqj( k), is represented by a directed line which is called a branch. Estimate at time

k: the admissible quantization level (node) with the biggest metric at time k is taken as the

desired estimate of the state at time k, that is, the node with the biggest metric at time k is the

desired predicted value of x( k) if z( k) is neither available nor used for estimation; otherwise,

the node at time k with the biggest metric is the filtered value of x( k). If there exist more than