Oleg P. Kuznetsov

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.), Prof., and Chairman of the Scientific Council of the Russian Association for Artificial Intelligence. Since 2019, the Laboratory has been headed by Dr. Sci. (Phys.-Math.) Lyudmila Yu. Zhilyakova. Currently, the Laboratory staff includes 9 employees, particularly 3 Doctors of Sciences and 4 Candidates of Sciences.

Lyudmila Yu. Zhilyakova, Head of Laboratory No. 11

For many years, the Laboratory developed the design and technical implementation principles of industrial pneumatic automation systems. In 1964, M.А. Aizerman, T.K. Berends, T.K. Efremova, A.A. Tagaevskaya, and A.A. Tal, employees of the Laboratory, received the Lenin Prize for developing and implementing the Universal System of Industrial Pneumatic Automation Elements (USIPAE) and creating devices of the Start system based on the USIPAE. Research and development activities using the USIPAE led to the design of control systems for various industrial facilities with the participation of the Institute’s employees.

The results of those works were published in five monographs. L.A. Zalmanzon left a noticeable trace in the development of domestic pneumatic automation and theoretical and practical foundations of fluidics. His creative heritage includes seven monographs on the subject.

In the late 1970s, employees who dealt with pneumatic automation problems moved to Laboratory No. 2, and Laboratory No. 11 switched to studying discrete systems and control processes and their theoretical models (finite-state automata and Petri nets).

In the 1960s, A.A. Tal’ developed a questionnaire approach to the design of finite-state automata. In the 1970s, V.A. Buevich, N.N. Ivanov, G.I. Mikhailov, V.V. Rudnev, and A.A. Tal’ created a tool for describing finite-state automata sets using Post’s formal calculus. A.A. Tal’ and S.A. Yuditskii developed methods for the structural description of Petri nets. In the 1980s, with the arrival of O.P. Kuznetsov, A.K. Grigoryan, A.V. Markovskii, and L.B. Shipilina from Laboratory No. 3, the development of logical control languages was intensified. YARUS-2, a language developed by the research group, was used in the software of CNC machines serially produced in the 1980s.

In the recent decade, the main line of Laboratory’s research has been the development of intellectualization theory and methods for discrete systems and control processes. At different times, studies have been carried out in the following fields: 1) network representations of knowledge, 2) network representations of objects and processes, 3) artificial intelligence and cognitive sciences, 4) group behavior of robots, 5) modeling of neural networks, and 6) modeling and analysis of social networks.

1. Network representations of knowledge

The most common network representations of knowledge are representations of situations based on linear and fuzzy cognitive maps and representations based on ontologies.

In recent decades, the line of research involving cognitive maps to support decision-making in semi-structured situations, called cognitive situational analysis, has been actively developing. Organizations of the socio-political sphere show great interest in it, which can be explained as follows. In semi-structured situations characteristic of this area, a system of concepts is not formulated; the main parameters are not quantitative but qualitative and are obtained by expertise instead of objective measurements. In such situations, it is not possible to use the approaches of traditional decision theory based on quantitative assessments of clearly formulated alternatives; decision-making is preceded by work on structuring the situation (i.e., creating its model).

Ontological representations of knowledge differ from other semantic networks by a serious foundation, theoretical (descriptive logic) and technological (standards, languages, and software environments). They serve as a formalized description of subject areas and are actively used in modern information systems.

1.1. 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 situational analysis. Models of agents’ interaction were constructed for two cases: (a) the agents’ beliefs about the situation coincide and are given by a single linear cognitive map; b) the agents’ beliefs are inconsistent and are given by different cognitive maps. A method for finding the Nash equilibrium solution in the class of pure strategies was developed for each model. 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.

In 2013, the Nash equilibrium solution of a repetitive game on a cognitive map was constructed in the case when the game duration is common knowledge. The solution was found in the class of pure strategies by considering two maximization problems of two linear functions. (These problems can be solved separately due to the linearity of the goal functions of agents.) The problem was solved using recurrent dynamic programming equations.

