RIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B.P. 5 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

ON THE DECOMPOSITION
OF STOCHASTIC CONTROL
PROBLEMS

Albert

A. BENVENISTE, P. BERNHARD, G.COHEN

Rapport de Recherche N° 187

Août 1976
ON THE DECOMPOSITION OF STOCHASTIC CONTROL PROBLEMS

A. Benveniste*, P. Bernhard**, G. Cohen***

Résumé :

Dans l'étude de la commande des systèmes interconnectés (ou coordination) la question principale est la gestion des interactions. Pour les systèmes stochastiques, cela conduit au difficile problème de construire un modèle local des interactions qui soit satisfaisant. Ce point de vue permet une grande simplification dans l'approche du problème de Chong. La conclusion est que la modélisation actuellement utilisée pour l'aléatoire ne permet pas une étude satisfaisante de la commande stochastique des systèmes interconnectés.

Abstract :

In studying the control of interconnected systems (coordination), the main issue is the manage-
ment of the interactions. For stochastic systems, this raises a difficult question of constructing
a local model of the stochastic process of interaction, realistic enough but leading to reasonably
sized local problems. This view point leads to a greatly simplified solution of Chong's problem.
The conclusion is that known representations of stochastic processes are not well suited to deal
with the problem considered.

This paper was presented as an invited lecture at the 1st IFAC Symposium on Large Scale
Systems (Udine, June 1976).

<footnote>* IRIA-LABORIA - Rocquencourt - 78150 Le Chesnay.</footnote>

<footnote>** Centre d'Automatique de l'ENSMP - 77305 Fontainebleau et IRIA-LABORIA.</footnote>

<footnote>*** Centre d'Automatique de l'ENSMP - 77305 - Fontainebleau.</footnote>
## Introduction.

This paper proposes an analysis of what we claim are the main issues underlying the difficult problem of stochastic decentralized control, or rather stochastic optimal control of interconnected systems.

However, many different views on this problem can be found in the literature, with widely varying assumptions and objectives. We must therefore first specify what kind of questions we want to tackle. To do so, we shall first summarize some of the essential features of the standard, deterministic theory (22) (23), and then indicate which of these features we want to preserve, and what is added by the stochastic nature of the problem.

## Deterministic decomposition and coordination.

The essential features of the deterministic theory are as follows :

- The system is decomposed, i.e., represented as made of smaller interconnected subsystems.

- This creates new variables : *the interaction variables* which take into account, via a *coupling constraint* the fact that the overall system is not a collection of independent subsystems. These variables can be expressed in terms of the original variables. This expression we shall call their *global model*.

- The solution of the overall, or global, problem is reached iteratively via the solution of successive local optimization problems, precisely defined and updated by the coordinator. In the limit, the concatenation of the local optimal control vectors is the globally optimal control sought. (Some add a direct action by the coordinator).

- The local controllers are not allowed to use the global, model of the interactions. Hence, one must define an interaction management policy characterized by a local model of the interactions, that can be used to find a locally optimal control.

This last step which is closely related to Geoffrion's *problem manipulation* (15) is the crucial item in understanding and classifying the various methods, and corresponds to Mesarovic's coordination principles (23). At least
four are known at the present time for deterministic problems :

i) feasible methods (6) (akin to resource allocation, as appears in (47) also called "model coordination" (24) (28), close to parametric optimization (14))

ii) shadow prices (dual from the previous one, one, see (24) also called "goal coordination". It is Mesarovic's "decoupling mode" or ("Interaction balance principle") (22), (23), and the best known method, (3) (20))

iii) Mesarovic's prediction mode (22), (23), widely developed by our research team (9), (10) (11) used with convexifying terms in these references and in Pearson's "pseudo model coordination" (24) (this reference contains a serious mistake).

iv) Cohen's min-max decoupling mode (12).

The aim of the total scheme is clearly to make the subproblems smaller, in some sense, than the global one, in relation to the smaller size of the subsystems. However, one is not able to give an axiomatic definition of what is sought.

Therefore, the justification for these methods must come from success in areas where the classical ones have failed. There may be at least three reasons for this failure :

- because of reliability and/or human considerations, the users a priori discard a centralized implementation of the decision making process. This happens primarily in the global control of large plants or in management problems.

- because the solution of the global problem involves computations of excessive size. Although a decomposed solution often involves more computations altogether, they can be performed iteratively on a smaller machine, and better controlled. (This makes the computation process itself more reliable). If the nature of the problem considered is such that it must be solved via dynamic programming, then decomposition may lead to dramatic reductions in the total amount of computation, (see (13)), and actually allow us to overcome the "curse of dimensionality".
- because the interactions, in a physically decomposed system, are not well accounted for by the available model. Quite often, each subsystem is well modelized while its interactions with the others are not as well identified. We are currently investigating ways of explicitely taking this situation into account. But event without doing so, decentralized control schemes may be much less sensitive to this kind of modelling error.

## Stochastic control of interconnected system.

We want to preserve the global, and somewhat vague, aim we have just outlined.

Therefore, we are not interested in problems where the only decentralized feature is just information, and where all controllers work with the global model. (Although we regard highly the remarkable work which has been done in that direction, under the name of cooperative games, team theory, decentralized control, and so on. (1) (2) (16) (18) (19) (21) (26)). Taking into account the imperfect knowledge of the global model of interaction is particularly relevant in that context.

Here more than ever, one is unable to give a precise axiomatic definition of the problem considered, the justification would come a posteriori from the efficiency and the usefulness of the algorithms that would be produced. An attempt at an axiomatization would be to assume a decentralization of the a priori information on the structure of the system. We shall see that this does not suffice. In essence, the optimal solution with this type of assumption, and no other restriction, consists in each controller attempting to identify the missing information. We shall show that this leads to diverging dimensions !.

## Outline of the paper.

