报告——概率布尔网络.pdf
报告——概率布尔网络.pdf
Probabilistic Boolean Networks: Stability, Stabilization, Controllability, and Observability Series One, Lesson Nine Lecturer: Yuqian Guo (School of Automation, Central South University) Center of STP Theory and Its Applications August 15-22, 2020 LiaoCheng University, LiaoCheng, Shandong, P.R. China Outline 1 Basic Concepts of PBNs 2 Stability Analysis of PBNs Finite-time Stability Asymptotical Stability 3 Feedback Stabilization of PBNs Fintie-time Feedback Stabilization Asymptotical Feedback Stabilization 4 Controllability of PBNs 5 Observability of PBNs 6 Questions 2 / 115 Outline 1 Basic Concepts of PBNs 2 Stability Analysis of PBNs Finite-time Stability Asymptotical Stability 3 Feedback Stabilization of PBNs Fintie-time Feedback Stabilization Asymptotical Feedback Stabilization 4 Controllability of PBNs 5 Observability of PBNs 6 Questions 3 / 115 I. Basic Concepts of PBNs + Boolean network (BN) was first proposed by Kauffman1 as a qualitative model for GRNs. + Even though a BN provides a rougher description of GRNs, it is still capable of efficiently predicting the long-term behavior of GRNs2 . + Probabilistic Boolean network (PBN)3 is a stochastic generalization of deterministic BN, aiming to describe uncertainties and stochasticity in GRNs. 1 Stuart A Kauffman. “Metabolic stability and epigenesis in randomly constructed genetic nets”. In: Journal of Theoretical Biology 22.3 (1969), pp. 437–467. 2 Gautier Stoll et al. “Continuous time boolean modeling for biological signaling: application of Gillespie algorithm”. In: Bmc Systems Biology 6.1 (2012), pp. 116–116. 3 Ilya Shmulevich, Edward R Dougherty, and Wei Zhang. “From Boolean to probabilistic Boolean networks as models of genetic regulatory networks”. In: Proceedings of the IEEE 90.11 (2002), pp. 1778–1792. 4 / 115 I. Basic Concepts of PBNs + Boolean network (BN) was first proposed by Kauffman1 as a qualitative model for GRNs. + Even though a BN provides a rougher description of GRNs, it is still capable of efficiently predicting the long-term behavior of GRNs2 . + Probabilistic Boolean network (PBN)3 is a stochastic generalization of deterministic BN, aiming to describe uncertainties and stochasticity in GRNs. 1 Stuart A Kauffman. “Metabolic stability and epigenesis in randomly constructed genetic nets”. In: Journal of Theoretical Biology 22.3 (1969), pp. 437–467. 2 Gautier Stoll et al. “Continuous time boolean modeling for biological signaling: application of Gillespie algorithm”. In: Bmc Systems Biology 6.1 (2012), pp. 116–116. 3 Ilya Shmulevich, Edward R Dougherty, and Wei Zhang. “From Boolean to probabilistic Boolean networks as models of genetic regulatory networks”. In: Proceedings of the IEEE 90.11 (2002), pp. 1778–1792. 4 / 115 A Reference Book 5 / 115 + This lecture is based on the work regarding stability and stabilization4,5,6,7,8,9,10 , controllability and observability11,12,13,14 . 4 Shiyong Zhu, Jianquan Lu, and Daniel W.C.Ho. “Finite-time Stability of Probabilistic Logical Networks: A Topological Sorting Approach”. In: IEEE Transactions on Circuits & Systems -II: Express Briefs 67.4 (2020), pp. 695– 699. 5 Yuqian Guo et al. “Stability and Set Stability in Distribution of Probabilistic Boolean Networks”. In: IEEE Transactions on Automatic Control 64 (2 2019), pp. 736–742. 6 Rongpei Zhou and Yuqian Guo. “Set Stabilization in Distribution of Probabilistic Boolean Control Networks”. In: Proceedings of the 2018 13th World Congress on Intelligent Control and Automation July 4-8, 2018, Changsha, China. 2018, pp. 274–279. 7 Rongpei Zhou et al. “Asymptotical Feedback Set Stabilization of Probabilistic Boolean Control Networks”. In: IEEE Transactions on Neural Network & Learning Systems (2020), DOI: 10.1109/TNNLS.2019.2955974. 8 Liqing Wang, Yang Liu, and & Cybernetics: Systems Wu. “Stabilization and Finite-Time Stabilization of Probabilistic Boolean Control Networks”. In: (2020), DOI: 10.1109/TSMC.2019.2898880. 9 Yin Zhao and Daizhan Cheng. “On controllability and stabilizability of probabilistic Boolean control networks”. In: Science China Information Sciences 57.1 (2014), pp. 1–14. 10 Rui Li, Meng Yang, and Tianguang Chu. “State feedback stabilization for probabilistic Boolean networks”. In: Automatica 50.4 (2014), pp. 1272–1278. 11 Yin Zhao and Daizhan Cheng. “On controllability and stabilizability of probabilistic Boolean control networks”. In: Science China Information Sciences 57.1 (2014), pp. 1–14. 12 Fangfei Li and Jitao Sun. “Controllability of probabilistic Boolean control networks”. In: Automatica 47.12 (2011), pp. 2765–2771. 13 Ettore Fornasini and Maria Elena Valcher. “Observability and Reconstructibility of Probabilistic Boolean Networks”. In: IEEE Control Systems Letters 4.2 (2020), pp. 319–324. 14 J. Zhao and Z. Liu. “Observability of probabilistic Boolean networks”. In: Proceedings of the Chinese Control Conference, 2015. 2015, pp. 183–186. 6 / 115 + A PBN is a randomly switched Boolean network n o σ1 (t) σ1 (t) x (t + 1) = f x (t) j ∈ N 1 j 1 1 n o x2 (t + 1) = f σ2 (t) xj (t) j ∈ N σ2 (t) 2 2 .. . n o xn (t + 1) = fnσn (t) xj (t) j ∈ Nnσn (t) (1) xi ∈ D := {0, 1}; σi (t) ∈ DNi := {0, 1, · · · , Ni − 1}, i ∈ [1 : n], are random switching sequences; and fij , i ∈ [1 : n], j ∈ DNi , are Boolean functionsoof their n respective neighbouring nodes xk (t) k ∈ Nij . 7 / 115 + Constituent networks (or contexts, subnetworks) K := σ1 σ2 ··· σn−1 σn 0 0 .. . 0 0 .. . ··· ··· 0 0 .. . 0 1 .. . 0 0 0 .. . 0 0 0 .. . 0 .. . 0 .. . ··· ··· ··· ··· ··· ··· ··· N1 − 1 N2 − 1 · · · 0 Nn − 1 1 0 1 1 .. .. . . 1 Nn − 1 .. .. . . Nn−1 − 1 Nn − 1 (Πn N )×n i=1 i The jth row from bottom defines the jth subnetwork Σj There are N := Πni=1 Ni subnetworks in total. 8 / 115 + Basic assumptions15 : σi (t), i ∈ [1 : n], are mutually independent; σi (t) is independent and identically distributed, P{σi (t) = j} = pji , i ∈ [1 : n], j ∈ [0 : Ni − 1] + Selection probabilities of constituent networks P{σ1 (t) = j1 , · · · , σn (t) = jn } = pj11 · · · pjnn + Under the basic assumptions, a PBN is essentially a finite-state homogenous Markovian chain. Thus the stability of a PBN is completely determined by its state transition probabilities. 15 A PBN does not necessarily satisfy these assumptions, such as context-sensitive PBNs and Markovian switching PBNs. 9 / 115 + The vector-form of a logic variable α ∈ Dm is defined as δmm−α := Colm−α (Im ). Then, fij (x1 , x2 , · · · , xn ) = Li,j x1 x2 · · · xn Thus, in the vector-form, the PBN becomes x1 (t + 1) = L1 n σ1 (t) n x1 (t) n x2 (t) n · · · n xn (t) x2 (t + 1) = L2 n σ2 (t) n x1 (t) n x2 (t) n · · · n xn (t) .. . x (t + 1) = L n σ (t) n x (t) n x (t) n · · · n x (t) n n n 1 2 n (2) where Li = [Li,Ni −1 , Li,Ni −2 , · · · , Li,1 , Li,0 ] 10 / 115 + Define x(t) = x1 (t) n x2 (t) n · · · n xn (t) σ(t) = σ1 (t) n σ2 (t) n · · · n σn (t) The PBN becomes x(t + 1) = L n σ(t) n x(t) where L is a logic matrix; σ(t) ∈ ∆N is an independent and identically distributed (i.i.d.) random sequences with P{σ(t) = δNj } = P {The jth subnetwork Σj is selected} 11 / 115 + Transitional Probability Matrix (TPM) P 16 n o j i [P]i,j := P x(t + 1) = δ2n x(t) = δ2n [P]i,j ≥ 0, X [P]i,j = 1 i Define the probability distribution vector (PDV) of σ as [pσ ]j = P{σ(t) = δNj }. Then, P = L n pσ 16 Conventionally, the TPM is defined as P> 12 / 115 + State Transfer Graph (STG): The STG of a PBN is a weighted directed graph (N , E, W) where N =n∆2n is the set of nodes; o E = (δ2j n , δ2i n ) [P]i,j > 0 is the set of directed edges; W : E → (0, 1], (δ2j n , δ2i n ) 7→ [P]i,j , is the weight of edge. Example 0.3 0.6 0.3 0 0.5 0.4 0 0.5 0.5 P= 0 0 0.2 0 0 0.7 0.3 0 0.6 δ41 δ42 0.4 0.7 0.5 0.5 0.5 δ44 0.3 δ43 0.2 13 / 115 + An Example: Consider a simplified apoptosis network [Kobayashi & Hiraish (2011)17 ] σ1 (t) x1 (t + 1) = f1 (x1 (t), x2 (t)) σ (t) x2 (t + 1) = f2 2 (x1 (t), x2 (t), x3 (t)) x (t + 1) = f σ3 (t) (x (t), x (t)) 3 1 2 3 (3) x1 (t), x2 (t), and x3 (t) represent the concentration level of the inhibitor of apoptosis proteins, active caspase3, and active caspase-8, respectively. The switching signals σj (t) ∈ {0, 1}, j = 1, 2, 3, are i.i.d. processes where f10 = x1 (t), f11 = ¬x1 (t) ∧ x2 (t), f20 = ¬x1 (t) ∧ x3 (t), f21 = x1 (t) ∧ x2 (t), f30 = x2 (t), f31 = x1 (t) ∧ x2 (t) 17 Koichi Kobayashi and Kunihiko Hiraishi. “An integer programming approach to optimal control problems in contextsensitive probabilistic Boolean networks”. In: Automatica 47.6 (2011), pp. 1260–1264. 14 / 115 Algebraic Form: x(t + 1) = L n σ(t) n x(t) L = [L1 , L2 , L3 , L4 , L5 , L6 , L7 , L8 ] x(t) = x1 (t) n x2 (t) n x3 (t) σ(t) = σ1 (t) n σ2 (t) n σ3 (t) L1 = δ8 [3 3 4 4 5 7 6 8], L3 = δ8 [1 1 4 4 7 7 8 8], L5 = δ8 [7 7 8 8 1 3 6 8], L7 = δ8 [5 5 8 8 3 3 8 8], L2 = δ8 [3 3 4 4 6 8 6 8], L4 = δ8 [1 1 4 4 8 8 8 8], L6 = δ8 [7 7 8 8 2 4 6 8], L8 = δ8 [5 5 8 8 4 4 8 8] 15 / 115 Selection probabilities: P(σi (t) = j) = pji , i = 1, 2, 3, j = 0, 1 p01 = 0.4, p11 = 0.6 p02 = 0.7, p12 = 0.3 p03 = 0.2, p13 = 0.8. For any j, decompose δ8j as δ8j = δ2j1 n δ2j2 n δ2j3 . Then, [pσ ]j = P{σ(t) = δ8j } = P{σ1 (t) = δ2j1 , σ2 (t) = δ2j2 , σ2 (t) = δ2j3 } = pj11 pj22 pj33 ⇓ pσ = 0.01 × [5.6 22.4 2.4 9.6 8.4 33.6 3.6 14.4]> . 16 / 115 The TPM: σ P = Lnp = 8 X [pσ ]j Lj j=1 0.12 0 0.28 0 = 0.18 0 0.42 0 0.12 0 0 0 0 0 0.28 0 0 0 0.4 0.4 0.18 0 0 0 0 0 0.42 0 0 0 0.6 0.6 0.084 0.336 0.036 0.144 0.056 0.224 0.024 0.096 0 0 0 0 0 0 0.12 0 0 0.48 0 0 . 0 0 0 0 0.7 0 0.08 0 0 0.32 0.3 1 17 / 115 + Accessibility and Communicate State δ2j n is accessible from state δ2i n , denote by i → j, if n o P x(t) = δ2j n , for some t ≥ 1 x(0) = δ2i n > 0 Two states δ2i n and δ2j n that are accessible to each other are said to communicate, denote by i ↔ j. Lemma For any i 6= j, the following statements are equivalent: δ2i n → δ2j n ; [Pt ]j,i > 0 for some t with 1 ≤ t ≤ 2n − 1; There is a path from δ2i n to δ2j n in the STG. 18 / 115 + Accessibility and Communicate State δ2j n is accessible from state δ2i n , denote by i → j, if n o P x(t) = δ2j n , for some t ≥ 1 x(0) = δ2i n > 0 Two states δ2i n and δ2j n that are accessible to each other are said to communicate, denote by i ↔ j. Lemma For any i 6= j, the following statements are equivalent: δ2i n → δ2j n ; [Pt ]j,i > 0 for some t with 1 ≤ t ≤ 2n − 1; There is a path from δ2i n to δ2j n in the STG. 18 / 115 + Recurrent States A state δ2j n is said to be recurrent if n o P x(t) = δ2j n for some t ≥ 1 x(0) = δ2j n = 1. Lemma δ2i n → δ2j n and δ2i n is recurrent. ⇓ δ2i n ↔ δ2j n and δ2j n is recurrent. 19 / 115 + Recurrent States A state δ2j n is said to be recurrent if n o P x(t) = δ2j n for some t ≥ 1 x(0) = δ2j n = 1. Lemma δ2i n → δ2j n and δ2i n is recurrent. ⇓ δ2i n ↔ δ2j n and δ2j n is recurrent. 19 / 115 + Invariant Set (or Closed Set) A subset C ⊂ ∆2n is called an invariant subset if P x(t + 1) ∈ C x(t) ∈ C = 1. A subset C ⊂ ∆2n is invariant if and only if n o X [P]i,j = 1 ∀j ∈ idx(C) := j δ2j n ∈ C i∈idx(C) Lemma The transition probability from any state to an invariant subset is increasing with time. 20 / 115 + Invariant Set (or Closed Set) A subset C ⊂ ∆2n is called an invariant subset if P x(t + 1) ∈ C x(t) ∈ C = 1. A subset C ⊂ ∆2n is invariant if and only if n o X [P]i,j = 1 ∀j ∈ idx(C) := j δ2j n ∈ C i∈idx(C) Lemma The transition probability from any state to an invariant subset is increasing with time. 20 / 115 + The Largest Invariant Subset The union of two invariant subsets is still invariant. The union of all invariant subsets contained in M is referred to as the largest invariant subset in M, denoted by I(M). Proposition Suppose that M = {δ2j n j ∈ Λ0 }, where Λ0 ⊆ [1 : 2n ]. We define a sequence of subsets of indices as follows: X Λs = j ∈ Λs−1 [P]i,j = 1 , s = 1, 2, · · · . i∈Λs−1 Then, there must exist an integer k ≤ |M| such that Λk = Λk−1 . In addition, it holds that I(M) = {δ2j n j ∈ Λk }. 21 / 115 + The Largest Invariant Subset The union of two invariant subsets is still invariant. The union of all invariant subsets contained in M is referred to as the largest invariant subset in M, denoted by I(M). Proposition Suppose that M = {δ2j n j ∈ Λ0 }, where Λ0 ⊆ [1 : 2n ]. We define a sequence of subsets of indices as follows: X Λs = j ∈ Λs−1 [P]i,j = 1 , s = 1, 2, · · · . i∈Λs−1 Then, there must exist an integer k ≤ |M| such that Λk = Λk−1 . In addition, it holds that I(M) = {δ2j n j ∈ Λk }. 21 / 115 + Probabilistic Boolean Control Network (PBCN) σ (t) x1 (t + 1) = f1 1 (u1 (t), · · · , um (t), x1 (t), · · · , xn (t)) x (t + 1) = f σ2 (t) (u (t), · · · , u (t), x (t), · · · , x (t)) 2 1 m 1 n 2 . .. σ (t) xn (t + 1) = fn n (u1 (t), · · · , um (t), x1 (t), · · · , xn (t))) ⇓ x(t + 1) = L n σ(t) n u(t) n x(t) TPMs P = L n pσ Pj = L n pσ n δ2j m Note: Pj is the TPM when u(t) ≡ δ2j m 22 / 115 + Closed-loop TPM: K ∈ L2m ×2n u(t) = Kx(t), ⇓ x(t + 1) = L n σ(t) n u(t) n x(t) = L n σ(t) n K n x(t) n x(t) = L n σ(t) n KΦn x(t) Φn : Power-reducing Matrix ⇓ PK = (L n pσ )KΦn . 23 / 115 + Reachability xd is said to be k-step reachable from x0 if there is a control sequence u = {u(t)} such that P{x(k; x0 , u) = xd } > 0. xd is said to be reachable from x0 (denoted by x0 → xd ) if there is a control sequence u = {u(t)} such that P{x(t; x0 , u) = xd for some t ≥ 1} > 0. xd is reachable from x0 if and only if xd is k-step reachable from x0 for some k ≤ 2n − 1. 24 / 115 Reachability Matrix R= n −1 2X (P n 12m )k k=1 Proposition δ2i n → δ2j n ⇔ [R]j,i > 0 Sketchy Proof: (P n 12m )k = (P1 + P2 + · · · + P2m )k X = Pik−1 · · · Pi1 Pi0 all possible combinations h i Thus, (P n 12m )k > 0 if and only if xd is k-step reachable j,i from x0 . 25 / 115 + Control Invariant Subsets A subset C ⊆ ∆2n is called a control invariant subset if, for any state x0 ∈ C, there exists a control u0 ∈ ∆2m such that P{x(t + 1) ∈ C x(t) = x0 } = 1. (4) The union of any two control invariant subsets is still control invariant. The union of all control invariant subsets contained in a given subset M ⊆ ∆2n is termed as the largest control invariant subset contained in M and is denoted by Ic (M). If C = {xe } is control invariant, then, xe is called a control fixed point. 26 / 115 Proposition Suppose that M0 = {δ2i n |i ∈ Λ0 }. A sequence of index sets Λs , s ∈ Z+ , is defined as X m Λs = j ∈ Λs−1 ∃k ∈ [1 : 2 ], s.t. [Pk ]i,j = 1 . i∈Λs−1 Subsequently, there must exist a positive integer η 6 |M0 | such that Λη = Λη+1 . Additionally, Ic (M0 ) = {δ2j n |j ∈ Λη } holds. 27 / 115 Outline 1 Basic Concepts of PBNs 2 Stability Analysis of PBNs Finite-time Stability Asymptotical Stability 3 Feedback Stabilization of PBNs Fintie-time Feedback Stabilization Asymptotical Feedback Stabilization 4 Controllability of PBNs 5 Observability of PBNs 6 Questions 28 / 115 II. Stability Analysis of PBNs + Consider a PBN x(t + 1) = L n σ(t) n x(t) x(t) ∈ ∆2n is the state; L ∈ L2n ×N2m is a logic matrix, L = [L1 , L2 , · · · , LN ]; σ(t) ∈ ∆N is an i.i.d. random sequence with a PDV pσ . The TPM is P = L n pσ . 29 / 115 Outline 1 Basic Concepts of PBNs 2 Stability Analysis of PBNs Finite-time Stability Asymptotical Stability 3 Feedback Stabilization of PBNs Fintie-time Feedback Stabilization Asymptotical Feedback Stabilization 4 Controllability of PBNs 5 Observability of PBNs 6 Questions 30 / 115 II.1 Finite-time Stability Definition (Finite-time Stability (FTS)) A state xe ∈ ∆2n is said to be finite-time stable if there is a positive integer T such that P{x(t) = xe x(0) = x0 } = 1 ∀t ≥ T, ∀x0 ∈ ∆2n . [Li, Yang, & Chu (2014)a ] a Rui Li, Meng Yang, and Tianguang Chu. “State feedback stabilization for probabilistic Boolean networks”. In: Automatica 50.4 (2014), pp. 1272–1278. 31 / 115 Definition (Finite-time Set Stability) A subset M ⊂ ∆2n is said to be finite-time stable if there is a positive integer T such that P{x(t) ∈ M x(0) = x0 } = 1 ∀t ≥ T, ∀x0 ∈ ∆2n . [Li, Yang, & Chu (2016)a ] a Li Rui, Yang Meng, and Chu Tianguang. “VÇÙ pp. 371–380. ä 8Ü ½››”. In: XډƆêÆ 36.3 (2016), + Typical Set Stability Problems: Synchronization of networks Node Synchronization Output Tracking 32 / 115 Definition (Finite-time Set Stability) A subset M ⊂ ∆2n is said to be finite-time stable if there is a positive integer T such that P{x(t) ∈ M x(0) = x0 } = 1 ∀t ≥ T, ∀x0 ∈ ∆2n . [Li, Yang, & Chu (2016)a ] a Li Rui, Yang Meng, and Chu Tianguang. “VÇÙ pp. 371–380. ä 8Ü ½››”. In: XډƆêÆ 36.3 (2016), + Typical Set Stability Problems: Synchronization of networks Node Synchronization Output Tracking 32 / 115 + Criterion of FT Stability in terms of TPM Theorem A PBN is finite-time stable with respect to xe if and only if n Col P2 −1 = {xe } (5) Sketchy Proof:(Necessity) FT stability ⇒ xe is a fixed point, and the solution from any initial state reaches xe with 2n − 1 steps. ⇒ (5) (Sufficiency) (5) ⇒ n n Pxe = P2 x0 = P2 −1 (Px0 ) = [xe , · · · , xe ](Px0 ) = xe ⇒ xe is a fixed point⇒ For any t ≥ 2n , any x0 , P{x(t) = xe x(0) = x0 } ≥ P{x(2n − 1) = xe x(0) = x0 } = 1 ⇒ FT stability 33 / 115 + Criterion of FT Stability in terms of TPM Theorem A PBN is finite-time stable with respect to xe if and only if n Col P2 −1 = {xe } (5) Sketchy Proof:(Necessity) FT stability ⇒ xe is a fixed point, and the solution from any initial state reaches xe with 2n − 1 steps. ⇒ (5) (Sufficiency) (5) ⇒ n n Pxe = P2 x0 = P2 −1 (Px0 ) = [xe , · · · , xe ](Px0 ) = xe ⇒ xe is a fixed point⇒ For any t ≥ 2n , any x0 , P{x(t) = xe x(0) = x0 } ≥ P{x(2n − 1) = xe x(0) = x0 } = 1 ⇒ FT stability 33 / 115 + Criterion of FT Stability in terms of TPM Theorem A PBN is finite-time stable with respect to xe if and only if n Col P2 −1 = {xe } (5) Sketchy Proof:(Necessity) FT stability ⇒ xe is a fixed point, and the solution from any initial state reaches xe with 2n − 1 steps. ⇒ (5) (Sufficiency) (5) ⇒ n n Pxe = P2 x0 = P2 −1 (Px0 ) = [xe , · · · , xe ](Px0 ) = xe ⇒ xe is a fixed point⇒ For any t ≥ 2n , any x0 , P{x(t) = xe x(0) = x0 } ≥ P{x(2n − 1) = xe x(0) = x0 } = 1 ⇒ FT stability 33 / 115 + Criterion of FT Stability in terms of TPM Theorem A PBN is finite-time stable with respect to xe if and only if n Col P2 −1 = {xe } (5) Sketchy Proof:(Necessity) FT stability ⇒ xe is a fixed point, and the solution from any initial state reaches xe with 2n − 1 steps. ⇒ (5) (Sufficiency) (5) ⇒ n n Pxe = P2 x0 = P2 −1 (Px0 ) = [xe , · · · , xe ](Px0 ) = xe ⇒ xe is a fixed point⇒ For any t ≥ 2n , any x0 , P{x(t) = xe x(0) = x0 } ≥ P{x(2n − 1) = xe x(0) = x0 } = 1 ⇒ FT stability 33 / 115 + Criterion of FT Stability in terms of TPM Theorem A PBN is finite-time stable with respect to xe if and only if n Col P2 −1 = {xe } (5) Sketchy Proof:(Necessity) FT stability ⇒ xe is a fixed point, and the solution from any initial state reaches xe with 2n − 1 steps. ⇒ (5) (Sufficiency) (5) ⇒ n n Pxe = P2 x0 = P2 −1 (Px0 ) = [xe , · · · , xe ](Px0 ) = xe ⇒ xe is a fixed point⇒ For any t ≥ 2n , any x0 , P{x(t) = xe x(0) = x0 } ≥ P{x(2n − 1) = xe x(0) = x0 } = 1 ⇒ FT stability 33 / 115 + Criterion of FT Stability in terms of TPM Theorem A PBN is finite-time stable with respect to xe if and only if n Col P2 −1 = {xe } (5) Sketchy Proof:(Necessity) FT stability ⇒ xe is a fixed point, and the solution from any initial state reaches xe with 2n − 1 steps. ⇒ (5) (Sufficiency) (5) ⇒ n n Pxe = P2 x0 = P2 −1 (Px0 ) = [xe , · · · , xe ](Px0 ) = xe ⇒ xe is a fixed point⇒ For any t ≥ 2n , any x0 , P{x(t) = xe x(0) = x0 } ≥ P{x(2n − 1) = xe x(0) = x0 } = 1 ⇒ FT stability 33 / 115 + Criterion of FT Stability in terms of TPM Theorem A PBN is finite-time stable with respect to xe if and only if n Col P2 −1 = {xe } (5) Sketchy Proof:(Necessity) FT stability ⇒ xe is a fixed point, and the solution from any initial state reaches xe with 2n − 1 steps. ⇒ (5) (Sufficiency) (5) ⇒ n n Pxe = P2 x0 = P2 −1 (Px0 ) = [xe , · · · , xe ](Px0 ) = xe ⇒ xe is a fixed point⇒ For any t ≥ 2n , any x0 , P{x(t) = xe x(0) = x0 } ≥ P{x(2n − 1) = xe x(0) = x0 } = 1 ⇒ FT stability 33 / 115 + Criterion of FT Stability in terms of TPM Theorem A PBN is finite-time stable with respect to xe if and only if n Col P2 −1 = {xe } (5) Sketchy Proof:(Necessity) FT stability ⇒ xe is a fixed point, and the solution from any initial state reaches xe with 2n − 1 steps. ⇒ (5) (Sufficiency) (5) ⇒ n n Pxe = P2 x0 = P2 −1 (Px0 ) = [xe , · · · , xe ](Px0 ) = xe ⇒ xe is a fixed point⇒ For any t ≥ 2n , any x0 , P{x(t) = xe x(0) = x0 } ≥ P{x(2n − 1) = xe x(0) = x0 } = 1 ⇒ FT stability 33 / 115 + Criterion of FT Stability in terms of STG18 P{x(t) = xe x(0) = x0 } = 1 ∀t ≥ T, ∀x0 ∈ ∆2n . m (i) xe is a fixed point (ii) x0 → xe ∀x0 (iii) The paths from any x0 to xe in G \ (xe , xe ) is bounded m G \ (xe , xe ) is acyclic Note: G \ (xe , xe ) is the graph obtained from the STG G of the PBN by removing the self-loop of xe 18 Shiyong Zhu, Jianquan Lu, and Daniel W.C.Ho. “Finite-time Stability of Probabilistic Logical Networks: A Topological Sorting Approach”. In: IEEE Transactions on Circuits & Systems -II: Express Briefs 67.4 (2020), pp. 695– 699. 34 / 115 + Criterion of FT Stability in terms of STG18 P{x(t) = xe x(0) = x0 } = 1 ∀t ≥ T, ∀x0 ∈ ∆2n . m (i) xe is a fixed point (ii) x0 → xe ∀x0 (iii) The paths from any x0 to xe in G \ (xe , xe ) is bounded m G \ (xe , xe ) is acyclic Note: G \ (xe , xe ) is the graph obtained from the STG G of the PBN by removing the self-loop of xe 18 Shiyong Zhu, Jianquan Lu, and Daniel W.C.Ho. “Finite-time Stability of Probabilistic Logical Networks: A Topological Sorting Approach”. In: IEEE Transactions on Circuits & Systems -II: Express Briefs 67.4 (2020), pp. 695– 699. 34 / 115 + Criterion of FT Stability in terms of STG18 P{x(t) = xe x(0) = x0 } = 1 ∀t ≥ T, ∀x0 ∈ ∆2n . m (i) xe is a fixed point (ii) x0 → xe ∀x0 (iii) The paths from any x0 to xe in G \ (xe , xe ) is bounded m G \ (xe , xe ) is acyclic Note: G \ (xe , xe ) is the graph obtained from the STG G of the PBN by removing the self-loop of xe 18 Shiyong Zhu, Jianquan Lu, and Daniel W.C.Ho. “Finite-time Stability of Probabilistic Logical Networks: A Topological Sorting Approach”. In: IEEE Transactions on Circuits & Systems -II: Express Briefs 67.4 (2020), pp. 695– 699. 34 / 115 + Criterion of FT Stability in terms of STG18 P{x(t) = xe x(0) = x0 } = 1 ∀t ≥ T, ∀x0 ∈ ∆2n . m (i) xe is a fixed point (ii) x0 → xe ∀x0 (iii) The paths from any x0 to xe in G \ (xe , xe ) is bounded m G \ (xe , xe ) is acyclic Note: G \ (xe , xe ) is the graph obtained from the STG G of the PBN by removing the self-loop of xe 18 Shiyong Zhu, Jianquan Lu, and Daniel W.C.Ho. “Finite-time Stability of Probabilistic Logical Networks: A Topological Sorting Approach”. In: IEEE Transactions on Circuits & Systems -II: Express Briefs 67.4 (2020), pp. 695– 699. 34 / 115 0.3 7 6 0.3 7 0.6 0.4 0.7 0.6 3 0.5 4 0.2 0.3 0.6 1 1 0.5 1 0.7 0.5 4 5 0.5 0.4 2 0.4 5 3 0.4 6 2 0.2 0.6 0.3 0.5 1 1 0.5 1 8 8 1 STG G G \ (xe , xe ) 35 / 115 Theorem A PBN is finite-time stable with respect to xe if and only if G \ (xe , xe ) is acyclic. [Zhu, Lu, W.C.Ho (2020)a ] a Shiyong Zhu, Jianquan Lu, and Daniel W.C.Ho. “Finite-time Stability of Probabilistic Logical Networks: A Topological Sorting Approach”. In: IEEE Transactions on Circuits & Systems -II: Express Briefs 67.4 (2020), pp. 695– 699. 36 / 115 + Finite-time Set Stability Finite-time stability w.r.t. M ⇔ Finite-time stability w.r.t. the largest invariant subset in M, denoted by I(M) n ⇔ Col{P2 −|I(M)| } ⊆ I(M) ⇔ I(M) 6= ∅ and the STG has no cycles outside I(M). 37 / 115 The STG of a PBN that is finite-time stable w.r.t. M 38 / 115 Outline 1 Basic Concepts of PBNs 2 Stability Analysis of PBNs Finite-time Stability Asymptotical Stability 3 Feedback Stabilization of PBNs Fintie-time Feedback Stabilization Asymptotical Feedback Stabilization 4 Controllability of PBNs 5 Observability of PBNs 6 Questions 39 / 115 II.2 Asymptotical Stability 3 0.5 0 0 P= 0.2 0.8 0.5 0.2 2 1 0.8 1 0 0.5 0 0 0.5 0 0 0 0 1 0 1 lim P{x(t) = δ44 x(0) = x0 } t→∞ 4 = lim [Pt x0 ]4 = 1 t→∞ 1 STG of a PBN that is not FT stable 40 / 115 II.2 Asymptotical Stability 3 0.5 0 0 P= 0.2 0.8 0.5 0.2 2 1 0.8 1 0 0.5 0 0 0.5 0 0 0 0 1 0 1 lim P{x(t) = δ44 x(0) = x0 } t→∞ 4 = lim [Pt x0 ]4 = 1 t→∞ 1 STG of a PBN that is not FT stable 40 / 115 II.2 Asymptotical Stability 3 0.5 0 0 P= 0.2 0.8 0.5 0.2 2 1 0.8 1 0 0.5 0 0 0.5 0 0 0 0 1 0 1 lim P{x(t) = δ44 x(0) = x0 } t→∞ 4 = lim [Pt x0 ]4 = 1 t→∞ 1 STG of a PBN that is not FT stable 40 / 115 Definition (Stability with Probability One (SPO)) A state xe ∈ ∆2n is said to be stable with probability one if n o P lim x(t) = xe x(0) = x0 = 1 ∀x0 ∈ ∆2n . t→∞ [Zhao & Cheng (2014)a ] a Yin Zhao and Daizhan Cheng. “On controllability and stabilizability of probabilistic Boolean control networks”. In: Science China Information Sciences 57.1 (2014), pp. 1–14. 41 / 115 Definition (Stability in Stochastic Sense (SSS)) A state xe ∈ ∆2n is said to be stable in stochastic sense if lim Ex(t; x0 ) = xe t→∞ ∀x0 ∈ ∆2n . [Meng, Liu, & Feng(2017)a ] a Min Meng, Lu Liu, and Gang Feng. “Stability and l1 gain analysis of Boolean networks with Markovian jump parameters”. In: IEEE Transactions on Automatic Control 62.8 (2017), pp. 4222–4228. 42 / 115 Definition (Stability in Distribution (SD)) A state xe ∈ ∆2n is said to be stable in distribution if lim P x(t) = xe x(0) = x0 = 1 ∀x0 ∈ ∆2n . t→∞ [Guo, Zhou, Wu, Gui, & Yang(2019)a ] a Yuqian Guo et al. “Stability and Set Stability in Distribution of Probabilistic Boolean Networks”. In: IEEE Transactions on Automatic Control 64 (2 2019), pp. 736–742. + These three definitions of stability are equivalent, as shown latter. + The concept of stability in distribution is easily generalized to set stability. 43 / 115 Definition (Stability in Distribution (SD)) A state xe ∈ ∆2n is said to be stable in distribution if lim P x(t) = xe x(0) = x0 = 1 ∀x0 ∈ ∆2n . t→∞ [Guo, Zhou, Wu, Gui, & Yang(2019)a ] a Yuqian Guo et al. “Stability and Set Stability in Distribution of Probabilistic Boolean Networks”. In: IEEE Transactions on Automatic Control 64 (2 2019), pp. 736–742. + These three definitions of stability are equivalent, as shown latter. + The concept of stability in distribution is easily generalized to set stability. 43 / 115 Definition (Stability in Distribution (SD)) A state xe ∈ ∆2n is said to be stable in distribution if lim P x(t) = xe x(0) = x0 = 1 ∀x0 ∈ ∆2n . t→∞ [Guo, Zhou, Wu, Gui, & Yang(2019)a ] a Yuqian Guo et al. “Stability and Set Stability in Distribution of Probabilistic Boolean Networks”. In: IEEE Transactions on Automatic Control 64 (2 2019), pp. 736–742. + These three definitions of stability are equivalent, as shown latter. + The concept of stability in distribution is easily generalized to set stability. 43 / 115 1 3 4 0.3 0.2 0.5 The limitations 1 1 lim x(t), 2 t→∞ lim Ex(t) t→∞ 1 0 1 P= 0 0 1 0 0 0 0 0.5 0 0.2 0 0.3 1 0 do not exist; However, for any x0 , lim P x(t) ∈ M x(0) = x0 = 1 t→∞ M = {δ41 , δ42 } 44 / 115 1 3 4 0.3 0.2 0.5 The limitations 1 1 lim x(t), 2 t→∞ lim Ex(t) t→∞ 1 0 1 P= 0 0 1 0 0 0 0 0.5 0 0.2 0 0.3 1 0 do not exist; However, for any x0 , lim P x(t) ∈ M x(0) = x0 = 1 t→∞ M = {δ41 , δ42 } 44 / 115 Definition (Set Stability in Distribution (SSD)) A subset M ⊂ ∆2n is said to be stable in distribution if lim P x(t) ∈ M x(0) = x0 = 1 ∀x0 ∈ ∆2n . t→∞ [Guo, Zhou, Wu, Gui, & Yang(2019)a ] a Yuqian Guo et al. “Stability and Set Stability in Distribution of Probabilistic Boolean Networks”. In: IEEE Transactions on Automatic Control 64 (2 2019), pp. 736–742. 45 / 115 + Criterion of Stability with Probability One19 n o P lim x(t) = xe x(0) = x0 = 1 ∀x0 ∈ ∆2n . t→∞ m xe is a fixed point.(Thus, it is recurrent) x0 → xe ∀x0 .(Thus, it is the unique recurrent state) m point. xe is a fixed ! n −1 2X Pk 0 Rowi (where xe = δ2i n ) k=1 19 Yin Zhao and Daizhan Cheng. “On controllability and stabilizability of probabilistic Boolean control networks”. In: Science China Information Sciences 57.1 (2014), pp. 1–14. 46 / 115 + Criterion of Stability with Probability One19 n o P lim x(t) = xe x(0) = x0 = 1 ∀x0 ∈ ∆2n . t→∞ m xe is a fixed point.(Thus, it is recurrent) x0 → xe ∀x0 .(Thus, it is the unique recurrent state) m point. xe is a fixed ! n −1 2X Pk 0 (where xe = δ2i n ) Rowi k=1 19 Yin Zhao and Daizhan Cheng. “On controllability and stabilizability of probabilistic Boolean control networks”. In: Science China Information Sciences 57.1 (2014), pp. 1–14. 46 / 115 + Criterion of Stability with Probability One19 n o P lim x(t) = xe x(0) = x0 = 1 ∀x0 ∈ ∆2n . t→∞ m xe is a fixed point.(Thus, it is recurrent) x0 → xe ∀x0 .(Thus, it is the unique recurrent state) m point. xe is a fixed ! n −1 2X Pk 0 (where xe = δ2i n ) Rowi k=1 19 Yin Zhao and Daizhan Cheng. “On controllability and stabilizability of probabilistic Boolean control networks”. In: Science China Information Sciences 57.1 (2014), pp. 1–14. 46 / 115 + Criterion of Stability with Probability One19 n o P lim x(t) = xe x(0) = x0 = 1 ∀x0 ∈ ∆2n . t→∞ m xe is a fixed point.(Thus, it is recurrent) x0 → xe ∀x0 .(Thus, it is the unique recurrent state) m point. xe is a fixed ! n −1 2X Pk 0 (where xe = δ2i n ) Rowi k=1 19 Yin Zhao and Daizhan Cheng. “On controllability and stabilizability of probabilistic Boolean control networks”. In: Science China Information Sciences 57.1 (2014), pp. 1–14. 46 / 115 + Criterion of Stability with Probability One19 n o P lim x(t) = xe x(0) = x0 = 1 ∀x0 ∈ ∆2n . t→∞ m xe is a fixed point.(Thus, it is recurrent) x0 → xe ∀x0 .(Thus, it is the unique recurrent state) m point. xe is a fixed ! n −1 2X Pk 0 (where xe = δ2i n ) Rowi k=1 19 Yin Zhao and Daizhan Cheng. “On controllability and stabilizability of probabilistic Boolean control networks”. In: Science China Information Sciences 57.1 (2014), pp. 1–14. 46 / 115 + Criterion of Stability with Probability One19 n o P lim x(t) = xe x(0) = x0 = 1 ∀x0 ∈ ∆2n . t→∞ m xe is a fixed point.(Thus, it is recurrent) x0 → xe ∀x0 .(Thus, it is the unique recurrent state) m point. xe is a fixed ! n −1 2X Pk 0 (where xe = δ2i n ) Rowi k=1 19 Yin Zhao and Daizhan Cheng. “On controllability and stabilizability of probabilistic Boolean control networks”. In: Science China Information Sciences 57.1 (2014), pp. 1–14. 46 / 115 + Criterion of Stability with Probability One19 n o P lim x(t) = xe x(0) = x0 = 1 ∀x0 ∈ ∆2n . t→∞ m xe is a fixed point.(Thus, it is recurrent) x0 → xe ∀x0 .(Thus, it is the unique recurrent state) m point. xe is a fixed ! n −1 2X Pk 0 (where xe = δ2i n ) Rowi k=1 19 Yin Zhao and Daizhan Cheng. “On controllability and stabilizability of probabilistic Boolean control networks”. In: Science China Information Sciences 57.1 (2014), pp. 1–14. 46 / 115 + Criterion of Stability with Probability One19 n o P lim x(t) = xe x(0) = x0 = 1 ∀x0 ∈ ∆2n . t→∞ m xe is a fixed point.(Thus, it is recurrent) x0 → xe ∀x0 .(Thus, it is the unique recurrent state) m point. xe is a fixed ! n −1 2X Pk 0 (where xe = δ2i n ) Rowi k=1 19 Yin Zhao and Daizhan Cheng. “On controllability and stabilizability of probabilistic Boolean control networks”. In: Science China Information Sciences 57.1 (2014), pp. 1–14. 46 / 115 Theorem A PBN is asymptotically stable w.r.t. xe = δ2i n with probability one if and only if xe is a fixed point and ! n −1 2X (6) Rowi Pk 0 k=1 [Zhao & Cheng (2014)a ] a Yin Zhao and Daizhan Cheng. “On controllability and stabilizability of probabilistic Boolean control networks”. In: Science China Information Sciences 57.1 (2014), pp. 1–14. Note: Condition (6) can be replaced by n Rowi P2 −1 0 because the transition probability from any state to a fixed point is nondecreasing. 47 / 115 Theorem A PBN is asymptotically stable w.r.t. xe = δ2i n with probability one if and only if xe is a fixed point and ! n −1 2X (6) Rowi Pk 0 k=1 [Zhao & Cheng (2014)a ] a Yin Zhao and Daizhan Cheng. “On controllability and stabilizability of probabilistic Boolean control networks”. In: Science China Information Sciences 57.1 (2014), pp. 1–14. Note: Condition (6) can be replaced by n Rowi P2 −1 0 because the transition probability from any state to a fixed point is nondecreasing. 47 / 115 + Criterion of asymptotical stability in distribution A Necessary Condition: lim P x(t) = xe x(0) = x0 = 1 t→∞ ∀x0 ∈ ∆2n . ⇓ xe is a fixed point. x0 → xe ∀x0 It is also sufficient. 48 / 115 + Criterion of asymptotical stability in distribution A Necessary Condition: lim P x(t) = xe x(0) = x0 = 1 t→∞ ∀x0 ∈ ∆2n . ⇓ xe is a fixed point. x0 → xe ∀x0 It is also sufficient. 48 / 115 Sketchy Proof of Sufficiency. lim P x(t) = xe x(0) = x0 = 1 t→∞ lim Pt = t→∞ 0(2n −1)×2n 1T2n m ∀x0 ∈ ∆2n . n (Assume xe = δ22n ) m lim α(t) = 12n −1 , t→∞ where Pt := ΓT (t) 0(2n −1)×1 αT (t) 1 . m lim α(2n t) = 12n −1 t→∞ (By Monotonicity) 49 / 115 P(2n (t + 1)) = P(2n t)P(2n ) xe is a fixed point. x0 → xe ∀x0 ⇓ n ⇓ n n n α(2 (t+1)) = Γ(2 )α(2 t)+α(2 ). ⇓ α(2n ) 0 ⇓ η(t + 1) = Γ(2n )η(t) Γ(2n ) is strictly Schur stable η(t) := α(2n t) − 12n −1 | {z } ⇓ lim η(t) = 0 t→∞ ⇓ lim α(t) = 12n −1 t→∞ 50 / 115 P(2n (t + 1)) = P(2n t)P(2n ) xe is a fixed point. x0 → xe ∀x0 ⇓ n ⇓ n n n α(2 (t+1)) = Γ(2 )α(2 t)+α(2 ). ⇓ α(2n ) 0 ⇓ η(t + 1) = Γ(2n )η(t) Γ(2n ) is strictly Schur stable η(t) := α(2n t) − 12n −1 | {z } ⇓ lim η(t) = 0 t→∞ ⇓ lim α(t) = 12n −1 t→∞ 50 / 115 P(2n (t + 1)) = P(2n t)P(2n ) xe is a fixed point. x0 → xe ∀x0 ⇓ n ⇓ n n n α(2 (t+1)) = Γ(2 )α(2 t)+α(2 ). ⇓ α(2n ) 0 ⇓ η(t + 1) = Γ(2n )η(t) Γ(2n ) is strictly Schur stable η(t) := α(2n t) − 12n −1 | {z } ⇓ lim η(t) = 0 t→∞ ⇓ lim α(t) = 12n −1 t→∞ 50 / 115 Theorem A PBN is asymptotically stable w.r.t. xe in distribution if and only if xe is a fixed point. x0 → xe ∀x0 . Or, equivalently, xe is a fixed point and n Rowi P2 −1 0 [Guo, Zhou, Wu, Gui, & Yang(2019)a ] a Yuqian Guo et al. “Stability and Set Stability in Distribution of Probabilistic Boolean Networks”. In: IEEE Transactions on Automatic Control 64 (2 2019), pp. 736–742. 51 / 115 + Criterion of asymptotical stability in stochastic sense lim Ex(t; x0 ) = xe t→∞ m lim Pt x0 = xe t→∞ ∀x0 ∈ ∆2n . Ex(t; x0 ) = Pt x0 ∀x0 ∈ ∆2n m Asymptotically stable in distribution 52 / 115 + Relations between Different Definitions of Stability FTS SSS SD SPO 53 / 115 + Asymptotical Set Stability lim P x(t) ∈ M x(0) = x0 = 1 ∀x0 ∈ ∆2n . t→∞ m lim P x(t) ∈ I(M) x(0) = x0 = 1 t→∞ ∀x0 ∈ ∆2n . m I(M) 6= ∅ x0 → I(M) ∀x0 Note: x0 → I(M) means x0 → x for some x ∈ I(M). 54 / 115 STG of a PBN that is asymptotically stable w.r.t. M 55 / 115 + Stability of Markovian Switching PBNs x(t + 1) = L n σ(t) n x(t) x(t) ∈ ∆2n L ∈ L2n ×n2n σ(t) ∈ ∆N is a homogeneous Markov chain with transition probability matrix Pσ , where n o pσij := [Pσ ]i,j = P σ(t + 1) = δNi σ(t) = δNj . 56 / 115 Define ξ(t) := σ(t) n x(t) ∈ ∆2n N . Then, ξ(t) is a homogeneous Markov chain. Denote the 1-step transition probability matrix of ξ(t) as Pξ ; that is, o n j ξ ξ i pij := [P ]i,j = P ξ(t + 1) = δ2n N ξ(t) = δ2n N . Proposition The Markovian switching PBN is finite-time (or asymptotically) M-stable with M = {δ2j n j ∈ ΛM } iff ξ(t) is finitetime (or asymptotically) Md -stable, where n o j i Md = ∆N n M := δN n δ2n i ∈ [1 : N], j ∈ ΛM . (7) How to calculate Pξ ? 57 / 115 Define ξ(t) := σ(t) n x(t) ∈ ∆2n N . Then, ξ(t) is a homogeneous Markov chain. Denote the 1-step transition probability matrix of ξ(t) as Pξ ; that is, o n j ξ ξ i pij := [P ]i,j = P ξ(t + 1) = δ2n N ξ(t) = δ2n N . Proposition The Markovian switching PBN is finite-time (or asymptotically) M-stable with M = {δ2j n j ∈ ΛM } iff ξ(t) is finitetime (or asymptotically) Md -stable, where n o j i Md = ∆N n M := δN n δ2n i ∈ [1 : N], j ∈ ΛM . (7) How to calculate Pξ ? 57 / 115 Define ξ(t) := σ(t) n x(t) ∈ ∆2n N . Then, ξ(t) is a homogeneous Markov chain. Denote the 1-step transition probability matrix of ξ(t) as Pξ ; that is, o n j ξ ξ i pij := [P ]i,j = P ξ(t + 1) = δ2n N ξ(t) = δ2n N . Proposition The Markovian switching PBN is finite-time (or asymptotically) M-stable with M = {δ2j n j ∈ ΛM } iff ξ(t) is finitetime (or asymptotically) Md -stable, where n o j i Md = ∆N n M := δN n δ2n i ∈ [1 : N], j ∈ ΛM . (7) How to calculate Pξ ? 57 / 115 Lemma Pξ = Pσ D[N,2n ] ∗ L. Proof: Take any δ2i n N = δNi1 n δ2i2n , δ2j n N = δNj1 n δ2j2n . Then, pξij =P(σ(t + 1) = δNi1 , x(t + 1) = δ2i2n σ(t) = δNj1 , x(t) = δ2j2n ) =P(σ(t + 1) = δNi1 σ(t) = δNj1 ) × P(x(t + 1) = δ2i2n σ(t) = δNj1 , x(t) = δ2j2n ) i i h h i h = Pσ δNj1 LδNj1 δ2j2n = Pσ δNj1 LδNj1 δ2j2n 2n (i1 −1)+i2 i i1 2 i h = Pσ D[N,2n ] δNj1 δ2j2n LδNj1 δ2j2n 2n (i1 −1)+i2 h i = Pσ D[N,2n ] ∗ L δNj1 δ2j2n 2n (i1 −1)+i2 h i n 2 (j1 −1)+j2 σ = P D[N,2n ] ∗ L δN2n 2n (i1 −1)+i2 σ = P D[N,2n ] ∗ L i,j (“∗” represents Khatri-Rao Product of matrices.) 58 / 115 + Synchronization of PBNs Z1 Z2 Y1 Z3 Master network Y3 Y2 Slave network Master Network: z(t + 1) = Lz z(t), z(t) ∈ ∆2n Slave Network: y(t + 1) = L n σ(t) n z(t) n y(t), z(t) ∈ ∆2n σ(t) ∈ ∆N is a homogeneous Markov chain. 59 / 115 Definition Finite-time synchronization: P{y(t; y0 ) = z(t; z0 )} = 1 ∀t ≥ T, ∀y0 , ∀z0 , ∀σ0 . Asymptotical synchronization: lim P{y(t; y0 ) = z(t; z0 )} = 1 t→∞ ∀y0 , ∀z0 , ∀σ0 . 60 / 115 Rewrite the master network as z(t + 1) = Lz z(t) = 1TN ⊗ (Lz D[2n ,2n ] ) n σ(t) n z(t) n y(t) Define x(t) = z(t) n y(t). Then, the coupled network can be expressed as x(t + 1) = L̄ n σ(t) n x(t) L̄ := 1TN ⊗ (Lz D[2n ,2n ] ) ∗ L “∗” represents Khatri-Rao Product of matrices. Define ξ(t) = σ(t) n x(t). Then, ξ(t) is a homogenous Markov chain with TPM Pξ = Pσ D[N,22n ] ∗ 1TN ⊗ (Lz D[2n ,2n ] ) ∗ L. 61 / 115 Finite-time (or asymptotical) synchronization m x(t) = z(t) n y(t) converges to Msyn in Finite-time (or asymptotically) Msyn = {δ2j n n δ2j n j = 1, 2, · · · , 2n } m ξ(t) = σ(t) n z(t) n y(t) converges to M̄syn in Finite-time (or asymptotically) i M̄syn = {δN n δ2j n n δ2j n i = 1, 2, · · · , N, j = 1, 2, · · · , 2n } 62 / 115 Example Consider master BN z(t + 1) = Lz z(t), z(t) ∈ ∆2n with n = 2, Lz = δ4 [3 1 4 3] and slave PBN y(t + 1) = L n σ(t) n z(t) n y(t), z(t) ∈ ∆2n with L = [L1 , L2 ] and L1 = δ4 [1 1 1 2 1 1 2 1 4 4 4 4 3 1 2 3], L2 = δ4 [3 3 3 3 2 1 2 2 3 3 4 3 1 3 1 3]. σ(t) ∈ ∆2 is a homogenous Markov chain with 0.3 0.6 σ P = . 0.7 0.4 63 / 115 Define ξ(t) = σ(t) n z(t) n y(t), then L̄ := 1T2 ⊗ (Lz D[4,4] ) ∗ [L1 L2 ] = δ16 [9 9 9 10 1 1 2 1 16 16 16 16 11 9 10 11 11 11 11 11 2 1 2 2 15 15 16 15 9 11 9 11]. Pξ = Pσ D[2,16] ∗ L̄ 64 / 115 (Pξ )> = 0 0 0 0 0.3 0.3 0 0.3 0 0 0 0 0 0 0 0 0 0 0 0 0 0.6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.3 0 0 0 0 0 0 0 0 0 0 0 0 0 0.6 0 0.6 0.6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.3 0 0 0 0 0 0 0 0.3 0 0 0 0 0 0 0 0.3 0 0 0 0 0 0 0 0 0.3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.3 0 0 0 0 0 0 0 0.3 0 0 0 0 0 0 0 0.3 0 0 0 0 0 0 0 0.3 0 0 0.3 0 0 0 0 0 0.3 0 0 0 0 0 0 0 0 0.3 0 0 0 0 0 0 0 0 0.3 0 0 0 0 0 0 0 0.6 0 0 0 0 0 0 0 0.6 0 0 0 0 0 0 0 0.6 0 0 0 0 0 0 0 0.6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.6 0 0 0 0 0 0 0 0.6 0 0 0 0 0 0 0 0 0.6 0 0 0 0 0 0 0.6 0 0.6 0 0 0 0 0 0 0 0 0 0.6 0 0 0 0 0 0.6 0 0 0 0 0 0 0 0 0 0.6 0 0 0 0 0 0 0 0 0 0.7 0.7 0 0.7 0 0 0 0 0 0 0 0 0 0 0 0 0 0.4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.7 0 0 0 0 0 0 0 0 0 0 0 0 0 0.4 0 0.4 0.4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.7 0 0 0 0 0 0 0 0.7 0 0 0 0 0 0 0 0.7 0 0 0 0 0 0 0 0 0.7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.7 0 0 0 0 0 0 0 0.7 0 0 0 0 0 0 0 0.7 0 0 0 0 0 0 0 0.7 0 0 0.7 0 0 0 0 0 0.7 0 0 0 0 0 0 0 0 0.7 0 0 0 0 0 0 0 0 0.7 0 0 0 0 0 0 0 0.4 0 0 0 0 0 0 0 0.4 0 0 0 0 0 0 0 0.4 0 0 0 0 0 0 0 0.4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.4 0 0 0 0 0 0 0 0.4 0 0 0 0 0 0 0 0 0.4 0 0 0 0 0 0 0.4 0 0.4 0 0 0 0 0 0 0 0 0 0.4 0 0 0 0 0 0.4 0 0 0 0 0 0 0 0 0 0.4 0 0 0 0 0 65 / 115 Set of Synchronization States: M̄syn = {δNi n δ2j n n δ2j n i = 1, 2, · · · , N, j = 1, 2, · · · , 2n } Λ0 j = {δ16 j ∈ Λ0 } = {16(i − 1) + 4(j − 1) + j i = 1, 2, j = 1, 2, 3, 4} = {1, 6, 11, 16, 17, 22, 27, 32}. The largest invariant Subset in M̄syn j I(M̄syn ) = {δ16 j ∈ Λ2 := {11, 16, 17, 27, 32}} X Rowr [(Pξ )3 ] > 0. r∈Λ2 Thus, these two BNs are asymptotically synchronized. 66 / 115 Outline 1 Basic Concepts of PBNs 2 Stability Analysis of PBNs Finite-time Stability Asymptotical Stability 3 Feedback Stabilization of PBNs Fintie-time Feedback Stabilization Asymptotical Feedback Stabilization 4 Controllability of PBNs 5 Observability of PBNs 6 Questions 67 / 115 III. Feedback Stabilization of PBNs + Consider a PBCN x(t + 1) = L n σ(t) n u(t) n x(t) Structural matrix: L ∈ L2n ×N2n+m ; σ(t) ∈ ∆N is an i.i.d. random sequence; TPM P = L n pσ = [P1 , P2 , · · · , P2m ] n o j i k [Pk ]i,j = P x(t + 1) = δ2n x(t) = δ2n , u(t) = δ2m 68 / 115 + Problem: Find a state-feedback u(t) = Fx(k) to stabilize a PBN to a point or a subset in finite-time or asymptotically. + If F = δ2m [k1 , k2 , · · · , k2n ] Then, the TPM of the closed loop, denoted by PF , is Colj (PF ) = Colj (Pkj ) 69 / 115 Outline 1 Basic Concepts of PBNs 2 Stability Analysis of PBNs Finite-time Stability Asymptotical Stability 3 Feedback Stabilization of PBNs Fintie-time Feedback Stabilization Asymptotical Feedback Stabilization 4 Controllability of PBNs 5 Observability of PBNs 6 Questions 70 / 115 III.1 Fintie-time Feedback Stabilization + Hierarchical structure of the STG of a FT stable PBN Ω0 = {xe } Ω1 = x P{x(t + 1) = xe x(t) = x} = 1 Ωk = x P{x(t + 1) ∈ Ωk−1 x(t) = x} = 1 We can always rearrange the STG into the hierarchical structure for a finite-time stable PBN. 71 / 115 10 6 12 4 8 9 3 7 1 2 5 11 How to construct a finite-time stable STG? 72 / 115 10 6 12 4 8 9 3 7 1 2 5 11 How to construct a finite-time stable STG? 72 / 115 10 6 12 4 8 9 3 7 1 2 5 11 How to construct a finite-time stable STG? 72 / 115 10 6 12 4 8 9 3 7 1 2 5 11 How to construct a finite-time stable STG? 72 / 115 10 6 12 4 8 9 3 7 1 2 5 11 How to construct a finite-time stable STG? 72 / 115 10 6 12 4 8 9 3 7 1 2 5 11 How to construct a finite-time stable STG? 72 / 115 10 6 12 4 8 9 3 7 1 2 5 11 How to construct a finite-time stable STG? 72 / 115 10 6 12 4 8 9 3 7 1 2 5 11 How to construct a finite-time stable STG? 72 / 115 10 6 12 4 8 9 3 7 1 2 5 11 How to construct a finite-time stable STG? 72 / 115 10 6 12 4 8 9 3 7 1 2 5 11 How to construct a finite-time stable STG? 72 / 115 10 6 12 4 8 9 3 7 1 2 5 11 How to construct a finite-time stable STG? 72 / 115 10 6 12 4 8 9 3 7 1 2 5 11 How to construct a finite-time stable STG? 73 / 115 + Construction of Finite-time Stabilizing Feedback Based on [li, Yang, & Chu (2014)20 ] Define a sequence of subsets as Ω0 = {x e} Ω1 = x ∃u s.t. P{x(t + 1) = xe x(t) = x, u(t) = u} = 1 Ωk = x ∃u s.t. P{x(t + 1) ∈ Ωk−1 x(t) = x, u(t) = u} = 1 k = 2, 3, · · · If xe is control invariant, then Ω0 ⊆ Ω1 ⊆ Ω2 ⊆ · · · 20 Rui Li, Meng Yang, and Tianguang Chu. “State feedback stabilization for probabilistic Boolean networks”. In: Automatica 50.4 (2014), pp. 1272–1278. 74 / 115 Theorem A PBN is finite-time stabilizable w.r.t. xe by a state feedback if and only if xe is control invariant; There is a positive integer K such that ΩK = ∆2n . [li, Yang, & Chu (2014)a ] a Rui Li, Meng Yang, and Tianguang Chu. “State feedback stabilization for probabilistic Boolean networks”. In: Automatica 50.4 (2014), pp. 1272–1278. 75 / 115 + A finite-time stabilizing feedback gain F can be obtained as follows: Assigning a control effort u(xe ) for xe such that P{x(t + 1) = xe x(t) = xe } = 1; Assigning a control effort u(x) for every x ∈ Ωk \ Ωk−1 such that P{x(t + 1) ∈ Ωk−1 x(t) = x} = 1. Then, n F = [u(δ21n ), u(δ22n ), · · · , u(δ22n )] [li, Yang, & Chu (2014)21 ] 21 Rui Li, Meng Yang, and Tianguang Chu. “State feedback stabilization for probabilistic Boolean networks”. In: Automatica 50.4 (2014), pp. 1272–1278. 76 / 115 0.6 0.2 0.2 0.5 4 0.2 0.3 7 6 0.4 0.2 0.7 0.6 0.4 0.7 0.7 0.6 0.4 6 6 0.6 3 0.3 7 0.3 7 0.3 0.5 3 4 0.4 0.3 5 3 1 0.4 0.5 4 5 5 0.2 0.3 0.5 0.5 2 0.6 1 2 0.6 1 0.5 2 1 0.5 1 1 1 1 1 0.5 0.5 1 8 8 1 1 8 u ≡ δ21 u ≡ δ22 u = δ2 [1, 2, 2, 1, 1, 2, 2, 2]x 77 / 115 0.6 0.2 0.2 0.5 4 0.2 0.3 7 6 0.4 0.2 0.7 0.6 0.4 0.7 0.7 0.6 0.4 6 6 0.6 3 0.3 7 0.3 7 0.3 0.5 3 4 0.4 0.3 5 3 1 0.4 0.5 4 5 5 0.2 0.3 0.5 0.5 2 0.6 1 2 0.6 1 0.5 2 1 0.5 1 1 1 1 1 0.5 0.5 1 8 8 1 1 8 u ≡ δ21 u ≡ δ22 u = δ2 [1, 2, 2, 1, 1, 2, 2, 2]x 77 / 115 0.6 0.2 0.2 0.5 4 0.2 0.3 7 6 0.4 0.2 0.7 0.6 0.4 0.7 0.7 0.6 0.4 6 6 0.6 3 0.3 7 0.3 7 0.3 0.5 3 4 0.4 0.3 5 3 1 0.4 0.5 4 5 5 0.2 0.3 0.5 0.5 2 0.6 1 2 0.6 1 0.5 2 1 0.5 1 1 1 1 1 0.5 0.5 1 8 8 1 1 8 u ≡ δ21 u ≡ δ22 u = δ2 [1, 2, 2, 1, 1, 2, 2, 2]x 77 / 115 0.6 0.2 0.2 0.5 4 0.2 0.3 7 6 0.4 0.2 0.7 0.6 0.4 0.7 0.7 0.6 0.4 6 6 0.6 3 0.3 7 0.3 7 0.3 0.5 3 4 0.4 0.3 5 3 1 0.4 0.5 4 5 5 0.2 0.3 0.5 0.5 2 0.6 1 2 0.6 1 0.5 2 1 0.5 1 1 1 1 1 0.5 0.5 1 8 8 1 1 8 u ≡ δ21 u ≡ δ22 u = δ2 [1, 2, 2, 1, 1, 2, 2, 2]x 77 / 115 0.6 0.2 0.2 0.5 4 0.2 0.3 7 6 0.4 0.2 0.7 0.6 0.4 0.7 0.7 0.6 0.4 6 6 0.6 3 0.3 7 0.3 7 0.3 0.5 3 4 0.4 0.3 5 3 1 0.4 0.5 4 5 5 0.2 0.3 0.5 0.5 2 0.6 1 2 0.6 1 0.5 2 1 0.5 1 1 1 1 1 0.5 0.5 1 8 8 1 1 8 u ≡ δ21 u ≡ δ22 u = δ2 [1, 2, 2, 1, 1, 2, 2, 2]x 77 / 115 0.6 0.2 0.2 0.5 4 0.2 0.3 7 6 0.4 0.2 0.7 0.6 0.4 0.7 0.7 0.6 0.4 6 6 0.6 3 0.3 7 0.3 7 0.3 0.5 3 4 0.4 0.3 5 3 1 0.4 0.5 4 5 5 0.2 0.3 0.5 0.5 2 0.6 1 2 0.6 1 0.5 2 1 0.5 1 1 1 1 1 0.5 0.5 1 8 8 1 1 8 u ≡ δ21 u ≡ δ22 u = δ2 [1, 2, 2, 1, 1, 2, 2, 2]x 77 / 115 0.6 0.2 0.2 0.5 4 0.2 0.3 7 6 0.4 0.2 0.7 0.6 0.4 0.7 0.7 0.6 0.4 6 6 0.6 3 0.3 7 0.3 7 0.3 0.5 3 4 0.4 0.3 5 3 1 0.4 0.5 4 5 5 0.2 0.3 0.5 0.5 2 0.6 1 2 0.6 1 0.5 2 1 0.5 1 1 1 1 1 0.5 0.5 1 8 8 1 1 8 u ≡ δ21 u ≡ δ22 u = δ2 [1, 2, 2, 1, 1, 2, 2, 2]x 77 / 115 0.6 0.2 0.2 0.5 4 0.2 0.3 7 6 0.4 0.2 0.7 0.6 0.4 0.7 0.7 0.6 0.4 6 6 0.6 3 0.3 7 0.3 7 0.3 0.5 3 4 0.4 0.3 5 3 1 0.4 0.5 4 5 5 0.2 0.3 0.5 0.5 2 0.6 1 2 0.6 1 0.5 2 1 0.5 1 1 1 1 1 0.5 0.5 1 8 8 1 1 8 u ≡ δ21 u ≡ δ22 u = δ2 [1, 2, 2, 1, 1, 2, 2, 2]x 77 / 115 + Finite-time Feedback Set Stabilization Finite-time Feedback M-Stabilizable m Finite-time Feedback Ic (M)-Stabilizable 78 / 115 Outline 1 Basic Concepts of PBNs 2 Stability Analysis of PBNs Finite-time Stability Asymptotical Stability 3 Feedback Stabilization of PBNs Fintie-time Feedback Stabilization Asymptotical Feedback Stabilization 4 Controllability of PBNs 5 Observability of PBNs 6 Questions 79 / 115 III.2 Asymptotical Feedback Stabilization Consider a PBCN x(t + 1) = L n σ(t) n u(t) n x(t) Structural matrix: L ∈ L2n ×N2n+m ; σ(t) ∈ ∆N is an i.i.d. random sequence; TPM P = L n pσ = [P1 , P2 , · · · , P2m ] n o j k i [Pk ]i,j = P x(t + 1) = δ2n x(t) = δ2n , u(t) = δ2m 80 / 115 + Feedback Stabilizability Theorem A state xe is asymptotically feedback stabilizable iff 1 xe is a control-fixed point, and 2 x0 → xe ∀x0 , that is, n xe> (P n 12m )2 −1 0. [Zhou & Guo(2018)a ] [Zhou, Guo, Wu, & Gui(2019)b ] [Wang, Liu, Wu, Lu, & Yu(2019)c ] a Rongpei Zhou and Yuqian Guo. “Set Stabilization in Distribution of Probabilistic Boolean Control Networks”. In: Proceedings of the 2018 13th World Congress on Intelligent Control and Automation July 4-8, 2018, Changsha, China. 2018, pp. 274–279. b Rongpei Zhou et al. “Asymptotical Feedback Set Stabilization of Probabilistic Boolean Control Networks”. In: IEEE Transactions on Neural Network & Learning Systems (2020), DOI: 10.1109/TNNLS.2019.2955974. c Liqing Wang, Yang Liu, and & Cybernetics: Systems Wu. “Stabilization and Finite-Time Stabilization of Probabilistic Boolean Control Networks”. In: (2020), DOI: 10.1109/TSMC.2019.2898880. 81 / 115 + Feedback Set Stabilizability Theorem A subset M is asymptotically feedback stabilizable iff 1 Ic (M) 6= ∅, and 2 x0 → Ic (M) ∀x0 , that is, h i X 2n −1 Rowj (P n 12m ) 0. j∈idx(Ic (M)) [Zhou, Guo, Wu, & Gui(2020)a ] a Rongpei Zhou et al. “Asymptotical Feedback Set Stabilization of Probabilistic Boolean Control Networks”. In: IEEE Transactions on Neural Network & Learning Systems (2020), DOI: 10.1109/TNNLS.2019.2955974. 82 / 115 + Design of Asymptotically Stabilizing Feedback Decomposition of State Space: Ξk = {δ2s n |s ∈ Θk }, Θ0 = idx(Ic (M)), !c k−1 [ Θs Θk = j ∈ s=0 k = 1, 2, · · · , λ. Or equivalently, Ic (M) Ξ0 := ( Ξk := x∈ k−1 [ k ∈ [0 : λ], X i∈Θk−1 [P n 12m ]i,j > 0 , (8) !c Ξs ) x → Ξk−1 s=0 83 / 115 For any δ2j n ∈ ∆2n , we define a set of admissible controls as follows: ( ) X [Pk ]i,j = 1 , if δ2j n ∈ Ξ0 δ2km i∈Θ0 j κ(δ2n ) := X k [Pk ]i,j > 0 , if δ2j n ∈ Ξs , s > 1. δ2m i∈Θs−1 Based on the construction, under any state feedback u(t) = Kx(t) satisfying, for all j ∈ [1 : 2n ], Colj (K) ∈ κ(δ2j n ). 84 / 115 6 0.2 0.7 0.4 0.7 0.6 0.7 0.5 4 0.2 6 0.2 0.4 0.6 3 0.3 7 0.6 0.2 0.4 6 0.2 0.2 0.6 0.3 7 0.3 7 0.3 0.5 3 4 0.4 0.3 5 3 1 0.4 0.5 4 5 5 0.2 0.3 0.5 0.5 2 0.4 1 2 0.4 1 0.5 2 1 0.5 1 1 1 1 1 0.5 0.5 1 8 8 1 1 8 u ≡ δ21 u ≡ δ22 u = δ2 [1, 2, 2, 1, 1, 2, 2, 2]x 85 / 115 6 0.2 0.7 0.4 0.7 0.6 0.7 0.5 4 0.2 6 0.2 0.4 0.6 3 0.3 7 0.6 0.2 0.4 6 0.2 0.2 0.6 0.3 7 0.3 7 0.3 0.5 3 4 0.4 0.3 5 3 1 0.4 0.5 4 5 5 0.2 0.3 0.5 0.5 2 0.4 1 2 0.4 1 0.5 2 1 0.5 1 1 1 1 1 0.5 0.5 1 8 8 1 1 8 u ≡ δ21 u ≡ δ22 u = δ2 [1, 2, 2, 1, 1, 2, 2, 2]x 85 / 115 6 0.2 0.7 0.4 0.7 0.6 0.7 0.5 4 0.2 6 0.2 0.4 0.6 3 0.3 7 0.6 0.2 0.4 6 0.2 0.2 0.6 0.3 7 0.3 7 0.3 0.5 3 4 0.4 0.3 5 3 1 0.4 0.5 4 5 5 0.2 0.3 0.5 0.5 2 0.4 1 2 0.4 1 0.5 2 1 0.5 1 1 1 1 1 0.5 0.5 1 8 8 1 1 8 u ≡ δ21 u ≡ δ22 u = δ2 [1, 2, 2, 1, 1, 2, 2, 2]x 85 / 115 6 0.2 0.7 0.4 0.7 0.6 0.7 0.5 4 0.2 6 0.2 0.4 0.6 3 0.3 7 0.6 0.2 0.4 6 0.2 0.2 0.6 0.3 7 0.3 7 0.3 0.5 3 4 0.4 0.3 5 3 1 0.4 0.5 4 5 5 0.2 0.3 0.5 0.5 2 0.4 1 2 0.4 1 0.5 2 1 0.5 1 1 1 1 1 0.5 0.5 1 8 8 1 1 8 u ≡ δ21 u ≡ δ22 u = δ2 [1, 2, 2, 1, 1, 2, 2, 2]x 85 / 115 6 0.2 0.7 0.4 0.7 0.6 0.7 0.5 4 0.2 6 0.2 0.4 0.6 3 0.3 7 0.6 0.2 0.4 6 0.2 0.2 0.6 0.3 7 0.3 7 0.3 0.5 3 4 0.4 0.3 5 3 1 0.4 0.5 4 5 5 0.2 0.3 0.5 0.5 2 0.4 1 2 0.4 1 0.5 2 1 0.5 1 1 1 1 1 0.5 0.5 1 8 8 1 1 8 u ≡ δ21 u ≡ δ22 u = δ2 [1, 2, 2, 1, 1, 2, 2, 2]x 85 / 115 An Algorithm [Zhou, Guo, Wu, & Gui(2020)22 ] 22 Rongpei Zhou et al. “Asymptotical Feedback Set Stabilization of Probabilistic Boolean Control Networks”. In: IEEE Transactions on Neural Network & Learning Systems (2020), DOI: 10.1109/TNNLS.2019.2955974. 86 / 115 + Application to Output Tracking We consider PBCN with q output nodes x(t + 1) = L n σ(t) n u(t) n x(t) y(t) = Hx(t) (9) where y(t) = nqi=1 yi (t) denotes the vector form of the output variables and H ∈ L2q ×2n . Definition We assume that that y∗ = δ2r q ∈ ∆2q corresponds to a reference signal. The asymptotical feedback output tracking problem of the PBCN is said to be solvable if there is a state feedback u(t) = Kx(t) such that, for any initial state x0 , lim P{Hx(t) = y∗ } = 1. (10) t→∞ 87 / 115 Theorem Suppose that σ(t) is an i.i.d. process with the probability distribution vector pσ . We define a sequence of index sets as: Λ0 = {j|Hδ2j n = δ2r q }, X k [Pk ]i,j = 1 . Λs = j ∈ Λs−1 ∃u = δ2n , s.t., i∈Λs−1 s = 1, 2, · · · , We denote the smallest integer by η such that Λη = Λη+1 . Then, the asymptotical feedback output tracking problem is solvable iff X n Rowi (L n pσ n 12m )2 −|Λη | 0. (11) i∈Λη 88 / 115 Outline 1 Basic Concepts of PBNs 2 Stability Analysis of PBNs Finite-time Stability Asymptotical Stability 3 Feedback Stabilization of PBNs Fintie-time Feedback Stabilization Asymptotical Feedback Stabilization 4 Controllability of PBNs 5 Observability of PBNs 6 Questions 89 / 115 IV. Controllability of PBNs + Consider a PBCN x(t + 1) = L n σ(t) n u(t) n x(t) Structural matrix: L ∈ L2n ×N2n+m ; σ(t) ∈ ∆N is an i.i.d. random sequence; TPM P = L n pσ = [P1 , P2 , · · · , P2m ] n o [Pk ]i,j = P x(t + 1) = δ2i n x(t) = δ2j n , u(t) = δ2km 90 / 115 + Definition of Controllability Definition (Finite-time Controllability) A PBCN is controllable if, for any pair of states (δ2i n , δ2j n ), there is a control sequence u and a positive integer T such that n o j i P x(T) = δ2n x(0) = δ2n = 1. [Li & Sun (2011)a ] a Fangfei Li and Jitao Sun. “Controllability of probabilistic Boolean control networks”. In: Automatica 47.12 (2011), pp. 2765–2771. 91 / 115 Definition A PBCN is controllable if, for any pair of states (δ2i n , δ2j n ), there is a control sequence u such that o n P x(t) = δ2j n for some t ≥ 1 x(0) = δ2i n = 1. [Zhao & Cheng (2014)a ] a Yin Zhao and Daizhan Cheng. “On controllability and stabilizability of probabilistic Boolean control networks”. In: Science China Information Sciences 57.1 (2014), pp. 1–14. 92 / 115 + Criterion for Controllability Theorem The PBCN is controllability iff R 0, where R= n −1 2X (P n 12m )k . k=1 [Zhao & Cheng (2014)a ] a Yin Zhao and Daizhan Cheng. “On controllability and stabilizability of probabilistic Boolean control networks”. In: Science China Information Sciences 57.1 (2014), pp. 1–14. 93 / 115 + Criterion for Finite-time Controllability Theorem The PBCN is finite-time controllable if and only if for any pair of states (x0 , xd ), there is a positive integer s such that s xd ∈ Col PW[2n ,2m ] x0 [Li & Sun (2011)a ] a Fangfei Li and Jitao Sun. “Controllability of probabilistic Boolean control networks”. In: Automatica 47.12 (2011), pp. 2765–2771. 94 / 115 Sketchy Proof: x(t + 1) = Li u(t)x(t) = Li W[2n ,2m ] x(t)u(t) ⇓ Ex(t + 1) = PW[2n ,2m ] Ex(t)u(t) ⇓ Ex(s) = PW[2n ,2m ] Ex(s − 1)u(s − 1) = ··· s = PW[2n ,2m ] x(0)u(0)u(1) · · · u(s − 1) 95 / 115 + Relations between Definitions Finite-time controllability implies controllability; The reverse is not true. Example Consider a PBCN with a state node and an input node and P = [P1 P2 ], where 1 0 0.5 1 P1 = , P2 = . 0 1 0.5 0 96 / 115 This PBCN is obviously controllable because the TPM is completely connected under u(t) ≡ δ22 . However, under any control sequence, the n-step TPM P̄(n) ∈ R2×2 is P̄(n) =(P n un−1 ) · · · · (P n u1 )(P n u0 ) k 0.5 1 n−k k =(P1 ) · (P2 ) = 0.5 0 1 1 k 2 2 2 1 k × (− ) + − × (− ) = 13 1 2 1 3k 32 3 1 k 2 1 . − 3 × (− 2 ) 3 × (− 2 ) + 3 3 where k the number of δ22 ’s in the control sequence. It is easy to verify the following: [P̄(n)]2,1 = 1 1 1 − × (− )k 6 0.5 < 1. 3 3 2 97 / 115 Outline 1 Basic Concepts of PBNs 2 Stability Analysis of PBNs Finite-time Stability Asymptotical Stability 3 Feedback Stabilization of PBNs Fintie-time Feedback Stabilization Asymptotical Feedback Stabilization 4 Controllability of PBNs 5 Observability of PBNs 6 Questions 98 / 115 V. Observability of PBNs x(t + 1) = L n σ(t) n x(t) y(t) = H n x(t), (12) x(t) ∈ ∆2n , y(t) ∈ ∆2q ; Structural matrix: L ∈ L2n ×N2n , H ∈ L2q ×2n ; σ(t) ∈ ∆N is an i.i.d. random sequence with PDV pσ ; TPM P = L n pσ For convenience, we denote the state trajectory over [0 : θ] starting from x0 by x(θ; σ, x0 ) := [x0 x(1; σ, x0 ) · · · x(θ; σ, x0 )] and the corresponding output trajectory by y(θ; σ, x0 ) := [y(x0 ) y(1; σ, x0 ) · · · y(θ; σ, x0 )]. 99 / 115 + Definitions of Observability Definition (Finite-time Observability in Probability (FTOP)) A PBN is said to be observable in probability on [0 : θ] if, for any two distinct initial states x0 , x̄0 ∈ ∆2n , it holds that P {y(θ; σ, x0 ) 6= y(θ; σ, x̄0 )} > 0. (13) A PBN is said to be finite-time observable in probability if there is a non-negative integer θ such that it is observable in probability on [0 : θ]. [Zhao & Liu (2015)a ] a J. Zhao and Z. Liu. “Observability of probabilistic Boolean networks”. In: Proceedings of the Chinese Control Conference, 2015. 2015, pp. 183–186. 100 / 115 Definition (Finite-time Observability with Probability One (FTOPO)) A PBN is said to be observable with probability one on [0 : θ] if, for any two distinct initial states x0 , x̄0 ∈ ∆2n , it holds that P {y(θ; σ, x0 ) 6= y(θ; σ, x̄0 )} = 1. (14) It is said to be finite-time observable with probability one if a non-negative integer θ exists, such that the PBN is observable with probability one on [0 : θ]. [Zhou, Guo, & Gui (2019)a ] a Rongpei Zhou and Yuqian Guo. “Set Stabilization in Distribution of Probabilistic Boolean Control Networks”. In: Proceedings of the 2018 13th World Congress on Intelligent Control and Automation July 4-8, 2018, Changsha, China. 2018, pp. 274–279. 101 / 115 Definition (Asymptotical Observability in Distribution (AOD)) A PBN is said to be asymptotically observable in distribution if, for any two distinct initial states x0 , x̄0 ∈ ∆2n , it holds that lim P {y(t; σ, x0 ) 6= y(t; σ, x̄0 )} = 1. (15) t→∞ [Zhou, Guo, & Gui (2019)a ] a Rongpei Zhou and Yuqian Guo. “Set Stabilization in Distribution of Probabilistic Boolean Control Networks”. In: Proceedings of the 2018 13th World Congress on Intelligent Control and Automation July 4-8, 2018, Changsha, China. 2018, pp. 274–279. 102 / 115 FTOP AOD FTOPO Figure 1: The ellipses labeled with FTOP, AOD, and FTOPO represent the set of PBNs that are observable in the sense of FTOP, AOD, and FTOPO, respectively. 103 / 115 Definition Given a time instant T ∈ Z+ , a PBN is observable in [0, T] if, for every admissible output sequence y(0), y(1), . . . , y(T), it is possible to uniquely identify the corresponding initial condition x(0). The PBN is observable if it is observable in some interval [0, T] [Fornasini & Valcher (2020)a ] a Ettore Fornasini and Maria Elena Valcher. “Observability and Reconstructibility of Probabilistic Boolean Networks”. In: IEEE Control Systems Letters 4.2 (2020), pp. 319–324. 104 / 115 Definition (Weakly Reconstructibility) Given a PBN and a time instant T ∈ Z+ , the PBN is weakly reconstructible in [0, T] if for every admissible output sequence y(0), y(1), . . . , y(T), there exists τ ∈ [0, T] (depending on the specific output sequence) such that the knowledge of the output samples y(0), y(1), . . . , y(τ ) allows to uniquely identify x(τ ) ∈ LN . The PBN is weakly reconstructible if it is weakly reconstructible in some interval [0, T]. [Fornasini & Valcher (2020)a ] a Ettore Fornasini and Maria Elena Valcher. “Observability and Reconstructibility of Probabilistic Boolean Networks”. In: IEEE Control Systems Letters 4.2 (2020), pp. 319–324. 105 / 115 Definition (Strongly Reconstructibility)) Given a PBN and a time instant T ∈ Z+ , we say that the PBN is strongly reconstructible in [0, T] if, given any admissible output sequence y(0), y(1), . . . , y(T) ∈ LP , it is possible to uniquely identify x(T) ∈ LN . The PBN (3) is strongly reconstructible if it is strongly reconstructible in some interval [0, T]. [Fornasini & Valcher (2020)a ] a Ettore Fornasini and Maria Elena Valcher. “Observability and Reconstructibility of Probabilistic Boolean Networks”. In: IEEE Control Systems Letters 4.2 (2020), pp. 319–324. 106 / 115 + [Fornasini & Valcher (2020)23 ] 23 Ettore Fornasini and Maria Elena Valcher. “Observability and Reconstructibility of Probabilistic Boolean Networks”. In: IEEE Control Systems Letters 4.2 (2020), pp. 319–324. 107 / 115 + Observability Analysis Based on Set Reachability Definition (Finite-time Reachability) Assume that M0 , Md ⊂ ∆2n are the initial and target subsets, respectively. Md is said to be reachable with probability one from M0 on [0 : θ] if, for any initial state x0 ∈ M0 , it holds that P {∃k ∈ [0 : θ], s.t. x(k; σ, x0 ) ∈ Md } = 1. (16) Md is said to be finite-time reachable with probability one from M0 if there is a θ such that Md is reachable with probability one from M0 on [0 : θ]. 108 / 115 Definition (Asymptotical Reachability) A target subset Md ⊂ ∆2n is said to be asymptotically reachable in distribution from an initial subset M0 ⊂ ∆2n if, for any initial state x0 ∈ M0 , it holds that lim P {∃k ∈ [0 : t], s.t. x(k; σ, x0 ) ∈ Md } = 1. t→∞ (17) 109 / 115 Parallel Extension: x̄(t + 1) = L n σ(t) n x̄(t) ȳ(t) = Hx̄(t) Interconnected Network: Define ξ(t) := x(t) n x̄(t), η(t) := y(t) n ȳ(t), σξ (t) := σ(t). Then, ξ(t + 1) = Lξ σξ (t)ξ(t) η(t) = Hξ ξ(t), Lξ = LW[2n ,N·2n ] LW[N·2n ,N·2n ] W[N,N·2n ] Mr,N , Hξ = HW[2q ,2n ] HW[2n ,2n ] , (18) (19) 110 / 115 Distinguishable Set: GH = {x n x̄|Hx 6= Hx̄}. Initially Indistinguishable Set: n o j i GI\H := δ2n n δ2n Coli (H) = Colj (H) and i < j . 111 / 115 Proposition (a) The original PBN is finite-time observable with probability one iff the subset GH is finite-time reachable with probability one from GI\H for the interconnected PBN. (b) The original PBN is asymptotically observable in distribution iff the subset GH is asymptotically reachable in distribution from GI\H for the interconnected PBN. 112 / 115 Outline 1 Basic Concepts of PBNs 2 Stability Analysis of PBNs Finite-time Stability Asymptotical Stability 3 Feedback Stabilization of PBNs Fintie-time Feedback Stabilization Asymptotical Feedback Stabilization 4 Controllability of PBNs 5 Observability of PBNs 6 Questions 113 / 115 Questions + Are there other reasonable ways to define controllability and observability of PBNs? + If your answer is “yes”, what is the difference between the existing definitions and yours? + If one of your definitions tells a different story, find a sufficient or even a necessary and sufficient condition. + Now you are ready to write a paper and publish it. 114 / 115 Questions + Are there other reasonable ways to define controllability and observability of PBNs? + If your answer is “yes”, what is the difference between the existing definitions and yours? + If one of your definitions tells a different story, find a sufficient or even a necessary and sufficient condition. + Now you are ready to write a paper and publish it. 114 / 115 Questions + Are there other reasonable ways to define controllability and observability of PBNs? + If your answer is “yes”, what is the difference between the existing definitions and yours? + If one of your definitions tells a different story, find a sufficient or even a necessary and sufficient condition. + Now you are ready to write a paper and publish it. 114 / 115 Questions + Are there other reasonable ways to define controllability and observability of PBNs? + If your answer is “yes”, what is the difference between the existing definitions and yours? + If one of your definitions tells a different story, find a sufficient or even a necessary and sufficient condition. + Now you are ready to write a paper and publish it. 114 / 115 Questions + Are there other reasonable ways to define controllability and observability of PBNs? + If your answer is “yes”, what is the difference between the existing definitions and yours? + If one of your definitions tells a different story, find a sufficient or even a necessary and sufficient condition. + Now you are ready to write a paper and publish it. 114 / 115 Thank you! 115 / 115