On an Approach to Knowledge Management and the Development of the Knowledge-Вased Multi-Agent System

Abstract

The chapter discusses the architecture of the Knowledge-Вased Multi-Agent System (KBMAS) and describes the software agent models. The purpose and functional organization of the system software agents used for planning and management of computing resources of the KBMAS are considered. An approach to the applied software agent’s development that integrates knowledge-based reasoning mechanisms with neural network models is proposed. The structure of the problem-oriented Multi-Agent Solver, including groups of reactive and cognitive software agents used to solve complex ill-formalized problems, is considered. The interaction diagram of reactive agents and the states and transitions diagram of cognitive agent of the computing node are given. The control scheme is shown that includes methods for determining the availability of microservices used by agents, reliability assurances and coordinated operation of the system’s computing nodes. The method of reinforcement learning, the system of rules (productions), and the queries to the knowledge base are described. Methods of distribution of software agents in the KBMAS computing nodes, as well as construction of an optimal logical structure of the Distributed Knowledge Base, which has minimal information connectivity and ensures effective operation of the system on multicomputers, are proposed.

1. Introduction

The Knowledge-Вased Multi-Agent System is a Distributed Artificial Intelligence System that uses intelligent applied and system software agents. Knowledge-based reasoning mechanisms and artificial neural networks are integrated into the model of applied software agents, which are designed to solve complex, ill-formalizable problems [1, 2, 3, 4].

System software agents are used to effectively manage computational processes and provide application software agents with access to information-computing resources of the multicomputer.

Applied software agents function using Event-Driven Microservices (EDM) — independent, autonomous resources designed as separate interacting processes with lightweight interprocess communications. Microservices can be implemented as autonomous processes or as functions, they may or may not store state.

A feature of the microservice architecture is that microservices are loosely coupled. EDM communicates not through request-response API (Application Programming Interface), but through events defined in event streams, which are neutral with respect to one technology or another. This allows you to choose the most appropriate tooling to implement each job, allowing you to achieve the required level of performance.

In today’s EDM architecture, information is exchanged by issuing and consuming events, which may be transferred through simple notifications as well as complex structures with state support. The events are not destroyed when consumed, as in conventional messaging systems, but remain available to other consumers, who can read them as needed.

Microservices consume events from input event streams, process information, generate their own outgoing events, provide data for to implement a request-response access scheme, exchange information with third-party APIs, or perform other necessary actions.

Unlike Service-Oriented Architecture (SOA), which typically uses web service standards like SOAP (Simple Object Access Protocol), microservice architecture uses simpler protocols. A microservice can be designed as a stand-alone service on a PAAS (Platform As A Service), or it can be a process of its own Operating System.

In traditional Operating System architectures, information-computing resources are hidden behind universal APIs that do not allow the KBMAS developer to implement problem-dependent optimization. Effective implementation of KBMAS is possible on the basis of an exokernel OS and event-driven intelligent system software modules.

High performance is achieved through the implementation of special mechanisms for managing information and computing resources, as well as the possibility of direct access to hardware [5, 6].

Using the services of an exokernel OS, the KBMAS designer is able to choose or implement his own System Libraries (LibOS). For example, specialized VMM (Virtual Memory Management) or IPC (InterProcess Communication) modules defined in LibOS can work much faster than general-purpose software modules doing a similar job in a monolithic or microkernel Operating System. System software agents can effectively manage information-computing resources using exokernel OS services, which is the basis for creating high-performance knowledge processing systems.

Currently, in distributed systems, hypervisors are usually used instead of exokernel architecture. Hypervisors of the first type do not use OS services, they directly control the hardware. In hypervisors of the second type, instead of an exokernel that provides untrusted servers with a low-level interface to access computing resources, the host OS runs. Guest OSs are used instead of user (unprivileged) mode servers. The advantage of building an exokernel virtualization system instead of using hypervisors is that, in this case, an extra layer of mapping is eliminated.

Unlike a hypervisor, which must support disk address translation tables (and other tables to convert virtual resources to physical resources), there is no need for such reassignment when using an exokernel OS. The exokernel only needs to keep track of which Virtual Machine (VM) has been given certain hardware resources. The exokernel architecture does not require creating a copy of a real computer and isolating virtual machines from physical resources. In this case, each VM is provided with a subset of the real computer resources. The exokernel OS operates in privileged mode, distributing computing resources between VMs and controlling them so that none of the machines tries to use not intended for this VM computing resources.

