Multi-Agent Implementation of Filtering Multiset Grammars

Abstract

Chapter is dedicated to the application of multi-agent technology to generation of sets of terminal multisets (TMS) defined by filtering multiset grammars (FMG). Proposed approach is based on creation of multi-agent system (MAS), corresponding to specific FMG in such a way, that every rule of FMG is represented by independently acting agent. Such MAS provides high-parallel generation of TMS and may be effectively used in any proper hardware environment. Directions of further development of the proposed approach are discussed.

1. Introduction

Filtering multiset grammars (FMG) were developed as a result of multiset-based deep integration and convergence of classical mathematical programming and modern knowledge engineering for compact, flexible and natural representation of wide spectrum of combinatorial problems and their solution by application of unified algorithmics [1, 2, 3, 4, 5, 6].

One of the advantages of FMG is natural parallelism of generation of multisets (MS) due to the possibility of independent application of rules to the currently available MS. Such feature being supported by appropriate hardware is a very promising background for the effective implementation of FMG and hence effective solution of the aforementioned problems. However, the “brutal force” approach, demanding on the extensive parallelism, is not suitable here because of evident cost restrictions. More attractive looks such techniques which would be based on the “branches and bounds” logics providing cut off sets of multisets (SMS) which provably do not contain terminal multisets (TMS), defined by FMG, without their generation.

To develop such perspective approach we propose to apply multi-agent technology (MAT) [7, 8, 9, 10, 11, 12] as a basis for implementation of the aforementioned techniques. The main idea of the suggested method of TMS generation is representation of the generating engine as a multi-agent system (MAS), which includes:

1. N agents, each corresponding to one rule from FMG scheme;

2. one agent corresponding to FMG filter;

3. one supervising agent, accumulating generated TMS, satisfying filter.

This MAS operates in such a way that every rule is applied (i.e. agent becomes active) as soon as there occurs multiset, matching this rule. By this approach maximally possible degree of parallelism is achieved.

Structure of the chapter is as follows. Section 2 contains main definitions and notions of the multigrammatical framework, necessary for further considerations. Proposed techniques of the multi-agent implementation of multisets generation is introduced in Section 3. Directions of future development of these techniques are discussed in the conclusion.

2. Basic notions and definitions of the multigrammatical framework

Classical theory of sets is based on notion of set as an unordered collection of mutually distinguishable elements. Basic assumption of theory of multisets is that aforementioned collection may contain indistinguishable (identical) elements:

$$v=\left\{\underset{n_1\mathit{\text{times}}}{\underbrace{a_1,\dots ,a_1}},\dots ,\underset{n_i\mathit{\text{times}}}{\underbrace{a_i,\dots ,a_i}},\dots ,\underset{n_m\mathit{\text{times}}}{\underbrace{a_m,\dots ,a_m}}\right\}.$$E1

Record (1) is usually represented as

$$v=\left\{n_1\cdot a_1,\dots ,n_m\cdot a_m\right\},$$E2

where $v$ is called multiset, $n_i\cdot a_i$ – multiobjects (MO), $a_i$ – objects, $n_i$– their multiplicities, for all$i=1,\dots ,m$. According to (2), multiset may be considered as a set of multiobjects, and, in fact, multiset $\left\{1\cdot a_1,\dots ,1\cdot a_m\right\}$ and set $\left\{a_1,\dots ,a_m\right\}$ represent one and the same collection. Set$\left\{a_1,\dots ,a_m\right\}$, denoted as $\beta \left(v\right)$, is called basis of multiset$v$. Both empty multiset and empty set are denoted as $\left\{\mathrm{Ø}\right\}$.

Zero multiplicity of some object is equivalent to the absence of this object in multiset, i.e.

$$\left\{n_1\cdot a_1,\dots ,n_m\cdot a_m,0\cdot a_{m+1}\right\}=\left\{n_1\cdot a_1,\dots ,n_m\cdot a_m\right\}.$$E3

Fact, that object $a$enters MS$v$ (or MS$v$includes object $a$), is denoted as $a\in v$. Symbol “$\in$” is also used to denote, that MO$n\cdot a$ enters MS$v$ (MS$v$ includes MO$n\cdot a$):$n\cdot a\in v$. Structure of the left operand determines what kind of relation is referred in every particular case. Similarly, symbol “$\notin$” is used to denote, that object $a$ (multiobject $n\cdot a$) does not enter multiset $v$. Due to (3),$a\notin v$ and $0\cdot a\in v$ are equivalent.

