INTELLECTUALIZATION METHODS FOR DISCRETE PROCESSES AND CONTROL SYSTEMS
Laboratory No. 11 is one of the oldest in the Institute. Outstanding scientists worked here, namely, Prof. M.A. Aizerman (Head of the Laboratory until 1963), Prof. E.M. Braverman, Prof. L.A. Zalmanzon, Prof. L.I. Rozonoer, and Prof. A.A. Tal’ (Head of the Laboratory in 1963—1991).
In 1991—2019, the Laboratory was headed by Oleg P. Kuznetsov, Dr. Sci. (Eng.), Professor, and Chairman (2000—2021) of the Scientific Council of the Russian Association for Artificial Intelligence.
Since 2019, Laboratory No. 11 has been headed by Lyudmila Yu. Zhilyakova, Dr. Sci. (Phys.—Math.).
Currently, the Laboratory staff includes 17 employees, particularly 4 Doctors of Sciences and 2 Candidates of Sciences.
The main research areas of Laboratory No.11 are artificial intelligence (AI) and network structures, namely:
- biologically oriented AI methods and modeling of biological neural networks;
- network representations of knowledge, objects, and processes;
- multi-agent systems and group behavior;
- modeling and analysis of social networks.
1. Biologically Oriented AI Methods (O.P. Kuznetsov, N.I. Bazenkov, L.Yu. Zhilyakova, and N.V. Chaplinskaya)
The brain performs many tasks more efficiently than the computer. Some examples are visual image processing, orientation in space, and decision-making under incomplete information. It means that information processing mechanisms in the brain are fundamentally different. Revealing the basic principles of these mechanisms should lead to a breakthrough in AI technologies. Research within this area has several interrelated lines.
1.1 Modeling of interactions in multi-transmitter neural ensembles (O.P. Kuznetsov, N.I. Bazenkov, and L.Yu. Zhilyakova)
In 2015, together with neurobiologists from the Koltsov Institute of Developmental Biology (the Russian Academy of Sciences), research into discrete models of chemical extra synaptic interactions between neurons in biological nervous systems was started. These interactions play a key role in the nervous system’s functioning, but there are few attempts to describe them mathematically.
The basic principles of the developed model are as follows. Neurons are located in a single extracellular space (ECS). When a neuron is active, it releases a specific transmitter substance in the ECS. The released transmitter affects all neurons with receptors sensitive to it. (In other words, this transmitter is a broadcasting signal.) Depending on the receptor type, the transmitter’s effect on a receptor can be excitatory or inhibitory. The neurons and the ECS form a neural ensemble generating rhythmic activity. This ensemble can be described by a network: a directed connection from neuron A to neuron B exists if A releases a transmitter to which the receptors of B are sensitive. An algorithm was developed to calculate the model behavior, and the algorithm was implemented in software.
In 2020, O.P. Kuznetsov proposed a non-biological generalization of this model, the so-called asynchronous multi-agent multi-sort system. Omitting biological entities; the model remains a network of abstract agents exchanging signals of various sorts. It can be interpreted as a social network with different types of information exchanges. A method was proposed to determine the boundaries of stable behavior under varying parameters of the network. In 2021, O.P. Kuznetsov investigated signal propagation in a chain of asynchronous threshold elements and described the conditions of signal propagation through the chain.
1.2 Modeling of spiking neural networks (N.V. Chaplinskaya)
In 2022, a new learning rule was proposed for spiking neural networks based on the plasticity effect of synaptic delays. It was used to recognize three contrasting images by a spiking neural network with three neurons. The capabilities of this rule will be investigated for other architecture networks with application to more complex problems. Also, this will be modified by adding other synaptic plasticity characteristics to increase the biological plausibility of the models.
1.3 Biologically plausible models of motion control (N.I. Bazenkov)
Human locomotion modeling and control is a topical problem at the junction of mathematics, biology, and medicine. A promising line of research is to develop modern machine learning methods and biologically adequate models of motion control. Laboratory’s studies are devoted to constructing a model of individual movements based on experimental data.
The applied goal of the research is the short-term prediction of the movements of a bionic prosthetic leg user to improve prosthetic control. A global goal of the research is to construct a movement model for predicting user movements in abnormal situations (not considered in laboratory tests). This research combines accurate biomechanical models of the skeleton and musculature with reinforcement learning methods.
2. Network Representations of Knowledge, Objects, and Processes
2.1 Structural optimization methods for complex systems (M.V. Goubko and N.I. Shushko)
Managing the system structure reduces to a combinatorial optimization problem: choosing an admissible structure from a finite set that minimizes a given cost function. Laboratory’s research of optimal structure models was based on the concept of “sectional” cost functions (A.A. Voronin and S.P. Mishin, Volgograd). M.V. Goubko generalized this model and developed a general structural optimization theory for complex systems with applications to computer science, management, mathematical chemistry, and other fields. Current studies focus on algorithms for obtaining an optimal structure of road networks through mixed linear programming.
2.2 Theory of resource networks (O.P. Kuznetsov, L.Yu. Zhilyakova, N.V. Chaplinskaya, and V.R. Koreshkov)
O.P. Kuznetsov proposed the resource network model in 2009. In this model, the vertices of a direct graph contain a homogeneous resource. The weights of the edges denote their capacities. The vertices distribute the resource to the outgaining edges at each step according to one of two rules. If the resource amount exceeds the total weight of all outgoing edges, each outgoing edge is given an amount equal to its capacity. Otherwise, the vertex completely distributes its resource among all edges proportionally to their capacities. The total resource amount does not change. A special case (a complete homogeneous network) was described: the network is given by a complete graph in which all edges have the same capacity. This simple example demonstrated the main properties inherent in an arbitrary resource network: stability under a small resource amount, dependence on the initial conditions under a large resource amount, and the existence of a threshold separating small and large resource values.
L.Yu. Zhilyakova almost completely described the behavior of resource networks and presented the results in two monographs.
A modification of the model, a resource network with the limited capacity of attractor vertices (vertices that accumulate a resource surplus), was proposed and investigated.
N.V. Chaplinskaya and L.Yu. Zhilyakova studied the resource network with “greedy” vertices (2020—2021). As opposed to the standard model, when distributing the resource, a vertex first fills its loop and then allocates the residual amounts into the outgoing arcs. The limiting characteristics of such networks were obtained.
V.R. Koreshkov investigates non-ergodic resource networks and an open resource network, i.e., a network receiving a resource from the outside (2022).
2.3 Ontological approach to knowledge management in scientific organizations (O.P. Kuznetsov, and V.S. Sukhoverov)
An approach was proposed to determine the competence of researchers based on correlating the terminology of their publications with the terms of the subject area ontology. The subject area of scientific knowledge was represented as a tree with two types of vertices: theme vertices and term vertices.
Two types of profiles were defined: a document (publication) profile, characterizing the document’s relevance to the themes of the subject area, and an employee profile, characterizing the employee’s competence in certain themes of the subject area. A formula was proposed to evaluate the document’s relevance to a specific ontology theme. This formula is adopted to calculate the competence of employees according to their publications. The calculated competencies can be used to select experts, reviewers, etc. In 2017, the first version of the software system was developed and successfully tested on papers published in Automation and Remote Control. In 2019, a system for determining the competencies of the Institute’s employees was developed using the publications database. Currently, the system is operating in debugging conditions.
2.4 Symbolic information processing in AI systems (D.Yu. Maximov)
The studies started with developing a technique to assign a new task executor for a group of robots based on the lattice of their capabilities. Subsequently, the symbolic information represented by the lattice elements was processed in neural networks (in associative memory) and cognitive maps. Theorems on the convergence of such networks and maps and on the storage of a given set of symbolic information patterns in associative memory were proved. Possible applications of such networks and maps were considered.
2.5 Semiotic Models in Decision Support Systems under Uncertainty (A.A. Kulinich)
A Decision Support System (DSS) was proposed based on a semiotic model of a subject area and natural language processing methods. The model includes three models of the subject area: syntactic, semantic, and pragmatic. Methods were developed for solving the direct problem (predicting the situation development) and the inverse problem (calculating the situation parameters for transfer into a target state). A body of texts relevant to the subject area was used as the knowledge base of the semiotic model. A semantic calculator was proposed to extract generic relations from the body of texts based on distributional analysis (Word2Vec). Experimental software was developed.
3. Multi-agent Systems and Group Behavior of Robots (R.P. Agaev, D.K. Khomutov, A.A. Kulinich, A.Yu. Efremov, Ya.Yu. Tsodikova, and A.K. Loginov)
3.1 Decentralized control of multi-agent systems (R.P. Agaev and D.K. Khomutov)
The dynamics of network multi-agent systems are essentially determined by a digraph of information links between agents. The decentralized control of such systems is studied based on the research of P.Yu. Chebotarev and R.P. Agaev on the algebraic theory of digraphs. For normalized Laplace matrices, the localization area of their spectrum was obtained.
For several consensus search protocols, the asymptotics were studied, and the limit state components were expressed through the eigenprojectors of the Laplace matrices of agents’ dependence digraphs. Theorems with graph-theoretic interpretations of consensus solutions were proved. The consensus problem in multi-agent systems with an unconnected influence digraph was investigated. An orthogonal projection method for regularizing consensus was proposed. Several latent consensus models were studied for agent influence digraphs without spanning outgoing trees. Also, consensus models with delay were considered. A lecture course on the theory of multi-agent systems was prepared. This course is delivered at the Moscow Institute of Physics and Technology and ICS RAS.
Another aspect of algebraic graph theory (design and analysis of metrics, closeness measures, and centrality indices for vertices) is used when investigating the structure of various networks. Such measures are necessary for clustering and classification on graphs. Laboratory’s employees proposed new closeness measures and algebraic indices of graph vertices with application to data analysis. Their connections with the characteristics of Markov chains were established.
3.2 Formation and operation models for intelligent robot teams with the reactive and BDI architectures (A.A. Kulinich)
Group behavior models of robots with the reactive architecture were constructed. Behavior algorithms were proposed for a swarm of robots, “lazy” robots, and selfish robots. The operating environment of robots was represented as nested subspaces of the “Robot Group—Environment” system. The model of an intelligent robot with the BDI architecture was developed. Collective operation conditions for robots were described. They include information exchange protocols for the beliefs, intentions, and joint operation conditions of robots as well as action coordination protocols. Experimental studies of the proposed models, algorithms, and architectures showed their effectiveness.
3.3 Swarm robotics (A.Yu. Efremov)
Swarm robotics considers the collective behavior of many simple agents arising from their local interactions with themselves and the environment. Robotic flocking is one line of research. The basic flocking model (the self-organized coordinated motion of a group of autonomous mobile objects) consists of three velocity and course control rules that describe the maneuvering of individual objects based on the positions and velocities of their nearest neighbors.
Virtual agents are used to influence the behavior of all (some) robots in the swarm: agents setting the target point and those setting the desired course. The agents have maneuvering constraints, the case not considered in most previous studies. An algorithm for avoiding obstacles (a set of convex polygons) was considered within this model. The robot dimensions, constraints on their minimum and maximum velocities, maximum acceleration, and rotation rate were introduced. With obstacles described by a set of convex polygons, the robots avoid collisions and move along a boundary. The use of virtual objects is investigated for typical maneuvering with safe distance control.
3.4 Voting in a Stochastic Environment (Ya.Yu. Tsodikova and A.K. Loginov)
This line of research deals with dynamic systems determined by collective decision-making in a stochastic environment. It continues the studies of dynamic voting models begun by A.V. Malishevsky and M.A. Aizerman (Laboratory No. 25). The Voting in Stochastic Environment (ViSE) model is developed to analyze the influence of different social attitudes of the participants (egoism, collectivism, etc.) on social dynamics. Cooperation mechanisms are constructed, and optimal decision and incentive procedures are designed in different conditions. The concept of an optimal voting threshold was introduced and investigated.
4. Processes in Social Networks
4.1 Information influence and control in social networks
In the 2000s, research on information influence and control in social networks was initiated by D.A. Gubanov, D.A. Novikov, and A.G. Chkhartishvili. A social network is a set of agents that exchange information and execute actions based on their beliefs (reputation, trust, and opinions). The agent’s beliefs change under the influence of other network participants and control subjects. A set of models was developed for various situations of informational influence, control, and confrontation. These models have an internal structure of agents and reflect socio-psychological effects (consensus, maintained disagreement, polarization, etc.). For each model, methods were proposed to influence the network state and the effects observed. An actional approach to the formalization of social network elements was introduced.
The results are applied in practice. Since the late 2000s, information processes in online social networks (LiveJournal, Facebook, Reddit, and VKontakte) have been studied by D.A. Gubanov, N.I. Bazenkov, I.V. Kozitsin, and other researchers. Methods and information technologies of social network analysis are developed, including ones to identify active groups and communities, calculate user influence, assess user vulnerability to information influences, and identify discussion initiators and network distribution channels. Recent research is to identify the opinions of individuals in online social networks and identify the mechanisms of their dynamics based on deep machine learning methods.
4.2 Propagation of activities in networks of MIMO-agents (L.Yu. Zhilyakova and P.A. Nechaeva)
L.Yu. Zhilyakova proposed a new propagation model for multiple activities in networks of heterogeneous agents perceiving and generating multiple types of information (MIMO-agents). Agents are threshold elements characterized by the threshold value, a stochastic vector of susceptibility to various signals, and memory depth and strength. A network of MIMO-agents is a weighted graph in which the weights characterize the strength of agents’ influence. When calculating the impact of its environment, an agent considers the arc weights and the type of activities of its different neighbors.
Small networks with two types of activities were investigated. Criteria for a network of agents to be an ensemble of some kind (see the past research below) were established (L.Yu. Zhilyakova). A simulation model for large networks was developed (P.A. Nechaeva). The model is used to study activity propagation in networks with many nodes and various topologies.
5. Past research
Conflict Situations Modeling Based on Linear Cognitive Maps (S.G. Kulivets)
An approach to model conflict situations was proposed that combines game theory and cognitive maps. Models of agent’s interaction were constructed for two cases when the agents’ beliefs a) coincide and b) are inconsistent. The stability ranges of the cognitive map parameters were estimated within which the player’s strategy does not change. The analysis results were illustrated by studying the conflict of interests between Russia and Norway in the Barents Sea.
Reflective Formation Methods for Wireless Network Topologies (N.I. Bazenkov)
Wireless ad hoc networks are networks formed by autonomous wireless transmitters without additional infrastructure. The topology formation problem is assigning an appropriate power to each node to ensure network connectivity while minimizing the total power of all nodes. It is necessary to consider distributed algorithms when each node seeks to maximize a local objective function. A promising approach to developing such algorithms involves game theory: the topology formation problem is stated as a non-cooperative game. In this game, the network nodes are agents (players), and their utility functions incorporate two goals: maintaining network connectivity and minimizing power.
Laboratory No. 11 proposed a reflective double best-response algorithm in which an agent predicts the possible response of neighbors to its actions. As a result, more efficient actions are chosen at the cost of increased computations. Two modifications of the network formation algorithm were developed. The convergence of both algorithms was proved analytically, and their effectiveness was demonstrated in numerical experiments.
The Theory of Stationary Ensembles (O.P. Kuznetsov and S.G. Kulivets)
In 2015—2016, O.P. Kuznetsov proposed and investigated the model of a stationary neuronal ensemble, a network of McCulloch—Pitts neurons. Such a network is called a stationary ensemble if it maintains the unit state (all neurons are active) without external impacts. Necessary and sufficient conditions for a neural network to be a stationary ensemble were proved. In 2017—2018, S.G. Kulivets developed a software environment for constructing a network of formal neurons, calculating their behavior, identifying ensembles and networks of ensembles, and viewing the state graph of each ensemble.
Holographic Image Processing Methods (O.P. Kuznetsov and A.V. Markovskii)
In the early 2000s, Laboratory No. 11 developed two models of image information processing and storage based on the holographic approach. O.P. Kuznetsov proposed pseudo-optical neural networks (PNNs): information is transmitted using analog wave signals, whereas recording and reading are carried out according to holographic principles. L.B. Shipilina developed tools for PNN modeling. As shown by computer experiments, PNNs have an efficient organization of fast processes of image recognition and restoration as well as high resistance to damage. A.V. Markovskii developed a quasi-holographic distributed coding method for digital images. This method encodes a digital image for restoration even if a significant part of its surface was lost (90% and more).
The research results can be used to eliminate interference when transmitting graphic documentation via communication networks and protect graphic information.