Virtual machines can serve as containers that contain software agents (processes and threads) and their surroundings. It is easier to provide mobility of software agents together with their VM than to move individual agents around. When using a virtual machine, the local group of software agents is moved together with the necessary environment for it (configuration files, system tables, etc.).

Development of KBMAS on the basis of exokernel OS includes creation of system and applied software agents, definition of their states and actions, as well as events (messages), delivery environment properties, and other characteristics describing the agents and their interaction. Development of a problem-oriented KBMAS can be performed using a special Multi-Agent-KB5 software toolkit [4], which allows knowledge engineers to design a distributed intelligent system based on high-level abstractions implemented by high-performance specialized system software modules. Using the Multi-Agent-KB5 toolkit, a knowledge engineer can create groups of applied software agents that act rationally, are able to respond in a timely manner to environmental events and learn in this environment.

In a broad sense, rationality is the ability to do the right thing. Ideal rationality, that is, choosing the optimal (best) action in a given situation, is not always achievable and may require large computational resources. The concept of rationality in the KBMAS uses to both applied and system software agents.

In logic programming paradigm, the rational behavior of an applied software agent is realized by means of logical inference methods (resolutions and unifications). A software agent can act rationally without using logical inference. In some situations, a reflex action may be more successful than a slower action taken after logical inference.

Problem-solving in the KBMAS is done by decomposing a complex problem into subtasks, which are jointly solved by rational applied software agents. Horizontal and vertical decomposition is used. Horizontal decomposition results in a multi-connected system with a flat structure. Vertical decomposition results in a hierarchical system with multiple levels. The levels are vertically subordinate to each other and have their own goals and functions, the implementation of which is aimed at achieving the global goal of the intelligent system.

Two types of applied software agents are used in the KBMAS to solve applied problems: cognitive and reactive. Mathematical models of these types of agents are described in [4].

KBMAS is an emergent system that implements the principle of self-organization. In the self-organizing KBMAS software agents are capable of making decisions under conditions of incompleteness, vagueness, and fuzziness of knowledge.

2. Structural and functional organization of the KBMAS

In traditional Knowledge-Based Systems, problems are solved by a single intelligent solver. This intelligent solver is designed as a monolithic application. It is assumed to use a complete and consistent Knowledge Base and has a global view of the problem. This model uses monotone logic (closed-world), the intelligent solver search by AND/OR-connection (reduction) graph (Figure 1).

Figure 1.

AND/OR-connection graph.

The reduction graph shown in Figure 1 corresponds to the following fragment of the formalized description of the problem domain (in the language of logical programming):

RCSF(A,B,C,...,G,F) :- RCSF(A,B,C,...,G, f1); ... ; RCSF(A,B,C,...,G, fn).

RCSF(A,B,C,...,G,f1) :- RCS(A,B,C,f1), VS(G,A,B,C,f1).

RCS(A,B,C,F) :- SOVA(A,B,F), SOVB(B,C,F), SС(C,A).

SOVA(X,Y,F) :- SA(X,Y), FR1(X,Y,F).

SOVB(K,L,F) :- SB(K,L), FС(L,F).

FR1(G,M,R) :- FA(G,R), FB(M,R).

There are effective parallel algorithms for reduction graph processing. However, these algorithms can be used only in Shared Memory Processors systems (SMP). These algorithms are not suitable for multicomputers, which use a completely different model of concurrency — message-based distributed computing.

To implement parallel search algorithms on the reduction graph in multicomputer (cluster) systems, as an option, it would be possible to organize a single virtual address space (Distributed Shared Memory, DSM) using page swap. However, in the case of the DSM mechanism, which is implemented by the Operating System or middleware, system performance is low. A more complex but predictable message-based model is preferable.

The Knowledge-Вased Multi-Agent System uses a network of cooperating software agents instead of a single intelligent solver performing a parallel search on the reduction graph. Each individual software agent has only partial knowledge of the problem and can solve only some subtask.

