Decentralized Optimal Control of Distributed Interdependent Automata With Priority Structure

Data Flowchart

Notation

${\color{Golden} P}^i=\left ( {\color{Teal} T}, {\color{Red} U}^i, {\color{Blue} X}^i, {\color{DarkRed} Y}^i, {\color{Green} W}^i, {\color{Purple} f}^i, {\color{Magenta} g}^i \right )$ : subsystem model, the plant P ⁱ, deterministic finite-state automaton.

${\color{Teal} T}={0,1,2,...} \subset \mathbb{N} \ \cup \{0\}\ \texttt{with}\ {\color{Teal} k\in T}\texttt{:an\ event\ {\color{Teal} time}.}$

${\color{Red} \nu} {\color{Teal} _k}^i \in {\color{Red} U}^i=\{ 1,...,{\color{Red} m}_i \} \subset \mathbb{N}\texttt{:finite sets of discrete {\color{Red} inputs}.}$

${\color{Blue} \xi} {\color{Teal} _k}^i \in {\color{Blue} X}^i=\{ 1,...,{\color{Blue} n}_i \} \subset \mathbb{N}\texttt{:discrete\ {\color{Blue} states}.}$

${\color{DarkRed} y}{\color{Teal} _k}^i \in {\color{DarkRed} Y}^i=\{ 1,...,{\color{DarkRed} q}_i \}\subset \mathbb{N}\texttt{:finite\ sets\ of\ discrete\ {\color{DarkRed} outputs}.}$

