Hybrid Model of Coalition Formation in Network-Centric Systems

Abstract

The article proposes a hybrid model for the formation of heterogeneous mobile robot coalitions in a group management system with a network-centric architecture. The hybrid model of heterogeneous coalition formation includes graph and game components. The graph component characterizes the communication properties of mobile robots as infrastructure objects of a network-centric system, and the game component characterizes the possibility of cooperation between mobile robots in the form of coalitions that combine the capabilities of individual mobile robots and possess a set of competencies necessary to complete the task. Indicators of the effectiveness of network-centric system objects are formed, for which the network metric of centrality by mediation and the game-theoretic metric of centrality by the Shapley vector were used to calculate. The formulation of the task of forming a heterogeneous coalition is formalized as a discrete multi-criteria optimization problem. To solve this problem, combined evolutionary computational procedures are being developed for calculating the centrality index by mediation for the vertices of a weighted graph and for forming an optimal heterogeneous coalition in a cooperative game in the form of a characteristic function. The problem of forming a heterogeneous coalition of mobile robots as part of a network-centric system to perform a specialized task is being solved

Please cite this article in English as:

Serov V.A., Trubienko O.V. Hybrid model of coalition formation in network-centric systems. Herald of the Bauman Moscow State Technical University, Series Instrument Engineering, 2025, no. 1 (150), pp. 137--161 (in Russ.). EDN: VMUSGV

References

[1] Gorodetskiy A., Tarasova I., eds. Smart electromechanical systems. Group interaction. In: Studies in Systems, Decision and Control, vol. 174. Cham, Springer, 2019. DOI: https://doi.org/10.1007/978-3-319-99759-9

[2] Gorodetskiy A., Tarasova I., eds. Smart electromechanical systems. Situational Control. In: Studies in Systems, Decision and Control, vol. 261. Springer, Cham, 2020. DOI: https://doi.org/10.1007/978-3-030-32710-1

[3] Gorodetskiy A., Tarasova I., eds. Smart electromechanical systems. Behavioral decision making. In: Studies in Systems, Decision and Control, vol. 352. Cham, Springer, 2021. DOI: https://doi.org/10.1007/978-3-030-68172-2

[4] Gorodetskiy A., Tarasova I., eds. Smart electromechanical systems. Recognition, identification, modeling, measurement systems, sensors. In: Studies in Systems, Decision and Control, vol. 419. Cham, Springer, 2022. DOI: https://doi.org/10.1007/978-3-030-97004-8

[5] Voronov E.M., Mikrin E.A., Obnosov B.V., eds. Stabilizatsiya, navedenie, gruppovoe upravlenie i sistemnoe modelirovanie bespilotnykh letatelnykh apparatov. Sovremennye podkhody i metody [Stabilization, guidance, group control, and system modeling of unmanned aerial vehicles. Modern approaches and methods]. Moscow, BMSTU Publ., 2018.

[6] Pshikhopov V.Kh., ed. Gruppovoe upravlenie podvizhnymi obektami v neopredelennykh sredakh [Group control of moving objects in uncertain environments]. Moscow, FIZMATLIT Publ., 2015.

[7] Kalyaev I.A., Gayduk A.R., Kapustyan S.G. Modeli i algoritmy kollektivnogo upravleniya v gruppakh robotov [Models and algorithms of collective control in groups of robots]. Moscow, FIZMATLIT Publ., 2009.

[8] Manko S.V., Lokhin V.M., Diane S.K. Prototype multi-agent robotic debris removal system: principles of development and experimental studies. Russian Technological Journal, 2022, vol. 10 (6), pp. 28--41 (in Russ.). DOI: https://doi.org/10.32362/2500-316X-2022-10-6-28-41

[9] Navarro I., Matha F. A survey of collective movement of mobile robots. Int. J. Adv. Robot. Syst., 2013, vol. 10, no. 1. DOI: https://doi.org/10.5772/54600

[10] Bertuccelli L., Choi H.-L., Cho P., et al. Real-time Multi-UAV task assignment in dynamic and uncertain environments. AIAA Guidance, Navigation, and Control Conf., 2009, no. AIAA-2009-5776. DOI: https://doi.org/10.2514/6.2009-5776

[11] Xu D., Zhang X., Zhu Z., et al. Behavior-based formation control of swarm robots. Math. Probl. Eng., 2014, vol. 2014, art. 205759. DOI: https://doi.org/10.1155/2014/205759

