Open access peer-reviewed chapter - ONLINE FIRST

Multi-Agent Implementation of Filtering Multiset Grammars

By Igor Sheremet

Submitted: June 18th 2020Reviewed: July 1st 2020Published: July 25th 2020

DOI: 10.5772/intechopen.93303

Downloaded: 19

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:

  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=a1,,a1n1timesai,,ainitimesam,,amnmtimes.E1

Record (1) is usually represented as

v=n1a1nmam,E2

where vis called multiset, niaimultiobjects (MO), aiobjects, ni– their multiplicities, for alli=1,,m. According to (2), multiset may be considered as a set of multiobjects, and, in fact, multiset 1a11amand set a1amrepresent one and the same collection. Seta1am, denoted as βv, is called basis of multisetv. Both empty multiset and empty set are denoted as Ø.

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

n1a1nmam0am+1=n1a1nmam.E3

Fact, that object aenters MS v(or MS vincludes object a), is denoted as av. Symbol “” is also used to denote, that MO naenters MS v(MS vincludes MO na):nav. Structure of the left operand determines what kind of relation is referred in every particular case. Similarly, symbol “” is used to denote, that object a(multiobject na) does not enter multiset v. Due to (3),avand 0avare equivalent.

Number v=mis called dimensionality of MS v, and number

v=i=1mni,E4

is called power of MS v.

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

MS vis included to MS v', if

navnavnn,E5

i.e. for every MO naentering MS vthere exists MO na, which multiplicity nis not less than n. There may be also navsuch that av(as seen, this does not contradict (5), because0avand 0<n).

If vvand vv, then MS vis strictly included to MS v, that is denoted vv.

MS v, which is included to MS v, is called submultiset of MS v; MS v, which is strictly included to MS v, is called strict submultiset of MS v.

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=1eur5usd12rur,
v=6eur5usd12rur.

As seen, according to (5), vvand vv'.∎

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:

nn1a1nmam=n×n1a1n×nmam,E6

where “×” denotes multiplication of integer numbers;

v+v=aβvβvnaϵvnavn+na,E7
vv=aβvβvnaϵvnavn>nnna.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 ∩:

vv=aβvβvnaϵvnavmaxnna,E9
vv=aβvβvnaϵvnavminnna,E10

We have used equivalence between avand 0avin (9).

Example 2. Letvand vbe as in Example 1. Then

3v=3eur15usd36eur,
v+v=7eur10usd24rur,
vv=Ø,
vv=5eur,
vv=6eur5usd12rur,
vv=1eur5usd12rur.

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 VF, where Vis filtrated SMS, F is filter, and “” – symbol of operation.

Conditions entering filter F may be boundary and optimizing.

Boundary conditions (BC) are recorded as aθn, where θ><=. Multiset vsatisfies BC aθn, if mavand mθnis true (as everywhere, avis equivalent to 0av).

Let F=bc1bckbe a filter, containing only boundary conditions.

Then

VF=i=1kVbci.E11

Example 3. Let V=v1v2v3, where

v1=4eur3rur,
v2=8usd10rur,
v3=3eur19usd17rur,

and F=usd>3rur12. Then

VF=Vusd>3Vrur12==v2v3v1v2=v2.

Optimizing conditions (OC) are recorded asa=opt,where optmaxmin. Multiset vVsatisfies OC a=max, if navand all multisets vVvsatisfy boundary condition an. Similarly, multiset vVsatisfies OC a=min, if navand all multisets vVvsatisfy boundary condition an.

Let Fopt=oc1oclbe filter, containing only optimizing conditions. Then, similarly to (6),

VFopt=i=1lVoci.E12

Example 4. Let Vbe the same as in Example 3, and

Fopt=usd=maxrur=min. Then

VFopt=v{usd=max})vrur=min=v3v1=Ø.

If filter Fcontains both boundary and optimizing conditions, i.e.

F=FFopt,E13

then

VF=VFFopt,E14

i.e. result of filtering set of multisets Vby filter Fis obtained by application of boundary subfilter FtoV, after what resulting SMS is filtered by optimizing subfilter Fopt.

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=v0R, where v0called kernel is multiset, and Rcalled scheme is finite set of so called rules. Set of all objects used in kernel and scheme of MG Sis denoted as AS.

Rule rRis a construction

vv,E15

where multisets v and vare called respectively left part and right part of the rule r, and “” is divider. The only restriction on left and right parts of the rule isvØ.

If vv, then result of application of rule r to multiset vis multiset

v'=vv+v..E16

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

vrv',E17

and it is said, that MS v'is generated from MS vby application of rule r. If left part vis not included to MS v, result of application r to vis empty MS Ø.

Set of multisets, generated by application of multigrammar S=v0R, or, just the same, defined by this multigrammar, is recursively created as follows:

V0=v0,E18
Vi+1=VivVirRv'vrv',E19
VS=V.E20

As seen, VSincludes all multisets, which may be generated from MS v0by sequential application of rules rR, and VSis fixed point of the sequence V0,V1,,Vi,,so

VS=i=0Vi.E21

In general case VSmay be infinite.

If MS v'may be generated from MS vby application of some sequence (chain) of rules entering scheme R, it is denoted as

vRv',E22

and, if so,

VS=vv0Rv.E23

Multiset vVSis called terminal multiset (TMS), if

