logo

SCIENCE CHINA Information Sciences, Volume 61 , Issue 1 : 010201(2018) https://doi.org/10.1007/s11432-017-9265-2

From STP to game-based control

More info
  • ReceivedAug 21, 2017
  • AcceptedSep 28, 2017
  • PublishedDec 12, 2017

Abstract


Acknowledgment

This work was supported partly by National Natural Science Foundation of China (NSFC) (Grant Nos. 61333001, 61773371, 61733018).


References

[1] Cheng D Z. Semi-tensor product of matrices and its application to Morgans problem. Sci China Ser F-Inf Sci, 2001, 44: 195--212. Google Scholar

[2] Bates D M, Watts D G. Relative curvature measures of nonlinearity. J Roy Stat Soc, 1980, 42: 1--25. Google Scholar

[3] Cheng D Z, Qi H S. Controllability and observability of Boolean control networks. Automatica, 2009, 45: 1659--1667. Google Scholar

[4] Cheng D Z, Qi H S, Zhao Y. An Introduction to Semi-tensor Product of Matrices and Its Applications. Singapore: World Scientific, 2012. Google Scholar

[5] Isidori A. Nonlinear Control Systems. 3rd ed. London: Springer, 1995. Google Scholar

[6] Cheng D Z, Dong Y L. Semi-tensor product of matrices and its some applications to physics. Meth Appl Anal, 2003, 10: 565--588. Google Scholar

[7] Cheng D Z. Some applications of semi-tensor product of matrix in algebra. Comput Math Appl, 2006, 52: 1045--1066. Google Scholar

[8] Ma J, Cheng D Z, Mei S W, et al. Approximation of the boundary of power system stability region based on semi-tensor theory part one: theoretical basis (in Chinese). Autom Electr Power Syst, 2006, 30: 1--5. Google Scholar

[9] Mei S, Liu F, Xie A. Transient Analysis of Power Systems — A Semi-tensor Product Approach (in Chinese). Beijing: Tsinghua University Press, 2010. Google Scholar

[10] Ma J, Cheng D Z, Mei S W, et al. Approximation of the boundary of power system stability region based on semi-tensor theory part two: application (in Chinese). Autom Electr Power Syst, 2006, 30: 7--12. Google Scholar

[11] Cheng D Z, Feng J E, Lv H L. Solving fuzzy relational equations via semi-tensor product. IEEE Trans Fuzzy Syst, 2012, 20: 390--396. Google Scholar

[12] Feng J E, Lv H L, Cheng D Z. Multiple fuzzy relation and its application to coupled fuzzy control. Asian J Control, 2013, 15: 1313--1324. Google Scholar

[13] Cheng D Z. Semi-tensor product of matrices and its applications to dynamic systems. In: New Directions and Applications in Control Theory. Berlin: Springer, 2005. 61--79. Google Scholar

[14] Cheng D Z, Ma J, Lu Q, et al. Quadratic form of stable sub-manifold for power systems. Int J Robust Nonlin Control, 2004, 14: 773--788. Google Scholar

[15] Chiang H D, Hirsch M W, Wu F F. Stability regions of nonlinear autonomous dynamical systems. IEEE Trans Autom Control, 1988, 33: 16--27. Google Scholar

[16] Xue A C, Wu F F, Lu Q, et al. Power system dynamic security region and its approximations. IEEE Trans Circ Syst I, 2006, 53: 2849--2859. Google Scholar

[17] Drossel B, Mihaljev T, Greil F. Number and length of attractors in a critical Kauffman model with connectivity one. Phys Rev Lett, 2005, 94: 088701. Google Scholar

[18] Farrow C, Heidel J, Maloney J, et al. Scalar equations for synchronous Boolean networks with biological applications. IEEE Trans Neural Netw, 2004, 15: 348--354. Google Scholar

[19] Heidel J, Maloney J, Farrow C, et al. Finding cycles in synchronous Boolean networks with applications to biochemical systems. Int J Bifurcat Chaos, 2003, 13: 535--552. Google Scholar

[20] Cheng D Z, Qi H S. A linear representation of dynamics of Boolean networks. IEEE Trans Autom Control, 2010, 55: 2251--2258. Google Scholar

[21] Cheng D Z, Qi H S. State-space analysis of Boolean networks. IEEE Trans Neural Netw, 2010, 21: 584--594. Google Scholar

