A game theoretic approach to moving horizon control

Sanjay Lall and Keith Glover

Abstract A control law is constructed for a linear time varying system by solving a two player zero sum differential game on a moving horizon, the game being that which is used to construct an H_{∞} controller on a finite horizon. Conditions are given under which this controller results in a stable system and satisfies an infinite horizon H_{∞} norm bound. A risk sensitive formulation is used to provide a state estimator in the observation feedback case.

1 Introduction

The moving horizon control technique was developed in the 1970’s, with one of the first papers being that by Kleinman (Kleinman 1970) in 1970. The techniques in his paper were later reformulated and generalized by various authors, see for example (Chen & Shaw 1982, Kwon & Pearson 1977, Kwon, Bruckstein & Kailath 1983). Kwon and Pearson (Kwon & Pearson 1977) proved stability for linear time varying systems using a controller which optimised a quadratic cost function integrated over a time interval from the current time t to a fixed distance ahead t + T. The solution to this problem was given in terms of a Riccati differential equation, integrated backwards from time t + T at each time t.

For time varying systems, this gives a practical method of stabilising the system. Kwon et. al. (Kwon et al. 1983) formulated a general procedure for the recursive update of such Riccati equations, which generalise easily to the indefinite Riccati equations in this paper.

Further, this method allows stabilization of systems which are known only for the short term future. In dealing with long term variation of systems, there are at present two extreme options. The first is to assume a time invariant system and design a controller robust against time varying perturbations, which usually leads to very conservative controller design. The other is to design fully for time varying systems. In the case of both linear quadratic and H_{∞} controllers, this requires the backwards integration from infinity of a Riccati equation (see for example (Tadmor 1993, Ravi, Nagpal & Khargonekar 1991)), and somewhat optimistically assumes knowledge of the system throughout future time. The moving horizon method can be viewed as a compromise between these two methods.

The aim of this present paper is to extend the work of Tadmor (Tadmor 1992), in which a receding horizon controller is formulated with each finite horizon optimisation based upon an H_{∞} optimisation. It is hoped that the practical advantages of receding horizon control might be combined with the robustness advantages of H_{∞} control. Tadmor proved that that this controller was stable and satisfied an infinite horizon norm bound. Although derived using different approaches to the H_{∞} problem, the controller described in this paper is essentially the same in the state feedback case, differing only in the terminal constraint used.

In the observation feedback case, however, it is difficult to produce a natural formulation of the H_{∞} receding horizon control problem. For the finite horizon problem, typically the assumptions made are that the initial state at the beginning of each optimization interval is completely known, or is completely unknown. In the latter case it is treated as part of the disturbance and subject to a quadratic weighting (Uchida & Fujita 1992) (Khargonekar, Nagpal & Poolla 1991). In the receding horizon problem, though, we have observations from before the optimization interval. We attempt to make use of prior observations using the theory of risk sensitive control, as developed by Whittle (Whittle 1990), which has been shown to be equivalent to H_{∞} control in many situations.

2 Preliminaries

We consider the system

ẋ(t) = A(t)x(t) + B_{1}(t)w(t) + B_{2}(t)u(t)  (1)
z(t) = C_{1}(t)x(t) + D_{12}(t)u(t)
y(t) = C_{2}(t)x(t) + D_{21}(t)w(t)

where the coefficient matrices are bounded matrix valued functions of time. We use the following assumptions

D′_{12}C_{1} = 0 D′_{12}D_{12} = I D_{21}B′_{1} = 0 D_{21}D′_{21} = I  (2)

which can be removed by suitable changes in variables, see for example (Doyle, Glover, Khargonekar & Francis 1989, Ravi et al. 1991, Tadmor 1993). Further, we shall assume there exists ε > 0 such that

B_{1}(t)B_{1}(t)′ ≥ εI for all t > 0
C_{1}(t)′C_{1}(t) ≥ εI for all t > 0  (3)

These assumptions can be removed by assuming uniform complete controllability and observability of the system, and slightly modifying the following arguments.

Let L_{2}^{m}[t_{i}, t_{f}] be the Hilbert space of square integrable functions on [t_{i}, t_{f}] ⊂ R taking values in R^{m}, and write R^{+} = [0, ∞). Denote the usual norm on L_{2} by ∥·∥_{2}, and if F: L_{2} → L_{2} then denote by ∥·∥_{∞} the norm on F induced by ∥·∥_{2} Then x: R^{+} → R^{n}, u ∈ L_{2}^{m_{1}}[t_{i}, t_{f}] ,w ∈ L_{2}^{m_{2}}[t_{i}, t_{f}], y: R^{+} → R^{p}. The signal w represents all external inputs including disturbances, sensor noise, and commands, z represents the error signal, y is the measured variable and u is the control input. We shall omit the space dimensions of signals in the sequel.

3 State feedback

3.1 Finite horizon H_{∞} control

Define the cost function

J_{γ}(u, w) = ∫_{t_{i}}^{t_{f}} {z(t)′z(t) − γ^{2}w(t)′w(t)} dt