rRvrØ,E24

i.e. no any rule rRmay be applied to this multiset. Set of terminal multisets (STMS) defined by multiset grammar S is denoted VS¯. Evidently,

VS¯VS.E25

Example 5. Let S=v0R, where kernel

v0=3eur6usd5rur,

and scheme R=r1r2, where r1is

2eur4usd,

and r2is

2usd3rur2eur.

According to (18)–(19),

V0=3eur6usd5rur,V1=V01eur10usd5rur,5eur4usd2rur,V2=V13eur8usd2rur,

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 v0by sequential currency exchanges, which parameters are fixed by rules r1and r2(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=v0RF, where v0and Rare, as above, kernel and scheme, while Fis a filter, including boundary and optimizing conditions, defining multisets, which would be selected from the set of TMS, generated by MG v_0R, i.e.

Vs=V¯v0RF.E26

Verbally, Vsis subset of V¯v0R, 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=v0RF, contains l=Ragents r1,,rl, 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, implementing filter F; one agent G, providing supervision on other agents interaction (in fact, implementing ubiquitous generation by application of rules to multisets, generated at previous steps). Agent Guses storage VSfor accumulation of all generated terminal multisets, satisfying filter F. Also Goperates storage V, containing current set of generated multisets, which are not yet transferred to other agents. Initial state of Vis v0. 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.

NSenderReceiverMessageComment
1Grijvj – number of MS, vØ
2riGjvv– result of application of rule
rito MS v
3riGjØRule riis not applicable to v
4Gjv,jvAs 1
5FGj1jth MS satisfies filter F
6FGj0jth 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. Current maximal number is denoted J. Also agent Guses variable Z, which value is set of couples jn, where n is number of agents riwhich until current moment have not sent to Gmessages with results of application of corresponding rule to jth MS.

Agent Gsends couple jvto all agents ri. After this, Gjoins to the current value of variable Z couple jl. Every agent ri, receiving message jvfrom agent G, tries to apply vto rule ri. If application is possible, risends to Gmessage j,v, where vis result of application of rule rito MS v. Otherwise risends to Gmessage jØ. Agent G, receiving message jv, where vØ, assigns Jnew value J+1, and sends message Jvto all agents. Also couple Jlis joined to Z, and couple jqZis eliminated from set Z, that means at least one rule was applied to jth MS, so this multiset is non-terminal. If agent Greceives message jØfrom ri, that means rule riwas not applied to jth multiset, and jqZis replaced by jq1. If now j0Z, 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 Gsends couple jvto agent F, which provides testing, whether v satisfies boundary subfilter FF. If testing is successful, agent Fsends to agent Gmessage j1, otherwise—message j0. In the case j1couple jvis joined to the current value of variable Vs. After no active agents riremain, agent Gapplies optimizing subfilter FoptFto the aforementioned current value Vs, eliminating from it all multisets, which do not satisfy Fopt. Final value of variable Vsis exactly set of terminal multisets, defined by FMG S=v0RF.

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 risuch, that corresponding them rules are applicable to multisets, having place in the storage V, and this applicability may be recognized directly by agent G. If such opportunity may be implemented, only those agents ri, 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 ai1n1iknk, where ais name of object, and in couples in, entering the set, which is second component of the couple, integer iis number of the rule, which left part contains multiobject na.

Example 6. Let scheme R=r1r2, where r1is

9eur10usd,

and r2is

5eur3rur7usd.

Then L=<eur<19><25>><rur<23>>.

Database L has such internal organization, that there exists associative index, providing direct selection of couple awfor object name a. To reduce search in the selected list of couples in, it may be created as ordered by increase of multiplicities n. Let v=n1a1nmambe a current multiset processed by agent G, and Q=a1n1amnmis set of queries to database L, each providing selection of couples aij1ijkii,such that npini. It is clear, that only in this case rules rj1i,,rjkiimay 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 ai1N1aipNpbe a set, selected from database L by query Q=a1n1amnm, corresponding to multiset v=n1a1nmam, and nj1aj1njsajsbe the left part of rule r. Then r may be applicable to v, if

aj1ajsaj1ajp.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 ruleriis applicable, to agent ri, 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 rionly tuple f1ni1ftnitof multiplicities of objects ai1,,ait, in MS v, such that tuple A=ai1aitis ordered lexicographically set of objects, having place in both left and right parts of rule r, and signs fibefore multiplicities nijof objects aij, having place in left side of rule r, are “–”, while all other are “+”. Receiving this tuple, agent r provides computation of tuple ni1nit, where nj=nj+fjnij,j=1,,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, where nis multiplicity of object aijin the left part, and n–its multiplicity in the right part of rule r).

Example 7. Let v=5eur10usd7rur18pound, and r is 3eur2rur5usd. Because set of lexemes, entering this rule, is ordered lexicographically as eurrurusdso tuple, sent by agent Gto agent r, would be5710and agent r would sent to agent Gtuple 537210+5=2515, and, thus, result of vrvwould be v=2eur15usd5rur18pound. As seen, multiplicity of object poundis 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.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Igor Sheremet (July 25th 2020). Multi-Agent Implementation of Filtering Multiset Grammars [Online First], IntechOpen, DOI: 10.5772/intechopen.93303. Available from:

chapter statistics

19total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us