[22] Zhao Y, Qi H S, Cheng D Z. Input-state incidence matrix of Boolean control networks and its applications. Syst Control Lett, 2010, 59: 767--774. Google Scholar

[23] Zhang K Z, Zhang L J. Observability of Boolean control networks: a unified approach based on finite automata. IEEE Trans Autom Control, 2016, 61: 2733--2738. Google Scholar

[24] Laschov D, Margaliot M, Even G. Observbility of Boolean networks: a graph-theoretic approach. Automatica, 2013, 49: 2351--2362. Google Scholar

[25] Fornasini E, Valcher M E. Observability, reconstructibility and state observers of Boolean control networks. IEEE Trans Autom Control, 2013, 58: 1390--1401. Google Scholar

[26] Cheng D Z, Qi H S, Liu T, et al. A note on observability of Boolean control networks. Syst Control Lett, 2016, 87: 76--82. Google Scholar

[27] Cheng D Z, Qi H S, Li Z Q, et al. Stability and stabilization of Boolean networks. Int J Robust Nonlin Control, 2011, 21: 134--156. Google Scholar

[28] Cheng D Z. Distrubane decoupling of Boolean control networks. IEEE Trans Autom Control, 2011, 56: 2--10. Google Scholar

[29] Mu Y F, Guo L. Optimization and identification in a non-equilibrium dynamic game. In: Proceedings of the 48h IEEE Conference on Decision and Control, Shanghai, 2009. 5750--5755. Google Scholar

[30] Zhao Y, Li Z Q, Cheng D Z. Optimal control of logical control networks. IEEE Trans Autom Control, 2011, 56: 1766--1776. Google Scholar

[31] Cheng D Z, Zhao Y, Xu T T. Receding horizon based feedback optimization for mix-valued logical networks. IEEE Trans Autom Control, 2015, 60: 3362--3366. Google Scholar

[32] Laschov D, Margaliot M. A maximum principle for single-input Boolean control networks. IEEE Trans Autom Control, 2011, 56: 913--917. Google Scholar

[33] Cheng D Z, Qi H S, Li Z Q. Model construction of Boolean network via observed data. IEEE Trans Neural Netw, 2011, 22: 525--536. Google Scholar

[34] Cheng D Z, Zhao Y. Identification of Boolean control networks. Automatica, 2011, 47: 702--710. Google Scholar

[35] Zhao Y, Kim J, Filippone M. Aggregation algorithm towards large-scale Boolean netwok analysis. IEEE Trans Autom Control, 2013, 58: 1976--1985. Google Scholar

[36] Zhao Y, Ghosh B K, Cheng D Z. Control of large-scale Boolean networks via network aggregation. IEEE Trans Neural Netw Learn Syst, 2016, 27: 1527--1536. Google Scholar

[37] Lu J Q, Li H T, Liu Y, et al. A survey on semi-tensor product method with its applications in logical networks and other finite-valued systems. IET Control Theory Appl, 2017, 11: 2040--2047. Google Scholar

[38] Gao B, Li L X, Peng H P, et al. Principle for performing attractor transits with single control in Boolean networks. Phys Rev E, 2013, 88: 062706. Google Scholar

[39] Gao B, Peng H P, Zhao D W, et al. Attractor transformation by impulsive control in Boolean control network. Math Probl Eng, 2013, 2014: 674571. Google Scholar

[40] Li R, Yang M, Chu T G. State feedback stabilization for Boolean control networks. IEEE Trans Autom Control, 2013, 58: 1853--1857. Google Scholar

[41] Li H T, Wang Y Z. Output feedback stabilization control design for Boolean control networks. Automatica, 2013, 49, 3641--3645. Google Scholar

[42] Meng M, Feng J E. A matrix appoach to hypergraph stable set and coloring problems with its application to storing problem. J Appl Math, 2014, 2014: 783784. Google Scholar

[43] Wang Y Z, Zhang C H, Liu Z B. A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems. Automatica, 2012, 48: 1227--1236. Google Scholar

[44] Xu M R, Wang Y Z, Wei A R. Robust graph coloring based on the matrix semi-tensor product with application to examination timetabling. Control Theory Technol, 2014, 12: 187--197. Google Scholar

[45] Zhang L Q, Feng J E. Mix-valued logic-based formation control. Int J Control, 2013, 86: 1191--1199. Google Scholar