We can regard J_{γ} as a function of either L_{2} signals or feedback strategies. Let M = { μ: [t_{i}, t_{f}] × R^{n} → R^{m1} } and N = { ν: [t_{i}, t_{f}] × R^{n} → R^{m2} }. These spaces are the strategy spaces, and we shall write strategies as μ, ν to distinguish them from signals u, w. With the control u(t) = μ(t, x(t)) in place, the operator T_{zw} maps w to z. If x(t_{i}) = 0, then we can define

∥T_{zw}∥_{∞} = sup_{w∈L_{2}[t_{i},t_{f}]} ∥T_{zw}w∥_{2}/∥w∥_{2}

The finite interval H_{∞} problem is to find a linear causal control μ such that ∥T_{zw}∥_{∞} < γ for a given γ > 0. ∥T_{zw}∥_{∞} < γ if and only if there exists ε > 0 such that

J_{γ}(u, w) ≤ −ε∥w∥_{2}^{2} ∀w ∈ L_{2}[t_{i}, t_{f}]  (4)

We formulate the finite time differential game

inf_{μ∈M} sup_{ν∈N} J_{γ}(μ, ν)  (5)

which is a zero sum game, where u is the minimizing player and w is the maximizing player. The designer chooses u(t) = μ(t, x(t)) such that even if nature is malicious and chooses the worst case w, then equation (4) is satisfied.

If the extremizing operators in equation (5) are interchangeable, then we call the optimal u and worst case w saddle point strategies. Theorem 1 gives sufficient conditions for the existence of a saddle point solution. A saddle point solution u(t) = μ^{∗}(t, x(t)), w(t) = ν^{∗}(t, x(t)) will satisfy

J_{γ}(μ^{∗}, w) ≤ J_{γ}(μ^{∗}, ν^{∗}) ≤ J_{γ}(u, ν^{∗}) ∀u, w ∈ L_{2}[t_{i}, t_{f}].

Theorem 1 (Basar & Olsder 1982, Limebeer, Anderson, Khargonekar & Green 1992) Let

J_{γ}(u, w) = ∫_{t_{i}}^{t_{f}} {z(t)′z(t) − γ^{2}w(t)′w(t)} dt + x(t_{f})′F x(t_{f})

where F > 0 is some weighting matrix. If

− Ṗ = P A + A′P + C′_{1}C_{1} − P (B_{2}B′_{2} − γ^{−2}B_{1}B′_{1})P, P (t_{f}) = F  (6)

has a unique symmetric bounded solution on t ∈ [t_{i}, t_{f}], then

J_{γ}(u, w) = x(t_{i})′P (t_{i})x(t_{i}) + ∫_{t_{i}}^{t_{f}} |u(τ) + B_{2}(τ)′P (τ)x(τ)|^{2}dτ
− ∫_{t_{i}}^{t_{f}} γ^{2}|w(τ) − γ^{−2}B_{1}(τ)′P (τ)x(τ)|^{2}dτ

Further, with full state information available to u(t) = μ^{∗}(t, x(t)) and w(t) = ν^{∗}(t, x(t)), there exists a unique feedback saddle point solution given by

μ^{∗}(t, x(t)) = −B_{2}(t)′P (t)x(t)
ν^{∗}(t, x(t)) = γ^{−2}B_{1}(t)′P (t)x(t)

and the saddle point value of the game is given by

J_{γ}(μ^{∗}, ν^{∗}) = x(t_{i})′P (t_{i})x(t_{i}).
□

3.2 The moving horizon differential game

We now try to find u(t) = μ^{∗}(t, x(t)) at time t, where μ^{∗} is the saddle point strategy for player u for

inf_{μ∈M_{t}} sup_{ν∈N_{t}} {∫_{t}^{t+T} {z(s)′z(s) − γ^{2}w(s)′w(s)} ds + x(t + T)′F (t + T)x(t + T)}

where M_{t} = { μ: [t, t + T] × R^{n} → R^{m1} }, N_{t} = { ν: [t, t + T] × R^{n} → R^{m2} }, and w(t) = ν^{∗}(t, x(t)).

The idea behind this is to try to gain both the robustness benefits of the H_{∞} formulation and the practical control of time varying systems associated with receding horizon control. At each time t we try to solve the finite horizon H_{∞} problem on the optimisation interval [t, t + T] to find a feedback strategy u(t) = μ(t, x(t)).

In practice, this would be implemented for a finite time δ > 0, after which a new calculation on the interval [t + δ, t + δ + T] would be performed. In this paper we idealise this situation and assume that the controller is updated continuously.

For each separate H_{∞} optimisation, the initial state may not be zero. Therfore, an induced norm interpretation on each finite horizon is not possible, since zero input u gives a nonzero output z on the interval [t_{i}, t_{f}], and thus the induced norm is undefined.

We also have a penalty on the terminal state, F (t) > 0. This is often incorporated into finite horizon problems to allow for compromises between the norm of z and the size of x(t_{f}). In the moving horizon case, we shall show that a sufficiently large F will cause the closed loop to be stable.

In order to find u(t) for the moving horizon problem we must integrate equation (6) backwards from the boundary condition at t + T to time t. We can rewrite this as a partial differential equation as follows

