Set of MAS messages.

## 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.

### Keywords

- multi-agent systems and technologies
- multisets
- multiset grammars
- filtering multiset grammars
- parallel computations

## 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:

*N*agents, each corresponding to one rule from*FMG*scheme;one agent corresponding to

*FMG*filter;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:

Record (1) is usually represented as

where *multiset*, *multiobjects* (*MO*), *objects*, *multiplicities*, for all*basis* of multiset

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

Fact, that object *enters MS* *MS* *includes* object *MO* *MS* *MS* *MO*

Number *dimensionality* of *MS*

is called *power* of *MS*

Two basic relations on multisets – *inclusion* (“*strict inclusion* (“

*MS* *included* to *MS*

i.e. for every *MO* *MS* *MO*

If *MS* *strictly included* to *MS*

*MS* *MS* *submultiset* of *MS* *MS* *MS* *strict submultiset* of *MS*

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

As seen, according to (5),

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:

where “×” denotes multiplication of integer numbers;

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

We have used equivalence between

**Example 2.** Let**Example 1**. Then

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 *SMS*, *F* is filter, and “

Conditions entering filter *F* may be boundary and optimizing.

*Boundary conditions* (*BC*) are recorded as *BC*

Let

Then

**Example 3.** Let

and

*Optimizing conditions* (*OC*) are recorded as*OC* *OC*

Let

**Example 4.** Let

If filter

then

i.e. result of filtering set of multisets *SMS* is filtered by optimizing subfilter

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

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 *kernel* is multiset, and *scheme* is finite set of so called rules. Set of all objects used in kernel and scheme of *MG*

*Rule*

where multisets *v* and *left part* and *right part* of the rule *r*, and “

If *application* of rule *r* to multiset

Speaking informally, (16) defines, that if left part of the rule, i.e. multiset *MS* *r* to multiset

and it is said, that *MS* *MS* *r*. If left part *MS* *r* to *MS*

*Set of multisets, generated by application of multigrammar* *defined by this multigrammar*, is recursively created as follows:

As seen, *MS*

In general case

If *MS* *MS* *R*, it is denoted as

and, if so,

Multiset *terminal multiset* (*TMS*), if

i.e. no any rule *STMS*) defined by multiset grammar *S* is denoted

**Example 5.** Let

and scheme

and

According to (18)–(19),

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

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

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 *TMS*, generated by *MG*

Verbally,

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* *N*.

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 | j – number of MS, | |||

2 | MS | |||

3 | Rule | |||

4 | As 1 | |||

5 | jth MS satisfies filter F | |||

6 | jth MS does not satisfy filter F |

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 *Z*, which value is set of couples *n* is number of agents *j*th *MS*.

Agent *Z* couple *MS* *Z*, and couple *Z*, that means at least one rule was applied to *j*th *MS*, so this multiset is non-terminal. If agent *j*th multiset, and *j*th *MS*, that’s why it is terminal, and, according to *FMG* semantics, it must be filtered. So agent *v* satisfies boundary subfilter *FMG*

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 *V,* and this applicability may be recognized directly by agent *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

**Example 6.** Let scheme

and

Then

Database *L* has such internal organization, that there exists associative index, providing direct selection of couple *L*, each providing selection of couples *MS*

**Statement 1.** Let *L* by query *r*. Then *r* may be applicable to

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 *MO* remain unchanged. So it is sufficient to send to agent *MS* *r*, and signs *r*, are “–”, while all other are “+”. Receiving this tuple, agent *r* provides computation of tuple *j*th place of tuple *A* number *r*).

**Example 7.** Let *r* is *r*, would be*r* would sent 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.