Open access peer-reviewed chapter

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

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 FMGis 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 FMGand 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 TMSgeneration is representation of the generating engine as a multi-agent system (MAS), which includes:

  1. Nagents, each corresponding to one rule from FMGscheme;

  2. one agent corresponding to FMGfilter;

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

This MASoperates 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.

Advertisement

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 basisof 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 MSv(or MSvincludesobject a), is denoted as av. Symbol “” is also used to denote, that MOnaenters MSv(MSvincludes MOna):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 dimensionalityof MSv, and number

v=i=1mni,E4

is called powerof MSv.

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

MSvis includedto MSv', if

navnavnn,E5

i.e. for every MOnaentering MSvthere exists MOna, 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 MSvis strictly includedto MSv, that is denoted vv.

MSv, which is included to MSv, is called submultisetof MSv; MSv, which is strictly included to MSv, is called strict submultisetof MSv.

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 – joinand 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, Fis filter, and “” – symbol of operation.

Conditions entering filter Fmay be boundary and optimizing.

Boundary conditions(BC) are recorded as aθn, where θ><=. Multiset vsatisfies BCaθ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 OCa=max, if navand all multisets vVvsatisfy boundary condition an. Similarly, multiset vVsatisfies OCa=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 SMSis 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 grammaras a couple S=v0R, where v0called kernelis multiset, and Rcalled schemeis finite set of so called rules. Set of all objects used in kernel and scheme of MGSis denoted as AS.

RulerRis a construction

vv,E15

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

If vv, then result of applicationof rule rto 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 MSv,then vis replaced by right part of this rule, i.e. multiset v. Result of application of rule rto multiset vis denoted as

vrv',E17

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

Set of multisets, generated by application of multigrammarS=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 MSv0by 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 MSv'may be generated from MSvby 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 Sis 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 MGprovides 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]. FMGare 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 grammaris 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 MGv_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.

Advertisement

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 FMGapplication 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 FMGS=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 implementingFMG.

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 MSv
3riGjØRule riis not applicable to v
4Gjv,jvAs 1
5FGj1jth MSsatisfies filter F
6FGj0jth MSdoes 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 MShas 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 nis 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 Zcouple 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 MSv. 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 FMGsemantics, it must be filtered. So agent Gsends couple jvto agent F, which provides testing, whether vsatisfies 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 FMGS=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 MAScommunication network. To reduce such transmission it is possible not to send MOto 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 MAScommunication 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 Lhas 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 MSv, 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 Lby query Q=a1n1amnm, corresponding to multiset v=n1a1nmam, and nj1aj1njsajsbe the left part of rule r. Then rmay be applicable to v, if

aj1ajsaj1ajp.E27

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

Let us consider further enhancement of FMGapplication 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 MOremain unchanged. So it is sufficient to send to agent rionly tuple f1ni1ftnitof multiplicities of objects ai1,,ait, in MSv, 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 rprovides 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 Anumber 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 ris 3eur2rur5usd. Because set of lexemes, entering this rule, is ordered lexicographically as eurrurusdso tuple, sent by agent Gto agent r, would be 5710and agent rwould 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 MAScommunication network and, thus, total time of generation of STMS, defined by FMG.

Application of the described MAS-based generation of STMSis flexible as it is only possible: due to granularity of multigrammatical knowledge representation local corrections of FMGby 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 FMGfilters. Such flexibility provides the simplest implementation of the most practically useful “what-if” regimes of application of MG-centered knowledge-based decision support systems.

Advertisement

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 FMGimplementation upon this background:

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

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

  • design of special-purpose computing environments suitable for direct implementation of FMGand other dialects of MGfamily;

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

Advertisement

Acknowledgments

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

© 2020 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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, Computational Optimization Techniques and Applications, Muhammad Sarfraz and Samsul Ariffin Abdul Karim, IntechOpen, DOI: 10.5772/intechopen.93303. Available from:

chapter statistics

196total chapter downloads

More statistics for editors and authors

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

Access personal reporting

Related Content

This Book

Next chapter

Optimization Directions for Monitoring of Ground Freezing Process for Grzegorz Shaft Sinking

By Paweł Kamiński

Related Book

First chapter

Introductory Chapter: On Fingerprint Recognition

By Muhammad Sarfraz

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