− \frac{∂P (τ, σ)}{∂τ} = P (τ, σ)A(τ) + A(τ)′P (τ, σ) −
P (τ, σ)(B_{2}(τ)B_{2}(τ)′ − γ^{−2}B_{1}(τ)B_{1}(τ)′)P (τ, σ) + C_{1}(τ)′C_{1}(τ)
P (t, t) = F (t) for all t

The moving horizon saddle point controller is given by

u(t) = −B_{2}(t)′P (t, t + T)x(t)

In the case when all system matrices A, B_{1}, B_{2}, C_{1}, D_{12} are time invariant, then P (t, t + T) is independent of t also.

3.3 Stability

Tadmor (Tadmor 1992) proves stability for the above controller when F = ∞. In this case, we can consider the Riccati equation for P^{−1} and the interpretation on the finite horizon is that the controller is subject to the constraint x(t + T) = 0.

The linear quadratic problem with a similar terminal weight was considered by Kwon, Bruckstein and Kailath (Kwon et al. 1983). We use a modified form of their methods to handle the terminal weight.

Before the stability proof, we need the following lemmas, in which we will write P (τ, σ, F) for the solution of the Riccati equation with boundary condition P (τ, σ, F) = F for τ = σ, with σ fixed. The following results are derived in a slightly different way in (Kwon et al. 1983), and various similar results can be found in (Anderson & Moore 1989, Reid 1970, Bucy 1967, Ran & Vreugdenhil 1988, Basar & Bernhard 1991).

Lemma 2 Let P satisfy the following Riccati equation on [t_{i}, t_{f}], with F ≥ 0 and Q ≥ 0.

−Ṗ = P A + A′P − P (B_{2}B′_{2} − γ^{−2}B_{1}B′_{1})P + Q P (t_{f}) = F

then if P exists, and either F > 0 or Q > 0, then P (t) > 0 ∀t ∈ [t_{i}, t_{f}].

Lemma 3 Suppose

Ḟ + A′F + F A − F (B_{2}B′_{2} − γ^{−2}B_{1}B′_{1})F + C′_{1}C_{1} ≤ 0, F (t) > 0, t > 0  (7)

and P satisfies

−Ṗ = A′P + P A − P (B_{2}B′_{2} − γ^{−2}B_{1}B′_{1})P + C′_{1}C_{1}

then, if both sides exist,

P (τ, σ_{1}, F (σ_{1})) ≥ P (τ, σ_{2}, F (σ_{2})), τ ≤ σ_{1} ≤ σ_{2}

Proof We know (see (Basar & Bernhard 1991))

x(t_{i})′P (t_{i}, t_{f}, F (t_{f}))x(t_{i}) =  (8)
min_{u} max_{w} {∫_{t_{i}}^{t_{f}} (x(s)′C_{1}(t)′C_{1}(t)x(s) + u(s)′u(s) − γ^{2}w(s)′w(s)) ds + x(t_{f})′F (t_{f})x(t_{f})}

then

(i) If C̃_{1}(t)′C̃_{1}(t) ≥ C_{1}(t)′C_{1}(t) ∀t ∈ [t_{i}, t_{f}], then replacing C_{1} by C̃_{1} results in a new solution, P̃ satisfying P̃(t) ≥ P (t) ∀t ∈ [t_{i}, t_{f}].

(ii) Similarly, if F̃(t) ≥ F (t) ∀t ∈ [t_{i}, t_{f}], then P̃(t) ≥ P (t) ∀t ∈ [t_{i}, t_{f}].

With either of these changes, equation(8) becomes

x(t_{i})′P̃(t_{i}, t_{f}, F (t_{f}))x(t_{i}) =

min_{u} max_{w} {∫_{t_{i}}^{t_{f}} (x(s)′C_{1}(s)′C_{1}(s)x(s) + u(s)′u(s) − γ^{2}w(s)′w(s)) ds + x(t_{f})′F (t_{f})x(t_{f})
+ h(u, w)}

and h(u, w) > 0 ∀u, w ∈ L_{2}.

We can write equation(7) as

−Ḟ = A′F + F A − F (B_{2}B′_{2} − B_{1}B′_{1})F + (C′_{1}C_{1} + Δ),

where Δ ≥ 0. By definition,

P (σ_{2}, σ_{2}, F (σ_{2})) = F (σ_{2})

so, since the Riccati equation for P and F are equal at t = σ_{2}, and that for F has a bigger constant term,

F (t) ≥ P (t, σ_{2}, F (σ_{2})) for all t ≤ σ_{2}

We can rewrite this as

P (σ_{1}, σ_{2}, F (σ_{2})) ≤ P (σ_{1}, σ_{1}, F (σ_{1}))

so, when t = σ_{1}, the LHS is smaller than the RHS. We can take this point as a boundary condition, and, using (ii) above,

P (t, σ_{2}, F (σ_{2})) ≤ P (t, σ_{1}, F (σ_{1})) for all t ≤ σ_{1} ≤ σ_{2}
□