It seems that the most advanced work dealing with the control of interconnected stochastic subsystems is in Chong's thesis (7). We shall hereafter give an account of his algorithm. It will appear that focussing on the nature of the interactions local model leads to a greatly simplified presentation, which points out an implementation different from the original one, with a substantial decrease in the computational load.
We shall emphasize that the problem solved by this algorithm is not the one stated to start with, and from this point, we shall analyze what must necessarily be sacrificed in terms of optimality to obtain a decentralized implementation and/or computation. This will lead to various levels of optimality, related to the aim sought according to the above remarks.

Finally, we shall show how these levels are related to the local model of the interactions, attempt to discuss some of the more natural possibilities, and see what kind of algorithm they lead to. Our conclusion will be that the probabilistic approach to the decomposition of control problems in the presence of uncertainties seems to have little hope to lead to mathematically grounded viable algorithm at least in the present state of the theory of representation of stochastic processes. Of course this does not preclude the possibility of finding efficient heuristics. One possible alternative would be to use ideas borrowed from worst case design, as was already done for deterministic problems, see (12). A preliminary account of Cohen's work in that direction can be found in the internal report E/47 of Centre d'Automatique, ENSMP. A more complete work is to appear in the open literature.

## CHONG'S PROBLEM REVISITED.

We shall give the statement of the problem considered by Chong in (7), or "original problem", and then a careful statement of the problem actually solved, which we call the "$\mathcal{B}$-problem", ("$\mathcal{B}$" means "in decentralized form"). Also, we shall clearly indicate, what the local model of interaction and the coupling constraint are.

### Statement of the original problem.

The problem considered here is the same as Chong's, but without his restrictions on the structure of $B$, $S$, $Q$ and $R$, that he took block-diagonal. However, we keep decentralized measurement and noises. Let us consider the following $N$ interconnected linear dynamical systems :
$$
\begin{align*}
(1) \qquad \mathrm{d}x_t^i &= A_{ii} x_t^i \mathrm{d}t + B_{ii} u_t^i \mathrm{d}t + \sum_{j \neq i} \{A_{ij} x_t^i \mathrm{d}t + B_{ij} u_t^i \mathrm{d}t\} + \mathrm{d}\mu_t^i \\
\mathrm{d}y_t^i &= C_{ii} x_t^i \mathrm{d}t + \mathrm{d}v_t^i
\end{align*}
$$