[12] Ungureanu V. Pareto-Nash-Stackelberg game and control theory. In: Smart Innovation, Systems and Technologies, vol. 89. Cham, Springer, 2018. DOI: https://doi.org/10.1007/978-3-319-75151-1

[13] Serov V.A., Babintsev Yu.N., Kondakov N.S. Neyroupravlenie mnogokriterialnymi konfliktnymi sistemami [Neurocontrol of multicriteria conflict systems]. Moscow, MSU Publ., 2011.

[14] Smirnov A.V., Sheremetov L.B. Models of coalition formation among cooperative agents: The current state and prospects of research. Sci. Tech. Inf. Proc., 2012, vol. 39, no. 5, pp. 283--292. DOI: https://doi.org/10.3103/S014768821205005X

[15] Klusch M., Gerber A. Dynamic coalition formation among rational agents. IEEE Intell. Syst., 2002, vol. 17, iss. 3, pp. 42--47. DOI: https://doi.org/10.1109/MIS.2002.1005630

[16] Romero Cortes J., Sheremetov L. Model of cooperation in multi agent systems with fuzzy coalitions. In: Dunin-Keplicz B., Nawarecki E. (eds). From Theory to Practice in Multi-Agent Systems. CEEMAS 2001. Lecture Notes in Computer Science, vol. 2296. Berlin, Heidelberg, Springer, pp. 263--272. DOI: https://doi.org/10.1007/3-540-45941-3_28

[17] De Cristofaro M., Lansdowne C., Schlesinger A. Heterogeneous wireless mesh network technology evaluation for space proximity and surface applications. SpaceOps Conference, 2014, art. AIAA 2014-1600. DOI: https://doi.org/10.2514/6.2014-1600

[18] Goforth M., Ratliff J., Barton R., et al. Avionics architectures for exploration: wireless technologies and human spaceflight. IEEE WiSEE, 2014. DOI: https://doi.org/10.1109/WiSEE.2014.6973073

[19] Diane S.A.K., Iskhakov A.Yu., Iskhakova A.O. Network-centric motion control algorithm for a group of mobile robots. Modelirovanie, optimizatsiya i informatsionnye tekhnologii [Modeling, Optimization and Information Technology], 2022, vol. 10, no. 1 (in Russ.). DOI: https://doi.org/10.26102/2310-6018/2022.36.1.026

[20] Mulyukha V.A., Guk M.Yu., Zaborovskiy V.S. Supervisory network-centric control system for robotic objects. Robototekhnika i tekhnicheskaya kibernetika [Robotics and Technical Cybernetics], 2016, no. 3, pp. 42--47 (in Russ.). EDN: YVRNVZ

[21] Makarenko S.I., Oleynikov A.Y., Chernitskaya T.E. Models of interoperability assessment for information systems. Sistemy upravleniya, svyazi i bezopasnosti [Systems of Control, Communication and Security], 2019, no. 4, pp. 215--245 (in Russ.). EDN: NACKGD

[22] Steel J., Drogemuller R., Toth B. Model interoperability in building information modelling. Softw. Syst. Model., 2012, vol. 11, no. 1, pp. 99--109. DOI: https://doi.org/10.1007/s10270-010-0178-4

[23] New European Interoperability Framework. Promoting seamless services and data flows for European public administrations. Luxembourg, Publications Office of the European Union, 2017.

[24] Sahingoz O.K. Networking models in flying ad-hoc networks (FANETs): concepts and challenges. J. Intell. Robot. Syst., 2014, vol. 74, no. 1-2, pp. 513--527. DOI: https://doi.org/10.1007/s10846-013-9959-7

[25] Wang J., Jiang C., Han Z., et al. Taking drones to the next level: Cooperative distributed unmanned-aerial-vehicular networks for small and mini drones. IEEE Veh. Technol. Mag., 2017, vol. 12, iss. 3, pp. 73--82. DOI: https://doi.org/10.1109/MVT.2016.2645481

[26] Martynova L.A., Rozengauz M.B. Efficient operation of a group of standalone unmanned submersibles in a network-centric system of underwater illumination. Informatsionno-upravlyayushchie sistemy [Information and Control Systems], 2017, no. 3, pp. 47--57 (in Russ.). EDN: YSLPUL

[27] Skibski O., Michalak T.P., Rahwan T., et al. Algorithms for the Shapley and Myerson values in graph-restricted games. AAMAS, 2014, vol. 1, pp. 197--204.

