Estimation and Control with Quantized Measurements

A NEW INTERPRETATION OF TIlE DESCRIBI/\'G FU,VCTlON

4.3

47

A New Interpretation of the Describing Function

The difficulty in analysis and synthesis arises when the output autocorrelation function needs to be evaluated. Many times a quantizer is modeled as a unit gain (G = I) and a white noise source (Widrow, 1960; Ruchkin, 1961; Stciglitz, 1966; O'Neal, 1966; Irwin and O'Neal, 1968). Widrow (1960) neglects the input-noise cross correlation as well. It is well known, however, that choosing the value of G to be the describing-function gain k will minimize the variance of the noise source, (P",,",,(O), The gain may he chosen on the hasis of other considerations, and some of them are suggested below, For example, in the analysis process it is convenient to have the autocorrelation of the noise source be of little significance in determining the output autocorrelation; that is. we should like to minimize by our choice of G the ratio (4.19)

11> """,,(IIl)/1> ",(Ill ll·

It will be shown for zero-mean, Gaussian, random processes and odd n onlincaritics that G = k provides a global minimum of this ratio for all values of the time argument Ill. Since q}".\" is not influenced by the choice of G, this value of G also minimizes 1~1!(;I!JII1)I. This criterion may be thought of as a whiteness property. and the "whitest" noise source may provide simplifications in synthesis and analysis procedures. Lastly, in the synthesis process it is convenient to think of the quun tizcr output as the sum of a signal source and an uncorrclutcd noise source. It will be shown that when G is the describing function, the "noise-to-signal ratio." (4.20) is at a local minimum (the other extrema occur at G = ± v.]. This means that the noise source is as white as possible relative to the signal source. These three results depend on the following lemma. Lemma For zero-mean Gaussian processes and odd. zero-memory nonlincaritics it is true that

O::;r::;x.

(4.21)

PI"()(!{ Expand the joint normal probability-density function for :(t)

and :(t + r ) in Hermite polynomials. Then q>yY(r) may be written

48

OPTIMAL LiNEAR ESTIMATORS

(Gclb and Vander Velde, 1968, Appendix E): -r.

ePn{r)

L

=

a,;,p~'(r)

m(odd)= 1

I

= k2eP=Ar) +

(4.22)

a;;,p';'(r),

m(odJ);;;;;; 3

where pAr) is the correlation coefficient between :;(t) and rtr I

r 1[2 (_1[//1.)

(I", = )

f

x

_

~

2

1l",(U)

)"(0":11)

exp

(

[/2)

-) II",(II) du, _

(1/2)J .

= (-1)'" exp ( -tl ) -tI'" [ exp - 2 du" 2

+

r), and (4.23)

(4.24)

The assertion of the [emma follows from the fact that eP:: is an odd function of pAr) and that the sum on the right-hand side of Equation 4.22 is positive for p= > 0 and negative for o, < O. To prove that the describing function minimizes the significance of the ratio of noise autocorrelation to output autocorrelation we use Equation 4.18 to write

eP"",,(Jm) 1= 11 - G(2k - G) eP,=,AtlJ) I. (4.25) eP,..(III) ePn·(tll) Since fIJ.=lfIJ" is positive, the global minimum occurs either when G(2k - G) is at its maximum (which is k 1 at G = k) or when G is such that the second term cancels the first term. The latter possibility is ruled out by the lemma, so that G = k provides the global minimum. The value of IflJnGnG(m)1 is also minimized by this choice of G, since cPn . is independent of G. The noise-to-signal ratio, or criterion of whiteness relative to the signal, is given by

(4.26) The argument of the magnitude operation can never be zero, according to the lemma, so it follows that the extremal points occur at G = k and G = ±x.. We shall use the local minimum at G = k, which will be a global minimum if Iq)nl is less than 2k 2 IeP==I. The noise-to-signal ratio. Expression 4.20. can be calculated as a function of the magnitude of the correlation between two input samples for Gaussian random variables (both eP yy and q)=: arc odd

A NEil' INTERPRETATION OF TIlE DESCRIBING FUNCTION

49

functions of the input correlation, and by Expression 4.20 the noiseto-signal ratio is an even function of the correlation), Figures 4.3 and 4.4 show results for the optimal N-Ievel Gaussian quantizcr and the threshold quantizcr, respectively. To give some idea of the advantage of using the describing-function gain k rather than unit gain in the quantizcr model, Figure 4.3 shows the noise- to-signal ratios for both. 1.0

,

" " '-

....... - ............ _---

- ..

_--

N-2 ------NOISE TO SIGNAL RATIO

4>yr -1 GI2 k-GI4>.. GAUSSIAN QUANTIZER

0.1

-... _----~_

s

'"

---------~~1

0.01

2

0.001

, OJ---- G-k

------ G - 1 2

O.OOOll-_---'_ _-,J-_ _-,J-,--_-,-L:-'-..ul"-L 0.8 0.6 0.4 0.1 o 1.0 MAGNITUDE OF INPUT CORRELATION, Pz

Figure 4.3 Noise-to-signal ratio
G)(f)~z -

...I

I, Gaussian quantizcr.

50

OPTIMAL LINEAR ESTIMATORS 1.0

NOISE TO SIGNAL RATIO +yy 2

-l

+zz

k THRESHOLD QUANTIZER

0.1

0.01

2

0.001

2

O.B

0.6

0.4

0.2

MAGNITUDE OF INPUT CORRELATION, Pz

Figure 4.4 Noise-to-signal ratio !/J,jk 2 (!>== - I, threshold quantizcr.

For unit gain, not only is the ratio larger, but it does not go to zero as input correlation goes to zero. The approximate correlation time for the quantization noise can be determined from these plots: given the autocorrelation function of the zero-mean Gaussian process that is being quantized, the noise-

A NEW INTERPRETATiON OF TIlE DESCRIBING FUNCTiON

51

to-signal ratio and, thus, the noise autocorrelation may be determined for each value of input autocorrelation function. The plots may also be used to determine under what conditions the quantization noise is white. For example, suppose that noise-to-signal ratios of 0.0 I or less are considered negligible and that the process is being quantized to two levels. When the quantizcr is represented by the describing-function gain k, the quantization noise may be considered white if the correlation between adjacent input samples is less than 0.24. If unit gain is used, the quantization noise may never be considered white.

4.4

Optimal Linear Filters for Quantized Measurements

In this section we briefly consider the problem of designing the optimal linear filter for quantized measurements of a stationary process. Figure 4.5 shows the system to be evaluatcd : x is the scalarvalued signal, r is white observation noise, J' is the quantizcr output, and e is the estimation error. The linear filter weights the samples to provide the best linear estimate of the signal x.

WHITE NOISE QUANTIZER

'0

SIGNAL

'0

•

• ..Y

'0

~

LINEAR FILTER

Yo

,L K i Yn.l-i

1·1

'0

-x -"'¢'

•

eo

Figure 4.5 Linear filtering problem.

Estimation with a Finite Number of Meusuroments When a finite number of measurements are used to estimate the signal matrix methods may be used (Kellog, 1967). Suppose that the value of x" based on AI quantizcr outputs YII,YII-I""'YII-Af+l is to

52

OPTIMAL LINEAR ESTIMATORS

be estimated. Let 'In be a vector representing these measurements: Yn

Yn -

'In = (

I

(4.27)

Yn-~(+I

x

and let n be the minimum variance linear estimate of x" (without loss of generality it will be assumed that all random variables have zero mean). Then

Xn

=

(4.28)

KlJn,

and the choice of the row vector K that minimizes the variance of the estimate (Schweppe, 1967) is

(4.29) The variance in the estimate (Schweppe, 1967):

e2

= E(x - X)2 = x 2 -

IS

given by the following relation

KE(lJ"lJ~)KT.

(4.30)

Because the processes are stationary, the filter gains K may be expressed in terms of the quantities introduced in the previous section. There are only At independent elements in the M x M covariance matrix of '1, since the ijth element is

[E(lJlIlJ~)Jij

= EU'n+l-iYlI+I-) = ¢n-(i -

j).

(4.31)

Furthermore, the ith element of the row vector E(xlIlJ~) is [E(XlIlJ~)Ji = E(xlIJ',,+I-j) N

=

I

E(X,,!Zn+l_i E A i )y i P(zll+ l _ j E A i ) .

(4.32)

i> 1

For Gaussian processes the expectation of x, conditioned on z; + 1 -; E Ai, which may be found from the methods of Section 2.4, is

_ ¢n(i - 1)

-

I

i --2~-E(z"+1-i Zn+l-i E A ), {]z

(4.33)

OPTIMAL LINEAR FILTERS FOR QUANTIZED MEASUREMENTS

53

where ¢x:>.'(.'.) is the autocorrelation function of the .x process. Substituting this in Equation 4.32 yields" (4.34) where k is the quantizer describing-function gain of Section 4.2:

1 L., ~ E(z Iz E A')y' ..Pt: E A')..

k = --, (J

=j

(4.35)

== 1

The equation of the filter weights, Equation 4.29, may now be

expressed as (4.36) where the At-component vector rjJ.'Cl; and At x Af matrix Yare defined by

... ~ (

1>,,(0)

.

1>,,(M -

J

y~ [1>y,(i-j)}.

(4.37)

(4.38)

Estimation with all l njinit e Number ojMeasurcment.. . \Vhcn the number of measurements used in the estimate becomes infinite, spectrum-factorization techniques must be used to find the filter weights (Raggazzini and Franklin, 1958). The optimal filter will not be a rational function of the Z-transform variable, even if the x process has a rational spectrum, because the spectrum of the quantizcr output is not rational. This implies that an infinite number of filter weights must be stored, unless the quantization-noise spectrum is approximated by a rational function (Lanning and Battin, 1956). An alternative approach is to compute the mean square estimation error for difTerent memory lengths and truncate the memory when the improvement in mean square error with more measurements is negligible.t The matrix inversion that is required for the computation of the mean square error (Equation 4.30) may be done quite readily with existing computer routines, or it may be done recursively. The recursive computation is performed by partitioning the ('1 + 1) x ('1 + I) .. Smoothing and prediction are easily done by shifting the argument of Equation 4,Jt t Sec Grcnundcr and Szcgo (l1.J5iS) for a discussion of rates of convergence.

tP.,., in

54

OPTJ.\/AL LINEAR ESTJ.IfATORS

matrix Y into a 1 x 1 matrix, two vectors, and the '1 x (J matrix Y. The inverse of the (,/ + I) x ('I + I) matrix Y may be found in terms of the inverse of the 'I x '/ matrix Y (Schweppe, 1967). This process may be initiated by calculating the inverse of the I x I matrix Yand proceeding to higher dimensions. Figure 4.6 shows how the mean square estimation error varies with memory length for observations that have been quantized to two levels by the optimal Gaussian quantizcr. The computations were carried out for a first-order and second-order Gauss-Markov process. The exponential envelope of the autocorrelation for the second-order process is the same as the autocorrelation function of the first-order process. Note how little improvement there is beyond a memory length of 6 to 8 samples.

0.",-----------------------, 0."

0.34

0.32

O.lO

,

'-------------------------------------------

0.28

0.26

a

10

12

1.

16

1.

,.

FIlTER MEMORY LENGTH. SAMPl£S

Figure 4.6 Mean square error for two-level measurements.

N 1I111cric(/1 Results The optimal linear filters were calculated for quantized measurements of the first-order and second-order processes described above. The performance for a memory length of 20 was used as an indication of the performance of the infinite-memory filter. In Figure 4.7 these results arc compared with the ensemble performance of the Gaussian fit algorithm (in the pulse-code-modulation mode) for the first-order

OPT/,\fAL LINEAR FILTERS FOR QUANTIZED MEASUREMENTS

55

1.0 r------------------------,

...... ....

.... .....

.... ..... .....

............ - ...

-- ............ _---- ---------

2

(;;-)- 0.25

Noc:o----L -

QUANTIZER INPUT

0

x+ v

- - - - - ONE MEASUREMENT - - OPTIMUM LINEAR FILTER GAUSSIAN FITALGORITlfo,\ P£RFORMANCE ESTIMATE A 0

SIMULATIONS

O. OI ....._ _......._ _......_ _......._ _-'-_ _---'-_ _----L_ _~ 2 4 S 6 7 8 9 3 Nl.MBER OF QUANTIZER OUTPUT l£VELS. N

Figure 4.7 Estimation-error variance, Gaussian fit algorithm (reM) and optimal linear filrer.

process (the results with the second-order process were essentially the same and are not displayed). The graph shows data for cases both with and without observation noise. In the case in which observation noise is included both filters show a rapid decrease in error variance with the number of quantum levels and at 8 output levels (3 bits) arc within 12 percent of the error variance

56

OPTIMAL LINEAR ESTIMATORS

that is obtained with an infinite word length. There seems to be no advantage in performance over the linear filter beyond 4 or 5 output levels. In the case in which observation noise is not included the error variance of the Gaussian fit algorithm is approximately 10 percent below that of the optimal linear filter for 2 to 8 output levels. When the two methods are compared for their ability to attain the lower bound, it is seen that for 4 or more output levels the linear filter remains roughly halfway between the upper bound (the one-measurement error variance) and the lower bound.* The Gaussian fit algorithm is rapidly approaching the lower bound and achieves marc than 90 percent of the difference between upper and lower bounds by the time 8 output levels arc used. The problem of quantizers with linear feedback is discussed in Section 6.4, where it is shown that the optimal linear feedback clement must be determined in an iterative manner. Although no performance estimates of quantizers with optimal linear feedback were made, it is expected that they too will compare favorably with the Gaussian fit algorithm when the input processes are stationary. 4,5

Joint Optimization of the Quantizer and Filter

Until this point the optimal Gaussian quantizer has been discussed. It is optimal in the sense that the quantum intervals and quantizcr outputs have been so chosen as to minimize the mean square error between the quantizer input and output when the input sample is drawn from a Gaussian distribution. There is no reason to think that this choice of parameters will be optimal when linear estimates of the quantizer input arc being made from the quant izer output. Kellog (1967) briefly discusses t he pro blem and points out that the optimal static (one sample) quantizcr in conjunction with filtering is truly optimal only if the quantizer input samples are independent. Thus, we might expect that the optimal quantizer parameters will be a function of the filter memory length and the second-order probability-density functions of the quantizer input process. We proceed by assuming that the optimal linear filter is used for any choice of quantizer parameters, and we find the necessary conditions for these parameters in terms of optimal filter weights. This is a complex • This lower bound is computed under the assumptions that all rnca surcmcnts except the last one are linear and that only the last one is quantized.

JOINT OPTIMIZATION OF TilE QUANTIZER AND FILTER

57

parameter-optimization problem: the mean square error is a function of the quantizer describing-function gain k, the optimal linear filter weights, and the quantizer output autocorrelation function; all of these are functions of the quantizer parameters. The usual approach in system design has been to use the optimal static quantizer (Kellog, 1967; Gish, 1967). In this section (and Appendix C) we gi ve some analytical justification for this procedure: it is shown that ensemble mean square error is relatively insensitive to changes in quantizer parameters when the optimal static quantizer is used. This result is not restricted to Gaussian processes. The Necessary Equations for Minimum Mean Square Errol' In Section 4.4 the optimal linear filter K and mean square error in the optimal linear estimate were stated for zero-mean stationary processes:

K=

k¢~xY-[,

2

e = x

-

= x

2

2

(4.39) T

-

KYK

-

¢~x k 2

(Y)-) ¢x.•.

(4.40)

where rPxx is an At-dimensional column vector whose ith component is I), Y is an Ai x At matrix whose ijth element is

y

= [Y..t = (
k2

'

(4.41)

This may be used in Equation 4.40 to give

e2

= x 2 ~ ¢;x Y" l¢xx'

(4.42)

Let /5Y be the matrix of small changes in the elements of Y and /5c 2 the change in the mean square error that is caused by /5Y:

Je 2 = -rP.~:,(j(Y- L)rPxx =

¢~xy-l(jyy-lrPx"

(4.43)

58

OPTIMAL LINEAR ESTIMATORS

But

~

kK.

(4.44)

Substituting Equation 4.44 in Equation 4.43 gives

&' = Kk'bYKT M

~

M

I: I:

(4.45)

K,KpbYij.

t» 1 j = I

There are only AI independent clements in the AI x AI matrix Y, and they arc the AI quantities: _ 1>,,(111) b(m-~, )

m=O,l, ... ,M-l.

(4.46)

It is shown in Appendix C that with the usc of this information Equation 4.45 may be written

(4.47) As before, let the jth quantum interval Ai, with j ~ 1, ... , N, have lower and upper bounds ,P and tli + I, respectively, and let yi be the quantizcr output when the quantizcr input z falls in Ai. Note that the mean square error is an explicit function only of the parameters hU), with i ~ 0, ... , At - I, by virtue of Equations 4.41, 4.42, and 4.46, and the h(i) in turn are functions of the quantizer parameters til and j:', Thus the partial derivatives of the mean square error with respect to the quantizcr parameters may be found by means of the chain rule:

be' ~

AI-I

De2

(N+

I: - I: r o Dh(i)

11= 1

e

,,=

I

(~b(i)

-btl" tid"

+

N {'h(i)

I: -by" Dy"

)

11= 1

ee' (DhU))] bd" + i [Mi:l De' (ah U))] by". f l Db(i) [M Dd Db(i) Dy" i~O

ll

11= 1

t

»

0

(4.48)

JOINT OPTIMIZATION OF TIlE QUANTIZER AND FILTER

59

From this the necessary equations for minimum mean square error arc =

0,

IJ

+

= I, 2, ... ,N

I, (4.49)

=

0,

IJ

=

I, 2, ... , N.

The partial derivatives of the mean square error with respect to the variables b(i) that appear here may be inferred from Equation 4.47: i

=

0, (4.50)

th(i) M-j

2k 2

L

i = 1, 2, ... , AI - 1.

KjK j + i ,

j = 1

The partial derivatives of the b(i) with respect to the quantizer parameters arc derived in Appendix C and are 2 k2

( I") (/I

p~ ( J

I

,,)(J,n- 2+ Y" -

- Y

I

¢)'}'(O) III)

k(J; (

,

ub(11l }

m

= 0, (4.51)

(~tl"

2 p~ (d")(y,,k2

1

- Y ") [E(Yj+m

I

Zj

=

dO)

-

¢p.(m) (J;k d~J '

m i= 0, th(m)

2

" [

c/>,;m)

Dy" =k 2 P(Z E A ) E(Yj+mIYj=y")- O'~k E(zJlzJEA

II)] , (4.52)

where Zj and Yj+m are the quantizer input and output at times t j and respectively. Substituting Equations 4.50,4.51, and 4.52 in Equations 4.49 yields the specific necessary conditions for minimum mean square error in conjunction with optimal linear filtering. The number of equations is reduced when the probability distributions are symmetric.

tj + m ,

60

OPTIMAL LINEAR ESTIMATORS

Discussion The necessary conditions that must be satisfied by the quantizcr parameters in the one-sample, or static, case are given by Max (1960):

r"

I

(4.53)

= E(z z E A'),

y,,-l+ Y" = d"

2

(4.54)

.

These results may be substituted in Equations 4.51 and 4.52 to provide the partial derivatives of the h(lIl) variables evaluated at the statically optimal quantizcr parameters:

0, ,'b(m)

cd"

2 k 2 p,(d')(y' -

X

1 -

111

y,,)

[ E(Yj+m I Zj = d") -

);:2

+ 2

Y')J '

0, tb(m)

2y

= 0,

(4.55) m

# 0,

111

= 0, (4.56)

/l

(I

2 P(z E A') Ell'j+", Yj = y') -
m # O.

To obtain the last two equations the value of k that must be used is

(4.57) It is expected that the partial derivatives of b(m) with respect to the quantizcr parameters will be small because of the following: (l) the bracketed term in Equation 4.55 is the difTcrcncc between a conditionalmean estimate and the numerical average of two best linear estimates of the same quantity, and (2) the bracketed term in Equation 4.56 is the difference between a conditional-mean estimate and the best linear estimate of the same quantity, This conjecture was verified numerically: not only did minimization involve extensive computation. but the mean square error was never reduced by more than I percent from the results obtained by using the statically optimal quantizcr for the few cases that were tested.

JOINT OPTIMIZATION OF TilE QUANTIZER AND FILTER

61

We conclude that, since the statically optimal quantizcr nearly satisfies the necessary conditions when filtering is included, it should be a good design in the majority of cases, although this cannot be guaranteed by the analysis presented here.

4.6

Summary

This chapter has dealt with the topic of optimal linear estimation with quantized measurements. The autocorrelation function of the quantizer output was examined in some detail for zero-mean Gaussian processes, and the quantizcr was modeled by a gain clement and an additive-noise source. Choosing the gain element as the random-input describing function not only minimizes the variance of the noise, but also minimizes the contribution of the noise autocorrelation to the output autocorrelation. This reduces the amount of computation required to obtain the output autocorrelation to any given accuracy. The describing function also provides the "whitest" noise source for two criteria of \\ hitencss, Computation of the optimal linear filter was described, and its ensemble performance was compared with that given by the Gaussian lit algorithm in the pulse-code-modulation mode. For the comparisons that were used it was found that the error variance of the Gaussian fit algorithm is roughly 10 percent lower than that of the optimal linear filter, although the Gaussian fit algorithm is much more efficient in attaining lower bounds. Lastly it was shown that if a quantizcr is optimized without regard to the subsequent linear filter, it nearly satisfies the necessary conditions for the joint quantizcr-filter optimization.

5 Optimal Stochastic Control with Quantized Measurements S.I

Introduction

In this chapter we turn to the problem of controlling a system subject to random disturbances. Generally speaking, the problem of optimal control is more difficult to solve than that of optimal estimation. In fact. the latter can be shown to be a special case of the former. The optimal controller executes a strategy to minimize a performance index. which is the expected value of some function of the Slate variables and control variables. The optimal strategy combines the two functions of estimation and control, and the distinction between the two is not always clear. In some cases, usually involving the separation theorem, the tasks of the optimal stochastic controller can be divided into estimation and control. The following section contains a statement of the problem of discrete-time optimal stochastic control. The solution through dynamic programming is outlined and applied to a two-stage process with a linear system and quadratic cost. The separation theorem is discussed. In the next section the optimal stochastic control is computed for a two-stage process with one quantized measurement, and the "dual control" theory of Fcl'dbaurn (1960) is used to explain the nonlinear control. Lastly, another separation theorem for nonlinear measurements is presented; the system is linear and the cost quadratic, and feedback around a nonlinear measurement device is required. 62

OPTIMAL STOCIlASTIC CONTROL

5.2

63

Optimal Stochastic Control

In this section we present a statement of the problem of optimal stochastic control for discrete-time systems and indicate the method of attack by dynamic programming. The solution for a two-stage process with a linear system, quadratic cost. and nonlinear measuremcnts is obtained; the separation theorem is rederived by induction from this two-stage example. Statement (~f the Problem The problem of optimal stochastic control will now be stated. It is assumed that we know the following. State equation:

Measurement equation;

where Xi = state vector at time tf, u, = control vector at time t., =i = measurement vector at time ri , Wi = process-noise vector at time t., t'; = measurement-noise vector at time t.,

It is further assumed that the process-noise and observation-noise vectors arc independent of each other and of the initial conditions, that their probability-density functions arc known and. finally, that the probability-density function of the initial conditions is known. For clerical convenience let the collection of all past control actions and measurements be (5.1)

For any given control policy u,(0,) the expected value of the cost function from time tl;. to the end of the problem is givcn by J,

~

ELt,

LJx j , ui 0)]

+

¢(XN+ Il1

0,}.

(5.2)

As indicated in the equation, the expectation is conditioned on 01;. but, more importantly, it is carried out under the constraint that more

64

OPTiMAL STOCIIASTIC CONTROL

measurements are to be taken in the future through the relationships u;(0). The optimal control problem, then, is that of choosing the functional relations u/0) sa as to minimize the expected cost of completing the process.

Solution by Dynamic Programming The only known method of solution to this problem is dynamic programming (Dreyfus, 1965, 1964; Aok i, 1967; Bellman, 1962). As has been pointed out by several people (for example, Dreyfus, 1965), the cost is now ti functional of the state probability-density function, as distinct from what it is in the deterministic-control problem, in which it is a funct ion of the state. Proceeding to the last stage, the remaining cost is J", = E[L.\(x:v. u.\)

+

¢(X!l'+

d

I 0.'1].

(5.3)

Given any measurement and control sequence, this cost function is minimized with respect to II"" subject to the state equation constraint. The optimal cost at (y, J~(., may then be expressed as

J'N

= JR(uo, ... ,u.v-t;::t, ... ,:::v) = JR(0.. . ),

where it is to be understood that the arguments of J x arc those that determine the required conditional probability-density functions. At time t.\_ I the cost to complete the process by using WIY U,\"_I, but then the optimal Ii:' is

= E[L,\"-I(XN-I,U.v-d + E(J~~·10.v-l,u\,-dI0N-tJ.

J.\_I

(5.4)

The expectation over all possible measurements =", is necessary, since a t time t,\" _ 1 ::"\. has not yet occurred. The control 11.\' _ I is so chosen as to minimize J.., _ I , and the process of stepping back ward and minimizing is repeated. This leads to the well-known recursion relation (Dreyfus, 1965): J)'(0;)

= min u,

E[L,(x, , u;)

+

E(J7+

1(0;+d 10" uJ 10,].

(5.5)

Linear Sysiems and Quadratic Cost Now consideration will be limited to systems described by linear difference cq uations su bjcct to a quadratic-cost criterion:

+ GkUk +

Xk+ 1

=

s, =

E[tk .;Aix; + u[(0,)B,u;(0,) + .t,

l1>kXk

(5.6)

Wh>

ls'V+ IX....

+1

10k} (5.7)

OPTIMAL STOC IiASTIC CONTROL

65

where the newly introd uced qu ant ities a re the positive defin ite weighting matrices Aj • Hi. and "\",\' ' ' t. the sta te transition matrix 1IJ.. . and the contr ol gain matrix G, . No con straints arc placed o n the measuremen t equation or control.

Let us now develop the solution to a two-stage problem . using the con cept s outlined a bo ve. The tot al cos t is )0

= £( x6.4oxo +

u~Bouo

+ x fA lx , + u fB tu , + XIS1Xl i (-)0 ). (5.8)

The cos t for the last stage is

))=

E(xfAt x, + ufB lu l

= E(x f A ,x ,

+ XrS1X2 1e d

+ ufB ,u , + Il ,x, + G ,u , + 0',11 ., 10.). (5.9)

where the latter result is o bta ined by using the sta te equ ati on . Equation 5.6. for x , . The following notation is used for th e qu adrat ic form : 11.1'11 ,...) = y T(.. . ).1'.

By taking the derivative of the cost with respect to u , or by co mpleting sq uare s it can be sho wn tha t the o ptimal choice of control u , is u'j : (5.10) No tice that th is last co nt ro l ac tio n is a linear function of the co nditio nal mea n of the sta te. T his is a lways tr ue for the last co ntro l ac tion o f a probl em with linear system and quadratic cos t ; th e two-stage pr obl em conside red here may be th ought o f as the last two stages of a co nt rol process of arbitrary length. Equa tio n 5.10 is substituted in Equa tion 5.9 to produ ce the op tima l co st for the last stage :

Jj

= E[xf( A, + f S, ,).r , 10,J + Ell o·,II., +

E(x f I O , )<1>f S,G ,(B ,

+ GfS,G.) - 'Gf S, ,E(x , 10 , ). (5. 11)

W e rna)' drop the process-noise term (rorn the cost function. since it cannot be influenced by control. Furthermore . we may define the following matrix for conven ience :

C , .. f S, G ,(B ,

+ GfS ,G, )"GfS, , .

(5.1 2)

The last term o f the cost function may be man ipulated in the following

66

OPTIMAL STOClfASTlC CONTROL

manner: E(xf

/0d C 1E (X t 10d

0 d E(x [ 10d]

=

tr[C1E(xl

=

tr {C1[E(XIXf J 01) - E(elei' 1 0 d]]

=

E(xfC 1 X l

1

10 d -

1

tr [CIE(ele[ 0

d], (5.13)

where tr( ... ) denotes the trace of a matrix, and E(ele[ 10d is the covariance matrix of estimation errors after the measurement Z I has been processed. The optimal cost of completing the stage may be rewritten by substituting Equation 5.13 in Equation 5.11 (and dropping EII»'llls o) :

J~

= E(xfS1XI

1o.) + tr [C1E(elef led].

(5.14)

where the matrix S. is

s, = AI =

A.

+ cIlfS2<1>1 + <1>i[S2 -

- C1 S2GI(B1

+

G[S2Gd-1GfSl]cIll.

(5.15)

The cost for the last stage will now be averaged over all possible measurements Z I : E(J';

100. uo) =

E{E(x[SlXl

= E{xfslXl

+

10d +

tr [C lE(elef 10d] 1°0, uol

tr [CIE(ele[ 101)]

1°°' uo}.

(5.16)

Substituting this result in Equation 5.4 yields the total cost arrived at by using allY initial control Uo and the optimal control uj :

Jo

=

E{xl"Aoxo + ul"Bouo + XfS1XI (5.17)

The optimal control u~ is that which minimizes this expression. The Separation Theorem At this point we shall discuss some sufficient conditions for the socalled separation theorem (Joseph and Tou, 1961; Dcyst, 1967; Gunckel and Franklin, 1963). In addition to the previous assumptions about the independence of the process-noise vectors, observationnoise vectors, and initial-condition vector, it will now be assumed that they are normally distributed with known means and variances. It will also be assumed that the measurement equation is linear and that a measurement will be taken at each time instant.

()PTlJfAL STOCIfASTIC CONTROL

67

Several pertinent points may now be made: 1. All random variables are normally distributed because of the linear equations and Gaussian initial conditions. 2. The conditional mean of the state vector is generated by the (linear) Kalman filter. J. The covariance matrix of estimation errors conditioned on all past observations is known a priori (Deyst, 1967; Stricbcl, 1965) and is not influenced by the realization of the measurement/control sequence. Dynamic prozrammina must be used to solve for the optimal stochastic control sequence {u'f:" u'l , ... , u~~). The two-stage problem may be used to advantage by replacing t : with t rH I , l l with t:;, and to with ('I-I' Equations 5.9, 5.10, and 5.17 become

I N = E(x,~ANXN u'!.I

=

-(8.1/

+

u~Bxu.'1

+ x~+IS,v+lxN+110N'us),

+ GJ-S,v+ IG"r IG,~S.I/+ l
(5.18) (5.19)

I N- 1 = E(X.~-IAN-1XN-l

+ u~-IB,I/-IU,'1-1 + xIS,I/XNI0 N- I , u.'1 - I) + tr[E(CNEN1,'1 10 ,v - I , u.v - d J, (5.20)

where X"'l-I/ = E(x,v 10:;),

CN

= $rS.I/+ IG.,(B:; +

S",

=

A.\.

+

G.~s.'I+ IGN)-IG:'S.v+ 1
<1>~S.'I+ 1<1>,'1 - CN'

£"1.'1 = E[(XN - XNI.v)(XN -

XNI'IY ION].

Because the covariance matrix of estimation errors, £.\'1-"" is independent of any control action, the optimal control u~. _ I may be determined from a cost function equivalent to Equation 5.20:

I

N- 1 =

E(xr-tAN-IXN-1

+ X~SNXN !0 N -

+

U~-tBN-IUN-1

1, UN- I)'

(5.21)

Since this expression is the same as Equation 5. I8 with its subscripts reduced by 1, it follows that the expression for optimal control, Equation 5.19, is valid if all its subscripts are reduced by 1. The same holds for the matrices C o\ ' and S.\,. The remaining optimal control actions

68

OPTiMAL STOCIIASTiC CONTROL

are found in a like manner and may be expressed as

u7 =

-(B;

+ G{S;+ IG,j-IG{Si+ 1(J);iili'

(5.22)

where

s, =

A;

+ nSj+ 1

-

s., IGi(Bi + G{Sj+ lGJ-1G/Si+ 1](J)j,

S.'1+1 given.

(5.23)

The control gain matrix in Equation 5.22 is the same one that arises in the deterministic problem of a linear system and quadratic-cost control (Bryson and Ho, 1969). Thus the optimal stochastic control is "separated" into two parts: determination of the conditional mean of the state vector with the Kalman filter and multiplication of this estimate by the optimal gain sequence from the deterministic linear system and quadratic cost control problem. 5.3

Some Examples of Optimal Stochastic Control with Quantized Measurements

The purpose of this section is to compute the optimal stochastic control for a two-stage problem by using several quantizing elements in the observation path. The scalar state under consideration obeys the following difference equation: Xj=X j

-

1 +11;_1,

i = 1,2.

(5.24)

a;".

The initial conditions are Gaussian with mean Xo and variance No process noise has been included since, for the first stage, it may be combined with the initial conditions and, for the second (last) stage, it does not influence the control. One measurement without observation noise is to be taken at II through a quantizer, which will be specified later. The cost function for this problem is (5.25)

where ho , (/1, hi, and (/2 are positive weighting coefficients corresponding to the matrices of Equation 5.8 (the mean square value of the initial state cannot be influenced by control and has been eliminated). For linear systems and quadratic cost the optimal value of the last control action is always a linear function of the conditional mean of the state, as given by Equation 5.10: u"I

(5.26)

OPTf,I/AL STOCI/ASTlC CONTROL

69

Let eland s 1 be the scalar versions of the matrices C 1 (Equation 5.12) and 51 (Equation 5.15):

(5.27)

The total cost when the optimal value of Equation 5.17) as

u'l is used may be written (see

(5.28) Let the M quantum intervals be denoted by Ai, with i = 1, ... , M. Substituting for XI from the state equation, Equation 5.24, the cost may be rewritten as

At

+

elI i

»

COY

(x I

IXI E A i) Pi« 1 E A i).

(5.29)

J

where COY (x 1 Ix I E Ai) is the mean square estimation error in Xl, given that XI lies in Ai, and P(x l E Ai) is the a priori probability that x I will lie in Ai. Both these quantities are functions of the initial control, because x 1 is normally distributed with mean .'i'o + [10 and variance 2 11"0'

It is convenient to define a quantizer distortion function D at this time: (5.30)

This is the normalized mean square estimation error when a random variable is quantized. If the limits of the quantum intervals are [til],

and the a priori distribution is Gaussian (mean :, variance a~), then the distortion function may be explicitly stated by using the formulas

70

OPTIMAL STOClIASTIC CONTROL

in Chapter 2 for Gaussian random variables:

(5.3 I)

(5.32)

iii _;; Pi = - - . u=

The cost function, Equation 5.29, will be normalized with respect to

uL, which yields J~)

=

SI[1 + (-"0

+

oXo

(Jxo

~)2J + hO(~)2 + C1D(xO + tl o) . 0"'\"0

(J XlJ

(5.33)

u.'('o

Although observation noise has not been included, it can be taken into account by conditioning the estimation error in Equation 5.29 on :) E Ai, where

E(ril

= 0,

E(rTl

=

u;.

(5.34)

The formulas for mean square estimation error conditioned on quantized Gaussian measurements were derived in Chapter 2. They may be used to show that with observation noise the normalized cost function becomes

0 = [ 1 + (xo -

J -2~ a.xo

Sl

Cf x o

+ -(10) 2J + b o(-Uo ) 2 O"xo

(1xo

(5.35) where u; = a~" + a;. Observation noise decreases the dependence of the cost function on the distortion term in two ways. First, it is seen from Equation 5.35 that the distortion term D is multiplied by the quantity a~,/a;. which is always less than 1 when observation noise is present. Second, the distortion function D should. generally speaking. be smaller for the

OPTl.IfAL STOCHASTIC CONTROL

71

larger input standard deviation CT z , given the same quantum intervals defined by _[d i ; . because the ratio of quantum interval size to standard deviation is smaller.

N IIl11erical Results The optimal control law was calculated by minimizing Equation 5.33 for three quantizcrs, shown in Figure 5. t ; a two-level quanuzcr. a threshold quantizcr, and a three-level quantizcr. Observation noise was not included. The quantities ll~,:d, and LIT carried unit weighting for all computations. Two different wcightings for the squared terminal error, x~, were used: I and 100. The latter value presumes that the root-mean-square terminal error is ten times "more important" than the other three quantities. In all cases in which the weighting of the terminal error was unity, the optimal stochastic control was extremely close (within graphical accuracy) to a straight line of slope -0.6. This line is the optimal control law for a linear measurement; it is not presented graphically. This somewhat surprising result may be explained by examining the cost function, Equation 5.33. The coefficients .'i" ho, and C t have values

'01

(bl

'01 Figure 5.1 Quantizers used for observation. (a) Two-level quantizcr ; (b) threshold

quantizer ; (e) three-level quantizer.

72

OPTIMAL STOCIlASTlC CONTROL

1.5, 1.0, and 0.5, respectively. Since the distortion function D cannot exceed unity, that term never contributes more than 0.5 to the cost function and has very little influence on the choice of optimal control. The optimal control laws for terminal-error weighting of 100 arc shown in Figures 5.2, 5.3, and 5.4. The optimal (linear) control for linear measurements-that is, without quantization-is also shown. The deviation from the linear measurement case comes from the "dual control" aspect of optimal stochastic control (Fcl'dbaum, 1960); the control application not only influences the state in the usual manner but also acts like a test signal to gain information about the system. For the specific problem at hand any error in the estimate of the state after the measurement has been processed at time II will propagate through the system dynamics and contribute to the terminal error at t i- Because the terminal error is heavily weighted, the control at time to is used for setting up the measurement so that a more accurate estimate can be obtained. These facts arc reflected in the cost function, Equation 5.33, where the coefficients Sj, ho , and {'j have values 2.0, 1.0, and 99.0, respectively. The optimal control law for observations through a two-level quantizer is, for all practical purposes, linear with slope -0.95; see Figure 5.2. For the system used here a slope of - 1.0 would center the distribution of Xl at zero, which is the optimal situation for estimating r - - - - - - - - - - - - - - ..- - - - - - - - - - - - - ,

--t----t----t----t----:='k:---t---+---t----t-...§.. ·8

07'0

·2

·4 QUANTIZEO MEASUREMENT '6

Figure 5.2 Optimal control law for two-level quantizer.

OPTIMAL STOCIlASTIC CONTROL

73

the quantizcr input alone. Thus the control action makes a strong effort to minimize the covariance of estimation errors. The optimal control law for the threshold quantizcr is shown in Figure 5.3 for threshold halfwidths of 0.5, 1.0, 3.0, and 5.0. Because there is no observation noise, a measurement falling in the linear range yields an exact estimate of the state. The optimal control takes advantage of this fact by so placing the mean of the a priori distribution of x, as to increase the probability of a perfect measurement. The slope of the lines for threshold halfwidths a/"x" of 1.0, 3.0, and 5.0 is close to ~ 1.0, indicating that the mean of the a priori distribution of Xl is situated near the same value, regardless of the initial condition xo_

, "

..1/ TXI "

Figure 5.3 Optimal control law for threshold quantizer.

The curves for the three-level quantizer, Figure 5.4, resemble those for the threshold type of nonlinearity. They too have a slope ncar -1.0. For values of the threshold halfwidth of 0.5 and 1.0 the tendency is to put the distribution of x, at the center of the quantizcr, to gain information. As the threshold halfwidth increases to ~/"x<, = 3.5, the distribution of Xl is centered at a point close to ±7., the switching point, since each half of the three-level quantizcr is effectively a twolevel quantizcr at such wide thresholds. The curve for ~/(J Xu = 5 has the additional characteristic that it follows the linear-measurement control law for small values of xo. For larger values of the initial

74

OPTiM AL STO CH AS TiC CO NTROL

Figure 5.4 Optimal co nt rol law for th ree-level qu aruiz er.

cond it ion , however, the policy is ch an ged , a nd the probability-density function of Xl is centered ncar the switching po int. It wa s found that with threshold halfwidth s between l.l and 4.9 the policy is to go to the switch ing point if .xo is zero. With halfwidth s larger th an 4.9 the m ea su rement o ppo rt u nit ies a re ign ored, unless the initial cond iti on is close eno ug h to the switch point to mak e the control expenditu re worth while. The optimal control laws will not be as dramat ic when the weighting is more evenly d istributed. Nevertheless, the result s presented here suggest method s of controll ing a system wh en the mea surements are quant ized and the estimation errors are to be kept sma ll. Fo r example, a co ntro l action might be co m p uted by ignoring the qu antizer completely; thi s control could th en be modifi ed to place the mean value of th e next measurement at o r ncar the "closest" s witching point of the qu antizer or the midpoint of the quantum int er val, whichever is preferable. Proces ses with Afore than TIro Sta ges The difficult ies inh erent in the so lution to the problem of optimal stochas tic control with mo re than t wo sta ges can ea sily be de scribed at th is tim e. Recall that all the co m p uta tions of the optimal control in the preceding example were done under the as sumptio n th at the

orrtst st:

STOCIIASTIC CONTROL

75

distribution of the second from the last state variable (xo) was normal. This is not true when quantized measurements have been taken prior to the determination of the next to the last control, and the expectations must be found by numerical integration, in general. To make the problem even more complicated, the distribution of the state contains all previous control actions as parameters; this implies, for example, that the first control action will influence nearly all terms of the cost function in a very complicated manner.

5.4

A Separation Theorem for Nonlinear Measurements

In this section we present the result that is displayed in Figure 5.5, which shows a linear system subject to quadratic cost with an arbitrary nonlinca r clement in the observation path. It will be demonstrated that if the proper feedback loop can be placed around the nonlinear clement, the optimal stochastic controller is the cascading of (a) the nonlinear filter for generating the conditional mean of the state and (b) the optimal (linear) controller that is obtained when all noises are neglected. Given: i = 1,2, ... , N, =j

=

h,[( . ), Vi]'

i,

=

E ( i~

N+ I

(5.36) (5.37)

xiAiXi + uT s»,

1

0

)

(5.38)

k ,

PROCESS

"'n.~N=O-,-,IS,-"E~+o.{)<:)--_ _-I

liNEAR SYSTEM (QUADRATIC COST}

08S. NOISE

Figure 5.5 A separation theorem for nonlinear measurements.

76

OPT/ilEAL STOCllASTlC CONTROL

It is further assumed that the process-noise vectors, the measurementnoise vectors, and the initial-condition vector are independent of each other. Now place a feedback loop around the nonlinear element, and subtract the mean of the incoming measurement conditioned on past data, thus forming the residual rklk- I: rklk- 1 =

HkXk

~ E(llkX k

le k -

I, Uk- I)

(5.39)

= Ilkeklk-I,

where the prediction error eklk-I

=

Xk -

E(Xk

eklk- I

le

is given by

k - I , Uk-

d

+ n'k-I, E(Xk_1 [e,; d·

= q,k~lek-Ilk-1 ek-lIk-1

=

Xk-I -

(5.40)

The measurement equation is modified so that now Zk

=

(5.41)

hk(rklk - 1 , Vk)'

When the conditional mean is subtracted from the incoming measurement, the control then has no influence upon the distribution of the quantity actually measured, and therefore it cannot affect the covariance of estimation errors. The detailed proof of the separation theorem is carried out in Appendix 0, but by substituting Equations 5.39 and 5.40 in Equation 5.41 it can be seen that the distribution of Zk is determined by the distributions of »\-1, I' .. and Ck-llk-l' Any function that does not include the control variables (but it may include past measurements) can be incorporated with the residual, Equation 5.39, and the separation character of the optimal-control computations is still valid. The optimal control sequence, as calculated in Appendix 0, is given by uj =

-ie, + GTSi+ lG,)-IGTSi+ lq,iE(Xi Ie,),

S, = Ai SN+I

=

+

q,f[Si+

AN +1 •

1 -

s.,

1Gi(B i

+ GTSiGr IGTsi+ I]q,i'

(5.42) (5.43)

A SEPARATION TIIEOREM FOR NONLINEAR MEASUREMENTS

77

This control law is identical with Equation 5.22 in the case of linear measurements, in which the optimal stochastic controller is separated into two elements: a filter for generating the conditional mean of the state vector and a linear control law that is optimal when all uncertainties are neglected.

Computational Adculltag('s The primary advantage of feedback around the nonlinear measurement device is that the computation required to determine the optimal control sequence is greatly reduced: the backward solution (and associated storage) is eliminated, and the control action is a linear function of the conditional mean of the slate. A nonlinear filter is required for finding the conditional mean. This may be a significant problem in its own right, but it will be easier to approximate a nonlinear filter than to obtain a solution by dynamic programming. If the cost is not quadratic, dynamic programming must be used for finding the optimal control sequence (Dcyst, 1967; Striebel, 1965). Feedback around the nonlinearity would simplify the computations here, too, since the probability-density functions of the measurements are independent of the control.

Pcrfonnunce No claim has been made about the performance of the system that uses feedback around the nonlinear measurement device. Depending on the situation, the observation with feedback may give either better or worse performance than the optimal control without feedback. This may be explained by using the examples of two-level and threshold quantizers given in Section 5.3. The feedback around the nonlinearity centers the probabilitydensity function of the measurement at the origin of the quantizing clement. For the threshold quantizer this means that the poorest measurement situation exists all the time, and it cannot be changed by control action. On the other hand, the optimal control action for measurements through a two-level quantizcr tends to place the center of the probability-density function of the measurement at the switching point. But feedback around the quantizer centers the distribution "free of charge," that is, without expenditure of control, and the total cost is less than that when feedback is not used. The situation with feedback around the threshold quuntizcr may be improved by introducing a bias at the quantizcr input to ensure an accurate measurement. The separation theorem introduced in this

78

OPTl.\fAL STOCIIASTIC CONTROL

section is still valid, and the cost can be reduced. Indeed, one can extend this concept to a whole new class of problems in stochastic control, in which a set of measurement control variables may be considered in addition to the state equation control variable. For quantized measurements these variables could be a bias or a scale factor or both, much as in the case of the quantizcr with feedback, Section 3.2. Meier and his associates (1967, b) consider controls that influence measurements, but they concentrate on linear measurements with controllable observation-noise statistics. AppI i c(/{ions The measurement feedback could be implemented in any control system in which the linear system output exists in amplitudc-contin uous form before it is passed through a quuntizcr or other nonlinearity. The usc ofa nonlinear device would be dictated by hardware constraints or other considerations, since a linear (and optimal) control system could be designed for the available linear measurements. One example of a possible application is in inertial navigation, in which the accelerometer output exists in analog form before it is quantized and stored; feedback around the quantizer could be utilized in such a case (Quagliata, 1968). 5.5

Summary

In this chapter we considered the problem of optimal stochastic control and emphasized the case of linear systems, quadratic performance indices, and nonlinear measurements. The sufficient conditions for the separation of the estimation and control functions were described. A two-stage example was presented, and the nonlinear character of the optimal stochastic control is due to its "probing" property. The difficulties in treating processes of more than two stages were discussed. Lastly, it was shown that feedback around an arbitrary nonlinear measurement device can result in sufficient conditions for a separation theorem: the optimal stochastic controller is implemented by cascading, first, a nonlinear estimator, to generate the conditional mean of the state and, second, the optimal (linear) controller when all uncertainties arc neglected. Perhaps the most immediate application IS 111 systems in which the measurements undergo analog-to-digital conversion.

6 Suboptimal and Linear Control with Quantized Measurements

6.1

Introduction

In most cases of practical interest it is exceedingly difficult to obtain the solution to the optimal stochastic control problem (or the combined estimation and control problem) when the plant or measurement equations, or both, arc nonlinear, when the controls arc constrained, or when the cost is nonquadratic. This situation was demonstrated in Chapter 5. in which the results of only a two-stage problem with one quantized measurement were given. Different suboptimal control algorithms have evolved as a compromise between computational effort and an efficient control scheme; this chapter describes some previous work and some new ideas in this direction. One widely used algorithm is the so-called open-loop-optimal feedback control (Dreyfus. 1964). In Section 6.2 this is applied to systems with nonlinear measurements, and it is compared with the truly optimal control described in the previous chapter. A new algorithm for suboptimal stochastic control is presented in Section 6.3. This algorithm has the "dual control" characteristics and can be applied to a wide range of problems. The design of optimal linear controllers for stationary closed-loop systems is treated in Section 6.4. A plant control system and the predictive-quantization system are discussed. 79

80

SUBOPTIMAL AND LINEAR CONTROL

6.2

Open-loop-Optimal Feedback Control

Dreyfus (1964) gives a particularly lucid description of the algorithm for open-loop-optimal feedback control. The operation is as follows. Measurements and control actions arc recorded up to, say, time I b and an estima te of the state, xklb is generated. It is temporarily assumed that no future measurements arc to be taken, and a control sequence, {II., Ilk + I ' . . . , ".'1}' is computed, to minimize the cost of completing the process. This is the optimal open-loop control sequence from time l., given past observations and control actions. Only the first mcm bcr of the sequence, "., is actually implemented, however; this advances the time index to k + I, when a new measurement is taken. a new estimate '~k + II' + I is computed, and the process of computing the optimal openloop control is repeated. This open-loop-optimal feedback control law has the primary advantage that, although not optimal for the original problem, it is readily computed. Moreover, feedback is incorporated, so that it takes advantage of current information about the system. Let us turn to the problem of controlling a linear system with a quadratic-cost criterion:

(6.1)

To simplify manipulations somewhat, let Zk

Uk-

I

Xjlk

= [z.. Zk-l,,,,,ZI;P(XO)}' = {Uk-I' " k- 2 " ' " = E(x j Iz; o: d·

lIo},

Note that

j ?:. k,

(6.2)

(6.3)

Let

81

OPEN-LOOP-OPTIMAL FEEDBACK CONTROL

so that

Ej + 11k = f.1> j Ej 1kJ + Qj'

(6.4)

The open-loop cost function, J OI.. k , the cost of completing the process from time t k without incorporating future measurements, is given by

N+I Jm.,k

L

=

E[(xilk

+

t'ilk)T Alxilk

+ ('ild] +

uTBill;

i=k N+l

=

L

[x~kAi.tilk

+ liT Bill; +

tr(AiEi1k)].

(6.5)

i==k

The open-loop-optimal feedback control law chooses the sequence {II" . . _, liN} so as to minimize the cost function (Equation 6.5) subject to constraints of state (Equation 6.2) and covariance (Equation 6.4). For a comparison recall that the truly optimal stochastic control is found by choosing the functional relations 11,(0,) = 1I,(Zi' Vi-I) to minimize the expected cost of completing the process. Here we are, in effect, choosing U;(Zb U, : d. with i ~ k, to minimize the cost. Since future measurements are being ignored, the covariance terms in the cost are completely determined by E kk through Equation 6.4

and therefore cannot be controlled. Thus, an equivalent problem statement is as follows. Choose N+1

. J OL.k =

'\' -T A ~ Xilk iXllk

+

Uk"'"

II:,. to

minimize J~I..k:

TB jlli

II;

(6.6)

i==k

subject to i ~ i;

where

(6.7)

xklk is given. This is a deterministic control problem, whose

solution is well known (see, for example, Bryson and Ho, 1969):

ui

= -(Bi + GTSi+lGi)-lGTSi+l'1JiXilk>

S, = Ai + q,f[Si+ I

-

(6.8)

5 i + ,G;(B j + GTSi+ IGj)-'CTSi+ ,]cJ.>j, (6.9)

As mentioned previously, only the first member of the sequence is implemented; thus, for any time tk the open-loop-optimal feedback

82

SUBOPTl.\fAL AND LIi'iEAR CO,"iTROL

control algorithm chooses a control "k such that

Uk = -(Bk + G[Sk+ IGk)-IG[Sk+ ll1l kxklk'

(6.10)

This is the precise form of the control when the separation theorem is valid (Section 5.2). In other words, the open-loop-optimal feedback control proceeds as though the conditions for the separation theorem were valid, even though they arc not. When the open-loop-optimal feedback control sequence is substituted in the equivalent cost function, Equation 6.6, it becomes (Bryson and Ho, 1969): (6.11 ) This in turn may be used in the open-loop cost function, Equation 6.5, to yield S+ 1

J~)f..k = X~kSkXklk

+

L

i~

tr (AiEild·

(6.12)

k

Open-Loop-Optimal Fceilbuc]: Coutro! witlt Quantized Measurements In this section we shall apply the open-loop-optimal feedback control law to the quantized-measurement problems considered in Section 5.3. For that scalar state problem the open-loop-optimal feedback control, Equation 6.10, is 110

= -

SI

Sl

+

_

I xo,

(6.13)

)0

where SI = lit + 112 - lIi/(h 1 + Ill); see Section 5.3. This control law is the same as that used for linear measurements, Jt gives very good results when all the weighting coefficients in the cost function, Equation 5.25, arc unity: the fractional increase in minimal cost,

is al ways less than 0.05 percent for the examples presented in Section 5.3. When [he terrni nal-error weighting coefficient is increased to 100, the results are quite different, as is to be expected. Figures 6.1 and 6.2 show the fractional increase in cost when the open-loop-optimal feedback control is used for the threshold quantizcr and for the two-level and three-level quantizers, respectively. The increase in cost is roughly 20 to 80 percent but may be as high as 170 percent for the threshold quantizer.

OPEN-LOOP-OPTIJIAL FEEDBACK CONTROL

83

1.8 r - - - - - - - - - - - - - - - - - - - - - ,

J;L-JO

).0

JD 0.8

0.6

0.4

0.2 alvxo • 0.5 0

0

2

4

6

8

10

12

15..1 v Xo

FIpre 6.1 Fractional increase in minimal cost with open-loop-optimal feedback control.

The reason for this is evident by now: because it does not incorporate future measurements, the open-loop-optimal feedback control neglects the distortion term D in Equation 5.33 and the conditional-covariance term in Equation 6.5. It is precisely this term which is important when the terminal error is heavily weighted. In other words, the initial control is not expended in an effort to improve the quality of the measurement of Xl' This is especially serious when X2 is heavily

H..J

SUBOPTIMAL AND LINEAR COiVTROL

0.6,------------------

0.4

0.2 TWO· LEVEL QUANTIZER

0

JO -l ...QL....

2

4

6

a/crxo:3.0

0.8

8 0.5

to

I:: I 0

~XI

JO

0.6

0.4

THREE·LEVEL QUANTIZER

0.2

0 0

2

4

6

8

to

I0':0 I Figure 6.2 Fractional increase in minimal cost with open-loop-optimal feedback control: two-level and three-level quantizers.

weighted in the cost function, because any error in the estimate (!Iter the measurement has been processed propagates through the system and contributes to the terminal error X2' 6.3

A New Algorithm for Suboptimal Stochastic Control

The open-loop-optimal feedback control law suffers the disadvantage that it does not account for future measurements. As shown in Section 6.2 for linear systems and quadratic cost, the open-loop cost function may be decomposed into two parts: a part involving the conditional mean and a part involving the conditional covariance. It is the latter part that is neglected by the open-loop-optimal feedback control.

A

sew

ALGORITHM FOR SUBOPTIMAL STOCIfASTlC CONTROL

85

The logical step toward improving the performance (and increasing the computational requirements) is to allow for one or more, say At, future measurements in the computation of the control law and to usc the open-loop-optimal feedback control at all other times. We shall call this scheme At-measurement-optimal feedback control. First the algorithm is described and discussed, and the special case of one future measurement is examined in more detail. The section concludes with an example and some Monte Carlo simulation results of the stochastic control of a linear plant with coarsely quantized (nonlinear) measurements. Description 0( the Control Algoritlun The algorithm proceeds as follows. Measurements and control actions are recorded up to, say, time tk> and an estimate of the state vector (and, perhaps, its conditional probability-density function) is made. It is temporarily assumed that A1 measurements arc to be taken in the future (at preassigned times). The control sequence {Uk, Uk+ I" .. } is so computed as to minimize the cost of completing the process taking At measurements along the way. This control sequence is the At-measurement-optimal control sequence. Only Uk' the first member of the sequence, is actually implemented; this advances the time index, a new measurement is taken, a new estimate is computed, and the process of computing a new II! -measurcmcnt-optimal control sequence is rcpca ted. The M-measurement-optimal feedback control has two limiting forms: when At is zero, no future measurements arc included in the control computations, and it becomes the open-loop-optimal feedback control, but when /If is the actual number of measurements remaining in the problem, it becomes the truly optimal stochastic control. The primary advantage of the /If-measurement-optimal feedback control over other suboptimal control algorithms is that one or more future observations arc incorporated into the control computations. This allows for the "probing" or "test signal" type of control action, which is characteristic of the truly optimal stochastic control. The open-loop-optimal feedback control cannot take this form, since future measurements arc ignored. The concept of incorporating At future measurements rather than the actual number of measurements may also be used to simplify computations involving constrained controls, nonlinear plants, and nonquadratic cost criteria. For example, if the actual controls arc

86

SUBOPTIMAL AND LINEAR CONTROL

constrained at all future times, it can be assumed for the purposes of control computation that they arc constrained only at ,\[ future times and unconstrained at all other times. Similarly, it can be assumed that the plant is nonlinear only at M future times and linear at all other times, or that the cost is nonquadratic at j\[ future times and quadratic at all other times. In all these situations the suboptimal control approaches the optimal control as Al approaches the number of stages remaining in the problem. Generally speaking, the computational efTort will increase as Al increases: however, the writer knows of no analysis that shows that the performance will improve as Al increases. Problem Sta(ement

Given the following. (a) The state equation: i

=

0, 1, ... ,N,

where Xi is the state vector at time (;, and Wi is the process noise at time t..

IIi

(6.14)

is the control vector at time

(i-

(b) The measurement equation: i = 1,2, ... , N,

where

1'i

(6.15)

is the observation noise at time t i .

(c) The cost criterion: J

~ ELto L,(x" Il,) + (P(XN+ I)J.

(6.16)

(d) The probability-density functions: p(xo),

{p(»,,)},

{p(,',)}.

It is assumed that the vectors Xo, -( Wi}' and {vJ are independent. Open-Loop-Optimal Feedback Control The cost function to be minimized by the open-loop control at time t k is given by

J ou =

E[J.

L){x;, II;} + t/>(XN+ ,} IZ., U._ 1] .

(6.17)

This is minimized by the control sequence {II..... ,liN} subject to the

A NEW ALGOR/Til'!! FOR SUBOPTIMAL STOCIlASTlC CONTROL

87

state constraint, Equation 6.14. The first member of this sequence, is the open-loop-optimal feedback control at time (k'

Uk'

01le-A1easurcmcnt-Op! inial Fcedhack CUll I rot We shall treat a special case of M-measurement-optimal feedback control. If only one future measurement is incorporated in the control computation at time I b and if this measurement occurs at time t k + n , then the one-measurement cost function becomes k+ n- 1

J OJ / . k

=

E[

+

L

L}xj,u j)

)=k

E(J~n.k+n I z.. Uk+n- til z.. u.. IJ.

(6.18)

In this equation the open-loop-optimal cost function J~n.k+n is similar to Equation 6.17 after minimization, but it depends on the measurements {Zk' =k+n} and the controls U k + n- l • The first member of the control sequence {Uk"'" uv} that minimizes Equation 6.18 is the one-rr.casurcmcnt-optimal feedback control at time t k . The solution may still be difficult to find in practice. Even when the explicit dependence of the open-loop cost function on the open-loopoptimal controls Ilk+ n' ..• ,Uv can be removed, the solution of Equation 6.18 still involves an l1-stage two-point boundary value problem. If, however, the future measurement occurs at the "next" time, then it reduces to a parameter optimization over Ilk; that is, the one-measurement cost function becomes (6.19) In this equation J~n.k + 1 depends on the measurements Zk+ 1 and the controls Uk'

Linear Systellls, Qu{/(lratic Cost, and Nonlinear Meusurcmen;» The following paragraphs contain some specialized results when the state equation is linear,

i = 0, 1,2, ... ,N

(6.20)

and when the cost is quadratic, (6.21)

Here the weighting matrices [A j } and {B j } are positive semidefinite

88

SUBOPTIMAL AND LINEAR CONTROL

and positive definite, respectively. The measurements may still be nonlinear. It is shown in Appendix E that the optimal open-loop cost function in this case may be rewritten E(x[+

J't)[..H 1 =

ISH

+ tr[EH

IXH

1

Iz., I> Ud

llk+ 1(Fk + I -

SH

dJ + const,

(6.22)

where Sj

=

+ T[Sj+ 1 - s.; IG,(Bj + GTSi+

Ai

SN+l = A N + I

F,

=

lGj)-IGTSi+ 1]j,

(6.23)

,

T F i + I j +

Ai'

(6.24)

FN + 1 = A N + 1 , Ek+ 11k +

I

I

= COY (Xk+ 1 Zk+ l'

Ud·

(6.25)

The equation for the one-measurement cost function with the future measurements occurring at the next lime, Equation 6.19, becomes

J{}.\1.k

=

E[x[Akxk

+ u[BkUk + X[+

ISH IXk+1

+E{tr[Ek+11k+I(Fk+1 -SHdJIZk,UdIZk'Uk-l]. (6.26)

The value of Uk that minimizes this is the one-measurement-optimal feedback control at time t k for linear systems, quadratic cost, and nonlinear measurements. It is shown in Appendix E that the weighting matrix F H 1 - Sk+ 1 is at least positive semidefinite. If it were not, the control would minimize the cost by degrading, not improving, the knowledge of the state. It still may be a difficult problem to compute the conditional expectations in Equation 6.26. The simulation results presented in Chapter 3 indicate, however, that in the case of quantized measurements, a good approximation is given by the Gaussian fit algorithm, which assumes that the prediction error at time t k + 1 based on all past data will be Gaussian. It follows that the distribution of =H I before the measurement is taken also will be Gaussian, so the Gaussian formulas may be used for computing the expectation Ek+ Ilk+ I' In fact, using the Gaussian fit algorithm with the one-measurementoptimal feedback control is analogous to finding the first control action in a two-stage process with Gaussian initial conditions (cf. Eq uations 6.26 and 5.17).

A NEW ALGORITlI,\! FOR SUBOPTIMAL STOCHASTIC CONTROL

89

A comment about steady-state operation: the nonlinear control law obtained by minimizing Equation 6.26 with respect to "k will not, in general, reach a steady state even though the matrices Sk+ l ' Fk + l ' A k , and B; arc constant. As discussed in Chapter 2, this results from the fact that the covariance matrix conditioned on quantized measurements, Ek+ tlH l ' cannot be expected to reach a steady-state value.

S imu!at i OilS Consider the scalar state equation given by k

=

0, 1, ... ,N,

(6.27)

where x is the state, /I is the scalar control, and II' is Gaussian process noise. The initial conditions also have a Gaussian distribution. The cost function is quadratic in nature:

J =

E(.toAiX! + Bill! +

AN+IX~+I)'

(6.28)

Observations are taken through a three-level quantizcr, shown in Figure 5.1, with switch points at ±:(. Obtaining numerical solutions to the problem of stochastic control requires extensive usc of the probability-density function of the state conditioned on past measurements and control actions. Here it is assumed that the distribution just prior to a quantized measurement is Gaussian, as discussed above. Both the open-loop-optimal feedback control and the one-measurement-optimal feedback control have been simulated on the digital computer, The latter algorithm assumes that the one future measurement occurs at the next time instant. The control algorithms used the same realizations of the initial conditions and process noise, although the state trajectories, in general, were dilTercnt. Each case was run fifty times, and the ensemble averages were approximated by the numerical average of these fifty trials. In every case the weighting coefficients for the control effort -[ BJ are unity, and the process-noise variance is constant, but the latter varies from case to case. Nunierlca! Results The results of a seven-stage stochastic process arc described. Quantitative results are displayed for a terminal-control problem, and the results of other simulations arc discussed.

90

SUBOPTIMAL AND LINEAR CONTROL

Terminal Control In the terminal-control problem all state weighting coeflicients are unity except the last one, A 7 , which is 100. This means, roughly, that the root-mean-square terminal error is ten times "more important" than the other quantities in the cost function. Figure 6.3 shows the results when the measurements are taken through a three-level quantizcr ; the ensemble mean square state and ensemble average of the (approximate) conditional covariance of the state are plotted as a function of time. In this case the variance of the process noise is 0.2, and the quantizer switch points are at ± 1. The most noticeable difference between the two control laws is that the one-measurement control acts to reduce the conditional covariance of the state estimate. Note that the ensemble average of the conditional covariance is about half the average of the conditional covariance for the open-loop control. The one-measurement control is able to do this by centering the conditional distribution of the measurement near the quaruizcr switch point. This is reflected in the curves for the mean square value of the state, which stays in the neighborhood of 1.0 (the switch point) for the one-measurement control but gradually goes to zero for the open-loop control. The control elTort (not shown) for the one-measurement control is higher. and it requires a large

OBSERVATION

LO

~

•• 175 1.25

Xi

1.0

1.00 .

INITIAL CONJITIONS

\ \ \

0.75

Xo~ 0,

x:- 1.0

NOISE

VARIANCE-

0.2

\

\

ONE -MEASUREMEN!

\

"',

0.50

QP£N-l.QOP

CONTAOL

f

A- _

-

- -8- -

~

. .

__m _

.

-

.

-

-OJ }

.

--+

0

2

3

AVERAGE CONDITIONAL

CCV~R!~NCE.

I

0

4

5

X'

- /!:/

-8- -

-OJ -

AVERAGE SQUARE STATE,

/ / - &- -

CONTROL

0.25

}

6

7

E

TIME

Figure 6.3 Seven-stage terminal stochastic control with observations quantized to three levels.

A NEW ALGOR/TI/,I! FOR SUBOPT/,\fAL STOClIASTlC CONTROL

91

control action at the last application to bring the state from the vicinity of the quantizer switch point to the origin. The performance penalty of the open-loop-optimal feedback control as against the one-measurement-optimal feedback control is 17 percent in this case. Other simulations revealed that the performance penalty ranged as high as 44 percent when observations were taken through a two-level quantizcr. Other Simulations Cost functions other than that of the terminalcontrol type were simulated: the state deviations were weighted more hca vily as time progressed, or else the wcightings were constant. The performance ad vantage of the one-measurement control was always less than 10 percent in these cases. This arises from the fact that the one-measurement control tries to move the state around to gain information, but these movements arc restricted by the heavy weighting on the state deviations. Thus, a qualitative assessment, at least for linear systems and nonlinear measurements, is that incorporating future measurements in the control computations will yield the greatest return when the cost function is such that the state or control or both are free to reduce uncertainty in the estimate. In other situations the open-loop control is quite attractive, especially because of its computational simplicity.

6.4

The Best Linear Controller: Discussion

This section briefly discusses the problems inherent in the design of closed-loop systems when the measurements are quantized. A plantcontrol problem and a transmitter-receiver from a communication system (predictive quantization) arc both reduced to an iterative solution of the Wiener filtering problem when the quantizcr is replaced with a gain plus additive, uncorrclated noise. Throughout this section the lowercase Icttcr c denotes the Z-transform variable.

Plant Control Figure 6.4a shows the block diagram of the control system in which the output is to follow the input random process x, Here e is the system error, Q is the quantizing clement, r is the quantizer output, D(::.) is the digital compensation to be chosen, II' is additive process noise, F(::) is the fixed, time-invariant, stable pulse transfer function of the plant (and any hold networks), and c is the plant output. Synchronous

92

SUBOpnlfAL AND LINEAR CONTROL w

~' lo}

n

w

.~ (~)

lei

Figure 6.4 Plant-control block diagrams.

sampling clements are assumed to exist between all transfer functions. We shall usc the results of Chapter 4 and replace the quantizcr with the describing-function gain k and an additive, uncorrclated noise source /1. The quantizer output)' then becomes

+ /1,

y = ke

(6.29)

where (6.30)

This results in an equivalent block diagram of Figure 6.4b. The equation for the Z transform of the output sequence c can then be written as c(z) =

D(z)F(z)

I

+

+ kD(z)F(z)

k'"(.,0) - -

F(z)

1 + kD{z)F(z)

D(z)F(z) + ---:----/1(~)

11'(7) _.

+

kD(z)F(z)

-

(6.31)

TIlE BEST LINEAR CONTROLLER: DISCUSSION

93

Define the transfer function lIt::::) as Itt:

= I

c)

+

D(:)

(6.32)

kD(:)F(.:)

Substituting this in Equation 6.31 yields d::::)

D(:)

= F(:)II(.:)[kx(:) + 11(:)] +

F(::::)II(.:) D(:) \1(:).

(6.33)

may be eliminated from the last term by using Equation 6.32: d:)

=

F(:)l/(::::)[kx(::::)

+

11(::::)]

+ [I -

kF(::::)II(::::)]F(:)\\'(::::)

(6.34)

or, finally, d::::)

= F(::::)l/(::::)[kx(::::) + 11(::)

- F(::::)kll'(::)]

+

F(:)\I'(::).

(6.35)

The last equation suggests the block diagram of Figure 6.4c, which is a Wiener filtering problem of the sernifrec configuration type, (Vander Velde, 1967). The design problem is to find Il(::::), to minimize the mean square value of the system error e. An iterative design process has to be used, because the optimal filter II(::) depends on the spectrum of the noise II, which depends on the quantizcr input e, which in turn depends on the filter lIt::). This is illuminated by the expression for the system error as follows. The system output, Equation 6.35, is subtractcd from x: e(::::)

=

[I - kF(::)II(::)] [xl:) - F(:)l\'(:)] - F(:)IJ(::::)II(::).

(6.36)

In this equation 11(:) depends on e(:). The second-order probability distribution of the quantizcr input must be known before the quantization-noise autocorrelation function can be calculated. In view of the filtering that takes place around the loop it is usually justifiable to assume that the error samples e arc normally distributed. Smith (1966) indicates that this will be a good approximation if the spectrum of the input signal has a bandwidth wider than the linear part of the system. The addition of Gaussian process noise (not considered by Smith, 1966) will also make the quaniizcr input more Gaussian. It will be assumed from here on that the quantizer input samples arc jointly normal. The describing-function coefficient k will remain constant during the design process if the ratio of the quantum interval to the standard deviation is constant. This means that the quantum intervals and quantizcr output values are not specified until the design process has

9~

SUBOPTIMAL AND LINEAR CONTROL

been completed and the standard deviation of the quantizcr input

IS

known. The Design Procedure The design procedure is purely heuristic. Discussions with H. Smith indicate that the results should be interpreted with some carc. It may be initiated by computing the value of k for the quantizcr being used. Quantization noise is neglected, and a function /l(:) that minimizes the mean square error? is chosen.

The autocorrelation function of the error (' is computcd* and, under the Gaussian hypothesis, this determines the autocorrelation of the quantization noise (Chapter 4). A new function lI(e) that includes quantization noise is chosen, and the procedure outlined in this paragraph is repeated. When a satisfactory lI(e) has been computed, the compensation D(:) is then found from Equation 6.32. An alternative approach is to deal directly with the quantizcr output autocorrelation
A Transnnncr-Rcceircr System: Predict u:« QI/unti:atioll Figure 6.5a shows a transmitter-receiver pair that has been the subject of much investigation (for example: Bello ct al., 1967; Davisson, 1966, 1967; Fine, 1964; Gish, 1967; O'Neal, 1966, 196R). It is desired that information about the input process Xi = X(ti) be sent over a communication channel. Linear feedback is placed around the quantizcr, so that the signal being quantized is, in some sense, the error in predicting the incoming sample Xi' The quantizer input is IIi and the output Yi' The receiver operates on the sequence {y;} to produce an estimate of the transmitter input Xi' When the quantization clement is a relay and D(:) is a pulse counter, the transmitter is the well-known delta modulation scheme. With • Although the quantization noise is uncorrciatcd with the quanuzcr input. it is corn,.. luted with the x and II" pft1ccsscs. The cross-power spectral density function between the "input" x(.:) - n':)II"(':) und the quantization noise 1/(':) is required and 01;1)' be found in terms of the quantizuuon-noisc spectral density by multiplying both sides of Equation 6..'16 by 11(':). taking expectations, and selling the left-hand side equal to zero.

THE BEST LINEAR CONTROLLER: DISCUSSION x.

I·

u. I

95

o

n. I

x, I

(b)

(el

Figure 6.5 Transmitter-receiver block diagrams.

quantizcrs of more than two levels the system is sometimes called "differential pulse code modulation" (O'Neal, 1966). Using a threshold type of quantizcr is mathematically equivalent to using a predictivecorrection data-compression scheme (Davisson, 1967). Both Fine (1964) and Gish (1967) have shown that if the receiver operation is to be linear, the transmitter feedback must be the same linear operation, in order to minimize the mean square estimation error. To determine this error we note in Figure 6.5a that (6.37)

(6.38) where .x; is the prediction of Xi based on (Jj - l' )'; - 2' .•. }. Subtracting the second of these equations from the first shows the error £'; to be (6.39) which is just the error incurred in quantizing II;. Again we replace the quantizcr with the describing-function gain k and an uncorrelated norse source II: J'i

=

kll;

+ n.,

(6.40)

where

(6.41 )

96

SUBOPTIMAL AND LINEAR CONTROL

The error, Equation 6.39, may be written ('1 =

(I - k)u j

(6.42)

llj.

-

An expression for the Z transform of the quantizcr input may be written by examining the equivalent block diagram for the transmitter, Figure 6.Sb, as u(:) ~ I

+

I

kD(=)= I X(:)

D(=)=-I

+ ~~~~~I"(Z). 1 + kD(z)z

(6.43)

Define the transfer function ll(=) as 1I (z) ~

I -+--' k C' : D::-C(,..,._ )_--:_"I • 1

(6.44)

7

The Z transform of II, Equation 6.43, may then be expressed as II(Z) = ll(z)x(z)

I

+ j{[1

- lI(z)]I/(z).

(6.45)

Substituting this in Equation 6.42 gives the Z transform of the system error:

dz)

2k-l( I/(z) - ~~lI(z)[I/(z) k-I - b(z)] ) . k 2k - I

~ -~~

(6.46)

It is seen that, when displayed in this form, the filter (k - I )//(z)/(2k - I) is trying to extract the "signal" 11(:) from an input of signal plus "noise," - kx(:). This result, perhaps surprising, is not inconsistent. The

quantization-noise spectrum will have a wider bandwidth than will the spectrum of x, The optimal choice of lI(z) will therefore attenuate the low frequencies. This is realized by integration (summation) in the feedback compensation D(z), an approach that was used by De Jaeger (see Gish, 1967). lie analyzed and tested the system with sinusoidal inputs. Another interpretation can be made by adding and subtracting x(z) to the bracketed term in Equation 6.46. The equation for the system error then becomes 2k - I _ e(z) = -~~(kx(z) - ll(z)[kx(z) - n(zm, k

(6.47)

TilE BEST LINEAR CONTROLLER, DISCUSSION

97

where

_

k-I

li(:) = 1 - --II(z).

2k - 1

(6.48)

This suggests the Wiener filtering problem shown in Figure 6.5c.

The design procedure for this situation is iterative, as in the plantcontrol problem, because the spectrum of quantization noise 11(:) depends upon the quantizcr input, Equation 6.43. All assumptions and comments about the design process for the plant-control problem apply equally well to the quantizcr with feedback considered here.

6.5

Summary

In this chapter we have investigated suboptimal control algorithms and linear controllers. The open-loop-optimal feedback control was compared with the truly optimal stochastic control in the two-stage example in Chapter 5. The penalty in performance associated with the open-loop control can be quite high and is due to the fact that this

control neglects future measurements. A new algorithm, called A1measurement-optimal feedback control, was introduced to overcome the deficiencies of the open-loop control. It has the "probing" characteristic of the truly optimal control and can be applied in situations with other than nonlinear measurements. Simulations of the open-loop and AI-measurement controls indicate that the latter will yield the greatest improvement in performance when the cost function docs not penalize the probing action too heavily, as in a terminalcontrol problem. The last topic dealt with closed-loop systems containing quantizers. Both a plant-control problem and the predictivequantization system were restated as Wiener filtering problems requiring an iterative solution.

7 Summary and Recommendations for Further Study 7.1

Introduction

The mathematical operation of quantization exists in many C0111munication and control systems. The increasing demand on existing digital facilities (such as communicution channels and data-storage) can be alleviated by representing the same amount of information with fewer bits at the expense of more sophisticated data-processing. The purpose of this monograph is to examine the 1\\/0 distinct but related problems of state variable estimation and control when the measurements are quantized.

7.2

Summary and Conclusions

Analytical expressions have been derived for the conditional mean and conditional covariance of the state of a Gaussian linear system when the measurements have been arbitrarily quantized. These equations do not depend on the repeated application of Bayes' rule to the state probability-density function. The characteristics of the optimal filtering, smoothing, and prediction solutions were retained in the approximate implementations. The Gaussian fit filtering and smoothing algorithms appear to be the most promising because of their accuracy and ability to work with arbitrary quantization schemes and nonstationury processes. These tcchniq ucs were applied to three digital communication systems: pulse-code-modulation, predictive

ss

SUMMARY AND CONCLUSIONS

99

quantization, and predictive-comparison data-compression. Simulation results compare quite favorably with performance estimates. The important problem of designing linear estimators for quantized measurements of stationary processes was investigated. The quantizer is replaced with a gain clement and an additive-noise source; the random-input describing function optimizes several criteria that simplify system analysis and synthesis in addition to minimizing the mean square approximation error. The task of jointly optimizing the quantizer and its subsequent linear filter was undertaken. It was shown that the quantizer that is optimized without regard to filtering nearly satisfies the necessary conditions when filtering is included. \Ve conclude that this statically optimal design should be a good one in the majority of cases. The optimal stochastic control of a linear system with quantized measurements subject to a quadratic cost was computed for a twostage problem. The interpretation of the nonlinear control action leads to suggestions for suboptimal control laws. A separation theorem was derived for arbitrary nonlinear measurements under the conditions that the system is linear, the cost is quadratic, and that feedback around the nonlinear measurement device can be realized. The optimal stochastic controller is separated into two clements: a nonlinear filter for generating the conditional mean of the state and the optimal linear controller that is obtained when all uncertainties arc neglected. The truly optimal stochastic control is extremely complicated, and suboptimal algorithms must be used in most problems of any practical significance. The deficiency of a commonly used suboptimal feedback control law is alleviated by incorporating one or more future measurements into the control computations. This technique, called M> measurement-optimal feedback control, is applicable to most problems in discrete-time stochastic control. The problem of designing linear digital compensators for closedloop, time-invariant, linear systems when quantizers arc present was discussed. A plant control loop and a communication system (quantizcr with feedback) arc each reduced to an equivalent Wiener filtering problem. The (approximately) optimal linear compensator must be found by an iterative solution of this equivalent problem. 7.3

Recommendations for Further Study

One of the more important subjects for study is the noisy-channel version of the topics treated in Chapters 2 and 3, such as parameter

100

SU.\fMARr AND RFCO.\!'\/E!VDATIONS FOR FURTflER STUDY

estimation, Gauss-Markov processes, and communication systems. The noiseless-channel results should be of considerable value in this endeavor. The accuracy in the implementation of the conditional mean and conditional covariance of the state is limited only by the ingenuity and the computational capability available to the designer to find the conditional mean and covariance of the measurement vector. Any techniques that can improve the accuracy and speed of these computations will be welcome advances. Perhaps the major emphasis should be divided between relatively short vectors, such as those that might occur as a system output, and relatively large vectors (of ten to fifteen clements) that correspond to reasonable memory lengths of filters. The analyses and simulations presented here were based on the assumption that the stochastic processes being monitored and controlled were known. It would be desirable to perform an error analysis of the Gaussian fit algorithm, for example, and determine the performance degradation that occurs when the filter is operating under the wrong assumptions. Perhaps known results from the error analyses of linear filters can be used for this task. The quantizer with feedback is an efficient means of transmitting information, but it is likely to be inaccessible because of its remote location, and other designs should be examined in the light of the following critcria : What is the optimal fixed design for the class of spectra that arc likely to be transmitted? What suboptimal computations should be performed to improve case of mechanization and reliability? What adaptive techniques might be used to ensure nearly optimal autonomous operation? The resolution of such questions will bring the quantizcr with feedback much closer to practical application. The extension of the concept of the At-measurement-optimal feedback control to bounded control, nonquadratic criteria, and nonlinear plants is an area that may very well produce practical and efficient control strategies. There is no reason why such extensions cannot apply to the deterministic control problem as well, and numerical comparisons of these feedback control laws with the optimal control laws would be very illuminating. These suggestions for further study are representative of the important problems in estimation and control with quantized measurements. Their solution, perhaps with some of the ideas developed here, will contribute to the understanding of systems containing other types of nonlinearities as well.

Appendix A. Power Series Approximation to the Conditional Mean and Covariance of a Quantized Gaussian Vector The

III

components of a normally distributed vector arc quantized

and lie between the limits {Ii} and {Ii}; that is. l

= 1,2, .. . ,111.

(A.I)

The geometric center of the region A in which the vector lies is denoted by the vector y = ~(h

+ a)

(A.2)

and the collection of threshold halfwidths is [c'}: , = ~(h - a).

(A.3)

The joint normal probability-density function for the 111 measurements is now expanded in a power seriesabout the center of the region. Terms of fourth and higher order will be neglected. and Equations 2.36 and 2.37 will be used to calculate the mean and covariance of the measurement vector conditioned on : E A. The power-series expansion of the normal probability-density function is p(:) = pry)

+

('I' (,:(yK

I

D'p

+ ~T <,:' (yK (AA)

102

A PPEN DIX A

wher e , = : -

y,

(A .5)

p(:) = Cexp( -I:T I' ·' :),

,'p

_ = _ p(" ), TI' · '

a:

',

(A.6)

,

(A .7)

(A .S)

a nd C in Equ ation A.6 is the normalizati on co nsta nt of the probabilit y, den sity functio n. Lei the volume of the qu antum region A be V : V(A )

= 2,'2, ' . .. 2,m.

(A.9)

Th en the probabilit y that : is in A is found by integrating the proba bility-density function o ver A : PI: E A ) =

=

i I ( p(:) d:

I Ta'P ) c: + -2, -£1: 2 , + .. . .

d' ply) + -c7p ,

- 11

PI:

E

A) '" P(l')V(A )( I

(A. IO)

)') +"1 .Lm 1l" (,i - 3- . -

1'''

I

where the matrix II is given by

B

=

r - Il'l'TI-· ' -

F " '.

(A. I I )

Th e co nd itio na l mean is determ ined next, Co nsider the kth co mponent. and int egrate it o ver the region A :

L

:'p(:),/: =

L+ (t'

= t' P(: E A)

x (I

"d' +f ,

" )P(y

+

dn'p(y)

(A .12)

- r Tr · ', + !,TB, + .. .).

Onl y three term s a re retained in the expa nsion of p(:) since, when they a re mult iplied by , ', their order is increased by I. Only the secon d term . when mult iplied by ,', has a n even contribution.

APPENDIX A

!OJ

Thus Equation A.12 becomes

(A.13)

Dividing this by P(ZE A), given in Equation A.IO, and retaining only third-order terms yield the approximation to the conditional mean of:: E(:IZEA);::: y - Ar-1y,

(A.14)

where the diagonal matrix A is

A =

{(xt c5ij },

(A.IS)

and ()ij is the Kronecker delta. The covariance of: conditioned on: E A is the same as ~ conditioned on: E A, because the two random variables differ only by a constant. Thus, (A.16)

But the conditional mean of' in the rightmost term of Equation A.14 is only of second order; the rightmost term of Equation A.16 is therefore of fourth order and can be neglected.

(A.17)

Only the diagonal terms of the matrix in the integrand are even. Performing the integration in Equation A.17 yields

(A.IS)

Appendix B. Performance Estimates for the Gaussian Fit Algorithm This appendix considers the performance of the Gaussian fit algorithm over the ensemble of time functions for which it is intended. An approximation to the ensemble mean square error is found for stationary and nonstationary data, and the analysis is applied to the three digital systems of Chapter 3.

B.1

General Form of the Performance Estimate

The Gaussian hypothesis for the Gaussian fit algorithm is assumed, so that Equations 2.56 to 2.61 describe the propagation of the first two moments. The ensemble average covariance is found by averaging the conditional covariance over all possible measurement sequences. Consider AI" + l ' the conditional covariance just prior to the measurement at 1,,+ ,_ From Equations 2.57 to 2.59 it is seen that Equation 2.61 can be written 111,+

1

= ,P,(II1,);;

+ Q,

+ ,K,(II1,) cov (=, I A,. 111,. _',I,' .JK;(II1,);,

(8.1)

where the conditional mean and covariance or =n just prior to the reading at t n are explicitly shown in cov (z, 1- .. ). Let JH:+ I be the ensemble average of 111,+ I. and formally take the ensemble expcctaIO~

APPENDIX B

105

tion of both sides of Equation B.1 : M:+

I =

f dM"p(M")[,,P,,(M,,)~ + Q" + "K,,(Jl1")W(M,,)K~(M")~].

(B.2)

Here p(M") is the ensemble probability-density function for the matrix At", and the matrix W(M") is (3.3)

An approximate solution to Equation B.2 can be found by expanding the right-hand side in a Taylor series about the ensemble mean and neglecting terms of second and higher order. This will be an accurate solution when there is small probability that At" is "far" from IU:, and it results in the equation

At:

At:t 1 :::: "P"(M:)$~ + Q" + with Att = $oPo~ + Qo· (11

"K"(M:)W(M;)K~'(M:)~ (304)

By similar reasoning the ensemble average covariance just + I)st measurement, E;t l' is given by E: t 1 ::::

(Ilier

r., dM:+ d + K"+ dM;+ tlW(M;+ tlK~'t l(M: t d·

the

(B.5)

The form of W(M") depends on the quantization scheme, and explicit forms are given below for three types of digital systems. The case of a scalar z; is of special interest. Let {Ai}, with j = I, ... , N, denote the N quantum intervals, and let

2 (Jz"

T

= H"AI"II"

(B.6)

+ R",

Then the expression for the scalar JV(Aln ) becomes

JV(M") =

E[JI

cov (2'"

x P(=" E Ai

B.2

I=" E Ai, z", oL)

Iz", O";J IO";.. J

(B.?)

Pulse Code l\1odulation

or

JV(M*) The estimate of the ensemble mean square error of the Gaussian fit algorithm in the pulse-code-modulation mode is determined by

Cotnput ation

106

APPENDIX B

Equation BA with W(M) determined as follows. Dropping the subscripts, let the N quantum intervals Ai be defined by the boundaries {dj},withj~ 1, ... ,N + l;thatis,

j = 1,2, ... ,N.

(B.8)

A quantizer distortion function is defined for a Gaussian variable and a particular quantizcr and is givcn by (B.9)

where the conditional covariance and probability arc evaluated under the assumption that z is normally distributed before quantization, see Equation 5.31. This distortion function is the normalized minimal mean square error in the reconstruction of the quantizer input. Substituting Equation B.9 in Equation B.7 provides W(M) = ,,;

f D( z , :!...) p(z I {Jz

az

M) "z.

(B.IO)

An approximation to the ensemble statistics of z conditioned on M will be considered next. Let x be the mean of the state conditioned on past data Z. Then, from Equations !l.6, 22 =

ussin:

I

= H[E(xx T Z) - cov (x

IZJ]II T •

(B.Il)

The ensemble average of z is zero (or can be made zero by change of variable), so that averaging Equation B.II over all possible measurements Z yields the variance of Z, or ,,; ~ II(M" - M*)//T = (a~)2

(B.12)

- (aif,

where J1r is the a priori covariance of the process, and (":)' ~ IIM"II T + R, (,,:)' = IIM*II T + R.

(B.13)

Now it is assumed that the distribution of z is close to N(O, ,,;)which is strictly true when the measurements arc Iincar-c-and the desired result is W(IIf*) n

~

(,,*)' z"

f" -

exp Cf)

[-~(ZI"iY]D(~ ~) i*' * c Z. IT (Ji" a z" (Jz"

(2 )112

(B.14)

APPENDIX 8

107

The standard deviations are found from versions of Equations 13.12 or Equations B.13 with the same subscripts. Although analytical approximations can be made to Equation 13.14 it can be evaluated quite easily by numerical quadrature.

ThL' Optimal Quantizer For three or more quantum levels the collection {tti } of quantizer parameters may be so chosen as to minimize the ensemble covariance E:t;.. This was considered by the writer (1968), and it was found that for stationary processes the system mean square error is relatively insensitive to changes in {It} if the quantizcr is optimized for the a priori variance (a~)2. The insensitivity is caused by two competing factors: the filtering action reduces the variance, implying that the size of the quantum intervals should be reduced but, from Equation 0.12, a smaller means a larger variance of the conditional mean, and the quantum intervals should be increased. to insure efficient quantization when: is away from zero.

a:

n.3

Predictive Quantization

As in the case of pulse code modulation, an estimate of the ensemble average mean square error is generated by the recursive solution of Equations 13.4 and o.S with a different form for \V(M:). Recall that the feedback function L" is the mean of r, conditioned on all past measurements. This has the effect of setting: equal to zero in the distortion function given by Equation 8.9 (actually u; is being quantized, but Un and z; differ only by a constant, so their covariances arc the same). Consequently, \V(M:) for predictive quantization becomes

(13.15) The quantizer design for a stationary input may be made as follows. Temporarily assume that the quantizer is time-varying, and choose the parameters 1/i at time t" such that they arc optimal for (a!Y. Now D(O, lila:') becomes Dx(N), the minimal distortion for a unit-variance, zero-mean, Gaussian variable. and it is a function only of N, the number of quantum levels; see Max, [%0, for tabulations of {tt i ] and Dx(N). With this time-varying quantizcr IV(M:) becomes (B.16)

APPENDIX B

lOX

As

II

approaches infinity, the ensemble covariance and thus the

quantizcr parameters approach a constant. This final quantizcr

minimizes the ensemble covariance, because using any distortion other than D,(Nj yields a larger solution to the Rieeati equation, Equation BA. 8.4

Data-Compression

The lV(Af) function for the data-compression system is identical

with that in predictive quantization, except that there is only one quantum interval (of halfwidth x) in the distortion function. Equation B.IS becomes

* _ * '[J'!"~" exp(-!lI')dll_ (-=-)exp[-!(x/a:Y]] _""~,, (2rr)l/2 2 a:" (2rr)l/2 .

lV(M" j - (a,J

(B.17) Equations BA, B.S, and B.17 describe an approximation to the ensemble covariance. The sample-compression ratio, CR. is a common figure of merit for data-compression systems; it is the ratio of the number of input samples to the average number of transmitted samples. For the

system considered here it is

* - ( 1CR(M,j.

J'I"'.

2j eXP(-!1I 1/2 dllj _ ~/"'~"" (2n)

-'

(B.18)

Appendix C. Sensitivities of Mean Square Estimation Error with Respect to Quantizer Parameters This appendix contains the derivation of the partial derivatives of the mean square estimation error (MSEEl with respect to the quantizer parameters.

c.t

Change in l\1SEE due to Changes in Output Autocorrelation

Equation 4045 is repeated here: (C.I)

The AI x AI matrix 15Y is composed of the elements

.. = (5(
5Y (,)

2

j)) •

(C.2)

This matrix has only At independent clements. As in Equation 4.46, [et


h(lHl=~.

(C.3)

Now write (Was the sum of three matrices: (SY

= D + C + C",

(CAl 109

110

APPENDIX C

c=

<5b( 1)

0

<5b(2)

ob( 1)

0 0 "0

bb(M - 1) .........

0

<5b( I)

Substituting Equations CA and CS in Equation Cl yields

oe

2

= k

2KDKT

=

2

+ 2k 2KCKT

M

k

L

M

K?oh(O)

+ 2k 2

;=1

i-I

L L

K;Ki5h(i - j).

(C6)

i=2j=1

By making a change of subscripts in the second term this term may be rewritten M

2k 2

M

i-I

L L

K;K/5hU - j)

=

2k 2

;-1

L L

KjKi_",<)h(m)

;=2m=1

i=2j~1

/1.1 -1

= 2k 2

L

m= 1

,\I-m

<5b(m)

I

KjK j + m •

(C7)

j= I

The change in mean square estimation error due to changes in the b variables, Equation C6, now becomes (C8)

C.2

Partial Derivatives of h(m) with Respect to {d"}

The partial derivatives of the b(m) variables with respect to the quantizer input parameters d" will be treated first. From Equation C3 we have i'b(m) _

1(C¢n.(m)

cd" - k 2 ~

tk)

-

2¢n(lIl) k td"'

(C9)

APPENDIX C

111

The first term here is found by using the expressions from Equations 4.1 and 4.2, when IIJ is nonzero : (CIO)

where P «( I, (z) is the joint probability-density function for the quantizer ::,+

m' Z "

input samples at times t j + m and t j • Continuing with Equation CIO gives

l\'

- 2

."i:=

f

a«:

I yy 1

1

P ((z, £III) d( zP=;W) zj~ml:j

J-"

ill

= 2(y"-l

- y")p=/dn )

L

y'P(Zj+m E A' I Zj = d n )

s= 1

(CII)

When

III

is zero, the derivative is given by

p'2I

(~4>\"l"(O)_D!II ~ {n I (J )

---::;--," ((

((

s= 1

d

' . '

d,'

= (y"- 1)2 p=} d"J ~ =

[(yO -

1

f -

v

p=,(O d~

(yll)2 p=} d")

(y"f]p:z (£I"). J

(CI2)

The partial derivatives of k with respect to d" arc determined next. Equation 4.17 gives

(Cl3)

Substituting Equations CI I, C12, and CI3 in Equation C9 yields

APPENDIX C

112

the desired form of the partial derivative of him) with respect to d":

2

k 2 <J..... x (

th(lIl)

I'd"

Y")Po(d")

1 -

+ y"

y"-.

2

4\,,(0).)

--k2d,

m = 0,

(J=

:2(1'-1 - y")pz(d") ") , 2 d (E(), + m I-~ -~ d"} _
x

j

j

III

i:- 0. (CI4)

Partial Derivatives of hem) with respect to {y' ~

C.3

The partial derivatives of the !J(m) variables with respect quantizer output parameters .1'" are found from Equation C.3: tb(m) _

I (2¢)'.\,(m)

ty" - k 2

2¢)'\(m)

~ -

i'k)

--k- GY" .

to

the

(CI5)

The first term for nonzero m is found by using the expressions from Equation 4.1 : 2¢).,.{m) D::' ~ ~' =-~-L. L.y'/P(':'+mEA',;:,EA") (1 y" U y" r 1 S = 1 J J »

N

=

L

ySP(::j+m E A", Zj E A')

s= 1 N

+ L

yrp(::j+mEAr,ZjEA")

r= 1

=

2(.t.

= 2P(;: j When

III

yrp(::j+mEA'IZjE A"»)P(ZjEA") E

I

A")E(Yj + m Yj = y"),

(C.16)

is zero, the expression equivalent to Equation C.16 is

("'¢)".(O)

-~'~

oy"

= -iJ ~ L

Dr" s='

.2

(y') P(z E AS} =

2y"P(: E A'}'

(C.17)

and it is seen that Equation CI6 can also treat the case of m = 0,

APPEND/XC

113

The partial derivative of k with respect to J" is calculated by using Equation 4.17: {k DIN -,- ~ -,- -, " y'E(z I z E A')P(z E A') 0)''' uy" (jz r~l

I

= ,E(z (J,

IZ E A")P(z E A").

(CIS)

Equations C16 and C IS arc substituted in Equation CIS to provide the partial derivative of h(lIJ) with respect to j-": {"(Ill)

2

(

DJ" ~k2P(ZEA") E(Jj+mlYj~Y")-

1>,,(111))

ku; E(zlzEA"). (CI9)

Appendix D. A Proof of a Separation Theorem for Nonlinear Measurements 0.1

The Distribution of the Error in the Estimate

This, the first part of the proof, shows that the conditional probability-density function of the error in the estimate is not a function of past control actions. Equation 5.39 for the residual, Equation 5.40 for the prediction error, and Equation 5.41 for the measurement equation with feedback arc repeated here for convenience: (0.1 )

"klk-I =

Jlk,t'klk.-l'

('1.:1/,;-1 =

(J>k-Lt'k.-Ilk-l

=k = h~J"klk -

l'

+

Wk.-I.

(0.2) (0.3)

['k)'

Any function that docs not include the control variables (but it may include past measurements) can be added to the residual or be multiplied by the residual, and the following arguments arc still valid. At time t 1 prior to the processing of the measurement =1 the distributions of the error in the estimate, ello, the residual "uo . and the measurement =I arc all determined solely by the distributions of rojo , 'vo- and Equations 0.1, 0.2, and D.3, and these distributions are therefore not influenced by "0. Now we shall show that the distribution or the error in the estimate just (!Iter the first measurement is not influenced hy "0' either. Instead of considering the estimation error, though, it is more convenient to consider the prediction error el]O conditioned on the measurement =1 (the conditional distribution is 114

APPENDIX D

115

the same as that for the estimation error except for a bias). This conditional density function in its most general form is pte 110 I: I, Zo, 110)' Applying Bayes' rule, we have

(

I

pellO :1' Z 0,110 )

=

p(:lleIIO,ZO,uo)p(elioIZo,lIo) (~IZ)

P-l

(0.4)

0,110

Each of the three conditional density functions on the right-hand side of this equation is independent of 110: the function p(: I Iello, Zo, 110), because of Equations 0.1 and 0.3; the function p(e1l o IZo, 110), beca use of Eq uaiion 0.2; and the function p(: I I Zo, 11 0), because of Equations 0.1, 0.2, and 0.3. Thus the distribution of the error in the estimate after the first measurement is independent of 110, and so are all subsequent error distributions. The same is true of all later control actions, so that the distribution of the error in the estimate at each time never depends on the control.

0.2

The Optimal Control Sequence

Dynamic programming is used to find the optimal control sequence. Proceeding to the last stage, the optimal choice of lis is that which minimizes the performance criterion, (0.5)

subject to the state-equation constraint, Equation 5.36. The best choice of liS by direct minimization is

II; =

-(B,'1

+ G,(.S,.+ IG"r IG;(.S,'1+ I <1>",E(x", I Z"', UN_d,

(0.6)

where we have made the substitution SN+l

=

AN + I

•

From Equation 5.20 the cost of completing the process from time r", _ I with the use of allY JI", ~ I but the ()ptim(/II(~, can be written I

N- 1

= E(X~-IAN-IXN-l + u~-IBN-IIlN-l

+ X[.SNXN I ZN~ I ' UN-I) + tr [E(C".£SIN I ZN-I, U N - dJ + const,

(0.7)

where

+ <1>,(SN+ lN - CN, C N = ~SN+IG".(B.'1 + G~SN+IGN)-lG~SN+lN' SN = AN

I

E N1N = E(eNINe~IN ZN, U N-

d·

(0.8) (0.9)

(0.10)

116

APPENDIX D

The optimal choice of lIs_ 1 rmrnrmzcs Equation 0.7. But the first part of this proof showed that the distributions of both the estimation error and the measurements arc independent of control action. The second term in Equation 0.7 may thus be ignored. and an equivalent performance criterion is given by J~~ 1 = E(xL IAN-1XN-1

+ lI~-IBN-lll:'I-1 (0.11)

Since this is precisely the form of J", in Equation 0.5. with all subscripts decreased by I, it follows that 1 is determined by Eq uation 0.6 with all subscripts decreased by I. The remaining controls arc found by induction. with the result that

IIx _

117

=

-(Bi

s, = A" +

+ cts., IGr -cts., .l1l

jE(x j

I1lJ'[Si+ 1

S"'+I=A!'I+I'

-

I z; o.. d.

(0.12)

s., IG,(B + GTSj+ .Gi)-IG;rSi+ IJl1li • j

(0.13)

This control law IS identical with Equation 5.22 for the linearmeasurement case in which the optimal stochastic controller is separated into two clements, a filter for generating the conditional mean of the state vector and a linear control law that is optimal when all uncertainties arc neglected.

Appendix E. Derivation of the One-Measurement Cost Function Assume that measurements and control actions have occurred up to time (/;.- The control s, is determined by allowing for the measurement at time t u 1 and assuming an open-loop program from lk+ Ion. The cost of completing this process for a linear system and a quadratic cost function is, from Equation 6.19.

JOM,1i. = E[x[AkXk'+ uTB!.'lk

+

E(J~L.k+ I IZ" U,) IZ,. U'_I]'

(E.l)

where J~n.k + I is the minimal cost of completing the open-loop portion of the program; it is found from Equation 6.12 by replacing k with k + I:

J"01.,k+1 =

AT

Xk+I!k+l

S k+1 Xk+llk+l A

+

N+l

L

tr (A,Eilk+ 1).

(E.2)

i=k+ 1

where Xk+llk+l = E(Xk+l \Zk+t, £llk+1 = E[(x i -

5j

=

Ai

Ud,

Xilk+l)(Xj - xilk+dTjZk+l'U i - t ],

+ q>J'[Si+l

- Si+lG;(Bj

+ GTSi+lGj)-IC;rSi+l]¢Jj. (E.3)

117

li S

A PPEN DIX E

The la st term in Eq ua tio n E.2 may a lso be writt en s+ I

.\'+ 1

L

tr (A j£ ;Il+

d=

L

j ",, " + 1

i .. , + I

E(e~l + , A ,eil"+ I

I z ..... 1 . u.: d·

(EA)

Th e error pr op agat es th rough the system during this open-loo p co ntro l phase as ind icated in Equa tion 6.3 :

= cIl i + I, H l e' + I! l + 1 +

L

(J) i + l.j + l "'j '

(E.6)

j -k + 1 I = cIljcIl i _ I · · . l1J j + I Eq ua tio n E.6 ma y be substituted in Eq ua tion EA. All cro ss-prod uct term s drop out. becau se the noise vecto rs a re inde pendent of the estimatio n error l' l+ I ll + I and of eac h o ther. The terms invo lving the noi se co varianccs arc additive co nstants. Thus Equation E.4 becom es

wh ere lD;+ I. j +

.\' + I

L

tr (A,l:'n.. ,)

+I

j .. ,

,'Ii + 1

L

j =

+

E(e[+ IIoHI <J> T.. +I A jcbi.k+ l f'Ul lk+I ! Z HI . U, -d

1+ I

con st

= tr ( I:'' ' ' I' ' '

(E.7)

Th e summation of mat rices in Equa tion E.7 de pends only on the system a nd the cos t function . Deline this mat rix as F.. , : .\' +1

FU

L

I

<1'[. +1Aj<J>;., + 1

j "l + 1

=

f~,, + ,

[ +IFk+ 2cIl. +1 + A H 1.

= A,,,' + I'

(E.8) (E .9)

An eq uiva lent exp ression for the o ptima l open-loop co st J;".... , ma y be found by substituting Eq ua tio n E.8 in Equat ion E.7 a nd. in tu rn , substi tu ting the result in Eq ua tion E.2:

APPENDIX E

+ tr (E H

llk+ IFH I)

= E(x[+ ISH l XH I

+

tr[EH

119

+ const

IZH I' Uk)

I !H I ( F H 1 -

SHI)]

+ const.

(E.10)

The second of these two expressions for the cost is averaged over all measurements at [ H I and substituted in Equation E.I, to give JOlf.b the one-measurement cost function: JOI/,k

=

+ IIr Sk Uk + x[+ ISk+ IXH 1 I z.. Ud + tr{E[Ek+llk+I(Fk+1 - SHI)IZk' Uk]: + canst.

E(xrAkXk

(E.ll)

As a final point it will be shown that the weighting matrix F k + I Sk + I for Ek+ Ilk+ I in Equation E.II is at least positive semidefinite (if this matrix were indefinite or negative definite, the control would minimize the cost by degrading, not improving, the measurements). To show this we shall draw upon the duality between optimal control of deterministic linear systems subject to quadratic costs and statevariable estimation (Kalman, 1960). Let us make the following interpretation of the matrices in Equation E.3: A . . + [ = S . . . + I = covariance of state vector at time t N prior to processing of the measurement at t ..... , Ai = covariance matrix of (white) process noise at t.. G!' = measurement matrix at Ii' B, = covariance of (white) observation noise at Ii' Si+ I = covariance of prediction error at time Ij, 11)! = transition matrix of a system from time t i to li- I ' Then Equation (E.3) describes the evolution of the prediction-error covariance matrix as measurements are processed: the time index is decreasing as more measurements arc processed. By Equation E.9 the matrix Fi; I is equivalent to the error covariance at time I j without the benefit of observations. The matrix F j + I - Si+ I represents the improvement in covariance due to measurements and is always at least positive semidefinite.

References Aoki, M., Optimization of Stochastic Systems, Academic Press, New York, 1967. Balakrishnan, A., "An Adaptive Nonlinear Data Predictor," Proc. Natt. Tetcrnesry

c.or. (1962).

Bass, R.• and L. Schwartz. "Extensions to Multichannel Nonlinear Filtering," Hueltes R('fJ(Jr/ SSD 60220R. February 1966. Bellman, R., Adaptive Control Processes. Princeton Univ. Press, Princeton, New Jersey.

Bello, P., R. Lincoln, and H. Gish. "Statistical Delta Modulation," Proc. IEE£, 55, 308319 (March 1967). Bennett, \V,, "Spectra of quantized signals," Bell System Tali. J., 27, 446-472 (July 1948). Bertram, J. E., "The Effect of Quantization in Sampled-Feedback Systems," Trans. Am. //1.1'/. Etcc. Engrs .. PI. II (App!. Ind.), 77,177-182 (1958). Bryson, A. E., and Y. C. 110, Applied Optimal Control, Blaisdell Publishing Company. Waltham, Massachusetts. 1969. Buey. R., "Nonlinear Fillering Theory," IEEE Tn/lis. Automatic COlltrol, AC-IO, In (1965).

Curry, R. E., "Estimation and Contra] with Quantized Measurements," Ph.D. Thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge. Massachusetts, May 1968. Davenport, W. B., and W. L. Root, An Introduction fa the Theory (!{ Randani Signals Ul/(J Noise, McGrClw-llill Book Company, Inc., New York, 1958. Davisson, L., "Theory of Adaptive Data Compression," in Advances in Communication Svstems. A. Balakrishnan (Ed.). Academic Press. New York, 1966. Davisson, L., "An Approximate Theory of Prediction for Data Compression." IEEE Trans, lnfarm, Th''OYI'' 1T-l3, 274--278 (April 1967). Davisson, L., "The Theoretical Analysis of Data Compression Techniques," Proc. IEEE. 56.176--186 (February 196H) Dcyst. J., "Optimal Control in the Presence of Measurement Uncertainties," SC.D. Thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, Massachusetts. January 1967. Doob, J., Stochastic Processes, John Wiley & Sons, l nc., New York, 1953. l~()

REFERENCES

121

Dreyfus. S .• "Some Types of Optimal Control of Stochastic Systems," J. Soc.Tnd. App], MaIIJ., Ser. A. 2, 12G-134(1964) Dreyfus. S., Dynamic Programming and the Calculus oj Varialio1l.r, Academic Press, New York, 1965. Ehrman, L., "Analysis of Some Redundancy Removal Bandwidth Compression Techniques," Proc, IEEE, 55, 278-287 (March 1967). Fel'dbaum, A., "Dual Control Theory, I-IV," Automation and Remote Control: 21, 874, [033 (1960): 22, I, 109 (1961). Fine, T., "Properties of an Optimum Digital System and Applications," IEEE Trans. Inform. Theory, IT-10, 287-296 (1964). Fisher, J., "Conditional Probability Density Functions and Optimal Nonlinear Estimation." Ph.D. Dissertation. Univ. Calif., Los Angeles. California, 1966. Fraser, D., "A New Technique for the Optimal Smoothing of Data," Sc.D. Thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, Massachusetts, January 1967. Gclb, A., and W. Vander Vcldc, Mulriple Input Describing Functions and Nonlinear Systcin Design, McGraw-llill Book Company, Inc., New York, 1968. Gish, II., "Optimum Quantization of Random Sequences," Rept . 529, Division of Engineering and Applied Physics, Ilarvard Univ., May 1967. Graham, D. and O. Mckucr, Anolysi.s of Nonlinear Control Systems. John Wiley & Sons, Inc .. New YorLI%1. Grcnandcr, U., and G. Szego, Toeplit : Forms and Their A(!plicalions. Univ. ,Calif. Press, Berkeley, California, 1958. Gunckcl, T.. and G. Franklin, "A General Solution for Linear, Sampled Data Control," Tram. AS.\fE, Ser, D, J. Basic En.~., 85, 197-203 (1963). Gupta, S. S., "Bibliography on the Multivariate Normal Integrals and Related Topics," AmI. Mallt. St atist., 34, 829-838 (1963). 110. Y. C, and R. C K. Lee, "A Bayesian Approach to Problems in Stochastic Estimation and Control," Proc, Join, Aut omatic Conlro[ Conference, 3X2-387 (1964\. Huang. 1., and P. Schultheiss, "Block Quantization of Correlated Gaussian Random Variables.' I[:I':C 1'1'1111.1". COI!IIll/III. Sy.II<'IIIS, Scpt., 2X9-296 (1962). IEEE (Inst. Elcc. Electron. Engrs.) Proc. IEEE, Special Issue on Redundancy Reduction, SS (March 19(7). Irwin, J., and J. O'Neal, "The Design of Optimum DPCM (Differential Pulse Code Modulation) Encoding Systems Via the Kalman Predictor," JACe Preprints, 130I Vi. June 196X. Jazwinski, A., "Filtering for Nonlinear Dynamical Systems," IEEE Trans. Automattc Control, AC-Il, 765 (1966). Johnson, G. W., "Upper Bound on Dynamic Quantization Error in Digital Control Systems Via the Direct Method of Liapunov,' IEEE Trans. Automatic Control, AC-IO. 439-448 (1965). Joseph, P., and J. Tou, "On Linear Control Theory," Trans. Am. 111.1"1. Elec, Engrs., Pt. II (Appl, lnd.), 80,18 (1961). Kalman, R.• "A New Approach to Linear Filtering and Prediction Problems," Trans. AS,HE, Ser. D, J. Boric Eng., 27, 35-45 (March 1960). Kalman, R., and R. Bucy, "New Results in Linear Filtering and Prediction Theory," TranI'. ASME, Sa. D, J. Basic Eng., 28,95-108 (March 1961). Kcllog, W., "Information Rates in Sampling and Quantization," IEEE Trans. Inform. Tltcorr, 1T-13, 506-511 (1967). Klerer, M., and G. Korn, Digital Computer User's Handbook; Chap. 2.5. McGraw-1 lill Book Company. Inc .. New York, 1967. Korsak , II., "Linear Filtering and Prediction with Quantized Measurements," Mcm. 10, Project ESU 5830, Standford Research Institute. Menlo Park, California, February 1967.

122

REFER£,VCES

Kosyakin, A. A., "Taking the Effect of Quantization by Level into Account in the Statistical Analysis of Closed-Loop Digital Automatic Systems," Automation ami Remote Control, 27, 799-805 (1966). Kushner, II .• "On the Differential Equations Satisfied by Conditional Probabilitv Densities of Markov Processes, with Applications," J, Soc, l nd. Arrl. ,".["rh., Sa. A, 2.106-119 (1964). Lanning, J. II., and R. II. Battin, Random Processes in Automatic Control. McGrawlIill Book Company. Inc., New York. 1956. Lee, R. C. K., Optilllal Estimation, Identification, lind Control, MIT Press, Cambridge, Massachusetts. 1964. Max, J., "Quantizing for Minimum Distortion." IRE Trans. Inform. Theory, 1T-6, 7-12 (March 19(0). (a) Meier, L., A. Korsak. and R. Larson. "Effect of Data Quantization on Tracker Performance," Tall. MclII. 3, Project 6642, Stanford Research Institute. Menlo Park, California. October 1967. (b) Meier, L., J. Pcschon, and R. Dressler, "Optimal Control of Measurement Subsystems," IEEE Trans. Automatic Control, AC-I2. 528-536 (1967). Mowery. V.. "Least Squares Differential-Correction Estimation in Nonlinear Problems," IEEE Trans. Automatic Control. AC-IO. 399-407 (1965). O'Neal. J., "Predictive Quantizing Systems (Differential Pulse Code Modulation) for the Transmission of Television Signals," Bell SYS(CI/I Tech. J., 45, 689-720 (1966). Papoulis. A., Probability, Random Variables. and Stochastic Processes, McfIraw-Hill Book Company. Inc .• New York. 1965. Quagliata, L. J., private communication, March 1968. Raggazzini, J .. and G. Franklin. Sanmtrd-Datc Co//tro! Systems, McGraw-llill Book Comnanv, Inc., New York. 1958. Ruchkin, D .• "Linear Reconstruction or Quantized and Sampled Signals," IRE Trans. CO/llIIIIlIl. Svsiems. 350-355 (December 1961). Schweppe, F .• class notes from Course 6.603, Massachusetts Institute of Technology, Cambridge, Massachusetts, Spring 1967. Smith. II .. Approximate Analysis (~f Randomly Excited Nonlinear Controls. MIT Press, Cambridge, Massachusetts, 1966. Stciglitz, K.• "Transmission of an Analog Signal Over a Fixed Bit-Rate Channel," I£F.E Trans. lnfonn. Theory, 1T-12. 469-474 (1966). Stricbcl. C, "Sufficient Statistics in the Optimum Control of Stochastic Systems," 1. MlIlh. Anal. Apr!., 12.576-592 (1965). Swcrling , P .. "First Order Error Propagation in a Stagcwisc Smoothing Procedure for Satellite Observations," J. Astronautica! Sci.. 6. no. 3, 40-52 (1959,1. Vander vcldc. W .. class notes for Course 16.37. Massachusetts Institute of Technology. Cambridge. Massachusetts. Fall 1967, Wid row. B.• "Statistical Analysis of Amplitude-Quantized Sampled-Data Systems," Trans. Am. 111.I-(. Etrc. Engrs .• PI. II (Appl. Ind.), 555-568 (1960). Wiener. N., Extrapolation, tnterpotatian. and Smoothing of Stationary Time Series, MIT Press. Cambridge. Massachusetts, 1966. Wilkinson, J.II .. The A!gehruic Figt'llralut' Prohtnn, Clarendon Press. Oxford. 11.)65. Wenham, W. M., "Some Applications of Stochastic Differential Equations to Nonlinear Filtering," 1. Soc. Ind. Appl. Math., Sa. A, 2. 347-369 (1964).

INDEX Aoki. M .. 5. 64 Approximate estimation. See also Gaussian fit algorithm in data compression systems, 36--37 in peM systems, 31-32 in predictive quantization systems, 33-34 with small quantum intervals, 21-23 31-32. 36--37. 101-103

Conditional mean calculation of. for measurement vector. 17-21 exact expression for. 17-18 of Gaussian parameters, 12-13 of scalar Gaussian variable. 18 with small quantum intervals. 21, 23. 101-103 Curry, R. E., 39, 107

Balakrishnan, A., 4 Bass, R., 23 Batch processing, 15, 22

Data compression (predictivecomparison), 4. 35-36. 40, 95, 108 Davenport, W. B.• 3 Davisson, L.. 4, 5. 23. 37, 94-95 Dead-zone, 1. See also Threshold quantizer Del aeger, 96 Delta modulation, 94-95. See also Predictive quantization Describing function. 46--50 Deyst, J, J.• 66--67 Differential pulse code modulation. 95. See also Predictive quantization Distortion function. 69-70, 106 Doob, J .• II DPCM. See Differential pulse code modulation Dressler, R., 78 Dreyfus. S. E., 5, 64, 80 Dual control. Sec Optimal stochastic control

Battin, R. H .• 10, 53 Bayes' Rule, 3, 10, 115 Bellman, R., 64 Bello. P .• 4, 37-38, 94 Bennett, W., 4 Bertram, J. E., 5 Block quantization, 19-20 Bryson, A. E., Jr., 12-13, 68. 82 Bucy, R., 3 Communication systems, 4. See also Data compression; reM; Predictive quantization Conditional covariance exact expression for, 17-18 of Gaussian parameters, 12-14 of scalar Gaussian variables, 19 with small quantum intervals. 21, 23. 101-103 123

124

INDEX

Dynamic programming, 64-67,

115

Fel'dbaurn, A. A., 5, 72 Filtering. See Approximate estimation; Conditional mean: Gaussian fit algorithm; Optimal linear filter Fine, T., 4, 32-33, 94-95 Fisher, J., 23 Franklin, G., 53, 66 Fraser, D., 25-26

Gaussian fit algorithm in data compression systems, 54-56 description of, 23-25 in PCM systems, 32 performance estimates of, 25, 39-40, 54-56. 105-10R in predictive quantization systems, 33-35 similarity with Kalman filter, 25 simulations, 37-40 in smoothing, 25-30 Gclb, A., 5, 46, 48 Gish, II" 4. 37-38. 57. 94-97 Graham, D., 5 Grenander, U., 53 n Gunckel, T., 66 Ho, Y. C., 4, 12-13, 68, 82 Huang, 1., 19 Irwin J" 4, 37, 47 Jazwinski, A., 23 Johnson, G. W., 5 Joseph, P., 6, 66 Kalman, R., 3, 13, 119 Kalman filter role in nonlinear estimation, 15-16 in the separation theorem, 6, 67-68 similarity to the Gaussian fit algorithm, 25 for small quantum intervals, 22, 32 use in smoothing, 25 Kellog, W., 4, 51, 56-57 Klerer, M., 20-21 Korn, G., 20-21 Korsak, A., 2, 4 Kosyakin, A. A., 5 Kushner, H., 3 Lanning, J. H., 10, 53 Larson, R., 4

Lee, R. C. K., 4, 12-13, 15 Likelihood function, 8 Lincoln, R., 4, 37-38, 94 McRuer, D., 5 Max, J., 4, 107 Meier, L., 4, 78 M-measurement-optimal feedback control, 85-87 Monte Carlo techniques, 37, 41 Mowery, y" 4 Noise. See Quantizer, modeled as a gain element and noise source; Quantization noise Nonlinear estimation, 3. See also Approximate estimation; Conditional mean; Gaussian fit algorithm; Parameter estimation Notation, convention of, 6 O'Neal, J., 4. 37, 47, 94-95 One-measurement-optimal feedback control cost function for, 87, 117-119 derivation of, 86 linear systems and quadratic cost, R7-RR simulations, 89~91 Open-loop-optimal feedback control compared to optimal stochastic control, 82-84 compared to separation theorem, 82 description of. 80 linear systems and quadratic cost, 80-82

simulations, 89-91 Optimal control. See Optimal linear control; Optimal stochastic control Optimal linear control, 91-94 Optimal linear estimation, 3. See also Optimal linear filter Optimal linear filter coefficients of, 52-53 compared to nonlinear filter, 54-56 jointly optimized with quantizer parameters, 56-61 mean square error of, 52 Optimal stochastic control complexity of computations, 74-75 example with quantized measurements, 68-74 linear systems and quadratic cost, 64-66

INDEX separation theorem. See Separation theorem solution by dynamic programming, 64-67,115-116 statement of the problem, 63 Papoulis, A., 10 Parameter estimation. See also Approximate estimation maximum likelihood, estimate, 7-9 Bayes' estimate, 9-11 Gaussian parameters, 12-14 PCM (pulse code modulation) 4, 31-32, 39-40, 105-107 Peschon, J., 78 Predicting. Sec Approximate estimation; Conditional mean; Gaussian fit algorithm; Optimal linear filter Predictive-comparison data compression. See Data compression Predictive quantization, 4, 32-34, 39-40. 94-95, 107-108 Probability density functions, with quantized measurements, 9-10 Pulse code modulation. See PCM Quagliata, L., 78 Quantization noise, 5, 14, 20, 22-23. See also Quantizer, modeled as a gain element and noise source Quantizer, See also Quantization noise; Quantizer parameters in block quantization, 19 in closed-loop systems, 91-94 definition of, I distortion function, 69-70, 106 examples of, I, 43 (Fig. 4.1) modeled as a gain element and noise source, 42-46 output autocorrelation of, 42-44 threshold type, 35, 49-50, 73, 95

Quantizer parameters, 111-113

60,

125

107-108,

Raggazzini, 1., 53 Random input describing function, 46--50 Root, W. L., 3 Ruchkin, D., 4, 22, 46 Sample compression ratio, 40, 108 Schultheiss, P., 19 Schwartz, L., 23 Schweppe, F. C, 12-13, 15, 52, 54 Separation theorem using linear measurements, 6, 66--68, 82 using nonlinear measurements, 75-77, 114--.115 Smith, H., 5, 93-94 Smoothing. See Approximate estimation; Conditional mean; Gaussian fit algorithm; Optimal linear filter Steiglitz, K., 4, 22, 47 Stricbel, C., 67 Suboptimal control, 74. See also Mmeasurement-optimal feedback control; One-measurement-optimal feedback control Swerling, P., 3 Szcgo, G., 53 n Terminal control, 90 Threshold quantizer, 35, 49-50, 73, 95 Tou, J., 6, 66 Vander Velde, W. E., 5, 46, 48, 93 Wid row, 8., 4, 5, 22, 47 Wiener, N., 3 Wiener filter, 93-94, 97 Wilkinson, J. H., 22 Wonham, M., 3