Theorem 4 For the system described by equations (1-3), if at each time t the saddle point solution to the differential game on [t, t + T] exists, then if

Ḟ + A′F + F A − F (B_{2}B′_{2} − γ^{−2}B_{1}B′_{1})F + C′_{1}C_{1} ≤ 0, F (t) > 0, t > 0

and if there exists constants α_{1} > 0 and α_{2} > 0 such that

α_{1}I ≤ P (t, t + T, F (t + T)) ≤ α_{2}I

then the control u(t) = −B_{2}(t)′P (t, t + T, F (t + T))x(t) is stabilising.

Proof Let Λ(t) = A(t) − B_{2}(t)B_{2}(t)′P (t, t + T, F). Then, with the controller in place, ẋ = Λ(t)x(t) + B_{1}(t)w(t). Let V (t) = x(t)′P (t, t + T, F (t + T))x(t). Then

V̇ = x′ (−P′B_{2}B′_{2}P − γ^{−2}P B_{1}B′_{1}P − C′_{1}C_{1} + \frac{∂}{∂σ} P (t, σ, F (σ))|_{σ=t+T} ) x

Using Lemma 3,

\frac{∂}{∂σ} P (t, σ, F (σ))|_{σ=t+T} ≤ 0

Since C′_{1}C_{1} > εI, V̇ (t) < −εx(t)′x(t). Then, since by assumption P is bounded, it is a Lyapunov function for the closed loop system, hence the system is globally exponentially stable. □