${\color{Green} W} ^i \in \{ 0,1,...,{\color{Green} q}' \}^{{\color{Red} m}_i \times {\color{Blue} n}_i}\texttt{:{\color{Green} dependence matrix}.}$ $W^i(input,state)=y^{i+1} > 0\ or\ =0$

${\color{Purple} f}^i:{\color{Blue} X}^i \times {\color{Red} U}^i \to {\color{Blue} X}^i \texttt{:A deterministic\ {\color{Purple} state\ transition\ function}.}$

${\color{Magenta} g}^i: {\color{Blue} X} \to {\color{DarkRed} Y}^i\texttt{:{\color{Magenta} output function}\ of\ Moore-type.}$

${\color{Teal} T}={0,1,2,...} \subset \mathbb{N} \ \cup \{0\}\ \texttt{with}\ {\color{Teal} k\in T}\texttt{:an\ event\ {\color{Teal} time}.}$

${\color{Blue} \xi} {\color{Teal} _0}^i \in {\color{Blue} X}^i\texttt{:initial\ {\color{Blue} state}.}$

${\color{Red} \nu} {\color{Teal} _k}^i \in {\color{Red} U}^i \ \cup \{0 \} =\{ 0, {\color{Red}1,..., m}_i \} \texttt{:finite\ sets\ of\ discrete\ {\color{Red} inputs}.}$

$\phi^i{\color{Red} _u} :=\{ {\color{Red} \nu}_0^i, {\color{Red} \nu}_1^i,...\} \texttt{:{\color{Red} input}\ sequence.}$

$\phi^i {\color{Blue} _x} :=\{ {\color{blue} \xi}_0^i, {\color{Blue} \xi}_1^i,...\} \texttt{:the\ elements\ of\ an\ {\color{Blue} admissible\ run}.}$

$\phi^i {\color{DarkRed} _y} :=\{ {\color{DarkRed} y}_0^i, {\color{DarkRed} y}_1^i,...\} \texttt{:{\color{DarkRed} output} sequence.}$

${\color{Blue} \xi}_{k+1}^i=\left\{\begin{matrix} {\color{Blue} \xi}_k^i, & if\ {\color{Red} \nu}_k^i=0\ .& \\ {\color{Purple} f}^i({\color{Blue} \xi}_k^i, {\color{Red} \nu}_k^i), & if \ {\color{Red} \nu}_k^i \in {\color{Red} U}^i , & W({\color{Red} \nu}_k^i, {\color{Blue} \xi}_k^i=0)\\ {\color{Purple} f}^i({\color{Blue} \xi}_k^i, {\color{Red} \nu}_k^i), & if \ {\color{Red} \nu}_k^i \in {\color{Red} U}^i , & W^i({\color{Red} \nu}_k^i, {\color{Blue} \xi}_k^i) \in Y^{i+1} \end{matrix}\right.$ (1)

${\color{DarkRed} y}_{k+1}^i={\color{Magenta} g}^i({\color{Blue} \xi}_{k+1}^i)$ (2)

${\color{Blue} x}{\color{Teal} _k}^i \in \{ 0,1 \}^{{\color{Blue} n}_i \times 1}\texttt{:{\color{Blue} state}\ vector.}$

$\begin{Bmatrix} {\color{Blue} x}{\color{Teal} _{k}}^{i}_{,{\color{Blue} \ j}} =1 \\ {\color{Blue} x}{\color{Teal} _{k}}^{i}_{, \ p} =0 \end{Bmatrix} \texttt{if and only\ if\ } {\color{Blue} \xi}{\color{Teal} _k}^i={\color{Blue} j} \in \{ 1,...,{\color{Blue} n}_i \}\ \texttt{is\ the\ {\color{Blue} active\ state}\ of}\ {\color{Golden} P}^i\ \texttt{in}\ {\color{Teal} k}.$ (3)

${\color{Purple} F}{\color{Red} _l}^i \in \{ 0,1 \}^{{\color{Blue} n}_i \times {\color{Blue} n}_i}\texttt{:{\color{Purple} state\ transition}\ matrix,for any\ } {\color{Red} input\ l \in U}^i.$

${\color{Blue} h,j \in X}^i.$

${\color{Purple} F}_{\color{Red} l}^i({\color{Blue} j},h)=\left\{\begin{matrix} 1, & \texttt{if}\ {\color{Blue} j}={\color{Purple} f}^i({\color{Blue} h},{\color{Red} l}) \\ 0, & \texttt{otherwise}. \end{matrix}\right.$ (4) : P ⁱcan be transitioned from state ${\color{Blue} \xi}{\color{Teal} _k}^i= h$ into state ${\color{Blue} \xi}{\color{Teal} _k}^i={\color{Blue} j}$ if the input l is applied.

${\color{Purple} F}_{\color{Red} l}^i({\color{Blue} j},j)=1 \ \texttt{if} \ {\color{Purple} F}_{\color{Red} l}^i(p,j)=0\ \forall p\neq j,\ p\in \{ 1,...,{\color{Blue} n}_i\}.$

$\sum_{{\color{Blue} j}=1}^{{\color{Blue} n}_i}{\color{Purple} F}_{\color{Red} l}^i({\color{Blue} j},h)=1 \ \texttt{applies} \ \forall h \in \{ 1,...,{\color{Blue} n}_i\}\ \texttt{and}\ {\color{Red} l \in U}^i.$

${\color{Purple} \mathfrak{F}}^i=\left \{ {\color{Purple} F}_1^i, ..., {\color{Purple} F}_{{\color{Red} m}_i}^i \right \} : set\ of\ {\color{Purple} state\ transition}\ matrices.$

${\color{Blue} x}_0^i \in \{ 0,1\}^{{\color{Blue} n}_i \times 1}:initial \ vector. \sum_{{\color{Blue} j}=1}^{{\color{Blue} n}_i}{\color{Blue} x}_{0,{\color{Blue} j}}^i=1.$

$\phi^i{\color{Red} _u} :=\{ {\color{Red} \nu}_0^i, {\color{Red} \nu}_1^i,...\} \texttt{:{\color{Red} input} sequence.}$

$\phi^i {\color{Blue} _x} :=\{ {\color{blue} x}_0^i, {\color{Blue} x}_1^i,...\} \texttt{:a {\color{Blue} run} of\ } {\color{Golden} P}^i \ \texttt{over} \ {\color{Teal} T}\ \texttt{is\ {\color{Blue} admissible}.}$

${\color{Blue} x}_{{\color{Teal} k+1}}^i=\left\{\begin{matrix} {\color{Blue} x}_k^i, & \texttt{if}\ {\color{Red} \nu}_k^i=0 & \\ {\color{Purple} F}_{\color{Red} j}^i \cdot {\color{Blue} x}_k^i, & \texttt{if}\ {\color{Red} \nu}_k^i \in {\color{Red} U}^i, &{\color{Green} W}({\color{Red} \nu}_k^i, {\color{Blue} \xi}_k^i)=0 \\ {\color{Purple} F}_{\color{Red} j}^i \cdot {\color{Blue} x}_k^i, & \texttt{if}\ {\color{Red} \nu}_k^i \in {\color{Red} U}^i, & {\color{Green} W}^i({\color{Red} \nu}_k^i, {\color{Blue} \xi}_k^i)\in {\color{Blue} X}^{i+1}. \end{matrix}\right.$ (5)

${\color{Purple} F}^i=\sum_{{\color{Red} l}=1}^{{\color{Red} m}_i}{\color{Purple} F}{\color{Red} _l}^i\texttt{:accumulated\ {\color{Purple} state\ transition}\ matrix.}$ It encodes with ${\color{Purple} F}^i({\color{Blue} j},h)=1$ that the transition $\texttt{from}\ \xi_k^i=h\ \texttt{to}\ {\color{Blue} \xi}{\color{Teal} _k}^i={\color{Blue} j}$ is possible with at least one input. (6)

${\color{Purple} R}^i :=\sum_{{\color{Blue} p}=1}^{{\color{Blue} n}_i} \left ( {\color{Purple} F}^i \right )^{\color{Blue} p} \texttt{:a\ {\color{Purple} reachability}\ matrix.}$ To this one-step $\texttt{from}\ \xi_k^i=h\ \texttt{to}\ {\color{Blue} \xi}{\color{Teal} _k}^i={\color{Blue} j}$ reachability, Rⁱ formalizes the possibility of transferring P ⁱ between an arbitrary pair of states. (6) ${\color{Purple} R}^i({\color{Blue} j},h)=1$ models that state j is reachable from state h by at least one input sequence in at most n_i state transitions.

 for any transition  specified for Pⁱthrough the state transition function (or the set of state transition matrices  ). Possible interpretations of such transition costs are the time, the control effort, and/or the energy required to steer P ⁱ  by the use of the control input  , i.e.,  can encode state and control costs.

${\color{Blue} \Pi}_{\color{Red} j}^i(q,{\color{Blue} p})=\pi({\color{Blue} p},q,{\color{Red} j})\texttt{:{\color{Blue} cost} of the {\color{Purple} transition-}}$ ${\color{Purple} f}^i({\color{Blue} p},{\color{Red} j})={\color{Blue} q}$ .

${\color{Blue} \Pi}^i{\color{Red} _j}(q,{\color{Blue} p})=\infty\texttt{:if the\ transtion\ is\ infeasible\ for\ {\color{Red} input\ j}}.$ ${\color{Purple} F}^i_{\color{Red} j}(q,{\color{Blue} p})=0$ .

${\color{Blue} \Pi}^i{\color{Red} _j}(p,{\color{Blue} p})=0: \texttt{{self}-loops}, \forall {\color{Blue} p\in X}^i,{\color{Red} j\in U}^i.$

${\color{Blue} \Pi}^i:=\left \{ q, {\color{Blue} p} \in {\color{Blue} \chi}^i:min_{{\color{Red} j\in U}^i} {\color{Blue} \Pi}^i_{\color{Red} j}(q,{\color{Blue} p}) \right \}$ (7)

${\color{Purple} f}^i({\color{Blue} p},{\color{Red} j})={\color{Blue} q}$ over all ${\color{Red} j \in U}^i$ values.

${\color{Blue} \Pi}^i_{{\color{Red} U}^i}:=\left \{ q,{\color{Blue} p} \in {\color{Blue} \chi}^i:{\color{Blue} \Pi}^i_{{\color{Red} U}^i}=0 \ \texttt{if} \ {\color{Purple} F}^i({\color{Blue} p},q)=0 \texttt{,and:} {\color{Blue} \Pi}^i_{{\color{Red} U}^i} (q,{\color{Blue} p})=argmin_{{\color{Red} j \in U}^i} {\color{Blue} \Pi}^i_{\color{Red} j} (q,{\color{Blue} p})\ \texttt{if}\ {\color{Purple} F}^i({\color{Blue} p},q)=1\right \}$ (8)

${\color{Blue} \Pi}^i_{{\color{Red} opt}}\texttt{:{\color{Red} minimal} {\color{Blue} transfer costs} for }{\color{Golden} P}^i.$

${\color{Blue} \Pi}^i_{{\color{Red} opt}}(q,{\color{Blue} p})$ : The minimal costs for transferring the subsystem from the state ${\color{Blue} \xi^i=p} \texttt{\ into\ } \xi^i=q$ .

**Problem 1: Subsystem independent of other subsystems**

${\color{Green} W} ^i \in \{ 0,1,...,{\color{Green} q}' \}^{{\color{Red} m}_i \times {\color{Blue} n}_i}\texttt{:{\color{Green} dependence matrix}.}$

${\color{Green} W}^i(input,state)=y^{i+1} =0^{{\color{Red} m}_i \times {\color{Blue} n}_i} \texttt{:subsystem}\ {\color{Golden} P}^i\ \texttt{as independent of other subsystems.}$

${\color{Blue} \xi}^i_{\color{Red} F} \texttt{:goal {\color{Blue} state}.}$

${\color{Red} \nu}^i_{\color{Teal} k}={\color{Red} u}^i \cdot {\color{DarkRed} K}^i \cdot {\color{Blue} x}^i_{\color{Teal} k} \in {\color{Red} U}^i.$

${\color{Red} u}^i=[1,2,...,{\color{Red} m}_i]\texttt{:a row vector of all {\color{Red} input} indices in } {\color{Red} U}^i.$

${\color{DarkRed} K}^i \in \{0,1\}^{{\color{Red} m}_i \times {\color{Blue} n}_i} \texttt{{:\color{DarkRed} Controller} matrix.\ }$

${\color{Blue} \Pi}^i_{{\color{Magenta} opt}}\left ( {\color{Blue} \xi}^i_{\color{Red} F}, {\color{Blue} \xi}^i_0 \right ) := {\color{Magenta} min}_{\phi^i_{\color{Red} u}}\sum_{{\color{Red} j=1}}^{{\color{Red} d^i}} {\color{Blue} \Pi}_{{\color{Red} \nu_{j-1}^i}} \left ({\color{Blue} \xi}^i_{\color{Red} j}, {\color{Blue} \xi}^i_{\color{Red} {j-1}} \right ).$

The task is to compute a state-feedback controller,

which realizes for any arbitrary initializationan input sequencethat leads to an admissible run

The final state is the goal ${\color{Blue} \xi}^i_{{\color{Red} d^i}}={\color{Blue} \xi}^i_{\color{Red} F}$
The state-feedback control law has the structure: ${\color{Red} \nu}^i_{\color{Teal} k}={\color{Red} u}^i \cdot {\color{DarkRed} K}^i \cdot {\color{Blue} x}^i_{\color{Teal} k} \in {\color{Red} U}^i \ \leftarrow \\ {\color{Red} u}^i=[1,2,...,{\color{Red} m}_i]\texttt{:a row vector of all {\color{Red} input} indices in } {\color{Red} U}^i. \\ {\color{DarkRed} K}^i \in \{0,1\}^{{\color{Red} m}_i \times {\color{Blue} n}_i} \texttt{{:\color{DarkRed} Controller} matrix.\ }$ (9)
The costs of $\phi^i_{\color{Blue} x}$ are minimal over all admissible runs to transfer Pⁱ from ${\color{Blue} \xi}^i_{\color{Red} 0}$ to ${\color{Blue} \xi}^i_{\color{Red} F}$ : ${\color{Blue} \Pi}^i_{{\color{Magenta} opt}}\left ( {\color{Blue} \xi}^i_{\color{Red} F}, {\color{Blue} \xi}^i_0 \right ) := {\color{Magenta} min}_{\phi^i_{\color{Red} u}}\sum_{{\color{Red} j=1}}^{{\color{Red} d^i}} {\color{Blue} \Pi}_{{\color{Red} \nu_{j-1}^i}} \left ({\color{Blue} \xi}^i_{\color{Red} j}, {\color{Blue} \xi}^i_{\color{Red} {j-1}} \right ).$ (10)

(9): $\texttt{For a given }{\color{Blue} x}^i_{\color{Teal} k} \texttt{:current {\color{Blue} state},} {\color{Red} u}^i \cdot {\color{DarkRed} K}^i \texttt{:selects the {\color{Red}control input}\ } {\color{Red} \nu}^i_{\color{Teal} k} \texttt{\ to be applied}$ , in order to trigger the next state transition. The selection of Kⁱ according to the solution of (10) produces the ${\color{Blue} \xi}^i_{\color{Red} F}\texttt{th row of the matrix }{\color{Blue} \Pi}^i_{{\color{Magenta} opt}}$ , and establishes an optimal controller for Pⁱwith ${\color{Blue} \xi}^i_{\color{Red} F} \texttt{:goal {\color{Blue} state}.}$

Synthesis Algorithm for Independent Subsystems

${\color{DarkRed} K}^i \in \{0,1\}^{{\color{Red} m}_i \times {\color{Blue} n}_i} \texttt{{:\color{DarkRed} Controller} matrix.\ }$

${\color{Blue} \xi}^i_{\color{Red} F}\texttt{th row of the matrix }{\color{Blue} \Pi}^i_{{\color{Magenta} opt}}$

${\color{Blue} \xi}^i_{\color{Red} F} \texttt{:goal {\color{Blue} state}.}$

Compute controller matrix, and the part of costs referring to the goal state.

Control of Distributed Systems with Linear Structure

$\mathbb{P}=\{ P^1,...,{\color{Golden} P}^i,...,P^{\color{Red} z} \} \texttt{:optimal control of processes consisting of {\color{Red} z} subsystems, {\color{Red} interconnected} in a {\color{Red} linear} structure.}$

${\color{Golden} P}^{\color{Red} i}\ \texttt{has {\color{Red} higher priority} than }{\color{Golden} P}^{{\color{Blue} i+1}}.$

${\color{Red} C}^i \texttt{:{\color{Red} controller}, communicates with }{\color{Red} C}^{i-1} \texttt{and }{\color{Red} C}^{i+1},\ i \in \{ 2, ..., z-1\}$ .

Task of Distributed Controller Synthesis

Assumption 3 : Any subsystem ${\color{Golden} P}^i \in \mathbb{P}, i \in \{ 2,...,z \}$ is completely controllable: $R^i=1^{{\color{Blue} n}_i \times {\color{Blue} n}_i}$ .

Proposition 2 : Let $P=\{ P^1, P^2 \}$ be a pair of 2 connected subsystems for which an admissible run is a sequence of state pair $\left ( {\color{Blue} \xi}^1_{\color{Teal} k}, \xi^2_k \right )$ according to Definition 2 with ${\color{Green} W}^1(\nu^1_k, \xi^1_k) \in X^{\color{Red} 2}$ and ${\color{Green} W}^2=0^{{\color{Red} m}_2 \times {\color{Blue} n}_2}$ . The structure is completely controllable if P¹ and P² on their own are completely controllable according to Assumption 3.

Proof : Since the transition of P²are independent of the current state of P¹ , and since subsystem P² is completely controllable, a sequence $\phi^2_{\color{Red} u}$ of inputs exists to transfer P²from an arbitrary initial state ${\color{Blue} \xi}^2_0\texttt{ into }\xi^2_{\color{Red} F}$ .

Thus, P²is able to deliver any arbitrary output sequence $\phi^2_{\color{DarkRed} y}$ (and thus admissible run $\phi^2_{\color{Blue} x}$ ) to subsystem P¹, i.e., any condition formulated for P¹in terms of the dependence matrix ${\color{Green} W}^1$ is satisfiable by P². Since P¹itself is completely controllable as well, a sequence of input $\phi^1_{\color{Red} u}$ exists which transfers P¹into an arbitrary goal state ${\color{Blue} \xi}^1_{\color{Red} F}$ .

Problem 2: Two subsystems

For 2 subsystems ${\color{Golden} P}^1\texttt{ and }{\color{Golden} P}^2$ , let the goal states ${\color{Blue} \xi}^1_{\color{Red} F} \texttt{\ and\ } {\color{Blue} \xi}^2_{\color{Red} F}$ be defined. The control task is to compute 2 local feedback control laws, which generate for any initialization $\xi^1_0 \in X^1\texttt{ and }\xi^2_0 \in X^2$ , the input sequences $\phi^1_u=\left ( \nu^1_0,...,\nu^1_{d^1_1-1} \right )\texttt{ and }\phi^2_u=\left ( \nu^2_0,...,\nu^2_{d^2_2-1} \right )$ , such that the following hold.

The admissible runs $\phi^1_x = \left ( \xi^1_0,...,\xi^1_{d^1_1} \right )$ with $\xi^1_{d^1_1}=\xi^1_F$ and $\phi^2_x = \left ( \xi^2_0,...,\xi^2_{d^2_2} \right )$ with $\xi^2_{d^2_2}=\xi^2_F$ .
$\phi^1_u\texttt{ and }\phi^2_u$ follow from controllers of the following type: ${\color{Magenta} \nu^1_k=u^1\cdot K^1 \left ( \xi^2_k \right )\cdot x^1_k \in U^1, \nu^2_k=u^2\cdot K^2 \cdot x^2_k \in U^2}$ (11) with vectors $u^1\texttt{ and }u^2$ , and matrix ${\color{DarkRed} K}^2$ as in problem 1, and $K^1\left ( \xi^2_k \right ) \in \{ 0, 1 \}^{m_1 \times n_1}\texttt{ for }\xi^2_k \in X^2.$
The global path costs are minimal ${\color{Magenta} J_g=\sum^{d^1_1}_{k=1}\Pi_{\nu^1_{k-1}} \left ( \xi^1_k,\xi^1_{k-1} \right )+\sum^{d^2_2}_{k=1}\Pi_{\nu^2_{k-1}} \left ( \xi^2_k,\xi^2_{k-1} \right )}$ (12)

Thus, the solution is targeted to provide local controllers C¹ and C² for P¹ and P², such that the latter are driven from an arbitrarily chosen initial state into the respective local goal state, while the sum of the transfer costs for both control loops is as small as possible.

1. when C¹ receives the information from P¹ that state ${\color{Blue} \xi}^1_{\color{Teal} k}$ is reached ,

2. C¹ sends the request to C² that P² has to reach ${\color{Blue} \xi}^2_{\color{Red} F}$ as a temporary goal state. This state is encoded in K¹ in order to realize a cost-optimal path of P¹ into its goal state $\xi^1_{\color{Red} F}$ .

3. Then, C²realizes a path of P² into ${\color{Blue} \xi}^2_{\color{Red} F}$ . If the path comprises more than one transition, the pair (P¹,C¹) waits in state ${\color{Blue} \xi}^1_{\color{Teal} k}$ until P² has reached ${\color{Blue} \xi}^2_{\color{Red} F}$ ( ${\color{Blue} \xi}^2_{\color{Teal} k'}\texttt{ and }{\color{Red} \nu}^2_{{\color{Teal} k'}}$ the index k’ in Fig. 4 is meant to indicate that (P²,C²) evolve, while (P¹,C¹) wait in step k).

4. When P² attains $\xi^2_{\color{Red} F}$ , C² communicates to C¹ that the requested state is reached .

5. Eventually, the control input ${\color{Red} \nu}^1_{\color{Teal} k}$ supplied by C¹ together with ${\color{Blue} \xi}^2_{\color{Red} F}$ send by P² triggers the state transition in P¹ .

Pei

Email Address:

Blog Stats

State Action/Control

Meta

Decentralized Optimal Control of Distributed Interdependent Automata With Priority Structure