where $x^i, u^i, y^i$ are respectively the local state, the local control, and
the local observation. The processes $\mu^i, \nu^i$ ($i, j = 1, ..., N$) are inde-
pendent white noises with covariance matrices $\Sigma_{\mu^i}$ and $\Sigma_{\nu^i}$ respectively, as-
sumed positive definite for simplicity. We write $x$ for the concatenation of
$x^i$ ($x' = (x'_1, ..., x'_N)$), $A$ for the block-matrix with elements $A_{ij}$, and so on.
We define :

$$
(2) \quad \left\{
\begin{array}{l}
A^d = A; \quad A^d_{ij} = A_{ij} \cdot \delta_{ij} \quad (\delta_{ij} \text{ Kronecker symbol}), \\
\\
A^z = A - A^d;
\end{array}
\right.
$$

Thus $A^d$ and $A^z$ are the block-diagonal and zero-diagonal part of $A$. The initial conditions of (1) are

$$
(3) \quad \bar{x}_o = E(x_o) ; \quad \Sigma_o = \operatorname{cov}(x_o) ;
$$

we do not assume that Σ₀ is block-diagonal. The cost functional to be minimized
under the dynamical constraint (1) is, in global notation :

$$
(4) \quad J(x,u) = E \left\{ x'_{T} S x_{T} + \int_{0}^{T} \left( x'_{t} Q x_{t} + u'_{t} R u_{t} \right) dt \right\},
$$

where Q, S, R are (not necessarily block-diagonal) symmetric positive matrices.

Let us define the _information pattern_ for this problem. We introduce two
levels of control : _the coordination level_, and _the local level_ made up of N
decision-makers. Following Chong (⁷), we assume that

The coordination level has

(C,i) complete knowledge of dynamics (A, B, C), cost (Q,S,R) and statistics
($\Sigma_{\mu}$, $\Sigma_{\nu}$, $\bar{x}_{o}$, $\Sigma_{o}$);

(C,ii) periodic knowledge of observations : let L > 0 be such that T=pL, p ∈ N;
let $\gamma_t = \sigma\{y_s ; s \le t\}$ be the whole information available at time t; bet-
ween kL and (k+1)L, the coordination level knows $\gamma_{kL}$.
The i-th local controller has

(L,i) decentralized knowledge of dynamics ($A_{ii}$, $B_{ii}$, $C_{ii}$), cost ($Q_{ii}$, $S_{ii}$, $R_{ii}$) and statistics ($\Sigma_{\mu}^{i}$, $\Sigma_{\nu}^{i}$, $\Sigma_{\bar{x}}^{i}$, $\Sigma_{\bar{\omega}}^{ii}$);

(L,ii) decentralized knowledge of observations ; at time t, he knows
$y_t^i = \sigma\{y_s^i ; s \le t\}$;

(L,iii) decentralized knowledge of a priori information transmitted by the coordination level : between kL and (k+1)L, the i-th local level knows the a priori law $\mathcal{L}^i(\omega/k)$ of $x^i(\omega)$ knowing $\mathcal{Y}_{kL}$.

Assumption (L,iii) is not explicitely stated by Chong, but is indeed
used in his calculations. Thus, we have a <u>non classical information pattern</u>,
and the problem enjoys none of the good properties of the classical LQG-problem :
separation of estimation and control, and existence of a Markovian, linear feed-
back. <u>The objective is to achieve a heuristically reasonable method for solving</u>
<u>this problem, forcing the linear-Markovian character of the solution.</u>

Statement of the $\mathcal{B}$-problem.

The $\mathcal{B}$-problem is hoped to be "nearly equivalent" to the original problem,
and is in decentralizable form. Finally, we shall use the resulting optimal con-
trol law for the original problem.

Because of condition (C,ii), we shall assume that our system is governed
between kL and (k+1)L by the regular conditional version $P^{\omega/k}$ of the probability
law P knowing the trajectory {$y(\omega), 0 \le t \le kL$}. Between kL and (k+1)L, the i-th
local controller holds $v_t^i \triangleq \sum_{i \neq j} A_{ij} x_t^j + B_{ij} u_t^j$ to be an interaction.

The i-th controller is assumed to have only first order a priori infor-
mation about $v_t^i$ and he holds $v_t^i$ to be deterministic (.) (with respect to condi-
tional law $P^{\omega/k}$, that is $\mathcal{Y}_{kL}$-measurable with respect to P). The interaction
time history $v_t^i(.)$ is predicted by the coordination level and is viewed as a
coordination parameter given by the upper level for the k-th coordination period.
What we have just defined is the choice of the local interaction model in the
sense of §.1.
It would be desirable to achieve at the same time

- local minimization of the cost functionals, with the predicted $v^i(.)$'s;

$$ (5) \quad \left\{ \begin{array}{l} - v_t^i = \sum_{j \neq i} A_{ij} x_j^i + B_{ij} \quad \text{with the predicted } v^i(.) \text{'s and } (x^j, u^j) \text{ being} \\ \text{the local optimal state and control of the j-th local controller.} \end{array} \right. $$

Unfortunately, during the coordination period (kL, (k+1)L), the predicted interaction $v^i(.)$ is deterministic, whereas the $(x^j, u^j)'$s are not. So instead of (5), we shall achieve the following:

- local minimization of the cost functionals, with the predicted $v^i(.)$'s;

$$ (6) \quad \left\{ \begin{array}{l} - v_t^i = E\left( \sum_{j \neq i} A_{ij} x_t^j + B_{ij} u_t^j \mid \mathcal{Y}_{kL} \right) \quad \text{or equivalently} \\ v_t^i(\omega/k) = E^{\omega/k} \left( \sum_{j \neq i} A_{ij} x_t^j + B_{ij} u_t^j \right). \end{array} \right. $$

What are the admissible controls for the A-problem? In view of conditions (L,ii) and (C,ii) we shall require:

$$ (7) \quad u_t^i \in \sigma(\mathcal{Y}_t^i ; \mathcal{Y}_{kL}^i) \quad \text{between kL and (k+1)L.} $$

Now we can state precisely the A-problem:

$$ (D,i) \quad \text{minimize} \quad E\{\xi_T^i S \xi_T^i + \int_0^T \xi_t^i Q \xi_t^i + u_t^i R u_t^i dt\}, $$

the dynamical constraints and admissible controls being between kL and (k+1)L with conditional probability law $P^{\omega/k}$:

$$ (D,ii) \quad d\xi_t^i = A^d \xi_t^i dt + B^d u_t^i + v_t^i dt + d\mu_t^i $$

$$ E^{\omega/k}(\xi_{kL}^i) = \bar{x}_{kL}^{i}(\omega/k) $$

$$ \operatorname{cov}(\xi_{kL}^i) = \Sigma_{kL}^d $$

$$ dy_t^i = C \xi_t^i dt + dv_t^i $$

(D,iii) admissible controls: $v_t$ deterministic, $u_t^i$, $\mathcal{Y}_t^i$-measurable;

$$ (D,iv) \quad \text{coupling constraint:} \quad v_t = E^{\omega/k}(A^z \xi_t + B^z u_t). $$
(See (2) for the notations $A^d, A^z, \Sigma^d$; (D,iii) is in fact the same as (7)).

**Remark** : we write $\xi$ in order to distinguish between the fictive decoupled state $\xi$ of the $\mathcal{B}$-problem, and the real state $x$ of the original problem.

**Basic remark** : the difference between the $\mathcal{B}$-problem and the original problem lies in the fact that the actual coupling constraint is not taken into account in the computation of the control, for the following reason : (D,iv) is only an estimate of the effective coupling constraint.

**Solution of the $\mathcal{B}$-problem.**

We shall regard the task of the coordination level as a discrete time optimization problem, the control instants being the sequence $L, 2L, \dots, kL, \dots, T$. We shall give for this problem the Open-Loop Feedback Optimal (OLFO) control, and the optimal control. We shall first give the optimal solution of the $\mathcal{B}$-problem when there is only open-loop coordination i.e. $L = T$.

In the sequel we shall need the following matrix Riccati equations :

- Riccati equation related to the original control problem :

$$ (8) \qquad \frac{d}{dt} \Pi + \Pi A + A' \Pi - \Pi B R^{-1} B' \Pi + Q = 0, \quad \Pi_T = S $$

- error covariance matrix of the original filtering problem :

$$ (9) \qquad \frac{d}{dt} \Sigma - A\Sigma - \Sigma A' + \Sigma C' \Sigma^{-1} C\Sigma - \Sigma_{\mu} = 0, \quad \Sigma(0) = \Sigma_0 $$

- Two Riccati equations related to the decentralized control problems :

$$ (10) \qquad \left\{ \begin{array}{l} \text{OLFO-control : } \frac{d}{dt} \Pi^{\text{OLFO}} + \Pi^{\text{OLFO}} A + A^{\text{d}'} \Pi^{\text{OLFO}} - \Pi^{\text{OLFO}} B (R')^{-1} B' \Pi^{\text{OLFO}} + Q = 0 \\[1em] \Pi^{\text{OLFO}} (T) = S. \end{array} \right. $$

optimal control, between $kL$ and $(k+1)L$

$$ (11) \qquad \left\{ \begin{array}{l} \frac{d}{dt} \Pi^{\text{OPT}} + \Pi^{\text{OPT}} A + A^{\text{d}'} \Pi^{\text{OPT}} - \Pi^{\text{OPT}} B (R')^{-1} B' \Pi^{\text{OPT}} + Q = 0 \\[1em] \Pi^{\text{OPT}}((k+1)L) = \Pi(k+1)L, \quad \text{where } \Pi \text{ is given by (8).} \end{array} \right. $$
- error covariance matrix of the local problem between kL and (k+1)L

$$ (12) \qquad \left\{ \begin{array}{l} \displaystyle \frac{d}{dt} \Sigma^{\text{LOC}} - A^d \Sigma^{\text{LOC}} - \Sigma^{\text{LOC}}_{A'} + \Sigma^{\text{LOC}} C' \Sigma^{-1} C \Sigma^{\text{LOC}} - \Sigma_{\mu} = 0 \\[1em] \Sigma^{\text{LOC}}(kL) = \Sigma^d(kL), \text{ where } \Sigma \text{ is given by (9).} \end{array} \right. $$

**Solution of the $\mathcal{B}$-problem when $L = T$: open-loop coordination.**

Let $k^{\text{LOC}} = -R^{-1} B' \Pi^{\text{OLFO}}$, with $\Pi^{\text{OLFO}}$ given by (10);

Let $\bar{\xi}_t = E(\xi_t) = E(x_t)$, and $\hat{\xi}_t^i = E(\xi_t^i | \mathcal{Y}_t^i)$;

Let $\bar{u}_t^* = -R^{-1} B' \Pi_t \bar{\xi}_t^*$ be the optimal control history of the deterministic problem ($\mu = \nu = 0$) related to the original problem. We have the following result:

**Theorem 1:** the optimal control of the $\mathcal{B}$-problem is given by

$$ \bar{u}_t^* = K_t^{\text{LOC}} (\hat{\xi}_t - \bar{\xi}_t) + \bar{u}_t^* $$

**Remark:** $\bar{u}^*$ is made of two parts: an open loop part $\bar{u}^*$ computed by the coordination level, and a decentralized closed-loop part.

**Proof:** Let $\tilde{\xi}_t = \xi_t - \bar{\xi}_t$, $\bar{u}_t = E(u_t)$, $\tilde{u}_t = u_t - \bar{u}_t$.

We have

$$ (13) \qquad J(\xi, u) = J(\bar{\xi}, \bar{u}) + J(\tilde{\xi}, \tilde{u}) = \bar{J} + \tilde{J} $$

because the cross-terms in $(\bar{\xi}, \tilde{\xi})$... have zero expectation. Finally, it is straight forward to see what we have indeed two independent problems:

i) minimize $\bar{J}$: this is the deterministic problem, which has optimal control $\bar{u}^*$;

ii) minimize $\tilde{J}$: this is a $\mathcal{B}$-problem with zero-mean, thus with $v_t = 0$ in view of (D,iv).

Conditions (D,ii and iii) implies that the local dynamics are independent random processes; thus the cross terms in $(\tilde{\xi}_1, \tilde{\xi}_j)$... in the cost function-al $\tilde{J}$ turn out to be zero. This allows us to use $Q^d, S^d, R^d$ instead of $Q, S, R$. The optimal control of this problem is then exactly
$$ \tilde{u}_t^* = K_t^{\text{LOC}} \tilde{\xi}_t = K_t^{\text{LOC}} (\hat{\xi}_t - \bar{\xi}_t). $$

Finally, by definition of $\tilde{u}$, we have

$$ u_t^* = \bar{u}_t^* + \tilde{u}_t^* $$

<figure><img src="image_1.png" /></figure>

**Remark :** the separation of $J$ into $\bar{J} + \tilde{J}$ in (13) is that of the $\mathcal{B}$-problem into a deterministic coupled part which is solved at the global level, and a stochastic uncoupled one which is solved at the local level.

### The OLFO solution of the $\mathcal{B}$-problem.

The OLFO philosophy is here the following : at coordination time $kL$, solve the $\mathcal{B}$-problem between $kL$ and $T$, with the conditional law $P^{\omega/k}$ (in place of $P$), the decentralized a priori covariances $\Sigma_{kL}^d$ ($\Sigma$ given by (9)), while assuming no future coordination. The solution is thus given by theorem 1. This control is then used between $kL$ and $(k+1)L$. what gives $P^{\omega/k+1}$ and $\Sigma_{(k+1)L}^d$, and so on.

**Theorem 2 :** Let $u_{k,t}^*(\omega)$ be the optimal control of the $\mathcal{B}$-problem with open-loop coordination between $kL$ and $T$ (see previous §, with conditional law $P^{\omega/k}$ and a priori covariance matrix $\Sigma_{kL}^d$. The OLFO control is then :

$$ u_t^*(\omega) = u_{k,t}^*(\omega) \quad \text{for} \quad kL \le t < (k+1)L. $$

### The optimal solution of the $\mathcal{B}$-problem.

Let $\nu^k$ be the optimal return function related to the discrete time optimization problem of the coordination level :

$$ (14) \qquad \nu^k(\omega/k) = \inf_{u,v,\xi} \mathbb{E}^{\omega/k} \left\{ \xi_T' Q \xi_T + \int_{kL}^{T} \xi_t' Q \xi_t + u_t' R u_t \, dt \right\} $$

with dynamical constraints and admissible controls defined by (D,ii, iii, iv). $\nu^k$ is a $\mathcal{Y}_{kL}$-measurable random variable which satisfies the stochastic dynamic programming equation :
$$
(15) \quad \left\{
\begin{aligned}
\gamma^k(\omega/k) &= \inf_{u,v,\xi} E^{\omega/k}(\gamma^{k+1} + \int_{kL}^{(k+1)L} (\xi_t' Q \xi_t + u_t' R u_t) \, dt) \\
\gamma^P(\omega) &= \xi_T'(\omega) S \xi_T(\omega) \quad \text{where } T = pL
\end{aligned}
\right.
$$

The fundamental result is the following :

**Theorem 3 :** *We have*

$$
\gamma^k(\omega/k) = E^{\omega/k}(\xi'_{kL} \Pi_{kL} \xi_{kL}) + w^k, \quad \text{where}
$$

i) $\Pi$ is given by (8);

ii) $w^k$ is a fixed deterministic cost, which only depends on $\Sigma_\mu$ and $\Sigma_\nu$, and thus cannot be minimized.

**Proof** : by backward induction. The result is straight forward for k = p.
Assuming the relation true for k+1, we shall prove it for k. From (15) we
have thus :

$$
(16) \quad \left\{
\begin{aligned}
\gamma^k(\omega/k) &= w^{k+1} + \inf_{u,v,\xi} E^{\omega/k} (\xi'_{(k+1)L} \Pi_{(k+1)L} \xi_{(k+1)L}^\varepsilon) \\
&\quad + \int_{kL}^{(k+1)L} \xi_t' Q \xi_t + u_t' R u_t \, dt = w^{k+1} + \inf_{u,v,\xi} J^k(\xi,u).
\end{aligned}
\right.
$$

with dynamical constraint and admissible controls defined by (D,ii, iii, iv).
In fact, $J^k$ defines exactly a $\mathcal{B}$-problem with open-loop coordination between
$kL$ and $(k+1)L$, with terminal cost $\Pi_{(k+1)L}$.
As in the proof of theorem 1, we
set

$$
(17) \quad J^k(\xi, u) = J^k(\bar{\xi}, \bar{u}) + J^k(\tilde{\xi}, \tilde{u}) = \bar{J}^k + \tilde{J}^k
$$

The optimal cost for $\bar{J}^k$ is just

$$
\bar{\gamma}^k = \bar{\xi}'_{kL} \Pi_{kL} \bar{\xi}_{kL} \quad \text{where} \quad \bar{\xi}_{kL}(\omega) = E^{\omega/k}(\xi_{kL}) .
$$

We let the reader check that the optimal cost $\tilde{\gamma}^k$ for the zero-mean problem $\tilde{J}^k$ takes the form :

$$
(18) \quad \tilde{\gamma}^k(\omega/k) = \mathrm{Tr}(\Pi_{kL}^{\mathrm{OPT}} \Sigma_{kL}^d) + \int_{kL}^{(k+1)L} \mathrm{Tr}(\Pi_t^{\mathrm{OPT}} \Sigma_\mu + K_t^{\mathrm{LOC}} R^d K_t^{\mathrm{LOC}} \Sigma_t^{\mathrm{LOC}}) dt,
$$
where $\Pi^{\text{OPT}}$, $K^{\text{LOC}}$, $\Sigma^{\text{LOC}}$ are given in (11), Theorem 1, and (12) respectively. It is thus straight forward to see that $\tilde{\gamma}^k$ is indeed deterministic and cannot be minimized by the upper level. Finally, we have

$$E^{\omega/k}(\xi'_{kL} \Pi_{kL} \xi_k) = \bar{\xi}'_{kL} \Pi_{kL} \bar{\xi}_{kL} + \text{tr}(\Pi_{kL} \Sigma_{kL}^d), \text{ so that}$$
$$w^k = w^{k+1} + \tilde{\gamma}^k - \text{tr}(\Pi_{kL} \Sigma_{kL}^d)$$

■

The following theorem is then obvious :

**Theorem 4** : Let $u_{k,t}^*(\omega)$ be the optimal control law for the $\mathcal{B}$-problem defined between $kL$ and $(k+1)L$ by the dynamics (D,ii, iii, iv) and the cost functional

$$E^{\omega/k}(\xi'_{k+1} L^\Pi (k+1) L^\xi (k+1) L + \int_{kL}^{(k+1)L} (\xi_t' Q \xi_t + u_t' R u_t) dt).$$

The optimal control of the $\mathcal{B}$-problem is then

$$u_t^*(\omega) = u_{k,t}^*(\omega) \quad \text{for} \quad kL \le t < (k+1)L.$$

**Remark** : Let $\Pi^{\text{OLFO}}$ be given by (10). The OLFO control is then between $kL$ and $(k+1)L$ just the optimal control of the open-loop $\mathcal{B}$-problem with dynamics (D,ii, iii, iv) and cost

$$\bar{\xi}'_{k+1} L^\Pi (k+1) L^\bar{\xi} (k+1) L + E^{\omega/k} (\bar{\xi}'_{k+1} L^\Pi (k+1) L^\text{OLFO} \tilde{\xi} (k+1) L + \int_{kL}^{(k+1)L} (\bar{\xi}_t' Q \bar{\xi}_t + u_t' R u_t) dt)$$

where $\bar{\xi}_t = E^{\omega/k}(x_t)$, $\tilde{\xi}_t = \xi_t - \bar{\xi}_t$. So, the calculation of the optimal control of the $\mathcal{B}$-problem requires exactly the same amount of computation as that or the OLFO control, and thus seems more advisable. However there is no basis for telling which will be best when placed back in the original problem.

Finally comes out a way of implementing the optimal control different from that in Chong (7). Roughly speaking, the coordination's task consists in solving the coupled deterministic problem, whose solution he hands down as a prediction to the local level; the local controllers have then to solve zero-mean decoupled problems.
This is much simpler than the method used in (7), leads to simpler control structure and avoids duplication of computation between the two levels. Remark also that any idea of coordination by prices has disappeared from this solution, which is clearly based upon prediction methods.

## ABOUT THE FORMULATION OF STOCHASTIC COORDINATION OF INTERCONNECTED SYSTEMS.

The basis of this discussion will be the Linear-Quadratic-Gaussian (LQG) problem considered previously but most of the following considerations apply to more general situations.

In the deterministic case, the decomposition and coordination approach seeks to find a global optimum by decomposed computations and/or to allow decentralized implementation of the optimal control (as in (13)). In the stochastic case, the latter purpose remains but, considering the former, it is now clearly impossible to achieve the same level of optimality by centralized and decentralized control. Therefore, since sub-optimality is unavoidable, one must first discuss the kind of sub-optimality, or the level of "optimality" associated with each type of non-centralized control.

### Levels of optimality.

Let us call level 0, the optimality level given by the well known solution of the LQG problem with classical information pattern. The main feature is centralization of the decision in one hand, that of a decision maker with perfect memory, and who has access to all the available measurements in real time.

Assume now that there are several decision makers, each in charge of one part of the decomposed control vector, and having access to only one part of the decomposed measurement vector, in real time. Moreover, assume that all the decision-makers have to minimize the same objective functions (cooperative game). Many rules of information exchanges between them can be defined : no exchange at all, exchange of past measurements and/or past controls at fixed times or fixed time-delays and so on. These decentralized information patterns have been studied by Aoki (1), (2), Ho and Chu (16), Sandell and Athans (26),
Kurtaran and Sivan (18), (19), Witsenhausen (30) and so on ...

The main feature of these problems is the fact that none of the decision makers has access to all the measurements in real time, thus, none of them is able to make a decision of level 0. However, unlike in the next levels, all of them know the a-priori information on the system, that is the entries of the matrices A, B and so on... or, more precisely all of them are allowed to do calculations using the whole state vector x which is not decomposed. It is clear that the motivation of such an approach is the decentralized information pattern naturally occurring in many large systems, but it is not the decomposition of computations by defining smaller sub-problems.

However, the non-classical information patterns give rise to difficult problems even in the LQG case. Ho and Chu (16) and Witsenhausen (30) investigated them and the former give conditions for the optimal controls to be linear with respect to the measurements. Bismut (5) gave an example in which the best performance cannot be reached but only arbitrarily well-approximated, Witsenhausen (31) showed a simple case where the optimal control failed to be linear. Kurtaran and Sivan (18), (19) studied separation theorems for non-linear and linear controls. The latter constitute a practically interesting but restricted class of controls.

All these optimality levels whose features are decentralized information patterns (with or without exchanges) but no-decomposition of the state vector will be referred to in the sequel as *levels of type 1* (or 1a, if one restricts the class of admissible controls to linear ones).

The next type of levels to be considered now will be a rather "fuzzy" set of levels because, unlike the previous ones, it will not be possible to define them by some axioms, as we shall discuss hereafter. We are only able to outline what is the new feature that distinguishes these *levels of type 2* from those of type 1. Of course, this new feature is the one which appears in Chong's problem and, previously, in the deterministic theory : namely, it is the decomposition of the state vector, and as a consequence, the presence of new variables, the interactions. Of course, the motivation for this approach is to take into account new constraints : each local controller is now assumed to achieve an amount of computations which is "reasonably" related to the
size of its local part of the state vector. We have also mentioned the fact that no precise global model of the interactions may be available.

Admittedly, these are fuzzy statements but we shall see that they can hardly be made more precise. For example, assuming that the only a-priori informations available to controller i are the entries of the diagonal blocks $A_{ij}$, $B_{ij}$ and so on... of all system and criterion matrices seems a reasonable axiom but does not prevent this controller from doing computations of infinitely increasing size ! This will be shown hereafter.

The difficulties of decentralized information pattern, previously allowed to in connection with levels of type 1 are of course still present in levels of type 2. But enormous new difficulties arise from the decomposition of the state. One must now answer the questions. *How to manage with the interactions?* *How to define local objective functions?* (depending only on the local parts of all variables). Of course, the implicit aim in trying to purpose answers to these questions is to make the local controllers compute controls that give the "best" performance with respect to a given overall performance index, when implemented on-line.

In this task, the lower level of the hierarchy will, in general, be helped by an upper level, the coordinator whose information pattern and intervention must also be defined, but whose task must remain simple with respect to the overall complexity of the problems.

One of the central issues which we shall now discuss is that of the management policy of the interactions or that of "local models of interactions". This is the equivalent notion, in the stochastic case, of the coordination principles of Mesarovic et al. (23). It is also closely related to what Geoffrion (15) calls "problem manipulations : Source of master problems", which are problems more or less related to the original problem and in a form more amenable to decomposition. For example, in Chong's problem, the $\Delta$-problem plays the role of the "master problem" and we shall discuss hereafter the corresponding local model of interactions, among some others that naturally come up to mind.
## Local Models of interactions.

Considering equations (1) of the global system, we have introduced interaction variables $v^i$ which are, by definition :

$$v^i = \sum_{j \neq i} (A_{ij} x_t^j + B_{ij} u_t^j)$$

This is the global model of the interactions. Giving this model to each local controller amounts to canceling the state decomposition and will lead to an optimality level of type 1. From (D,iv), we have seen that the local interaction model actually considered by the lower level between periods kL and (k+1)L is in fact a deterministic model (which is periodically up-dated by the coordinator's informations). The immediate result is that the only coupling between the subproblems appears in the deterministic "equivalent" problem (the noises are set at their mean value) and this deterministic problem is solved on a global basis (Notice that it could have been solved by any known deterministic decomposition-coordination method). The part of the problem which remains really stochastic is in fact completely decoupled for the following two reasons ; because of the local interaction model (D,iv) and also because other coupling stochastic informations (namely $\Sigma^z$ the zero-diagonal part of $\Sigma$ given by (9)) are "set aside" (which amounts to the statement (L,iii)). This last feature is also quite a heuristic one and will be briefly discussed in the last paragraph.

Let us go on trying to propose more elaborate (?) interaction models. Some authors tried to approximate the stochastic processes $v_t^i$ by white noises. Let us mention for example, the works of Chong, Kwong et al (17) who considered weak interactions and represented them as "fake" white noises. Also Singh (27) uses such an approach in a problem of decomposed filtering. In fact, in the context of "weak" interactions, claiming suboptimality properties of any approximated method and proving it by numerical simulations do not give any feeling of the validity of the method for interactions that are not weak enough.

Going one step further, one could propose a model where the local controller is told to consider the interactions as a process having a Gauss Markov representation (which it actually has) that he must find, using any appropriate algorithm. To explain what happens then, we shall propose an adaptive imple-
mentation of that idea as follows. As usual, we consider successive time periods of length L. This time is assumed long enough to allow the local controllers to perform statistical measurements on a stabilized system. During each period, each local controller makes these measurements, while applying the control found to be optimal with the model of the interaction based upon the measurement of the previous period. (The corresponding computations being performed between the two periods). To start the procedure, let a period O(t ∈ [0,L]), be performed with the local model of interaction v = 0.

During the period zero, each local controller will then run a Kalman filter to estimate his local state :

$$
\hat{\xi}_i = A_{ii} \hat{\xi} + B_{ii} \hat{u}_i^O + D_i (y_i - C_i \hat{\xi}_i)
$$

$$
\hat{u}_i^O = K_i \hat{\xi}_i
$$

The concatenation of these equations leads to the following 2n dimensional
system :

$$
\begin{equation}
\begin{gathered}
\begin{pmatrix} dx \\ d\hat{\xi} \end{pmatrix} = \begin{pmatrix} A & -BK \\ DC & A^d - B^d KDC \end{pmatrix} \begin{pmatrix} x \\ \hat{\xi} \end{pmatrix} dt + \begin{pmatrix} d\mu \\ Kdv \end{pmatrix} \\
(19)
\end{gathered}
\end{equation}
$$

$$
y = (C \quad C) \begin{pmatrix} x \\ \xi \end{pmatrix}
$$

The local model remains

$$
d\xi_i = (A_{ii} - B_{ii}K_i) \xi_i dt + v_i dt + d\mu_i
$$

$$
y_i = C_i \xi_i + dv_i
$$

so that the interactions are given by

$$
(20) \qquad v = (A^Z - B^Z K) \begin{pmatrix} x \\ \hat{\xi} \end{pmatrix}
$$

Therefore, the measurements made during the period zero will lead each local
controller to identify $v_i$ as the output of a 2n dimensional system. (Except
occurrence of a non minimality of system (19) (20), which would be a very
particular feature of K, thus of the criterion, which does not happen in
general). Each will then construct a 2n dimensional estimation of the state,
leading to an overall system of dimension (2N+1)n. And so forth for the
following periods. At period k, the dimension would be ($2N^k+N^{k-1}+...+1$)n.
We are far from our objective of reasonably sized local problems !.

This difficulty was well known in stochastic differential game theory.
Several approaches have been proposed to overcome it. Either one arbitrarily
restricts the dimension of the allowed observers (25) (by choosing dimension
zero, we essentially have the fake white noise we have already mentioned. No
method is known at present to choose a "good small size nor to ascertain in
what respect the estimate obtained is satisfactory for our purpose). or one
attempts to look directly for an infinite dimensional observer (29). However,
this last approach leads to exceedingly complicated implicit integrodiffe-
rential equations, whose solution might not exist, since we are not in a nest-
ed information structure (16).

Therefore, this approach fails. It leads to computations of much larger
size than by giving the local controllers the global model of the interactions
an approach we have previously discarded on grounds of excessive size of the
local problems.

The last question in that direction is to know whether the coordinator
can define and update via a simple scheme local observers that the local con-
trollers would run, and that would provide estimates leading to the kind of
optimality. We do not know of an attempt in that direction that would overcome
the main difficulties we analyze in the next part.

SOME CONCLUSIONS AND PERSPECTIVES.

In this brief discussion of some aspects of the control and the coordi-
nation of interconnected systems, we wanted to underline the enormous difficul-
ties arising from the classical formulation of stochastic optimal control.
Many authors, before us, have already analyzed the difficulaties due
to a decentralized information pattern. These difficulties are present in
formulations of what we have called levels of type 1 (or 1a) and also in the
fuzzy set of levels of type 2. However, in the latter case, new important
difficulties arise from the presence of interaction variables and from the
fact that we want to keep the local problems and the coordination problem
to a reasonable size.

We have discussed some ways of dealing with these new variables at
the lower level, but none of them seem satisfactory, either because the local
model proposed is too simple and far from the true nature of the interactions,
or because this model (or management policy) leads to too complex local pro-
blem resolutions.

Moreover, we have not been able to define, by some sets of axioms,
what is allowed to the upper and lower levels. However this last objection
is not dramatic since it has not even been overcome in the deterministic case,
leading however to interesting algorithms. For that matter, it seems that a
reasonable attitude is to estimate the interest of any method a posteriori and
not to try to define the "game rules" a priori. If we want (perhaps oversimpli-
fying in some respect) to sum up the technical reasons that make stochastic
decomposition so much more complicated than deterministic decomposition, we can
say that the difficulties lie in two features of the interaction (and may be
other coupling) variables : they are correlated in space and in time.

By correlation in space, we mean that the behaviour of $v_i$ is dependent
on the behaviour of the subsystems $j(j \neq i)$, by definition of course, but this
takes a different form in deterministic and stochastic frameworks. In the for-
mer, the relevant quantities are time histories of vector-quantities and a
vector can be rebuilt by concatenation of subvectors. In the latter, the rele-
vant quantities assume also matrix forms (as covariance matrices) to limit our-
selves to second order probability moments. Unfortunately, a matrix cannot be
rebuilt by concatenation of its diagonal blocks. The problem is then to give
an approximated model of a space correlated stochastic process in terms of an
uncorrelated one. This is done very roughly in the problem previously revisi-
ted. Moreover, we must appreciate the quality of this approximation (and try
to choose the best approximation) on the basis of its effect on the minimiza-
tion of the mathematical expectation of the global criterion. For example, in Chong's problem in what precise sense is the solution of the $\mathcal{B}$-problem good when applied to the original problem. This seems to be an unsolvable question.

The correlation in time comes from the fact that $v_t^i$ is the output of a diffusion process and thus is not white. This problem is irrelevant in the deterministic framework but is critical technical importance in the classical stochastic framework. As a matter of fact, the interaction input $v_t^i$, from the point of view of the $i$th local controller is an uncertain input just like the exogenous uncertainties. However, the classical stochastic approach deals with white noises, or, if they are not white, they must be represented as diffusion processes driven by white noises. This leads to state size augmentation, a fact which is contradictory with our objective of reasonably sized local problems. This is one of the difficulties we have encountered in our attempts to propose interaction models.

The opinion of the authors is that, without denying the intrinsic difficulties of decentralization and coordination, additional drawbacks come from the classical stochastic formulation of control under uncertainties. This stems in part from the fact that this approach uses an extremely rich information and, hence, using it optimally in complicated situations is extremely ambitious. On the other hand, experience teaches that, very often, the probability laws are inferred from much poorer data, such as maximum range (taken to be "3 σ"). One possibility to cope with this situation is to be content with this poor information and to turn to worst-case design techniques. This approach should have the additional advantage of allowing a description of the exogenous uncertainties, including imperfect modelling, and of the interaction inputs in the same pattern at the lower level (already, in the stochastic approach, authors try to describe the interaction as fake white noises i.e. with the same model as exogenous noises). This possibility seems to be a promising avenue for overcoming the two previous difficulties of correlation in space and in time.

We shall present elsewhere results in this direction.
REFERENCES

(1) Aoki, M. "On feedback stabilizability of Decentralized Dynamic Systems", AUTOMATICA, Vol. 8, pp. 163-173, 1972.

(2) Aoki, M. "On Decentralized Linear Stochastic Control Problems with Quadratic Cost", IEEE TRANS. on AUTOMATIC CONTROL, Vol. AC-18, n°3, pp. 243-249, June 1973.

(3) Bensoussan, A., Lions J.L., Temam, R. "Decomposition des problèmes d'optimisation" Cahier de l'IRIA n°11, 1972.

(4) Bernhard, P. "Commande Optimale, Décentralisation et Jeux dynamiques". (Chap. 5 by Bernhard and Cohen), Dunod, Paris 1976.

(5) Bismut J.M. "An Example of Interaction between Information and Control : the Transparency of the Game", IEEE. TRANS. on AUTOMATIC CONTROL, Vol AC-18, pp. 518-522. October 1973.

(6) Brosilow, G.B., Lasdon, D.S., Pearson, J.D. "Feasible Optimization Methods for Interconnected Systems", JACC, Troy, New York. 1965.

(7) Chong, C.Y. "On the decentralized Control of Large Scale Systems", PhD dis- sertation MIT, Cambridge, Mass., May 1973. Also in Chong, C.Y., Athans, M. "On the Periodic Coordination of Linear Stochastic Systems", IFAC Congress, Boston. August, 1975.

(8) Chong, C.Y. "On the stochastic Control of Coupled Linear Systems", S.M. Thesis, MIT, 1972.

(9) Cohen, G. "Contribution à la théorie de la Commande Hiérarchisée et à la Coordination en ligne des Systèmes Dynamiques", Thèse de Docteur-In- génieur, Université de Paris-Sud-Orsay, France, Octobre 1975.
<figure><img src="image_2.png" /></figure>
(20) Lasdon L.S., Schoeffer J.D., "A Multilevel Technique for Optimization" Proc. JACC, Troy, New York, 1965.

(21) Marschark J., Radner, R., "The Economic Theory of Teams", YALE UNIVERSITY PRESS, New Haven, Connecticut, 1971.

(22) Mesarovic M.D., Macko D., Takahara Y., "Theory of Hierarchical, Multilevel Systems", ACADEMIC PRESS, 1970.

(23) Mesarovic M.D., Macko D., Takahara Y., "Two coordination Principle and their Application in Large Scale Systems Control" AUTOMATICA, Vol. 6, pp. 261-270, 1970.

(24) Pearson J.D., "Dynamic Decomposition Techniques", Chap. 4 in "Optimization Methods for Large Scale Systems...with Applications", D.A. Wismer Ed. MAC GRAW HILL, 1971.

(25) Rhodes J.B., Luenberger D.G., "Stochastic Differential Games with constrained estimators", IEEE Transactions on Automatic Control, AC-14, pp. 476-481, 1969.

(26) Sandell V.R., Athans, M., "Solution of some Non-Classical LQG Decision Problems", IEEE TRANS. on AUTOMATIC CONTROL, Vol. AC-19, pp 108-116, April 1974.

(27) Singh M.G., "A Decentralized Filter for Certain Time Lag Systems", Chap. 7 in "Recent Mathematical Developments in Control", D.J. Bell ed., ACADEMIC PRESS, 1973.

(28) Titli A., "Contribution à l'étude des Structures de Commande Hiérarchisée en vue de l'Optimisation des Processus Complexes" Thèse de Doctorat d'Etat, Université Paul Sabatier, Toulouse (France), 1972.

(29) Willman W.W., "Formal Solutions for a class of Stochastic Pursuit Evasion Games", IEEE Transactions on Automatic Control, Vol AC-14, pp. 504-509, 1969.
(30) Witsenhausen, "Separation of Estimation and Control for Discrete Time Systems" Proc. IEEE, Vol 59, pp. 1557-1566, 1971.

(31) Witsenhausen H.S., "A counterexample in Stochastic Optimal Control, SIAM J. of Control Vol. 6, pp. 131-147, 1968.