Number $\left|v\right|=m$ is called dimensionality of MS$v$, and number

$$\left|v\right|=\sum _{i=1}^m{n}_i,$$E4

is called power of MS$v$.

Two basic relations on multisets – inclusion (“$\subseteq$”) and strict inclusion (“$\subset$”) – are defined as follows.

MS$v$ is included to MS$v\text{'}$, if

$$\left(\forall n\cdot a\in v\right)\left(\exists n^{\prime }\cdot a\in v^{\prime }\right)n\le n^{\prime },$$E5

i.e. for every MO$n\cdot a$ entering MS$v$ there exists MO$n^{\prime }\cdot a$, which multiplicity $n^{\prime }$ is not less than $n$. There may be also $n^{\prime }\cdot a^{\prime }\in v^{\prime }$ such that $a^{\prime }\notin v$ (as seen, this does not contradict (5), because$0\cdot a^{\prime }\in v$ and $0<n^{\prime }$).

If $v\subseteq v^{\prime }$ and $v\ne v^{\prime }$, then MS$v$ is strictly included to MS$v^{\prime }$, that is denoted $v\subset v^{\prime }$.

MS$v$, which is included to MS$v^{\prime }$, is called submultiset of MS$v^{\prime }$; MS$v$, which is strictly included to MS$v^{\prime }$, is called strict submultiset of MS$v^{\prime }$.

Let us illustrate introduced notions by the following example, where, as in all other examples, having place in this chapter, objects will be represented by strings in brackets.

Example 1. Let

$$v=\left\{1\cdot \left(\mathit{eur}\right),5\cdot \left(\mathit{usd}\right),12\cdot \left(\mathit{rur}\right)\right\},$$

$$v^{\prime }=\left\{6\cdot \left(\mathit{eur}\right),5\cdot \left(\mathit{usd}\right),12\cdot \left(\mathit{rur}\right)\right\}.$$

As seen, according to (5), $v\subseteq v^{\prime }$ and $v\subset v\text{'}$.∎

Three basic operations on multisets are multiplication by a constant, addition, and subtraction, which are denoted by bold symbols ∗, + and − respectively. Semantics of these operations is defined by use of the well known set-theoretical operations (join and intersection), as well as arithmetic operations on integer numbers:

$$n\ast \left\{n_1\cdot a_1,\dots ,n_m\cdot a_m\right\}=\left\{\left(n\times n_1\right)\cdot a_1,\dots ,\left(n\times n_m\right)\cdot a_m\right\},$$E6

where “×” denotes multiplication of integer numbers;

$$v+v^{\prime }=\bigcup _{\begin{array}{c}a\in \beta \left(v\right)\cup \beta \left(v^{\prime }\right)\\ n\cdot \mathit{aϵv}\\ n^{\prime }\cdot a\in v^{\prime }\end{array}}\left\{\left(n+n^{\prime }\right)\cdot a\right\},$$E7

$$v-v^{\prime }=\bigcup _{\begin{array}{c}a\in \beta \left(v\right)\cup \beta \left(v^{\prime }\right)\\ n\cdot \mathit{aϵv}\\ n^{\prime }\cdot a\in v^{\prime }\\ n>n^{\prime }\end{array}}\left\{\left(n-n^{\prime }\right)\cdot a\right\}.$$E8

Along with these operations, we shall use set-theoretical operations on multisets – join and intersection, – denoted respectively by bold symbols ∪ and ∩, different from ∪ and ∩:

$$v\cup v^{\prime }=\bigcup _{\begin{array}{c}a\in \beta \left(v\right)\cup \beta \left(v^{\prime }\right)\\ n\cdot \mathit{aϵv}\\ n^{\prime }\cdot a\in v^{\prime }\end{array}}\left\{max\left\{n,n^{\prime }\right\}\cdot a\right\},$$E9

$$v\cap v^{\prime }=\underset{\begin{array}{c}a\in \beta \left(v\right)\cup \beta \left(v^{\prime }\right)\\ n\cdot \mathit{aϵv}\\ n^{\prime }\cdot a\in v^{\prime }\end{array}}{\cup }\left\{min\left\{n,n^{\prime }\right\}\cdot a\right\},$$E10

We have used equivalence between $a\notin v$ and $0\cdot a\in v$ in (9).

Example 2. Let$v$ and $v^{\prime }$ be as in Example 1. Then

$$3\ast v=\left\{3\cdot \left(\mathit{eur}\right),15\cdot \left(\mathit{usd}\right),36\cdot \left(\mathit{eur}\right)\right\},$$

$$v+v^{\prime }=\left\{7\cdot \left(\mathit{eur}\right),10\cdot \left(\mathit{usd}\right),24\cdot \left(\mathit{rur}\right)\right\},$$

$$v-v^{\prime }=\left\{\mathrm{Ø}\right\},$$

$$v^{\prime }-v=\left\{5\cdot \left(\mathit{eur}\right)\right\},$$

$$v\cup v^{\prime }=\left\{6\cdot \left(\mathit{eur}\right),5\cdot \left(\mathit{usd}\right),12\cdot \left(\mathit{rur}\right)\right\},$$

$$v\cap v^{\prime }=\left\{1\cdot \left(\mathit{eur}\right),5\cdot \left(\mathit{usd}\right),12\cdot \left(\mathit{rur}\right)\right\}.∎$$

Common feature of all described operations, which are known from theory of multisets [13, 14], is that their operands are multisets and integer numbers. Unlike them, following operation called “filtration” applies set of multisets (SMS) as the first operand and so called “filter”, being set of conditions, as the second operand. Filtration is denoted as $V\downarrow F$, where $V$ is filtrated SMS, F is filter, and “$\downarrow$” – symbol of operation.

Conditions entering filter F may be boundary and optimizing.

Boundary conditions (BC) are recorded as $\mathit{a\theta n}$, where $\theta \in \left\{>,<,\ge ,\le ,=\right\}$. Multiset $v$ satisfies BC$\mathit{a\theta n}$, if $m\cdot a\in v$ and $\mathit{m\theta n}$ is true (as everywhere, $a\notin v$ is equivalent to $0\cdot a\in v$).

Let $F_{\le }=\left\{{\mathit{bc}}_1,\dots ,{\mathit{bc}}_k\right\}$ be a filter, containing only boundary conditions.

Then

$$V\downarrow F_{\le }=\bigcap _{i=1}^k\left(V\downarrow \left\{{\mathit{bc}}_i\right\}\right).$$E11

Example 3. Let $V=\left\{v_1,v_2,v_3\right\}$, where

$$v_1=\left\{4\cdot \left(\mathit{eur}\right),3\cdot \left(\mathit{rur}\right)\right\},$$

$$v_2=\left\{8\cdot \left(\mathit{usd}\right),10\cdot \left(\mathit{rur}\right)\right\},$$

$$v_3=\left\{3\cdot \left(\mathit{eur}\right),19\cdot \left(\mathit{usd}\right),17\cdot \left(\mathit{rur}\right)\right\},$$

and $F_{\le }=\left\{\left(\mathit{usd}\right)>3,\left(\mathit{rur}\right)\le 12\right\}$. Then

$$\begin{array}{ll}V\downarrow F_{\le }& =\left(V\downarrow \left\{\left(\mathit{usd}\right)>3\right\}\right)\cap \left(V\downarrow \left\{\left(\mathit{rur}\right)\le 12\right\}\right)=\\ & =\left\{v_2,v_3\right\}\cap \left\{v_1,v_2\right\}=\left\{v_2\right\}.\end{array}∎$$

Optimizing conditions (OC) are recorded as$a=\mathit{opt},$ where $\mathit{opt}\in \left\{\mathit{max},\mathit{min}\right\}$. Multiset $v\in V$ satisfies OC$a=\mathit{max}$, if $n\cdot a\in v$ and all multisets $v^{\prime }\in V-\left\{v\right\}$ satisfy boundary condition $a\le n$. Similarly, multiset $v\in V$ satisfies OC$a=\mathit{min}$, if $n\cdot a\in v$ and all multisets $v^{\prime }\in V-\left\{v\right\}$ satisfy boundary condition $a\ge n$.

Let $F_{\mathit{opt}}=\left\{{\mathit{oc}}_1,\dots ,{\mathit{oc}}_l\right\}$ be filter, containing only optimizing conditions. Then, similarly to (6),

$$V\downarrow F_{\mathit{opt}}=\bigcap _{i=1}^l\left(V\downarrow \left\{{\mathit{oc}}_i\right\}\right).$$E12

Example 4. Let $V$ be the same as in Example 3, and

$F_{\mathit{opt}}=\left\{\left(\mathit{usd}\right)=\mathit{max},\left(\mathit{rur}\right)=\mathit{min}\right\}$. Then

$$V\downarrow F_{\mathit{opt}}=\left(v\downarrow \{\left(\mathit{usd}\right)=\mathit{max}\right)\left\}\right)\cap \left(v\downarrow \left\{\left(\mathit{rur}\right)=\mathit{min}\right\}\right)=\left\{v_3\right\}\cap \left\{v_1\right\}=\left\{\mathrm{Ø}\right\}.∎$$

If filter $F$ contains both boundary and optimizing conditions, i.e.

$$F=F_{\le }\cup F_{\mathit{opt}},$$E13

then

$$V\downarrow F=\left(V\downarrow F_{\le }\right)\downarrow F_{\mathit{opt}},$$E14

i.e. result of filtering set of multisets $V$ by filter $F$ is obtained by application of boundary subfilter $F_{\le }$ to$V$, after what resulting SMS is filtered by optimizing subfilter $F_{\mathit{opt}}$.

Application of filters, containing boundary and optimizing conditions, is illustrated by Figure 1.

Figure 1.

Filters application.

Considered operations on multisets and their sets make it possible to define syntax and semantics of family of multiset grammars.

Background of this family is notion of multiset grammar as a couple $S=⟨v_0,R⟩$, where $v_0$ called kernel is multiset, and $R$ called scheme is finite set of so called rules. Set of all objects used in kernel and scheme of MG$S$ is denoted as $A_S$.

Rule$r\in R$ is a construction

$$v\to v^{\prime },$$E15

where multisets v and $v^{\prime }$ are called respectively left part and right part of the rule r, and “$\to$” is divider. The only restriction on left and right parts of the rule is$v\ne \left\{\mathrm{Ø}\right\}$.

If $v\subseteq \mathit{v}$, then result of application of rule r to multiset $\mathit{v}$ is multiset

$$\mathit{v}\text{'}=\mathit{v}-v+v^{\prime }.$$_.E16

Speaking informally, (16) defines, that if left part of the rule, i.e. multiset $v$, is included to MS$\mathit{v},$ then $v$ is replaced by right part of this rule, i.e. multiset $v^{\prime }$. Result of application of rule r to multiset $\mathit{v}$ is denoted as

$$\mathit{v}\stackrel{r}{\Rightarrow }\mathit{v}\text{'},$$E17

and it is said, that MS$\mathit{v}\text{'}$ is generated from MS$\mathit{v}$ by application of rule r. If left part $v$ is not included to MS$\mathit{v}$, result of application r to $\mathit{v}$ is empty MS$\left\{\mathrm{Ø}\right\}$.

Set of multisets, generated by application of multigrammar$S=⟨v_0,R⟩$, or, just the same, defined by this multigrammar, is recursively created as follows:

$$V_{\left(0\right)}=\left\{v_0\right\},$$E18

$$V_{\left(i+1\right)}=V_{\left(i\right)}\bigcup \left(\bigcup _{\mathit{v}\in V_{\left(i\right)}}\bigcup _{r\in R}\left\{\mathit{v}\text{'}\left|\mathit{v}\stackrel{r}{\Rightarrow }\right.\mathit{v}\text{'}\right\}\right),$$E19

$$V_S=V_{\left(\infty \right)}.$$E20

As seen, $V_S$ includes all multisets, which may be generated from MS$v_0$ by sequential application of rules $r\in R$, and $V_S$ is fixed point of the sequence $V_{\left(0\right)},V_{\left(1\right)},\dots ,V_{\left(i\right)},\dots ,$ so

$$V_S=\bigcup _{i=0}^{\infty }{V}_{\left(i\right)}.$$E21

In general case $V_S$ may be infinite.

If MS$\mathit{v}\text{'}$ may be generated from MS$\mathit{v}$ by application of some sequence (chain) of rules entering scheme R, it is denoted as

$$\mathit{v}\stackrel{R}{\Rightarrow }\mathit{v}\text{'},$$E22

and, if so,

$$V_S=\left\{\mathit{v}\left|v_0\stackrel{R}{\Rightarrow }\right.\mathit{v}\right\}.$$E23

Multiset $\mathit{v}\in V_S$ is called terminal multiset (TMS), if

$$\left(\forall r\in R\right)\mathit{v}\stackrel{r}{\Rightarrow }\left\{\mathrm{Ø}\right\},$$E24

i.e. no any rule $r\in R$ may be applied to this multiset. Set of terminal multisets (STMS) defined by multiset grammar S is denoted $\overline{V_S}$. Evidently,

$$\overline{V_S}\subseteq V_S.$$E25

Example 5. Let $S=⟨v_0,R⟩$, where kernel

$$v_0=\left\{3\cdot \left(\mathit{eur}\right),6\cdot \left(\mathit{usd}\right),5\cdot \left(\mathit{rur}\right)\right\},$$

and scheme $R=\left\{r_1,r_2\right\}$, where $r_1$ is

$$\left\{2\cdot \left(\mathit{eur}\right)\right\}\to \left\{4\cdot \left(\mathit{usd}\right)\right\},$$

and $r_2$ is

$$\left\{2\cdot \left(\mathit{usd}\right),3\cdot \left(\mathit{rur}\right)\right\}\to \left\{2\cdot \left(\mathit{eur}\right)\right\}.$$

According to (18)–(19),

$$\begin{array}{l}{V}_{\left(0\right)}=\left\{\left\{3\cdot \left(\mathit{eur}\right),6\cdot \left(\mathit{usd}\right),5\cdot \left(\mathit{rur}\right)\right\}\right\},\\ V_{\left(1\right)}=V_{\left(0\right)}\cdot \cup \left\{\left\{1\cdot \left(\mathit{eur}\right),10\cdot \left(\mathit{usd}\right),5\cdot \left(\mathit{rur}\right)\right\}\right\},\left\{5\cdot \left(\mathit{eur}\right),4\cdot \left(\mathit{usd}\right),2\cdot \left(\mathit{rur}\right)\right\},\\ V_{\left(2\right)}=V_{\left(1\right)}\cup \left\{\left\{3\cdot \left(\mathit{eur}\right),8\cdot \left(\mathit{usd}\right),2\cdot \left(\mathit{rur}\right)\right\}\right\},\\ \cdots \end{array}$$

As seen, this MG provides generation of all possible collections of Euros, US dollars, and Russian rubles, which may be obtained from the initial collection $v_0$ by sequential currency exchanges, which parameters are fixed by rules $r_1$ and $r_2$ (2 Euros may be exchanged to 4 US dollars, 2 US dollars and 3 Russian rubles may be exchanged to 2 Euros).∎

Generalized scheme of application of multiset grammars is presented at Figure 2.

Figure 2.

Application of multiset grammars.

Due to the fact, that multiobjects contain both numerical and symbolic components (multiplicities and object names), generation of multisets provides knowledge-driven numerical computation, that creates a lot of new opportunities for simple formalizing and effective solution of various sophisticated practical problems with hard combinatorial background. To implement such opportunities, so called filtering multiset grammars were proposed in [1, 2]. FMG are such generalization of MG, that integrate two basic concepts—generation of set of multisets and selection from it such MS, that satisfy some logical conditions, joined to filter.

Filtering multiset grammar is a triple $S=⟨v_0,R,F⟩$, where $v_0$ and $R$ are, as above, kernel and scheme, while $F$ is a filter, including boundary and optimizing conditions, defining multisets, which would be selected from the set of TMS, generated by MG$⟨v\_0,R⟩$, i.e.

$$V_s={\overline{V}}_{⟨v_0,R⟩}\downarrow F.$$E26

Verbally, $V_s$ is subset of ${\overline{V}}_{⟨v_0,R⟩}$, which includes only such elements of this set, that satisfy filter $F$. Generalized scheme of application of filtering multiset grammars is presented at Figure 3.

Figure 3.

Application of filtering multiset grammars.

After description of syntax and semantics of filtering multiset grammars we may move to their implementation issues, which background are multi-agent technologies.

3. Basic techniques of the multi-agent implementation of multisets generation

Due to granularity and natural internal parallelism of multigrammatical representation it is perspective to try to use multi-agent paradigm as a background for implementation of the FMG application engine (AE), providing generation of multisets.

We shall use scheme, depicted at Figure 4, as a basis for primary multi-agent implementation of FMG AE. Proposed multi-agent system implementing FMG$S=⟨v_0,R,F⟩$, contains $l=\left|R\right|$ agents $r_1,\dots ,r_l$, each corresponding to one rule from set $R$ (everywhere below we shall denote rules and implementing them agents by the same symbols); one agent $F^{\ast }$, implementing filter $F$; one agent $G^{\ast }$, providing supervision on other agents interaction (in fact, implementing ubiquitous generation by application of rules to multisets, generated at previous steps). Agent $G^{\ast }$ uses storage $V_S$ for accumulation of all generated terminal multisets, satisfying filter $F$. Also $G^{\ast }$ operates storage $V$, containing current set of generated multisets, which are not yet transferred to other agents. Initial state of $V$ is $\left\{v_0\right\}$. Agents communicate via network N.

Figure 4.

Multi-agent system implementing FMG.

Described multi-agent system is operating according to the definition of mathematical semantics of FMG (15)–(26). Set of messages, which are circulating between the agents, is represented in Table 1.

N	Sender	Receiver	Message	Comment
1	$G^{\ast }$	$r_i$	$⟨j,v⟩$	j – number of MS,$v\ne \left\{\mathrm{Ø}\right\}$
2	$r_i$	$G^{\ast }$	$⟨j,v^{\prime }⟩$	$v^{\prime }$ – result of application of rule; $r_i$ to MS$v$
3	$r_i$	$G^{\ast }$	$⟨j,\left\{\mathrm{Ø}\right\}⟩$	Rule $r_i$ is not applicable to $v$
4	$G^{\ast }$	$⟨j,v⟩$,	$⟨j,v⟩$	As 1
5	$F^{\ast }$	$G^{\ast }$	$⟨j,1⟩$	jth MS satisfies filter F
6	$F^{\ast }$	$G^{\ast }$	$⟨j,0⟩$	jth MS does not satisfy filter F

Table 1.

Set of MAS messages.

All messages are couples, the first components of which are numbers of multisets, processed by the agents, and every MS has its unique number. Assigning numbers to multisets is performed by agent $G^{\ast }$. Current maximal number is denoted $J$. Also agent $G^{\ast }$ uses variable Z, which value is set of couples $⟨j,n⟩$, where n is number of agents $r_i$ which until current moment have not sent to $G^{\ast }$ messages with results of application of corresponding rule to jth MS.

Agent $G^{\ast }$ sends couple $⟨j,v⟩$ to all agents $r_i$. After this, $G^{\ast }$ joins to the current value of variable Z couple $⟨j,l⟩$. Every agent $r_i$, receiving message $⟨j,v⟩$ from agent $G^{\ast }$, tries to apply $v$ to rule $r_i$. If application is possible, $r_i$ sends to $G^{\ast }$ message $j,v^{\prime }$, where $v^{\prime }$ is result of application of rule $r_i$ to MS$v$. Otherwise $r_i$ sends to $G^{\ast }$ message $⟨j,\left\{\mathrm{Ø}\right\}⟩$. Agent $G^{\ast }$, receiving message $⟨j,v⟩$, where $v\ne \left\{\mathrm{Ø}\right\}$, assigns $J$ new value $J+1$, and sends message $⟨J,v⟩$ to all agents. Also couple $⟨J,l⟩$ is joined to Z, and couple $⟨j,q⟩\in Z$ is eliminated from set Z, that means at least one rule was applied to jth MS, so this multiset is non-terminal. If agent $G^{\ast }$ receives message $⟨j,\left\{\mathrm{Ø}\right\}⟩$ from $r_i$, that means rule $r_i$ was not applied to jth multiset, and $⟨j,q⟩\in Z$ is replaced by $⟨j,q-1⟩$. If now $⟨j,0⟩\in Z$, that means no one rule was applied to jth MS, that’s why it is terminal, and, according to FMG semantics, it must be filtered. So agent $G^{\ast }$ sends couple $⟨j,v⟩$ to agent $F^{\ast }$, which provides testing, whether v satisfies boundary subfilter $F_{\le }\subseteq F$. If testing is successful, agent $F^{\ast }$ sends to agent $G^{\ast }$ message $⟨j,1⟩$, otherwise—message $⟨j,0⟩$. In the case $⟨j,1⟩$ couple $⟨j,v⟩$ is joined to the current value of variable $V_s$. After no active agents $r_i$ remain, agent $G^{\ast }$ applies optimizing subfilter $F_{\mathit{opt}}\subseteq F$ to the aforementioned current value $V_s$, eliminating from it all multisets, which do not satisfy $F_{\mathit{opt}}$. Final value of variable $V_s$ is exactly set of terminal multisets, defined by FMG$S=⟨v_0,R,F⟩$.

As may be seen, proposed multi-agent system provides generation and filtration of multisets by parallel operation of all agents, entering this MAS.

However, there are some evident bottlenecks, limiting speed of multisets generation. Most essential of such bottlenecks are massive transmissions of multiply repeated sets of multiobjects via MAS communication network. To reduce such transmission it is possible not to send MO to agents $r_i$ such, that corresponding them rules are applicable to multisets, having place in the storage V, and this applicability may be recognized directly by agent $G^{\ast }$. If such opportunity may be implemented, only those agents $r_i$, which, possibly, may apply corresponding rules to current MS, would receive it. By this measure, traffic on MAS communication network may be reduced sharply.

To implement proposed logics, we shall introduce auxiliary database L, which elements would be couples $⟨a,\left\{⟨i_1,n_1⟩,\dots ,⟨i_k,n_k⟩\right\}⟩$, where $a$ is name of object, and in couples $⟨i,n⟩$, entering the set, which is second component of the couple, integer $i$ is number of the rule, which left part contains multiobject $n\cdot a$.

Example 6. Let scheme $R=\left\{r_1,r_2\right\}$, where $r_1$ is

$$\left\{9\cdot \left(\mathit{eur}\right)\right\}\to \left\{10\cdot \left(\mathit{usd}\right)\right\},$$

and $r_2$ is

$$\left\{5\cdot \left(\mathit{eur}\right),3\cdot \left(\mathit{rur}\right)\right\}\to \left\{7\cdot \left(\mathit{usd}\right)\right\}.$$

Then $L=\left\{<\left(\mathit{eur}\right),\left\{<1,9>,<2,5>\right\}>,<\left(\mathit{rur}\right),\left\{<2,3>\right\}>\right\}.$∎

Database L has such internal organization, that there exists associative index, providing direct selection of couple $⟨a,w⟩$ for object name $a$. To reduce search in the selected list of couples $⟨i,n⟩$, it may be created as ordered by increase of multiplicities $n$. Let $v=\left\{n_1\cdot a_1,\dots ,n_m\cdot a_m\right\}$ be a current multiset processed by agent $G^{\ast }$, and $Q=\left\{⟨a_1,\le n_1⟩,\dots ,⟨a_m,\le n_m⟩\right\}$ is set of queries to database L, each providing selection of couples $⟨a_i,\left\{j_1^i,\dots ,j_{k_i}^i\right\}⟩,$ such that $n_p^i\le n_i$. It is clear, that only in this case rules $r_{j_1^i},\dots ,r_{j_{k_i}^i}$ may have opportunity to be applied to MS$v$, and, totally, only those rules, in which all multiobjects from their left parts have multiplicities hot greater than those of the same objects having place in $v$. So there is an evident criterion for selection of rules, which may be applicable to the current multiset $v$.

Statement 1. Let $\left\{⟨a_{i_1},N_1⟩,\dots ,⟨a_{i_p},N_p⟩\right\}$ be a set, selected from database L by query $Q=\left\{⟨a_1,\le n_1⟩,\dots ,⟨a_m,\le n_m⟩\right\}$, corresponding to multiset $v=\left\{n_1\cdot a_1,\dots ,n_m\cdot a_m\right\}$, and $\left\{n_{j_1}\cdot a_{j_1},\dots ,n_{j_s}\cdot a_{j_s}\right\}$ be the left part of rule r. Then r may be applicable to $v$, if

$$\left\{a_{j_1},\dots ,a_{j_s}\right\}\subseteq \left\{a_{j_1},\dots ,a_{j_p}\right\}.∎$$E27

As seen, proposed associative organization of set of left parts of rules entering scheme R provides fast selection of sets of rules, which may be applied to the current multiset.

Let us consider further enhancement of FMG application engine, based on the multi-agent technology.

First of all, it is evident, that it is not necessary to send all multiobjects of multiset $v$, to which rule$r_i$ is applicable, to agent $r_i$, because replacement of left part of this rule by its right part is local operation, regarding in general case relatively small number of multiobjects in the processed multiset $v$, while all the rest MO remain unchanged. So it is sufficient to send to agent $r_i$ only tuple $⟨f_1{n}_{i_1},\dots ,f_t{n}_{i_t}⟩$ of multiplicities of objects $a_{i_1},\dots ,a_{i_t}$, in MS$v$, such that tuple $A=⟨a_{i_1},\dots ,a_{i_t}⟩$ is ordered lexicographically set of objects, having place in both left and right parts of rule r, and signs $f_i$ before multiplicities $n_{i_j}$ of objects $a_{i_j}$, having place in left side of rule r, are “–”, while all other are “+”. Receiving this tuple, agent r provides computation of tuple $⟨{\mathit{n}}_{{\mathit{i}}_1},\dots ,{\mathit{n}}_{{\mathit{i}}_{\mathit{t}}}⟩$, where ${\mathit{n}}_{\mathit{j}}=n_j+\left(f_j{n}_{i_j}\right),j=1,\dots ,t$. (There may be particular case, when some objects do enter both left and right parts but this singularity is simply handled by positioning to the jth place of tuple A number $-n+n^{\prime }$, where $n$ is multiplicity of object $a_{i_j}$ in the left part, and $n^{\prime }$–its multiplicity in the right part of rule r).

Example 7. Let $v=\left\{5\cdot \left(\mathit{eur}\right),10\cdot \left(\mathit{usd}\right),7\cdot \left(\mathit{rur}\right),18\cdot \left(\mathit{\text{pound}}\right)\right\}$, and r is $\left\{3\cdot \left(\mathit{eur}\right),2\cdot \left(\mathit{rur}\right)\right\}\to \left\{5\cdot \left(\mathit{usd}\right)\right\}$. Because set of lexemes, entering this rule, is ordered lexicographically as $⟨\mathit{eur},\mathit{rur},\mathit{usd},⟩$ so tuple, sent by agent $G^{\ast }$ to agent r, would be $⟨5,7,10,⟩$ and agent r would sent to agent $G^{\ast }$ tuple $⟨5-3,7-2,10+5⟩=⟨2,5,15⟩$, and, thus, result of $v\stackrel{r}{\Rightarrow }{v}^{\prime }$ would be $v^{\prime }=\left\{2\cdot \left(\mathit{eur}\right),15\cdot \left(\mathit{usd}\right),5\cdot \left(\mathit{rur}\right),18\cdot \left(\mathit{\text{pound}}\right)\right\}$. As seen, multiplicity of object $\left(\mathit{\text{pound}}\right)$ is not transferred to agent r, because this object does not enter rule r.∎

Proposed techniques provides further reduction of traffic on MAS communication network and, thus, total time of generation of STMS, defined by FMG.

Application of the described MAS-based generation of STMS is flexible as it is only possible: due to granularity of multigrammatical knowledge representation local corrections of FMG by replacement of one rules by another are easily reflected by corresponding replacement of only concerned agents without touching the other. The same may be done with FMG filters. Such flexibility provides the simplest implementation of the most practically useful “what-if” regimes of application of MG-centered knowledge-based decision support systems.

4. Conclusion

Proposed techniques of application of multi-agent technology to the high-parallel generation of sets of multisets, defined by filtering multiset grammars, provides essential growth of speed of creation of STMS. However, there are some evident ways of further enhancement of FMG implementation upon this background:

• development of methods of matching constructed MAS to real homogeneous or heterogeneous hardware in such a way that delays, caused by information exchange between agents, would be minimal;

• development of more efficient MAT application techniques concerning some more particular cases of MG – first of all, filtering context-free multiset grammars as well as filtering unitary MG and unitary multiset metagrammars;

• design of special-purpose computing environments suitable for direct implementation of FMG and other dialects of MG family;

• development of MAT-based techniques of implementation of algorithmics of unitary multiset metagrammars as most practically useful tool of the MG family.

Acknowledgments

Author is grateful to Prof. Fred Roberts and Prof. Alexey Gvishiani for useful discussions.