[46] Cheng D Z, Xu X R. Bi-decomposition of multi-valued logical functions and its applications. Automatica, 2003, 49: 1979--1985. Google Scholar

[47] Li H T, Wang Y Z. Boolean derivative calculation with application to fault detection of combinational circuits via the semi-tensor product method. Automatica, 2012, 48: 688--693. Google Scholar

[48] Liu Z B, Wang Y Z, Li H T. New approach to derivative calculation of multi-valued logical functions with application to fault detection of digital circuits. IET Control Theory Appl, 2014, 8: 554--560. Google Scholar

[49] Ouyang C T, Jiang J H. Reliability estimation of sequential circuit based on probabilistic matrices (in Chinese). ACTA Electron Sin, 2013, 41: 171--177. Google Scholar

[50] Ge A D, Wang Y Z, Wei A R, et al. Control design for multi-variable fuzzy systems with application to parallel hybrid electric vehicles. Control Theory Appl, 2013, 30: 998--1004. Google Scholar

[51] Xiao X H, Duan P Y, Lv H L, et al. Design of fuzzy controller for air-conditioning systems based-on semi-tensor product. In: Proceedings of the 26th Chinese Control and Decision Conference, Changsha, 2014. 3507--3512. Google Scholar

[52] Yan Y Y, Chen Z Q, Liu Z X. Solving type-2 fuzzy relation equations via semi-tensor product of matrices. Control Theory Technol, 2014, 12: 173--186. Google Scholar

[53] Xu X R, Hong Y G. Matrix expression and reachability of finite automata. J Control Theory Appl, 2012, 10: 210--215. Google Scholar

[54] Xu X R, Hong Y G. Matrix expression to model matching of asynchronous sequential machines. IEEE Trans Autom Control, 2013, 58: 2974--2979. Google Scholar

[55] Xu X R, Hong Y G. Observability and observer design for finite automata via matrix approach. IET Control Theory Appl, 2013, 7: 1609--1615. Google Scholar

[56] Yan Y Y, Chen Z Q, Liu Z X. Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition. Front Comput Sci, 2014, 8: 948--957. Google Scholar

[57] Hochma G, Margaliot M, Fornasini E. Symbolic dynamics of Boolean control networks. Automatica, 2013, 49: 2525--2530. Google Scholar

[58] Yan Y Y, Chen Z Q, Liu Z X. Semi-tensor product approach to controllability and stabilizability of finite automata. J Syst Eng Electron, 2015, 26: 134--141. Google Scholar

[59] Liu Z B, Wang Y Z, Cheng D Z. Nonsingularity of nonlinear feedback shift registers. Automatica, 2015, 55: 247--253. Google Scholar

[60] Zhang J, Lu S, Yang G. Improved calculation scheme of structure matrix of Boolean network using semi-tensor product. In: Proceedings of International Conference on Information Computing and Applications. Berlin: Springer, 2012. 242--248. Google Scholar

[61] Zhao D W, Peng H P, Li L X, et al. Novel way to research nonlinear feedback shift register. Sci China Inf Sci, 2014, 57: 092114. Google Scholar

[62] Zhong J H, Lin D D. A new linearization method for nonlinear feedback shift registers. J Comput Syst Sci, 2015, 81: 783--796. Google Scholar

[63] Zhong J H, Lin D D. Stability of nonlinear feedback shift registers. Sci China Inf Sci, 2016, 59: 012204. Google Scholar

[64] Chen Y B, Xi N, Miao L, et al. Applications of the semi-tensor product to the internet-based tele-operation systems (in Chinese). Robot, 2012, 34: 50--55. Google Scholar

[65] Liu X H, Xu Y. An inquiry method of transit network based on semi-tensor product (in Chinese). Complex Syst Complexity Sci, 2013, 10: 38--44. Google Scholar

[66] Li H T, Wang Y Z. On reachability and controllability of switched Boolean control networks. Automatica, 2012, 48: 2917--2922. Google Scholar

[67] Li H T, Wang Y Z, Xie L H, et al. Disturbance decoupling control design for switched Boolean control networks. Syst Control Lett, 2014, 72: 1--6. Google Scholar

[68] Li F F, Lu X W, Yu Z X. Optimal control algorithms for switched Boolean network. J Franklin Inst, 2014, 351: 3490--3501. Google Scholar

