Decentralized Optimal Control of Distributed Interdependent Automata With Priority Structure


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 i , 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) : i  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, Ri formalizes the possibility of transferring i  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 ni state transitions.

 


{\color{Blue} \pi} \left ( {\color{Blue} \xi}_k^i, {\color{Blue} \xi}_{k+1}^i, {\color{Red} \nu}_k^i \right )\texttt{:{\color{Blue} transition\ costs}.} for any transition {\color{Blue} \xi}_{{\color{Teal} k+1}}^i={\color{Purple} f}^i({\color{Blue} \xi}_k^i,{\color{Red} \nu}_k^i) specified for Pi through the state transition function (or the set of state transition matrices {\color{Purple} \mathfrak{F}}^i ). Possible interpretations of such transition costs are the time, the control effort, and/or the energy required to steer i from\ \xi_k^i\ to\ {\color{Blue} \xi}^i{\color{Teal} _{k+1}} by the use of the control input {\color{Red} \nu}^i{\color{Teal} _k} , i.e., {\color{Blue} \mathbf{\pi}} 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 initialization{\color{Blue} \xi}^i_0 \in{\color{Blue} X}^i \texttt{:arbitrary initialization.}an input sequence\phi^i{\color{Red} _u} =\{ {\color{Red} \nu}_0^i, {\color{Red} \nu}_1^i,..., {\color{Red} \nu}^i_{{\color{Magenta} d^i-1}}\} \texttt{:{\color{Red} input} sequence.}that leads to an admissible run\phi^i_{{\color{Blue} \xi}} =\left ( \xi^i_0,...,{\color{Blue} \xi}^i_{{\color{Red} d^i}} \right ) \texttt{:admissible run.}
  1. The final state is the goal {\color{Blue} \xi}^i_{{\color{Red} d^i}}={\color{Blue} \xi}^i_{\color{Red} F}
  2. 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)
  3. The costs of \phi^i_{\color{Blue} x} are minimal over all admissible runs to transfer Pi 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 Ki 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 Pi  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} \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 ).

 

 

{\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 controllableR^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 P1 and P2 on their own are completely controllable according to Assumption 3.

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

Thus, P2  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 Pin terms of the dependence matrix {\color{Green} W}^1 is satisfiable by P. Since P1  itself is completely controllable as well, a sequence of input \phi^1_{\color{Red} u} exists which transfers P1  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.

  1. 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 .
  2. \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.
  3. 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 C1 and C2 for P1 and P2, 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 C1 receives the information from P1 that state {\color{Blue} \xi}^1_{\color{Teal} k} is reached ,

2. C1 sends the request to C2 that P2 has to reach {\color{Blue} \xi}^2_{\color{Red} F} as a temporary goal state. This state is encoded in K1 in order to realize a cost-optimal path of P1 into its goal state \xi^1_{\color{Red} F}.

3. Then, Crealizes a path of P2 into {\color{Blue} \xi}^2_{\color{Red} F}. If the path comprises more than one transition, the pair (P1,C1) waits in state {\color{Blue} \xi}^1_{\color{Teal} k} until P2 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 (P2,C2) evolve, while (P1,C1) wait in step k).

4. When P2 attains \xi^2_{\color{Red} F}, C2 communicates to C1 that the requested state is reached .

5. Eventually, the control input {\color{Red} \nu}^1_{\color{Teal} k} supplied by C1 together with {\color{Blue} \xi}^2_{\color{Red} F} send by P2 triggers the state transition in P1 .


Control of Distributed Systems with Tree Structure

 


 

Sidebar