Poems

8 pages
8 views

A Case-Based Reasoning Approach for Norm Adaptation

of 8
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
A Case-Based Reasoning Approach for Norm Adaptation
Transcript
  ACase-BasedReasoningapproachforNorm adaptation  JordiCampos  1 ,MaiteLópez-Sánchez  1 ,andMarcEsteva  2 1 UniversitatdeBarcelona,585GranVia,08007Barcelona,Spain  {jcampos,maite}@maia.ub.es  2 IIIA-CSIC,CampusUAB,08193Bellaterra,Spain  marc@iiia.csic.es  Abstract.  Existingorganisationalcentredmulti-agentsystemsregulate agents'activities.However,population/environmentalchangesmaylead toapoorfullmentofsystem'sgoals,andtherefore,adaptingthewhole organisationbecomeskey.Inthispaper,weproposetouseCase-Based Reasoninglearningtoadaptnormsthatregulateagents'behaviour.More- over,weempiricallyevaluatethisapproachinaP2Pscenario.  1Introduction  DevelopingMultiAgentSystems(MAS)isacomplextaskduetothediculties ofhavingexibleandcomplexinteractionsamongautonomousentities.Organ- isingsuchsystemstoregulateagentinteractionshelpstopredict/regulatethe system'sevolutionwithincertainbounds.However,certainenvironmentalor populationchangesmaydecreaseitsabilitytoachieveitsorganisationalgoals. Thus,adaptingsuchanorganisationisnowbecominganimportanttopic[10]. Concerningthisadaptation,weproposetoaddan  Assistancelayer  [6]in chargeofit,insteadofexpectingagentstoincreasetheirbehaviourcomplexity itisrelevantinopenMAS,sincethereisnocontroloveragentcode.Inpar- ticular,weusethislayertoadaptnormsthatarepartofsystem'sorganisation. Notice,thatthesenormsregulateagents'activitybyboundingtheiractions,but agentsstillkeepitsdegreeoffreedomtochoosetheiractualactions.Thus,this additionallayercanadapttheorganisationwhilepreservingagents'autonomy. However,therelationshipbetweenthesenormsandsystem'soutcomesmakes theadaptationprocessverycomplex,sincethereisnodirectmappingamong them.Suchaprocesscanbecodedbythesystemdesignerorlearnt.Though, duetodicultiestodeneanoptimalmechanism,weadvocatebythelearning approach.Inthispaper,weuseaCase-BasedReasoningmethod,whichfaces newsituationsbasedonpastexperience[2].Asanillustration,wepresenta Peer-to-Peersharingnetwork(P2P)scenariowherecomputerscontactamong themtosharesomedata.Insuchascenario,therelationshipamongcomputers' activity,thenetworktracandthetimerequiredtoshareadatumiscomplex. Nextsection2providesdetailsonrelatedpreviouswork.Afterwards,our proposalisdescribedinsections3-4andevaluatedinsection5.Finally,our conclusionsarepresentedinsection6.   2  2Relatedwork  WithinMASarea,organisation-centredapproachesregulateopensystemsby meansofpersistentorganisationse.g.EI[11].Evenmore,severaloftheseap- proachesoermechanismstoupdatetheirorganisationalstructuresatrun-time e.g.Moise+[4].However,mostworkonadaptationmapsorganisationalgoals totasksandlookforagentswithcapabilitiestoperformtheme.g.OMACS [10].Consequently,theseapproachescannotdealwithscenariosthatlackofthis goal/taskmapping,likeourcasestudy.Inordertodealwiththissortofscenar- ios,ourapproachusesnormstoinuenceagentbehaviour,insteadofdelegating tasks.Specically,ourapproachusesanormadaptationmechanismbasedon socialpower.Inthissense,thereareotherworksthatalsousetheleadershipof certainagentstocreate/spreadnormse.g.therolemodelbasedmechanism[9]. Besides,mostworksonnormemergenceareagent-centredapproachesthatde- pendonparticipants'implementationandtheyrarelycreate/updatepersistent organisationse.g.infection-basedmodel[15]. Relatingnormsandoverallsystembehaviourisacomplexissuethatincreases itsintricacywhenthereisnocontroloverparticipant'simplementation.Inour approach,thistaskisdistributedamongsomeempoweredagentsthatnally reachanagreementaboutnormupdates.Currently,theyuseavotingscheme toagreeonactualnorms,buttheycouldusesomeotheragreementmechanisms presentintheliteraturee.g.argumentationprotocols[3].Inparticular,these agentstaketheirlocaldecisionsusingtheCase-BasedReasoning(CBR)learning techniquedescribedin[2],whichfacesnewsituationsbasedonpastexperience. TheAutonomicEI[5]alsouseCBRtoadapttheirorganisation,takingacen- tralisedapproach.Onthecontrary,wetakeadistributedapproachbothatthe processingandknowledgelevelsasdenedin[14]. RegardingourP2Pscenario,therearenetworkmanagementperspectiveap- proachesthattrytopromotelocalcommunicationsbuttheycannotdirectly actonnetworkconsumptiontobalancenetcapacityandtrace.g.P4P[16]. FromaMASangle,thereareworkswhereagentsadaptlocalnormsusinglocal informationbuttheycannotreason/actatanorganisationallevele.g.[12].  3AssistanceinP2Pscenario  Ourapproachconsistsinprovidingsupporttothecoordinationofagentssee coordinationsupportin[6].Infact,weproposedagenericTwoLevelAssisted MASArchitecture(2-LAMA[8])tohelpagentstoparticipateinorganisational- centredMAS.Weusethisgenericarchitecturetodevelopsystemsthatself- adapttheirorganisationdependingontheirevolution.Inparticular,wemodel ourPeer-to-Peersharingnetworkcasestudy(P2P)asaMASwithtwolevelof organisedagentsseeFigure1.Bothlevelssharethesamegoal,whichisthat allparticipantagentsobtainthedatabyconsumingminimumtime. Ontheonehand,wemodelthesetofcomputersthatsharesomedataas agents(  Ag DL = { P  1 ...P  n } )withina  domain-level  (  DL ).Itssinglerole  peer   3  MLDL Norms DL      N    o     r    m    s  D     L      ' A1 A2 A3 P5 P6P7 P8P1 P2P3 P4P9 P10P11 P12 Datum cluster1 cluster2 cluster3      E    n    v     P ,      A    g       P   →     r    e      l_      s     u     g      g      ← Norms ML      E    n    v     P ,      A    g       P   →     r    e      l_      s     u     g      g      ←     E    n    v     P ,      A    g       P   →     r    e      l_      s     u     g      g      ← Fig.1.  2-LAMAinP2Pscenario.  Table1.  ResultsinP2Pscenario.  timecNethdatacML BT  941.2205344.13.411.0-  2L.a  834.9293526.72.935.95133.3  2L.b  741.5292357.73.033.84694.1  andtherelationshipsamongthem(i.e.theoverlaynetwork)conformthesocial structureoftheirorganisation.Thisorganisationalsohasitsownsocialconven- tions:asharingprotocolderivedfromstandardBitTorrent[8]andtwonorms (  Norm DL ).Firstnormlimitsagents'networkusageinpercentageofitsnom- inalbandwidth:  normBW  DL = apeercannotusemorethan  max BW bandwidth percentagetosharedata.Thisway,itpreventspeersfrommassivelyusingtheir bandwidthtosend/receivedatato/fromallotherpeers.Noticethatamassive networkuse,maysaturateit,andtherefore,itmaydelayallcommunications. Secondnormlimitsthenumberofpeerstowhomapeercansendthedata:  normFR DL = apeercannotsimultaneouslysendthedatato  > max FR peers. Ontheotherhand,inordertosupportthecoordinationofpreviousagents, weaddan  Assistancelayer  tothedescribedMAS.Currently,thissupportcon- sistsinadaptingdomain-level'sorganisationtochangingcircumstances.More precisely,itconsistsinadaptingtwo  DL 'sorganisationalcomponents:norms seesection4andpartofthesocialstructurebysuggestingsocialrelationships amongpairsof  DL agents(  rel _  sugg ),see[8].Theseadaptationsareperformed bya  meta-level  (  ML )setofagents(  Ag ML = { A 1 ...A m } )thatplaytherole  assistant  .Eachassistantisinchargeofadisjointsubsetof  Ag DL (cluster). Infact,assistantsusean  interface  amongbothlevelstocollectlocalinfor- mationaboutconnectionbandwidthsandcommunicationlatencies(i.e.envi- ronmentobservableproperties,  EnvP  )andaboutwhohasthedatum(i.e.agent observableproperties,  AgP  ).Inparticular,eachassistantcountsonbothdetailed informationfromitsclusterandaggregatedinformationfromotherclusterssup- pliedbyotherassistants.Theyweightthemtocombinetheinformationbefore startingitsowndecisionprocessincurrenttests,eachassistantgivesthesame importancetoitslocalinformationthantoremoteone.  4Learningnormadaptation  Aswementioned,inP2Pscenario,adaptingnormstoobtaindesiredsystem outcomesisacomplextask.Mainly,becausethereisnodirectmappingbetween normsandsystem'sbehaviour.Forinstance,whenupdatinganorm(e.g.in- creasing   max FR ),itisdiculttoforeseetheeectoforganisationalchanges(e.g. howmanydatamessageswillbetransmitted),anditisevenmorecomplexto   4  Algorithm1Retrieve(left&top-right)&Reuse(bottom-right)phases.  01defretrieve(newCase):11if(retrCasesisempty): 02retrCases={};bestS=012heuCase=Heuristic.solve(newCase) 03foreachprevCaseincaseBase:13retrCases={heuCase} 04s=  σ (prevCase.prb,newCase.prb)14returnretrCases 05if(s>MIN_SIM): 06case(s>bestS):01defreuse(retrCases,newCase): 07retrCases={prevCase}02if(  δ (retrCases)>MAX_DIV) 08bestS=s03heuCase=Heuristic.solve(newCase) 09case(s   bestS):04retrCases={heuCase} 10retrCases=retrCases  ∪ {prevCase}05sol=adapt(retrCases,newCase) 06returnCase(newCase.prb,sol)  anticipatesystem'soutcomes(e.g.thetotaltimerequiredtospreaddata).In ordertofacethiscomplexity,themeta-levelusesalearningtechniquetodecide howtoadaptdomain-levelnormsdependingoncurrentsystemstatus.Inpartic- ular,weapplyaCBR[2]learningapproach,tosuggestnormupdates(solution) toanewsystemstatus(problem)basedonsimilarprevioussituations(previous cases).OurCBRapproachisbasedonaheuristicthattriestoaligntheamount ofserving/receivingcapacitysee[7].Infact,theheuristicitselfisusedbyour CBRtosuggestasolutionwhennosimilarcasesarefound.  Casedescription  .Thedescriptionofaproblemanditssolutionconforms a  case  thatcanbestoredasapreviouscaseina  casebase  .Theformer(  Prob ) isdescribedbyasetofattributes(  Attribs )derivedfrommeasuresperceived throughtheinterfaceastheyderivefromobservablemeasures,therearenot unknownattributes.Inparticular,weusethefollowingdiscretisedattributesto describeaproblem:  srvCap ,itindicatesifthereisenoughservingcapacityto serveallreceivingpeersbycomparingthebandwidthofallservingpeerswith thebandwidthofallreceivingpeers(  rcvBW );  netSat ,itestimatesthenetwork saturationbycomparingtheactualreceivingbandwidthofreceivingpeersand theirexpectedbandwidth(  rcvExpBW = rcvBW · max BW ,since  max BW limitsthedata injectedtowardsreceivingpeers);  wait ,itreectstheamountofpeersthat lackthedatumandarenotreceivingitcurrently;  sRatio ,itindicatessources' maximumratiotospreadthedatum,thusitisderivedfromcurrentfriends' norm;  bwUsg ,itindicatesthebandwidthusedbypeersintheircommunications, thusitisderivedfromcurrentbandwidthlimitnorm.Besides,a  solution  is describedbytwodiscreteattributes:  vFR ,itindicateshowtoupdate  max FR by increasingoneunit,decreasingoneunit,keepingthesamevalueoravoiding inuencingit(i.e.a  blankballot-paper  );  vBW ,itdeneshowtoadapt  max BW by settingitto100%,keepingitsvalueordividingitbytwo.  CBRCycle  .Therearefourmainphases[2]:retrieve,reuse,reviseandre- tain.Therstphase(  retrieve  )fetchesthemostsimilarcases(  retrCases  )from thecasebase(  caseBase  )asillustratedinleftsideofAlgorithm1.Itstartswith anemptylistofcasesandaminimumreferencesimilarity(  bestS  )seeline2. Then,ittraversesthecasebaseline3computingthesimilarity(  σ ,seebe- low)ofeachpreviouscase'sproblemdescription(  prevCase.prb  )withthenew problem(  newCase.prb  )line4.Incasethissimilarityisgreaterthana  mini-   5  mumtrustedsimilarity  (  MIN_SIM  )thecaseisacandidatetoberetrievedline 5.Inparticular,ifthissimilarityisgreaterthananypreviousoneline6then thepreviouscaseistheonetoberetrievedline7.Alternatively,ifthesim- ilarityisequaltopreviousgreatestoneline9thencurrentpreviouscaseis collectedwiththerestofsimilaronesline10.Inotherwords,ittriestoreturn themostsimilarpreviouscase,althoughitcanreturnmorecaseswhenthey havenearlythesamesimilarity.However,ifnopreviouscasehastheminimum trustedsimilaritytoconsideritisrepresentativeenoughtoadaptitssolution tothenewproblemline11,thealgorithmexecutestheheuristicline12 tosolvethisunknownproblem.Finally,inbothcasesthecasesarereturned line14.The  casesimilarityfunction  (  σ )amongtwoproblems(  p x ,p y ∈ Prob ) consistsoncomputingthe  attributesimilarityfunction  (  ς  i )amongcorrespond- ingvaluesofthesameattribute(  a  p x i ,a  p y i ∈ Attrib i )toaggregatethemina weightedmanner:  σ (  p x ,p y ) =  i ∈ Attribs  w σi · ς  i ( a  p x i ,a  p y i )  ,   w σi = 1 .Inor- dertocomputethisattributesimilarityfunction(  ς  i ),wedenea  labeldistance  function  (  λ i )thatprovidesanumericdistanceamongtwodiscretelabels(e.g.  λ waiting ( NONE , NONE ) = 0 ,  λ waiting ( NONE , FEW ) = 1 ,  λ waiting ( NONE , A _  LOT ) = 2 ). Infact,weregarddiscretelabelsasanorderedsetofequidistantvalues.Then, wedene  ς  i asan  inversemapping  fromlabels'sdistance  [0 ..λ MAXi ] tothe  [0 .. 1] interval:  ς  i ( a  p x i ,a  p y i ) = 1 − λ i ( a pxi ,a pyi ) λ MAXi .Insum,inbothsimilarityfunctions(  σ,ς  i ), a  0 meansnocoincidenceatallanda  1 meansthattheitemsareequal. Fromretrievedcases,thesecondCBRphase(  reuse  )employstheirsolutions tobuildanewoneforthecurrentcase.Incasethereismorethanonesimilar case,wecountona  divergencefunction  (  δ )tocomputethedivergenceamong themitisthestandarddeviationof  vFR discretevaluesconvertedintointegers, sinceinourexperiments  vBW wascorrelatedwithit.Thus,reusephasestartsby checkingifthedivergenceofretrievedcasesisgreaterthana  maximumtrusted divergence  (  MAX_DIV  )seeline2inrightsideofAlgorithm1.Insuchacase, itconsidersthatpreviouscases'solutionsaretoocontradictorytoprovidea goodsinglesolution.Hence,theheuristicisusedlines3-4.Oncethereisa setofslightlydivergentpreviouscasesnoticethatasinglepreviouscasehas nodivergenceitadaptstheirsolutiontothecurrentproblemline5.This taskcantakeintoaccount(i)allretrievedsolutionsbutalso(ii)thedierences betweentheretrievedproblemsandthecurrentone.Incurrentimplementation, our  adapt  functionusesonlytheformer(i).Inparticular,itreturnsasolution composedbythemostfrequent  vFR andthemostfrequent  vBW .Incasethereisa tie,thelessconservativeactions(i.e.changevalues)havepriorityoverthemore conservativeones(i.e.keepthesamevalues)sincetheymaymakethesystem evolveinadierentwayandavoidatieinasubsequentadaptationprocess. Next,thethirdphase(  revise  )requiresawaytoevaluatethesolution,but currentperformancemeasure(totaltime)isunknownuntiltheendofexecution i.e.thereisacreditassignmentproblem[13].Asweareworkingonthistopic intheP2Pscenario,currentimplementationhasonlythefourthphase(  retain  ). Itconsistsonstoringonlythenewpreviouscasesreturnedbytheheuristic. Thisway,thecasebasegrowseverytimetheheuristicisusedwhenweim- 
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x