The KВMAS integrates models, methods, and tools of Distributed Artificial Intelligence, parallel computing, and Event-Driven Microservices technology. The software agents of the KВMAS are loosely coupled intelligent software modules that can be distributed, often on a large scale (Figure 2).

Figure 2.

Structure of the KВMAS.

The use of decoupled components is a basic requirement for successful scaling. The opportunity to realize decoupled software modules is provided by the methodology of Object-Oriented Analysis and Design. The idea of decoupling underlies most of the of Object-Oriented patterns, which can be successfully used to create a Knowledge-Вased Multi-Agent System.

Computing nodes of the KBMAS are multiprocessors with shared memory. Software agents of the same node communicate with each other using a Local InterProcess Communication (LIPC). To improve performance the LIPC is implemented using specialized system libraries (LibOS). Software agents of the different nodes communicate through message exchange implemented using standard libraries and middleware.

Figure 3 shows the structure of a Multi-Agent Solver for one of the KВMAS nodes. Two types of applied software agents are used in the Multi-Agent Solver: cognitive and reactive. Applied software agents processing the domain knowledge use special Cognitive Data Structures (CDS). Four types of methods are implemented for work of applied software agents with the knowledge base: comparison (CMP), association (ASS), analysis (ANS), and specification (VAL). CMP method is called when comparing events or objects; ASS method is used to get answers to queries about relations between objects and events; ANS method implements logical analysis of events. For object specification (VAL-method) can be used both clear queries to the knowledge base and fuzzy queries [7].

Figure 3.

Multi-Agent Solver of the KВMAS node.

Different types of membership functions can be used to implement fuzzy queries. Figure 4 shows the examples of membership functions (μ_s) for two linguistic variables: Correctness and Completeness.

Figure 4.

Examples of the membership functions.

Figure 5 shows the result of a fuzzy query that uses these membership functions.

Figure 5.

Example of the result of a fuzzy query.

In the problem-oriented Multi-Agent Solver presented in Figure 4, the priorities of the applied software agents are set according to the sequence number of the software agent. In this case, the first software agent uses the tables TableU_1 and TableSovU_1. The software agent with number N has the lowest priority and is associated with table TableU_N.

Cognitive applied software agent coordinates the work of a group of reactive software agents. As an example, Figure 6 shows the diagram of the states and transitions of one of the cognitive applied software agents.

Figure 6.

State and Transition Diagram.

After initialization, the transition to the “Selection” state occurs, in which the cognitive software agent selects the necessary knowledge source, taking into account the informative signals from the reactive agents. The cognitive agent then goes into a “Coordination” state in which it coordinates the actions of the reactive software agents. If at the next step, the reactive agents do not find a coordinated solution, cognitive agent backtracking to the previous state of partial solution to the problem.

The diagram of one possible option of interaction between the reactive agents of a node, each of which is connected to only one neighbor, is shown in Figure 7.

Figure 7.

Interaction scheme of the reactive software agents.

The organization of the Multi-Agent Solver is described in more detail in the paper [4].

Computing node of the KBMAS can use the concurrency model in which several computing threads are in the execution state, and only one of the threads is actually executing on the processor at any given time. This concurrency model uses shared memory to exchange information. Competitive threads are described by the consistency model, which defines the order in which operations performed by local agents in a node should be executed, and the order in which the results of these operations should be transmitted to the group members.

In addition to competitive concurrency computations, simultaneous concurrency computations can be implemented in the KBMAS nodes. To implement parallel computing, Uniform Memory Access (UMA) multiprocessors are usually used. In this case, the whole set of software agents is divided into subsets (groups). Agents that belong to different groups can act simultaneously.

The execution of computing processes (threads) associated with groups of applied software agents is coordinated by system software agents, which provide access to information-computing resources of the multicomputer.

The agents are dynamically divided into groups using the compatibility matrix S and the inclusion matrix R. The compatibility matrix S has the following form (1):

$$S=\left[\begin{array}{ccccc}0& s_{12}& s_{13}& \cdots & s_{1M}\\ s_{21}& 0& s_{23}& \cdots & s_{2M}\\ s_{31}& s_{32}& 0& \cdots & s_{3M}\\ \cdots & \cdots & \cdots & \cdots & \cdots \\ s_{M1}& s_{M2}& s_{M3}& \cdots & 0\end{array}\right]\begin{array}{c}{S}_1\\ S_2\\ \begin{array}{c}{S}_3\\ \\ S_M\end{array}\end{array}$$E1

