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

This paper provides a comprehensive survey on semi-tensor product (STP) of matrices and its applications to different disciplines. First of all, the STP and its basic properties are introduced. Meanwhile, its inside physical meaning is explained. Second, its application to conventional dynamic systems is presented. As an example, the region of attraction of stable equilibriums is discussed. Third, its application to logical systems is presented. Particularly, the algebraic state space representation of logical systems and the important role it plays in analysis and control of logical systems are emphasized. Fourth, its application to finite games is discussed. The most interesting problems include potential game, evolutionary game, and game theoretic control. Finally, the mathematical essence of STP is briefly introduced.


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

  •   
    $x$ $\neg~x$
    $1$ $0$
    $0$ $1$
  •   

    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

  •   
    $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$
  •   
    $\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]$

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1