[28] Michalak T., Aadithya K., Szczepański P., et al. Efficient computation of the shapley value for game-theoretic network centrality. J. Artif. Intell. Res., 2013, vol. 46, pp. 607--650. DOI: https://doi.org/10.1613/jair.3806

[29] Van Campen T., Hamers H., Husslage B., et al. A new approximation method for the Shapley value applied to the WTC 9/11 terrorist attack. Soc. Netw. Anal. Min., 2017, vol. 8, no. 1, art. 3. DOI: https://doi.org/10.1007/s13278-017-0480-z

[30] Lindelauf R., Hamers H., Husslage B. Game theoretic centrality analysis of terrorist networks: the cases of Jemaah Islamiyah and Al Qaeda. CentER Discussion Paper, 2011, no. 107. DOI: https://doi.org/10.2139/ssrn.1934726

[31] Algaba E., Prieto A., Saavedra-Nieves A. Rankings in the Zerkani network by a game theoretical approach. arXiv:2202.07730. DOI: https://arxiv.org/abs/2202.07730v1

[32] Algaba E., Prieto A., Saavedra-Nieves A., et al. Analyzing the Zerkani network with the Owen value. In: Kurz S., Maaser N., Mayer A. (eds). Advances in Collective Decision Making. Studies in Choice and Welfare. Cham, Springer, 2023, pp. 225--242. DOI: https://doi.org/10.1007/978-3-031-21696-1_14

[33] Myerson R.B. Graphs and cooperation in games. Math. Oper. Res., 1977, vol. 2, no. 3, pp. 209--296. DOI: https://doi.org/10.1287/moor.2.3.225

[34] Amer R., Gimenez J.M. A connectivity game for graphs. Math. Meth. Oper. Res., 2004, vol. 60, no. 3, pp. 453--470. DOI: https://doi.org/10.1007/s001860400356

[35] Narayanam R., Narahari Y. A Shapley value-based approach to discover influential nodes. IEEE Trans. Autom. Sci. Eng., 2011, vol. 8, iss. 1, pp. 130--147. DOI: https://doi.org/10.1109/TASE.2010.2052042

[36] Perova J.P., Grigoriev V.P., Zhukov D.O. Models and methods for analyzing complex networks and social network structures. Russian Technological Journal, 2023, vol. 11, no. 2, pp. 33--49. DOI: https://doi.org/10.32362/2500-316X-2023-11-2-33-49

[37] Newman M.E.J. Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E, 2006, vol. 74, iss. 3, art. 036104. DOI: https://doi.org/10.1103/PhysRevE.74.036104

[38] Mieghem P.V. Graph spectra for complex networks. Cambridge Univ. Press, 2011.

[39] Borgatti S.P., Everett M.G. A graph-theoretic perspective on centrality. Soc. Networks, 2005, vol. 28, iss. 4, pp. 466--484. DOI: https://doi.org/10.1016/j.socnet.2005.11.005

[40] Rochat Y. Closeness centrality extended to unconnected graphs: the harmonic centrality index. ASNA, 2009. Available at: https://infoscience.epfl.ch/entities/publication/7864800f-6d09-4bb4-bb09-f12a335fca92 (accessed: 15.02.2025).

[41] Boldi P., Vigna S. Axioms for centrality. Internet Math., 2014, vol. 10, iss. 3-4. DOI: https://doi.org/10.1080/15427951.2013.865686

[42] Piraveenan M., Prokopenko M., Hossain L. Percolation centrality: quantifying graph-theoretic impact of nodes during percolation in networks. PLOS ONE, 2013, vol. 8, no. 1, art. e53095. DOI: https://doi.org/10.1371/journal.pone.0053095

[43] Szczepański P., Michalak T., Rahwan T. A new approach to betweenness centrality based on the Shapley value. Proc. 11th Int. Conf. on Autonomous Agents and Multiagent Systems, 2012, vol. 1, pp. 239--246.

[44] Brandes U. A faster algorithm for betweenness centrality. J. Math. Sociol., 2001, vol. 25, iss. 2, pp. 163--177. DOI: https://doi.org/10.1080/0022250X.2001.9990249

[45] Serov V.A. Genetic algorithms of optimizing control of multi- objective systems under condition of uncertainty based on conflict equilibrium. Herald of the Bauman Moscow State Technical University, Series Instrument Engineering,2007, no. 4 (69), pp. 70--80 (in Russ.). EDN: IJDHED