where s_ij=1, if the agents A_i and A_j use different computing resources and work in parallel, otherwise s_ij=0.

The distribution of agents into groups is based on the inclusion matrix R (2):

$$R=\left[\begin{array}{ccc}{r}_{11}& r_{12}& \begin{array}{cc}\cdots & r_{1M}\end{array}\\ r_{21}& r_{22}& \begin{array}{cc}\cdots & r_{2M}\end{array}\\ \begin{array}{c}\cdots \\ r_{H1}\end{array}& \begin{array}{c}\cdots \\ r_{H2}\end{array}& \begin{array}{c}\begin{array}{cc}\cdots & \cdots \end{array}\\ \begin{array}{cc}\cdots & r_{\mathit{HM}}\end{array}\end{array}\end{array}\right]\begin{array}{c}{R}_1\\ R_2\\ \begin{array}{c}\\ R_H\end{array}\end{array}$$E2

where M is the number of agents, H is the number of groups. r_ij = 1 if the agent A_i is included in the group Y_j. The agent A_i is included in the group Y_j if S_i ∩ R_j = ∅, that is the matrix rows do not intersect. For optimal partitioning into subsets, it is necessary to consider the functional features of the software agents, their requirements for computing resources, as well as know the structural organization of the KBMAS node used to implement parallel computations.

In the process of solving subtasks, software agents use microservices, which can be duplicated on different nodes of the computing system. The system software agents distribute the computational load and control the microservers based on the data provided by the agents-monitors.

The behavior of applied software agents becomes more rational by repeatedly solving the same problem. The applied software agent learns through a series of rewards and punishments. The agent’s actions change the environment to a new state. The environment returns the next state and reward to the agent. The cycle “state → action → reward” repeats until the problem is solved (Figure 8).

Figure 8.

The reinforcement learning control loop.

Signals s_t correspond to a state, a_t to an action, r_t to a reward at time t. The strategy according to which the agent chooses actions is a function that maps a set of states into a set of actions. The agent’s task is to choose (by trial and error) the best action that maximizes the target function, which is the sum of the rewards received by the software agent.

Various reinforcement learning algorithms can be used. The most effective is the Actor-Critic algorithm [8, 9, 10] in which the strategy generates action, and the value function critiques the actions.

The basis of reinforcement learning is function approximation. As a method of function approximation, KВMAS uses a multilayer neural network that models both policy functions and value functions.

The advantage function A=Q(s,a)-V(s) is used to generate reinforcing signals. Benefit V(s) which can be obtained by achieving a particular state (s) is evaluated by the agent before the action, and the value function of the action Q(s,a) — after the action has been taken.

3. Aggregation of distributive information structure

Created information data structures can have a large volume and dimension, so their loading and implementation is carried out in fragments. Logically interrelated data should be divided into a number of clusters that have the smallest interconnection under constraints on the dimensionality of clusters, as well as on the degree of semantic proximity of logical records included in the clusters. No less important is the question of choosing the type of data storage systems used [11, 12].

Let us introduce the variable Bⁱ_kj, which characterizes the handling by the k-th query of the i-th information element, which is in the j-th logical record. Variable X_ij = 1 if the i-th data partition is selected in the j-th logical record; X_ij = 0 otherwise. Variable a_ik = 1 if the i-th data partition is included in the k-th query; otherwise a_ik = 0.

Variable Bⁱ_kj characterizes the use of the j-th logical record by the k-th query (3):