If we can prove boundedness of P (t, t + T, F (t + T), then we shall have a sufficient condition for the controller to be stable. Tadmor (Tadmor 1992) proves that P (t, t + T, ∞) is bounded above and below. Slight modification of his proof shows:

Theorem 5 Let G_{i}(t_{0}, t_{1}) = ∫_{t_{0}}^{t_{1}} Φ(t_{0}, t)B_{i}(t)B_{i}(t)′Φ(t_{0}, t)′ dt. If (A, B_{2}) is uniformly controllable and G_{2}(t_{0}, t_{1})^{−1}G_{1}(t_{0}, t_{1}) is uniformly bounded for all t_{1} − t_{0} ≤ T, then there exists γ > 0 such that P (t, t + T, F (t + T)) is bounded above for all t > 0.

3.4 Infinite horizon norm bounds

Following (Tadmor 1992), with the controller u(t) = −B_{2}(t)′P (t, t + T, F (t + T))x(t) and w ∈ L_{2}[t_{0}, ∞] we know

∫_{t_{0}}^{∞} \frac{d}{dt} \{x(t)′P (t, t + T, F (t + T))x(t)\} dt =

∫_{t_{0}}^{∞} \{−z′z + 2w′B′_{1}P x − γ^{−2}x′P B_{1}B′_{1}P x + x′ ( \frac{∂}{∂σ} P (t, σ, F (σ))|_{σ=t+T} ) x\} dt

If the closed loop is stable, then

∫_{t_{0}}^{∞} \frac{d}{dt} \{x(t)′P (t, t + T, F (t + T))x(t)\} dt = −x(t_{0})′P (t_{0}, t_{0} + T, F (t_{0} + T))x(t_{0})

Let ŵ(t) = w(t) − γ^{−2}B′_{2}(t)P (t, t + T, F (t + T))x(t). Then, if x(t_{0}) = 0 ,

∥z∥_{2}^{2} − γ^{2}∥w∥_{2}^{2} = −γ^{2}∥ŵ∥_{2}^{2} + ∫_{t_{0}}^{∞} x′ ( \frac{∂}{∂σ} P (t, σ, F (σ))|_{σ=t+T} ) x dt

Using Lemma 3,

∥z∥_{2}^{2} − γ^{2}∥w∥_{2}^{2} ≤ 0

Hence ∥T_{zw}∥_{∞} ≤ γ.

4 Calculation of P (τ, σ, F (σ))

In order to implement the moving horizon controller, we need to calculate the value of P (t, t + T, F (t + T)) for all t > 0. This requires the solution of a Riccati differential equation over the interval [t, t + T] for each time t, given boundary conditions P (t, t + T, F (t + T)) = F (t+T) for all t > 0. Kwon, Bruckstein and Kailath (Kwon et al. 1983) applied results from scattering theory in their solution to the quadratic problem, to give a forwards differential equation for P (t, t + T, F (t + T)). Here we state the same solution for the indefinite Riccati equation. See (Verghese, Friedlander & Kailath 1980) for details on the derivation of these formulae. In this section, P (τ, σ) is used to mean P (τ, σ, 0). Define for convenience

N(τ) = B_{2}(τ)B_{2}(τ)′ − γ^{−2}B_{1}(τ)B_{1}(τ)′

Let

S(τ, σ) = ( \begin{matrix}Φ(τ, σ) & L(τ, σ) \\ P (τ, σ) & Ψ(τ, σ) \end{matrix} )

Consider the system of equations

\frac{∂}{∂τ} Φ(τ, σ) = Φ(τ, σ)[N(τ)P (τ, σ) − A(τ)]  (9)
\frac{∂}{∂τ} Ψ(τ, σ) = [P (τ, σ)N(τ) − A′(τ)]Ψ(τ, σ)  (10)
\frac{∂}{∂τ} L(τ, σ) = Φ(τ, σ)N(τ)Ψ(τ, σ)  (11)
\frac{∂}{∂τ} P (τ, σ) = A′(τ)P (τ, σ) + P (τ, σ)A(τ) − P (τ, σ)N(τ)P (τ, σ) + C_{1}(τ)′C_{1}(τ) (12)

with boundary conditions

S(σ, σ) = ( \begin{matrix}I & 0 \\ 0 & I \end{matrix} )

The following equations

\frac{∂}{∂σ} Φ(τ, σ) = [A(σ) + L(τ, σ)C_{1}(σ)′C_{1}(σ)]Φ(τ, σ)  (13)
\frac{∂}{∂σ} Ψ(τ, σ) = Ψ(τ, σ)[A′(σ) + C_{1}(σ)′C_{1}(σ)L(τ, σ)]  (14)
\frac{∂}{∂σ} L(τ, σ) = A(σ)L(τ, σ) + L(τ, σ)A′(σ) + L(τ, σ)C_{1}(σ)′C_{1}(σ)L(τ, σ) − N(σ) (15)
\frac{∂}{∂σ} P (τ, σ) = Ψ(τ, σ)C_{1}(σ)′C_{1}(σ)Φ(τ, σ)  (16)

give the partial derivatives with respect to σ.

It is straightforward to verify this by taking both sets of second partial derivatives, and showing that they are equal, and verifying that along the boundary the total derivative

\frac{d}{dt}S(t, t) = \frac{∂S(τ, t)}{∂τ}|_{τ=t} + \frac{∂S(t, σ)}{∂σ}|_{σ=t}

is zero, since Ψ, Φ, L, P are constant along the boundary. We can find a differential equation for P (t, t + T) in terms of t since

\frac{d}{dt}S(t, t + T) = \frac{∂S(τ, t + T)}{∂τ}|_{τ=t} + \frac{∂S(t, σ)}{∂σ}|_{σ=t+T}

Hence

\frac{dΦ}{dt} = Φ[N(t)P − A(t)] + [A(t + T) + LC_{1}(t + T)′C_{1}(t + T)]Φ  (17)
\frac{dΨ}{dt} = [P N(t) − A′(t)]Ψ + Ψ[A′(t + T) + C_{1}(t + T)′C_{1}(t + T)L]  (18)
\frac{dL}{dt} = ΦN(t)Ψ + A(t + T)L + LA′(t + T) + LC_{1}(t + T)′C_{1}(t + T)L − N(t + T) (19)
\frac{dP}{dt} = A′(t)P + P A(t) − P N(t)P + C_{1}(t)′C_{1}(t) + ΨC_{1}(t + T)′C_{1}(t + T)Φ  (20)

where Φ = Φ(t, t + T) etc. This gives a differential equation for P (t, t + t, 0). The boundary conditions for equations (17–20) are given by solving equations (9–12) backwards in time from τ = σ = T to τ = 0, σ = T. This backwards solution has to be performed only once, when t = 0.

We now make use of the following identity.

P (τ, σ, F (σ)) = P (τ, σ) + Ψ(τ, σ)F (σ)[I − L(τ, σ)F (σ)]^{−1}Φ(τ, σ)

This can be verified in a straightforward manner. Then

P (t, t + T, F (t + T)) = P + ΨF (t + T)[I − LF (t + T)]^{−1}Φ

These equations are simpler than they appear, since Φ = Ψ′. They give us a quadratic differential equation in matrices of size 2n, which is integrated forwards to give the controller.

5 State estimation and output feedback

In this section we consider the problem of optimally estimating the state. Let

J(t_{i}, t_{f}) = ∫_{t_{i}}^{t_{f}} {z(t)′z(t) − γ^{2}w(t)′w(t)} dt

Let u_{[0,t_{i}]} = { u(t); 0 ≤ t ≤ t_{i} }. Let t ∈ [t_{i}, t_{f}] be the current time. We then wish to find the feedback saddle point strategy for the u player given information u_{[0,t]} and y_{[0,t]}. For the moving horizon controller we only need to know this strategy at time t = t_{i}.

In recent years H_{∞} theory has been furnished with a certainty equivalence principle in several different formulations (Doyle et al. 1989, Whittle 1990, Basar & Bernhard 1991).

For the finite horizon time varying H_{∞} problem Basar and Bernhard (Basar & Bernhard 1991, p. 119) give a derivation of the optimal estimator for output feedback. Stated in simple terms, their result indicates that one should look, at each instant of time t, for the worst possible disturbance w_{[t_{i},t]} compatible with information available at that time about u_{[t_{i},t]} and y_{[t_{i},t]}. This generates a corresponding worst possible state trajectory, which should be used by the feedback law as if it were the actual state.

The worst case approach to our problem is to extend the maximisation problem into the past, and maximise the cost function with respect to unobservables before t_{i}, back to time t = 0. This would require us to assume that, for times 0 < t < t_{i}, w was trying to maximize the cost function on [t_{i}, t_{f}]. However, if we do this then w can make J_{γ} infinite, since there is no disincentive on the size of w outside [t_{i}, t_{f}]. This means that we cannot use this principle to estimate the state without further assumptions.

In fact, given the values of past observables, we can only draw conclusions about the current value of the state if we know some information about w (since we have the nondegeneracy assumption that D_{21}D′_{21} = I). In the finite horizon problem, we assume that in the past player w was trying to maximize the cost function over the entire finite interval.

One possible alternative approach is to assume that w is trying to maximize J(0, t_{f}), while u is trying to minimize J(t_{i}, t_{f}). For u, in fact this is equivalent to playing a moving horizon game in which only the endpoint moves.

Alternatively, it is possible to consider a stochastic formulation. In this case we should like to assume that outside the optimisation interval, w is accurately modelled by white noise. In order to do this, we need a stochastic model for H_{∞} control.

5.1 Risk sensitive control

There is a strong connection between the formulation of risk sensitive control developed by Whittle (Whittle 1990) and H_{∞} control. This is specified in (Glover & Doyle 1988). We consider here the system described by equations (1 – 3). However, we now change our assumptions so that w is white noise with covariance function δ(t)I, the identity matrix multiplied by a delta function. Define the cost function

C = ∫_{t_{i}}^{t_{f}} z(t)′z(t) dt + x(t_{f})′F (t_{f})x(t_{f})

where x(t_{i}) is normally distributed with mean x̂_{0} and covariance matrix V, and F (t) > 0. Let

L_{γ} = 2γ^{2} log(E_{μ}(exp(γ^{2}C/2)))

where in this case μ(t, y(t)) is a policy, and E_{μ} indicates the expectation when the input is u(t) = μ(t, y(t)). The risk sensitive control problem is

min_{μ∈M} L_{γ}

where M is the space of all policy functions μ. Glover and Doyle (Glover & Doyle 1988) show that this is equivalent to an H_{∞} problem. However, in this case, a sufficient statistic for the initial conditions are the mean and variance of the initial state. If the system has been running previous to the implementation of a risk sensitive controller, these can be provided by a Kalman filter.

The solution to the risk sensitive control problem is given by Whittle (Whittle 1990):

Theorem 6 If there exists an X_{∞} ≥ 0 satisfying

−Ẋ_{∞} = A′X_{∞} + X_{∞}A − X_{∞}(B′_{2}B_{2} − γ^{−2}B_{1}B′_{1})X_{∞} + C′_{1}C_{1} X_{∞}(t_{f}) = F (t_{f})

and Y_{∞} satisfying

Ẏ_{∞} = AY_{∞} + Y_{∞}A′ − Y_{∞}(C′_{2}C_{2} − γ^{−2}C′_{1}C_{1})Y_{∞} + B_{1}B′_{1} Y_{∞}(t_{i}) = V

such that Y_{∞}(t)^{−1} − γ^{−2}X_{∞}(t) > 0, then let

˙x̂ = Ax̂ + B_{2}u + Y_{∞}C′_{2}(y − C_{2}x̂) + γ^{−2}Y_{∞}C′_{1}C_{1}x̂ x̂(t_{i}) = x̂_{0}

and

x̌ = (I − γ^{−2}Y_{∞}X_{∞})^{−1}x̂

Then the optimal risk sensitive feedback control law is given by

u = −B′_{2}X_{∞}x̌

This has exactly the form of an H_{∞} controller (see, for example, Basar and Bernhard (Basar & Bernhard 1991, pp. 124-126)) with unknown weighted initial state. However, it is important to note that the assumptions are very different, and that w is white noise.

In the moving horizon case, we only need u(t) at t = t_{i}. At this time, x̂(t_{i}) and Y_{∞}(t_{i}) are the mean and variance of the state. Note that the moving horizon objective at time t_{i} is the expectation of Ł_{γ} over the current state variability and future disturbances. The information required, that is the mean and variance of the current state, is precisely that provided by a Kalman filter, as follows.

Theorem 7 Suppose x(0) has mean x̂_{0} and covariance matrix V. Let Y_{2} > 0 be the solution to

Ẏ_{2} = AY_{2} + Y_{2}A′ − Y_{2}(C′_{2}C_{2})Y_{2} + B_{1}B′_{1} Y_{2}(t_{i}) = V

and let x̂ satisfy

˙x̂ = Ax̂ + B_{2}u + Y_{2}C′_{2}(y − C_{2}x̂) x̂(t_{i}) = x̂_{0}

then x̂(t) is the mean of x and Y_{2}(t) is the variance of x at time t.

Hence we propose a moving horizon controller of the form

Ẏ_{2} = AY_{2} + Y_{2}A′ − Y_{2}(C′_{2}C_{2})Y_{2} + B_{1}B′_{1} Y_{2}(t_{i}) = V
˙x̂ = Ax̂ + B_{2}u + Y_{2}C′_{2}(y − C_{2}x̂) x̂(t_{i}) = x̂_{0}

− \frac{∂X_{∞}(τ, σ)}{∂τ} = X_{∞}(τ, σ)A(τ) + A(τ)′X_{∞}(τ, σ) −
X_{∞}(τ, σ)(B_{2}(τ)B_{2}(τ)′ − γ^{−2}B_{1}(τ)B_{1}(τ)′)X_{∞}(τ, σ) + C(τ)′C(τ)
X_{∞}(t, t) = F (t) for all t

Then the controller is given by

u(t) = −B_{2}(t)′X_{∞}(t, t + T)(I − γ^{−2}Y_{2}(t)X_{∞}(t, t + T))^{−1}x̂(t)

Let Z_{2∞}(t) = (I − γ^{−2}Y_{2}(t)X_{∞}(t, t + T))^{−1}Y_{2}(t) Then we can rewrite equations (5.1–5.1) as

˙x̌ = (A − (B_{2}B′_{2} − γ^{−2}B_{1}B′_{1})X_{∞})x̌ − Z_{2∞}(C′_{2}C_{2} + γ^{−2}R)x̌ + Z_{2∞}C′_{2}y
u(t) = −B′_{2}X_{∞}(t, t + T)x̌(t)

where

R(t) = C_{1}(t)′C_{1}(t) − \frac{∂X_{∞}(t, σ)}{∂σ}|_{σ=t+T}

Theorem 8 If X_{∞} and Z_{2∞} satisfy

α_{1}I ≤ X_{∞}(t, t + T) ≤ α_{2}I
α_{1}I ≤ Z_{2∞}(t) ≤ α_{2}I

for fixed α_{1}, α_{2} for all t > 0, then the above controller is globally exponentially stable.

Proof Let e = x − x̌. Then

\frac{d}{dt} ( \begin{matrix}x \\ e \end{matrix} ) = F ( \begin{matrix}x \\ e \end{matrix} )

where

F = [ \begin{matrix}A − B_{2}B′_{2}X_{∞} & B_{2}B′_{2}X_{∞} \\ −γ^{−2}B_{1}B′_{1}X_{∞} + γ^{−2}Z_{2∞}R & A − Z_{2∞}(C′_{2}C_{2} + γ^{−2}R) + γ^{−2}B_{1}B′_{1}X_{∞} \end{matrix} ]

Let

Ω = [ \begin{matrix}X_{∞} & 0 \\ 0 & γ^{2}Z_{2∞}^{−1} \end{matrix} ]

Let G = F′Ω + ΩF + Ω̇. Then

\frac{d}{dt} (( \begin{matrix}x \\ e \end{matrix} )′ Ω ( \begin{matrix}x \\ e \end{matrix} )) = ( \begin{matrix}x \\ e \end{matrix} )′ G ( \begin{matrix}x \\ e \end{matrix} )

Using

\frac{dZ_{2∞}^{−1}}{dt} = −Z_{2∞}^{−1}A − A′Z_{2∞}^{−1} + γ^{−2}R + C′_{2}C_{2} − Y_{2}^{−1}B_{1}B′_{1}Y_{2}^{−1} − γ^{−2}X_{∞}(B_{2}B′_{2} − γ^{−2}B_{1}B′_{1})X_{∞}

some algebra reveals

G = [ \begin{matrix}−X_{∞}B_{2}B′_{2}X_{∞} − γ^{−2}X_{∞}B_{1}B′_{1}X_{∞} − R & X_{∞}B_{2}B′_{2}X_{∞} − X_{∞}B_{1}B′_{1}Z_{2∞}^{−1} + R \\ X_{∞}B_{2}B′_{2}X_{∞} − Z_{2∞}^{−1}B_{1}B′_{1}X_{∞} + R & \begin{matrix}−X_{∞}B_{2}B′_{2}X_{∞} − γ^{2}Z_{2∞}^{−1}B_{1}B′_{1}Z_{2∞}^{−1} \\ −γ^{−2}(C′_{2}C_{2} + γ^{−2}R) \end{matrix} \end{matrix} ]

hence

\frac{d}{dt} [( \begin{matrix}x \\ e \end{matrix} )′ Ω ( \begin{matrix}x \\ e \end{matrix} )] = − ( \begin{matrix}x \\ e \end{matrix} )′ Ĝ ( \begin{matrix}x \\ e \end{matrix} ) − |B′_{2}X_{∞}x̌|^{2} − γ^{2}|C_{2}e|^{2} − x̌′Rx̌

where

Ĝ = −γ^{−2} [ \begin{matrix}X_{∞} \\ γ^{2}Z_{2∞}^{−1} \end{matrix} ] B_{1}B′_{1} [ \begin{matrix}X_{∞} \\ γ^{2}Z_{2∞}^{−1} \end{matrix} ]′

We know that x̌ = 0 if and only if x = e, and in this case

− ( \begin{matrix}x \\ e \end{matrix} )′ Ĝ ( \begin{matrix}x \\ e \end{matrix} ) = −γ^{2}|B′_{1}Y_{2}^{−1}x|^{2} < δ|x|^{2} for some δ > 0

since by assumption B_{1}B′_{1} > εI for some ε > 0. Using lemma 3, if F satisfies equation (7), then R > 0, since by assumption C′_{1}C_{1} > 0. □

If we have a bound for X_{∞}, then in order to bound Z_{2∞} we need only bound Y_{2}. Bounds for Y_{2} are given by Kalman (Kalman 1960). Therefore stability is again conditional on the existence of a bound for X_{∞}, of which we are assured in the case when F = ∞.

6 Conclusions

With the terminal constraint x(t + T) = 0, the moving horizon state feedback problem is known to be stable and to result in a global norm bound for the closed loop system, under the assumptions of Theorem 5. Several interesting problems remain. It is possible within the current formulation to use a time varying γ, which might allow both for attempts to improve performance if the system becomes easier to control with time, and to reduce performance demands if the system becomes more difficult to control.

It is also feasible to extend the above approach for the observation feedback case so that the horizon becomes [t − T_{1}, t + T_{2}]. In this case, we might expect a more conservative controller.

One motivation for this control methodology has been that it is possible to implement it knowing only details of the system up to time t + T ahead. In this formulation that knowledge is discreet; we assume that up to time t+T we know exactly the system matrices, after that we know nothing about them. This seems unnatural, since we might hope that an online identification process would give us a description of the future system with gradually increasing uncertainty in time. The linking of the present controller with a mathematical model for such uncertainty might produce a more realistic control system.

References

Anderson, B. D. O. & Moore, J. B. (1989), Optimal Control - Linear Quadratic Methods, Prentice Hall.

Basar, T. & Bernhard, P. (1991), H_{∞} Optimal Control and Related Minimax Design Problems. A Dynamic Game Approach, Systems and Control: Foundations and Applications, Birkhauser.

Basar, T. & Olsder, G. J. (1982), Dynamic Noncooperative Game Theory, Mathematics in Science and Engineering, Academic Press.

Bucy, R. S. (1967), ‘Global theory of the riccati equation’, Journal of Computer and System Sciences 1, 349–361.

Chen, C. C. & Shaw, L. (1982), ‘On receding horizon feedback control’, Automatica 18(3), 349–352.

Doyle, J. C., Glover, K., Khargonekar, P. P. & Francis, B. A. (1989), ‘State-space solutions to standard H_{2} and H_{∞} control problems’, IEEE Transactions on Automatic Control 34(8), 831–847.

Glover, K. & Doyle, J. C. (1988), ‘State-space formulae for all stabilizing controllers that satisfy an H_{∞}-norm bound and relations to risk sensitivity’, Systems and Control Letters 11, 167–172.

Kalman, R. E. (1960), ‘Contributions to the theory of optimal control’, Boletin de la Sociedad Matematica Mexicana 5(1), 102–119.

Khargonekar, P. P., Nagpal, K. M. & Poolla, K. R. (1991), ‘H_{∞} control with transients’, SIAM Journal on Control and Optimization 29(6), 1373–1393.

Kleinman, D. L. (1970), ‘An easy way to stabilize a linear constant system’, IEEE Transactions on Automatic Control p. 692.

Kwon, W. H., Bruckstein, A. M. & Kailath, T. (1983), ‘Stabilizing state-feedback design via the moving horizon method’, International Journal of Control 37(3), 631–643.

Kwon, W. H. & Pearson, A. E. (1977), ‘A modified quadratic cost problem and feedback stabilization of a linear system’, IEEE Transactions on Automatic Control 22(5), 838– 842.

Limebeer, D. J., Anderson, B. D. O., Khargonekar, P. P. & Green, M. (1992), ‘A game theoretic approach to H_{∞} control for time varying systems’, SIAM Journal on Control and Optimization 30(2), 262–283.

Mayne, D. Q. & Michalska, H. (1990), ‘Receding horizon control of nonlinear systems’, IEEE Transactions on Automatic Control 35(7), 814–824.

Ran, A. C. M. & Vreugdenhil, R. (1988), ‘Existence and comparison theorems for algebraic riccati equations for continuous and discrete time systems’, Linear Algebra and its applications 99, 63–83.

Ravi, R., Nagpal, K. M. & Khargonekar, P. P. (1991), ‘H_{∞} control of linear time varying systems: A state space approach’, SIAM Journal on Control and Optimization 29(6), 1394–1413.

Reid, W. T. (1970), Riccati Differential Equations, Academic Press.

Tadmor, G. (1992), ‘Receding horizon revisited: An easy way to robustly stabilize an ltv system’, Systems and Control Letters 18, 285–294.

Tadmor, G. (1993), ‘The standard H_{∞} problem and the maximum principle: the general linear case’, SIAM Journal on Control and Optimization 31(4), 813–846.

Uchida, K. & Fujita, M. (1992), ‘Finite horizon H_{∞} control problems with terminal penalties’, IEEE Transactions on Automatic Control 37(11), 1762–1767.

Verghese, G., Friedlander, B. & Kailath, T. (1980), ‘Scattering theory and linear least squares estimation, part iii: The estimates’, IEEE Transactions on Automatic Control 25(4), 794–802.

Whittle, P. (1990), Risk-sensitive optimal control, Wiley Interscience series in Systems and Optimization, Wiley.