Nonlinear Convergence Algorithm: Structural Properties with Doubly Stochastic Quadratic Operators for Multi-Agent Systems

Abdulghafor, Rawad; Turaev, Sherzod; Zeki, Akram; Abubaker, Adamu

doi:10.1515/jaiscr-2018-0003

Abstract

This paper proposes nonlinear operator of extreme doubly stochastic quadratic operator (EDSQO) for convergence algorithm aimed at solving consensus problem (CP) of discrete-time for multi-agent systems (MAS) on n-dimensional simplex. The first part undertakes systematic review of consensus problems. Convergence was generated via extreme doubly stochastic quadratic operators (EDSQOs) in the other part. However, this work was able to formulate convergence algorithms from doubly stochastic matrices, majorization theory, graph theory and stochastic analysis. We develop two algorithms: 1) the nonlinear algorithm of extreme doubly stochastic quadratic operator (NLAEDSQO) to generate all the convergent EDSQOs and 2) the nonlinear convergence algorithm (NLCA) of EDSQOs to investigate the optimal consensus for MAS. Experimental evaluation on convergent of EDSQOs yielded an optimal consensus for MAS. Comparative analysis with the convergence of EDSQOs and DeGroot model were carried out. The comparison was based on the complexity of operators, number of iterations to converge and the time required for convergences. This research proposed algorithm on convergence which is faster than the DeGroot linear model.

References