$$B_{\mathit{kj}}^i=\left\{\begin{array}{c}1,\mathit{\text{when}}\sum _{i=1}^I{a}_{\mathit{ik}}{x}_{\mathit{ij}}\ge 1;\\ 0,\mathit{\text{when}}\sum _{i=1}^I{a}_{\mathit{ik}}{x}_{\mathit{ij}}=0;\end{array}\right.$$E3

Note that the results obtained in solving such a problem are important from a practical point of view, given the constraints for designing an acceptable data structure and the ability to generate fast queries for sampling and editing distributional structures.

Let’s analyze this algorithm step by step.

4. Approximate algorithm for distributing data clusters between the server and local network clients

At this stage, the distribution of data batches for storage and processing is determined by the criterion of minimum total traffic.

We reduce the canonical graph of the data structure to an uncoupled graph and calculate the weight of each data batch, summarily consisting of the weight of the batch itself and the weight of arcs (links), taking into account the requirements of the network clients (4):

$$W_i=W_i^{\mathit{\text{part}}}+W_{\mathit{iq}}^{\mathit{\text{link}}}$$E4

where, $W_i^{\mathit{\text{part}}}$ — total weight of data partitions (5); $W_{\mathit{iq}}^{\mathit{\text{link}}}$— the weight of the arcs of the canonical data structure graph (6).

$$W_i^{\mathit{\text{part}}}=\sum _{k=1}^{k_0}\sum _{p=1}^{p_0}{\gamma }_{\mathit{kp}}^Q{\delta }_{\mathit{kp}}^Q{\vartheta }_{\mathit{pi}}$$E5

$$W_{\mathit{iq}}^{\mathit{\text{link}}}=\sum _{k=1}^{k_0}\sum _{p=1}^{p_0}{\gamma }_{\mathit{kp}}^Q{\delta }_{\mathit{kp}}^Q{\vartheta }_{\mathit{pi}}\sum _{q\ne i}^I{\vartheta }_{\mathit{pq}}{a}_{\mathit{iq}}^G$$E6

The weight of the i-th data batch is calculated by the formula (7):

$$W_i=\sum _{k=1}^{k_0}\sum _{p=1}^{p_0}{\gamma }_{\mathit{kp}}^Q{\delta }_{\mathit{kp}}^Q{\vartheta }_{\mathit{pi}}\left(1+\sum _{q\ne i}^I{\vartheta }_{\mathit{pq}}{a}_{\mathit{iq}}^G\right)$$E7

where, ${\mathrm{\gamma }}_{\mathit{kp}}^{\mathrm{Q}}$—the frequency of generation of user requests; ${\mathrm{\delta }}_{\mathit{kp}}^{\mathrm{Q}}$— elements of the matrix for generating user queries; ${\mathrm{\vartheta }}_{\mathit{pi}}$— the matrix for using data partitions when executing queries; $a_{\mathit{iq}}^G$— the semantic contiguity matrix of data partitions.

In the next step, the local network graph is converted into an unconnected graph with the calculation of the weight of each node (8):

$$W_r=t_r+\sum _{m^{\ne }r}^{R_0}{t}_{\mathit{rm}}$$E8

where $t_r$ — the total average duration of data processing in the r-th node, consisting of the time of decomposition of the query into subqueries, route selection and connection establishment, etc.;

$t_{\mathit{rm}}$ — the average duration of data transmission between nodes, determined based on the matrix of logical distances between the servers of the nodes of the local network.

Next, the matrix $V=‖{\omega }_{\mathit{ir}}‖$ is formed, the elements of which are the Cartesian product of the weights of each node by the weights of each data partition (9):

$${\omega }_{\mathit{ir}}=W_i\times W_r\text{for}i=\overline{1,I};r=\overline{1,R_0}.$$E9

In the final step of the first stage, the problem (10)

$$\underset{\left\{x_{\mathit{ir}}\right\}}{min}\sum _{i=1}^I\sum _{r=1}^{R_0}{\omega }_{\mathit{ir}}{x}_{\mathit{ir}}$$E10

is solved under the constraints:

• by the number of data partitions, the localization of which is possible on one node (11)

  $$\sum _{i=1}^I{x}_{\mathit{ir}}\le N_r,r=\overline{1,r_0}$$E11

• on the permissible redundancy of groups by network nodes (12)

  $$\sum _{r=1}^{r_0}{x}_{\mathit{ir}}\le M_i,i=\overline{1,I}$$E12

• on the amount of available external memory of the data storage system (13)

  $$\sum _{i=1}^I{x}_{\mathit{ir}}{\mathrm{\rho }}_i{\mathrm{\pi }}_i\le {\mathrm{\eta }}_r^{\mathit{ROM}}$$E13

where, ${\mathrm{\rho }}_i$ — the vector of group lengths in bytes; ${\mathrm{\pi }}_i$ — the vector of number of instances in groups; ${\mathrm{\eta }}_r^{\mathit{ROM}}$ — the amount of available memory on the server of the r-th host; $x_{\mathit{ir}}=1$, if the i-th data partition is included in the r-th network node; $x_{\mathit{ir}}=0$ – otherwise.

5. Problem of distributing data parties of each agent to the types of logical records

The problem posed at this stage is solved taking into account the criterion of the least total time of local data processing in each network node by agents. The number of aggregation tasks for this stage is determined by the number of local network nodes.

The initial data are the subgraphs of the graph of the canonical data structure, as well as the temporal and volumetric characteristics of the subgraphs of their canonical structure, a set of requests from users and network nodes.

The aggregation problem is solved here using approximate algorithms with restrictions:

• on the number of groups (14):

  $$\sum _{i=1}^I{x}_{\mathit{it}}\le F_t,\forall t=\overline{1,t_0},\mathit{\text{where}},F_t-\mathit{\text{number of groups in}}t-\mathit{\text{record}},$$E14

• on the non-repeatability of including groups in a record (15):

  $$\sum _{t=1}^{t_0}{x}_{\mathit{it}}=1,\forall i=\overline{1,I}$$E15

• on the cost of information storage.

The main cost characteristics of the distributive data structure are the cost of storing $E_{\mathit{ds}}$ information; the cost of executing $E_{\mathit{run}}^Q$ requests and transactions at a given time interval; the cost of transmitting information via $E_{\mathit{run}}^C$ communication channels.

The sum of these components determines the total cost (16):

$$E=E_{\mathit{ds}}+E_{\mathit{run}}^Q+E_{\mathit{run}}^C$$E16

The cost of storing distributed information is determined by the physical volume of information Vcr and the cost of storing a unit of information volume (one logical record) on the server. If we assume that the cost of storage in all nodes of the local network is a constant value, then $E_{\mathit{ds}}=V_L\bullet k_{\mathit{ds}}$.

That is, the product of the logical volume of stored information ($V_L)$ and the coefficient that takes into account the storage capacity on the media when organizing the database ($k_{\mathit{ds}}$; in practice, it is approximately equal to 1.2–1.5).

The cost of executing multiple user requests at a given time interval is the sum of the cost of servicing multiple user requests on servers and the cost of transmitting information through communication channels during the execution of user requests. The cost of performing transactions at a given time interval is also determined by the sum of the cost of performing steps (tasks) of transactions on server nodes and the cost of transferring transaction requirements to server nodes, fixing transactions and removing locks.

• from the total time of servicing operational requests on servers (17):

  $$\sum _{\mathit{rc}=1}^{r_0}\sum _{t=1}^{t_0}{B}_{\mathit{pr}}^t\bullet \left(t_q+t_l\right)<T_p$$E17

where ${\mathrm{T}}_p$ — additional service time of the p-th operational request; $t_q$ — average duration of generation of one request (or transaction task step); $t_l$— average processing time for one logical record on a local network host/server.

Variables $B_{\mathit{pr}}^t$ determine the types of logical records used by the p-th query in the r-th node of the computing system.

As a result, logical database structures are determined for each network node.

6. Localization of data by network nodes

This step uses the results of the previous steps and the characteristics of the data warehouse.

As a result of the proposed algorithm, localization matrices for a set of batches of data are formed by types of logical records (the result of the first stage), and then groups of records by local network nodes. In this case, the running time of the algorithms is additionally estimated.

7. Conclusion

The chapter examined the structural and functional organization of the Multi-Agent System, which uses intelligent applied and system software agents. To support the process of developing a problem-oriented KBMAS based on the considered agent-based models, the Multi-Agent-KB5 toolkit is used. This toolkit includes interactive wizards and property panels that allow creating groups of applied (reactive and cognitive) software agents. Inclusion of system software agents into KBMAS, which implement algorithms for planning and management of computational resources, taking into account the specifics of the interaction of applied agents, increases the performance of the system. KBMAS performance is also improved by optimizing the logical structures of the distributed knowledge base.