[69] von Neumann J, Morgenstern O. Theory of Games and Economic Behavior. Princeton: Princeton University Press, 1944. Google Scholar

[70] Candogan O, Menache I, Ozdaglar A, et al. Flows and decompositions of games: harmonic and potential games. Math Oper Res, 2011, 36: 474--503. Google Scholar

[71] Cheng D Z, Liu T, Zhang K Z, et al. On decomposed subspaces of finite games. IEEE Trans Autom Control, 2016, 61: 3651--3656. Google Scholar

[72] Monderer D, Shapley L S. Potential games. Games Econ Behav, 1996, 14: 124--143. Google Scholar

[73] Cheng D Z. On finite potential games. Automatica, 2014, 50: 1793--1801. Google Scholar

[74] Liu T, Qi H S, Cheng D Z. Dual expressions of decomposed subspaces of finite games. In: Proceedings of the 34th Chinese Control Conference (CCC), Hangzhou, 2015. 9146--9151. Google Scholar

[75] Hao Y, Cheng D Z. On skew-symmetric games. ArXiv Preprint,. arXiv Google Scholar

[76] Guo P L, Wang Y Z, Li H T. Algebraic formulation and strategy optimization for a class of evolutionary network games via semi-tensor product method. Automatica, 2013, 49: 3384--3389. Google Scholar

[77] Cheng D Z, He F H, Qi H S, et al. Modeling, analysis and control of networked evolutionary games. IEEE Trans Autom Control, 2015, 60: 2402--2415. Google Scholar

[78] Gopalakrishnan R, Marden J R, Wierman A. An architectural view of game theoretic control. Perfor Eval Rev, 2011, 38: 31--36. Google Scholar

[79] Hao Y, Pan S, Qiao Y, et al. Cooperative control vial congestion game. ArXiv Preprint,. arXiv Google Scholar

[80] Liu T, Wang J H, Cheng D Z. Game theoretic control of multi-agent systems. ArXiv Preprint,. arXiv Google Scholar

[81] Facchini G, Megen F V, Borm P, et al. Congestion models and weighted Bayesian potential games. Theory Decis, 1997, 42: 193--206. Google Scholar

[82] Cheng D Z. On equivalence of matrices. ArXiv Preprint,. arXiv Google Scholar

  • Figure 1

    A cubic matrix.

  • Figure 2

    “Hourglass architecture of game theoretic control.

  •   

    Algorithm 1 Construct ${\cal~U}$

    1. Let ${\cal~U}^k=(u^k_{i,j})$ be known. 2. for $i=1,\ldots,r$ do 3. if $u^k_{i,r+1}=1$ then 4. $\Col_{r+1}({\cal~U}^{k+1})=\Col_{r+1}({\cal~U}^{k})\vee~\Col_{i}({\cal~U}^{k})$. 5. end if 6. if ${\cal~U}^{k^*+1}={\cal~U}^{k^*}$ then 7. Set ${\cal~U}:={\cal~U}^{k^*}$. 8. Stop. 9. end if 10. end for

  • Table 1   Truth table for unary operators
    $x$ $\neg~x$
    $1$ $0$
    $0$ $1$
  • Table 2   Truth table for binary operators
    $x$ $y$ $x\vee~y$ $x\wedge~y$ $x\ra~y$ $x\lra~y$ $x\downarrow~y$ $x\uparrow~y$ $x\bar{\vee}~y$
    $1$ $1$ $1$ $1$ $1$ $1$ $0$ $0$ $0$
    $1$ $0$ $1$ $0$ $0$ $0$ $0$ $1$ $1$
    $0$ $1$ $1$ $0$ $1$ $0$ $0$ $1$ $1$
    $0$ $0$ $0$ $0$ $1$ $1$ $1$ $1$ $0$
  • Table 3   Structure matrices of binary operators
    $\sigma$ $\vee$ $\wedge$ $\ra$ $\lra$ $\downarrow$ $\uparrow$ $\bar{\vee}$
    $M_{\sigma}$ $\d_2[1,1,1,2]$ $\d_2[1,2,2,2]$ $\d_2[1,2,1,1]$ $\d_2[1,2,2,1]$ $\d_2[2,2,2,1]$ $\d_2[2,1,1,1]$ $\d_2[2,1,1,2]$