[1] W. Ren, R. W. Beard, and E. M. Atkins, A survey of consensus problems in multi-agent coordination, in American Control Conference, 2005. Proceedings of the 2005, pp. 1859–1864, IEEE, 2005.
Search in Google Scholar Back to article
[2] Z. Lin, B. Francis, and M. Maggiore, State agreement for continuous-time coupled nonlinear systems, SIAM Journal on Control and Optimization, vol. 46, no. 1, pp. 288–307, 2007.10.1137/050626405
Search in Google Scholar Back to article
[3] E. Lovisari and S. Zampieri, Performance metrics in the average consensus problem: a tutorial, Annual Reviews in Control, vol. 36, no. 1, pp. 26–41, 2012.10.1016/j.arcontrol.2012.03.003
Search in Google Scholar Back to article
[4] E. Eisenberg and D. Gale, Consensus of subjective probabilities: The pari-mutuel method, The Annals of Mathematical Statistics, pp. 165–168, 1959.10.1214/aoms/1177706369
Open DOI Search in Google Scholar Back to article
[5] M. H. DeGroot, Reaching a consensus, Journal of the American Statistical Association, vol. 69, no. 345, pp. 118–121, 1974.10.1080/01621459.1974.10480137
Search in Google Scholar Back to article
[6] R. L. Berger, A necessary and sufficient condition for reaching a consensus using degroot’s method, Journal of the American Statistical Association, vol. 76, no. 374, pp. 415–418, 1981.10.1080/01621459.1981.10477662
Search in Google Scholar Back to article
[7] I. Matei, J. S. Baras, and C. Somarakis, Convergence results for the linear consensus problem under markovian random graphs, SIAM Journal on Control and Optimization, vol. 51, no. 2, pp. 1574–1591, 2013.
Search in Google Scholar Back to article
[8] H. J. LeBlanc, H. Zhang, S. Sundaram, and X. Koutsoukos, Consensus of multi-agent networks in the presence of adversaries using only local information, in Proceedings of the 1st international conference on High Confidence Networked Systems, pp. 1–10, ACM, 2012.10.1145/2185505.2185507
Search in Google Scholar Back to article
[9] P. Lin and W. Ren, Constrained consensus in unbalanced networks with communication delays, Automatic Control, IEEE Transactions on, vol. 59, no. 3, pp. 775–781, 2014.10.1109/TAC.2013.2275671
Search in Google Scholar Back to article
[10] S. Bernstein, Solution of a mathematical problem connected with the theory of heredity, The Annals of Mathematical Statistics, vol. 13, no. 1, pp. 53–61, 1942.10.1214/aoms/1177731642
Search in Google Scholar Back to article
[11] S. Vallander, On the limit behavior of iteration sequence of certain quadratic transformations, in Soviet Math. Doklady, vol. 13, pp. 123–126, 1972.
Search in Google Scholar Back to article
[12] I. Olkin and A. W. Marshall, Inequalities: Theory of majorization and its applications, Academic, New York, 1979.
Search in Google Scholar Back to article
[13] R. N. Ganikhodzhaev, On the definition of bistochastic quadratic operators, Russian Mathematical Surveys, vol. 48, no. 4, pp. 244–246, 1993.10.1070/RM1993v048n04ABEH001058
Open DOI Search in Google Scholar Back to article
[14] T. Ando, Majorization, doubly stochastic matrices, and comparison of eigenvalues, Linear Algebra and Its Applications, vol. 118, pp. 163–248, 1989.10.1016/0024-3795(89)90580-6
Search in Google Scholar Back to article
[15] Y. I. Lyubich, D. Vulis, A. Karpov, and E. Akin, Mathematical structures in population genetics, Biomathematics(Berlin), 1992.10.1007/978-3-642-76211-6
Search in Google Scholar Back to article
[16] R. Ganikhodzhaev, Quadratic stochastic operators, lyapunov functions, and tournaments, Russian Academy of Sciences. Sbornik Mathematics, vol. 76, no. 2, p. 489, 1993.10.1070/SM1993v076n02ABEH003423
Open DOI Search in Google Scholar Back to article
[17] R. Ganikhodzhaev and U. Rozikov, Quadratic stochastic operators: Results and open problems, arXiv preprint arXiv:0902.4207, 2009.
Search in Google Scholar Back to article
[18] R. Ganikhodzhaev and F. Shahidi, Doubly stochastic quadratic operators and birkhoffs problem, Linear Algebra and its Applications, vol. 432, no. 1, pp. 24–35, 2010.10.1016/j.laa.2009.07.002
Search in Google Scholar Back to article
[19] R. Abdulghafor, S. Turaev, A. Abubakar, and A. Zeki, The extreme doubly stochastic quadratic operators on two dimensional simplex, in Advanced Computer Science Applications and Technologies (ACSAT), 2015 4th International Conference on, pp. 192–197, IEEE, 2015.10.1109/ACSAT.2015.36
Search in Google Scholar Back to article
[20] F. Shahidi, On dissipative quadratic stochastic operators, Applied Mathematics and Information Sciences, vol. 2, pp. 211–223, 2008.
Search in Google Scholar Back to article
[21] F. Shahidi, On the extreme points of the set of bistochastic operators, Mathematical Notes, vol. 84, no. 3, pp. 442–448, 2008.10.1134/S0001434608090150
Open DOI Search in Google Scholar Back to article
[22] R. Abdulghafor, F. Shahidi, A. Zeki, and S. Turaev, Dynamics classifications of extreme doubly stochastic quadratic operators on 2d simplex, in Advanced Computer and Communication Engineering Technology, pp. 323–335, Springer, 2016.10.1007/978-3-319-24584-3_26
Search in Google Scholar Back to article
[23] F. A. Shahidi, Doubly stochastic operators on a finite-dimensional simplex, Siberian Mathematical Journal, vol. 50, no. 2, pp. 368–372, 2009.10.1007/s11202-009-0042-3
Open DOI Search in Google Scholar Back to article
[24] F. Shahidi and M. Abu Osman, The limit behaviour of trajectories of dissipative quadratic stochastic operators on finite-dimensional simplex, Journal of Difference Equations and Applications, vol. 19, no. 3, pp. 357–371, 2013.10.1080/10236198.2011.644281
Search in Google Scholar Back to article
[25] F. Shahidi, On infinite-dimensional dissipative quadratic stochastic operators, Advances in Difference Equations, vol. 2013, no. 1, pp. 1–13, 2013.
Search in Google Scholar Back to article
[26] R. Abdulghafor, F. Shahidi, A. Zeki, and S. Turaev, Dynamics of doubly stochastic quadratic operators on a finite-dimensional simplex, Open Mathematics, vol. 14, no. 1, pp. 509–519, 2016.10.1515/math-2016-0045
Search in Google Scholar Back to article
[27] F. Shahidi, R. Ganikhodzhaev, and R. Abdulghafor, The dynamics of some extreme doubly stochastic quadratic operators, Middle-East Journal of Scientific Research (Mathematical Applications in Engineering), vol. 13, pp. 59–63, 2013.
Search in Google Scholar Back to article
[28] R. Abdulghafor, S. Turaev, M. Tamrin, and M. Izzuddin, Nonlinear consensus for multi-agent systems using positive intractions of doubly stochastic quadratic operators, International Journal on Perceptive and Cognitive Computing (IJPCC), vol. 2, no. 1, pp. 19–22, 2016.10.31436/ijpcc.v2i1.30
Search in Google Scholar Back to article
[29] R. Abdulghafor, S. Turaev, A. Zeki, and F. Shahidi, The convergence consensus of multi-agent systems controlled via doubly stochastic quadratic operators, in Agents, Multi-Agent Systems and Robotics (ISAMSR), 2015 International Symposium on, pp. 59–64, IEEE, 2015.
Search in Google Scholar Back to article
[30] L. Panait and S. Luke, Cooperative multi-agent learning: The state of the art, Autonomous Agents and Multi-Agent Systems, vol. 11, no. 3, pp. 387–434, 2005.10.1007/s10458-005-2631-2
Search in Google Scholar Back to article
[31] A. Ajorlou, A. Momeni, and A. G. Aghdam, Sufficient conditions for the convergence of a class of nonlinear distributed consensus algorithms, Automatica, vol. 47, no. 3, pp. 625–629, 2011.10.1016/j.automatica.2011.01.042
Search in Google Scholar Back to article
[32] A. N. Bishop and A. Doucet, Distributed nonlinear consensus in the space of probability measures, arXiv preprint arXiv:1404.0145, 2014.10.3182/20140824-6-ZA-1003.00341
Search in Google Scholar Back to article
[33] T. Vicsek, A. Czirók, E. Ben-Jacob, I. Cohen, and O. Shochet, Novel type of phase transition in a system of self-driven particles, Physical review letters, vol. 75, no. 6, p. 1226, 1995.10.1103/PhysRevLett.75.122610060237
Search in Google Scholar Back to article
[34] J. N. Tsitsiklis, D. P. Bertsekas, M. Athans, et al., Distributed asynchronous deterministic and stochastic gradient optimization algorithms, IEEE transactions on automatic control, vol. 31, no. 9, pp. 803–812, 1986.10.1109/TAC.1986.1104412
Search in Google Scholar Back to article
[35] A. Jadbabaie, J. Lin, and A. S. Morse, Coordination of groups of mobile autonomous agents using nearest neighbor rules, Automatic Control, IEEE Transactions on, vol. 48, no. 6, pp. 988–1001, 2003.10.1109/TAC.2003.812781
Search in Google Scholar Back to article
[36] F. Cucker, S. Smale, and D.-X. Zhou, Modeling language evolution, Foundations of Computational Mathematics, vol. 4, no. 3, pp. 315–343, 2004.10.1007/s10208-003-0101-2
Search in Google Scholar Back to article
[37] N. A. Lynch, Distributed algorithms. Morgan Kaufmann, 1996.
Search in Google Scholar Back to article
[38] S. M. Ulam, A collection of mathematical problems, New York, vol. 29, 1960.
Search in Google Scholar Back to article
[39] Z.-H. Guan, Y. Wu, and G. Feng, Consensus analysis based on impulsive systems in multiagent networks, Circuits and Systems I: Regular Papers, IEEE Transactions on, vol. 59, no. 1, pp. 170–178, 2012.10.1109/TCSI.2011.2158715
Search in Google Scholar Back to article
[40] G. Cui, S. Xu, F. L. Lewis, B. Zhang, and Q. Ma, Distributed consensus tracking for non-linear multiagent systems with input saturation: a command filtered backstepping approach, IET Control Theory & Applications, vol. 10, no. 5, pp. 509–516, 2016.10.1049/iet-cta.2015.0627
Search in Google Scholar Back to article
[41] L. Yu-Mei and G. Xin-Ping, Nonlinear consensus protocols for multi-agent systems based on centre manifold reduction, Chinese Physics B, vol. 18, no. 8, p. 3355, 2009.10.1088/1674-1056/18/8/040
Search in Google Scholar Back to article
[42] F. Shahidi, On dissipative quadratic stochastic operators, arXiv preprint arXiv:0708.1813, 2007.
Search in Google Scholar Back to article

Nonlinear Convergence Algorithm: Structural Properties with Doubly Stochastic Quadratic Operators for Multi-Agent Systems

Abstract

Paradigm

My account