1.2. Coalition formation modeling based on fuzzy cognitive maps (A.A. Kulinich)

A coalition is considered stable if any player benefits nothing from leaving it. A coalition is stabilized using an imputation of the total payoff that demotivates the players to leave the coalition. The traditional cooperative game theory approach is based on strong assumptions about the complete awareness, rationality, and intelligence of the players. Hence, this approach becomes inapplicable when forming coalitions under uncertainty. In the Laboratory, a coalition formation model was developed based on a fuzzy cognitive map of the controlled object and fuzzy expert assessments of the goals and strategies of the players involved in the conflict.

Three stability criteria for coalitions were proposed:

• The criterion of the mutual utility of players when sharing their resources to achieve a common goal.
• The criterion of cognitive dissonance, which characterizes the degree of imbalance of mutual utilities.
• The criterion of player’s attractiveness for the coalition.

These criteria were employed to recommend a proper choice of supporters for a decision-maker (DM) when forming a stable coalition. For the DM, the best supporters in the coalition are the players whose possibility and efficiency of achieving the goal are close to the DM’s ones. In this case, all players in the coalition have almost equal mutual utilities and efficiencies of achieving the goal, and, consequently, the minimum values of their cognitive dissonances.

1.3. Ontological approach to knowledge management in scientific organizations (K.V. Kryukov, 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 an ontology with two types of vertices: theme vertices and term vertices. The theme vertices form the mainframe of the tree and are interconnected via the theme-subtheme relation. A term vertex is connected with exactly one theme by the theme-term relation; all lower vertices are assumed to inherit this term. The concept of a profile was defined for two main objects of the problem: 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. Three parameters were considered:

1. the total number of references to the main terms of the theme in the document;
2. part of the document (its volume) in which the main terms of the theme were encountered;
3. the variety of terminology of the theme (the number of different terms) in the document.

The relevance of a group of documents is calculated by analogy. A document profile is a vector of its relevance to all ontology themes. An employee profile is a vector of the relevance of the employee’s papers to all themes of the subject area.

The calculated competencies can be used to select experts for various scientific activities (reviewers, opponents, etc.).

In 2013–2015, an ontology and a dictionary of control sciences were developed. In 2017, the first version of the software system was developed and successfully tested on papers published in Automation and Remote Control. By the beginning of 2019, a system for determining the competencies of the Institute’s employees was developed using the publications database.

2. Network representations of objects and processes

2.1. Theory of resource networks (L.Yu. Zhilyakova and O.P. Kuznetsov)

O.P. Kuznetsov proposed the resource network model in 2009. A resource network is a directed weighted graph containing a homogeneous resource at the vertices of unbounded capacity. The weight of each edge indicates its throughput, i.e., the maximum resource amount that can pass along this edge in one discrete-time step. The vertices distribute the resource to the outgoing edges at each step according to two threshold switching rules. If the resource amount exceeds the total weight of all outgoing edges, an amount equal to the capacity of a corresponding edge is transferred to each adjacent vertex. Otherwise, the vertex completely distributes its resource among all edges proportionally to their capacities. The total resource amount does not change.

O.P. Kuznetsov described a special case (complete homogeneous network) given by a complete graph with loops 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,
• the existence of an integral characteristic (a threshold separating small and large resource values).

L.Yu. Zhilyakova almost completely described the behavior of resource networks. Her results were presented in two monographs and are listed below:

• Resource networks were classified by the graph structure (regular, cyclic, and absorbing networks) and the input-output capacity ratio. The threshold switching mechanism of network operation was investigated, and methods for finding the limiting states and flows in each class of networks were developed.
• The concept of potential attractors was introduced. A potential attractor is a vertex that can attract a significant part of the resource under certain initial states. A vertex attractivity criterion was established.
• Oscillatory processes in cyclic networks with a small resource amount were described. A cyclic network with a large resource amount always has a limiting state and a limiting flow.
• Absorbing resource networks were investigated. There is no resource threshold in such networks; the limiting state linearly depends on the initial state for any total resource amount.
• Direct and inverse control problems were formulated for regular networks with several potential attractors and absorbing networks with several sinks. They were reduced to a quadratic optimization problem with a convex objective function.
• The resource network was used to model the distribution of pollutants in the aqueous medium.
• A modification of the model, a resource network with the limited capacity of attractor vertices, was proposed. When the resource amount reaches a given capacity limit, the attractors are saturated, and the resource surplus is transferred to other vertices (secondary attractors). These vertices are determined by the network topology. The behavior of resource networks with limited-capacity attractors is complex compared to resource networks without them.
• An operation algorithm for a resource network with limited-capacity attractors was described.
• The existence of the second threshold of the total resource amount was proved: upon reaching this threshold, the saturation of the secondary attractors occurs. Four intervals of total resource amounts corresponding to different behavior of the resource network were described.

2.2. Reflective formation methods for wireless network topologies (N.I. Bazenkov)

Wireless ad hoc networks are networks formed by autonomous wireless transmitters without additional infrastructure. Such networks are used in military and rescue operations, data collection at industrial facilities, and environmental monitoring. Their nodes usually operate on autonomous storage batteries; therefore, ensuring energy efficiency is very important. On the one hand, the topology formation problem is assigning an appropriate power to each node to ensure network connectivity; on the other hand, minimizing the total power of all nodes.

Ad hoc networks have no control center. Hence, using centralized algorithms is not possible. It is necessary to consider distributed algorithms when each node seeks to maximize a local objective function. A promising approach to developing such algorithms is the game-theoretic approach: the topology formation problem is stated as a noncooperative game. In this game, the network nodes are agents (players), and their utility functions incorporate two goals: maintaining network connectivity and minimizing power.

The naive best-response algorithm is known in the literature. 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. In the first modification, all nodes use the double best response until they stop changing their powers. After stopping, the resulting network is not always connected, so the nodes switch to the standard best response and complete network formation. In the second modification, a node uses the naive best response to improve its utility. If utility improvement is impossible, the node switches to the double best response. The convergence of both algorithms was proved analytically, and their effectiveness was demonstrated in numerical experiments.

3. Artificial intelligence and cognitive sciences (O.P. Kuznetsov)

In this line of research, the goal is to identify differences in information processing mechanisms adopted by the computer and the brain. This problem is important for cognitive sciences, studying the brain’s work, and artificial intelligence, developing intelligent systems. As is well known, the brain performs many information processing tasks more efficiently than the computer. A shortlist of these tasks includes the following:

• fast image processing: categorization and recognition from different angles based on similarity (not identity);
• gestalt perception, restoration of the whole from its piece, and quick recognition of dissimilarity (“something is wrong”);
• determination of relevance and separation of the essential from the non-essential;
• quick access to the desired content (associative search);
• quick reasoning based on schemas (rather than formal logic).

The speed of computer processes is millions of times higher compared to brain processes. The low efficiency of performing these tasks by the computer suggests that information-processing mechanisms in the brain are fundamentally different. Therefore, it is necessary to develop models close to brain processes that differ from algorithmic symbolic models (the foundation of most known intelligent technologies) and modern neural network models (a simple architecture having little in common with the brain’s complex structure).

In the early 2000s, Laboratory No. 11 developed two models to process and store image information. These models are based on the holographic approach, comprehended as an informational principle instead of its traditional physical sense. O.P. Kuznetsov proposed original pseudo-optical neural networks (PNNs) with holographic effects. Information is transmitted using analog wave signals, whereas recording and reading (restoration) 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 restoring 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.

In 2012–2015, research was carried out in two branches related to cognitive sciences. The first branch considered cognitive semantics based G. Lakoff’s concept (a draft solution of two problems: categorization and semantics).

The concept rests on the assumption that person’s cognitive structures and mechanisms significantly depend on his (her) sensory mechanisms and physical and social experience. Gestalt and image schema structures play an important role in this concept, explaining understanding and quick reasoning mechanisms. Note that PNNs may become a promising approach to gestalt modeling.

The second research branch is examining and developing dynamic networks related to activity spread. These studies can be very useful for developing the connectome, a well-known concept in neurobiology focused on structuring and formalizing the vast arrays of experimental data accumulated by neurophysiologists over the recent decades.

Revealing the fundamental principles of information processes in the brain will lead to a breakthrough in intelligent technologies.

4. Collective behavior of robots (A.A. Kulinich)

4.1. Social models of the formation and operation of robot teams with the reactive architecture

In 2016–2018, the collective behavior of robots was investigated based on the criteria formulated in social theories of human behavior in small social groups. These are G. Homans’ theory of mutual utility, which models motivations for forming teams, and L. Festinger’s theory of cognitive dissonance, which models a stable team through the motivation of robots to leave it. The following criteria for the collective behavior of robots were proposed: the ability to achieve the goal independently, mutual utility, and mutual cognitive dissonance. Based on these criteria, mathematical models of the collective behavior of robots with a reactive architecture were constructed; algorithms for the flocking behavior of robots and algorithms for the behavior of lazy and selfish robots were developed.

4.2. Models of the formation and operation of intelligent robot teams with the BDI architecture

The main feature of these models is representing the operational environment of robots as nested subspaces of the “Robot group–Environment” system. The subspaces form a lattice of environment’s state classes, and each class is assigned a symbol (name). A structured symbolic representation of the state space formally determines a qualitative ontology of the subject area (the environment’s conceptual framework). The mathematical model of an intelligent robot with the Belief–Desire–Intention (BDI) architecture was developed; all architecture elements were described by the state classes’ names in the conceptual framework. This model was employed to propose an algorithm for constructing a conceptual framework by a set of robots exchanging information about their resources. The algorithm represents robot’s beliefs (knowledge) and desires (goals) in terms of state classes’ names agreed upon by all robots. Collective behavior conditions for robot teams were formulated and implemented: protocols for exchanging information about the robots’ beliefs, goals, and conditions of collaboration and coordinating their actions were developed. The proposed models, algorithms, and architectures were tested on simulation models and showed their correctness.

5. Neural network models

5.1. Biological neural networks (O.P Kuznetsov, N.I. Bazenkov, B.B. Boldyshev, L.Yu. Zhilyakova, and S.G. Kulivets)

In 2015, together with neurobiologists from Koltsov Institute of Developmental Biology (Russian Academy of Sciences), research into discrete models of chemical (transmitter) interactions between neurons in biological nervous systems was started. In 2016–2017, the first discrete model of chemical interactions was proposed. The neurons in this model are located in a single extracellular space (ECS). When a neuron is active, it releases a specific transmitter substance in the ECS. Neurons are heterogeneous in two aspects:

1. Each neuron releases a certain type of transmitters and has receptors sensitive to a certain type of transmitters.
2. There are three types of neurons by electrical activity: an oscillator (a neuron periodically generating bursts of spikes), a reactive neuron (a McCulloch–Pitts neuron, becoming active as the result of external excitation only), a tonic neuron (a neuron active till its inhibition). Neurons interact through the ECS, and these interactions are not synaptic: a transmitter released by a neuron 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. From a neurobiological point of view, the neurons and the ECS form a neural ensemble, generating rhythmic activity without external impacts. 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.

In 2018, a new asynchronous model was developed, better matching biological reality. It introduces the concept of membrane potential, a function changing its value under the impact of transmitters existing in the ECS. A neuron is active when the membrane potential exceeds a certain value, called the threshold. The vector of neuron activities is called the external state of the neural system. The rate of change in the membrane potential is the sum of two rates: the endogenous rate, which depends on the neuron type, and the exogenous rate, which depends on the concentration of transmitters to which the receptors of a given neuron are sensitive.

Neurons operate in continuous time. Different events may occur:

• a change in the state of any neuron,
• the emergence of a new transmitter in the ECS,
• a discrete change in the concentration of an existing transmitter.

The events are points dividing the continuous-time scale into discrete time steps. No events occur within a step. The difference in the endogenous rates of neurons leads to asynchronous neural interactions and significant variability in the steps of the discrete sequence. An algorithm for calculating the behavior of this model was proposed and implemented in software.

5.2. The theory of stationary ensembles (O.P Kuznetsov and S.G. Kulivets)

In 2015–2016, a stationary neural ensemble model was proposed and investigated. This model is based on a known threshold network of ordinary McCulloch–Pitts neurons. Such a network is called a stationary ensemble if it maintains the unit state (all neurons are active) without external impacts. The main result was establishing necessary and sufficient conditions under which a neural network is a stationary ensemble. In 2017–2018, a software environment was developed for constructing models of formal neuron networks, calculating their behavior, identifying ensembles and networks of ensembles, and viewing the state graph of each ensemble as an automaton state graph.

The software environment includes the following functions:

• viewing the graph of a formal neuron network given by the adjacency matrix,
• calculating the sequence of network states under a given initial state and finding ensembles in the network,
• analyzing the influence of the ensemble’s inputs on the ensemble’s state.

6. Research of processes in social networks (D.A. Gubanov, L.Yu. Zhilyakova, and N.I. Bazenkov)

Oleg I. Aven

Leonid I. Mikulich

In 2018, Laboratory No. 32 (intelligent information technology for control systems) was affiliated to Laboratory No. 11. The former laboratory was founded in 1968 by Dr. Sci. (Eng.), Prof. (later, Correspondence Member of the USSR Academy of Sciences) O.I. Aven. At those times, Laboratory No. 32 focused on developing scientific foundations and methods to design computer-aided control systems for organizational complexes. In 1992, Laboratory No. 32 was renamed, and Cand. Sci. (Eng.) L.I. Mikulich became its Head.

From 1968 to 1992, under the supervision of O.I. Aven, Laboratory No. 32 participated in large-scale all-Union projects to design three automated control systems, Metal, Inturist, and Morflot.

In recent years, Laboratory No. 32 initiated and actively conducted research on intelligent analysis of information processes in network and multi-agent structures.

More than ten years ago, D.A. Gubanov, an employee of the former Laboratory No. 32, was the first at the Institute to start studying social networks.

Over the past five years, the following results were obtained:

• Mathematical models and methods for analyzing online social networks were developed, including the actional model of opinion dynamics in online social networks (together with A.G. Chkhartishvili) and corresponding methods for calculating the influence of users and clustering users of online social networks.
• Methods for identifying communities and influential agents in social networks based on language games were developed (together with L.I. Mikulich and T.S. Naumkina).
• Methods for extracting and analyzing the terminological structures of subject areas were proposed (together with D.A. Novikov).
• Algorithms and programs for analyzing online social networks were developed, including those for identifying active groups and communities, calculating the influence level of users and assessing the vulnerability of users to informational impacts, and identifying discussions initiators in networks.
• Algorithms and programs for extracting and analyzing terminological structures from texts of a given subject area were developed.
• Information processes in real online social networks (Facebook and VKontakte) were studied.
• A model of activity spread in a network with different types of agents and activities was proposed (together with L.Yu. Zhilyakova).

In the last five years, research projects of the Laboratory were supported by five grants of the Russian Foundation for Basic Research and two programs of the Department of Energy, Engineering, Mechanics and Control Processes (Russian Academy of Sciences).