57Rapid prototyping of large multi-agent systems t

RapidPrototypingofLargeMulti-AgentSystemsthroughLogicProgrammingW.Vasconcelos([e-mail])DepartmentofComputingScience,UniversityofAberdeenAberdeenAB243UE,UnitedKingdomD.Robertson([e-mail])CentreforIntelligentSystemsandtheirApplications(CISA)DivisionofInformatics,UniversityofEdinburghAppletonTower,CrichtonStreet,EdinburghEH89LE,UnitedKingdomC.Sierra([e-mail]),M.Esteva([e-mail])andJ.Sabater([e-mail])ArticialIntelligenceResearchInstitute(IIIA)ConsejoSuperiordeInvestigacionesCientcas(CSIC)CampusUAB,08193,Bellaterra,Catalonia,SpainM.Wooldridge([e-mail])DepartmentofComputerScience,UniversityofLiverpoolLiverpoolL697ZF,UnitedKingdomAbstract.Prototypingisavaluabletechniquetohelpsoftwareengineersexplorethedesignspacewhilegaininginsightonthedynamicsofthesystem.Inthispaper,wedescribeamethodforrapidlybuildingprototypesoflargemulti-agentsystemsusinglogicprogramming.Ourmethodadvocatestheuseofadescriptionofallpermittedinteractionsamongthecomponentsofthesystem,thatis,theprotocol,asthestartingspecication.Theprotocolisrepresentedinawaythatallowsustoautomaticallycheckfordesirablepropertiesofthesystemtobebuilt.Wethenemploythesamespecicationtosynthesiseagentsthatwillcorrectlyfollowtheprotocol.Thesesynthesisedagentsaresimplelogicprogramsthatengineerscanfurthercustomiseintomoresophisticatedsoftware.Ourchoiceofagentsaslogicprogramsallowsustoprovidesemi-automaticsupportforthecustomisationactivity.Inourmethod,aprototypeisaprotocolwithasetofsynthesisedandcustomisedagents.Executingtheprototypeamountstohavingtheseagentsenacttheprotocol.Wehaveimplementedanddescribedadistributedplatformtosimulateprototypes.1.IntroductionRapidprototypingoersameanstoexploreessentialfeaturesofaproposedsystem[9,27,35],promotingearlyexperimentationwithalternativedesignchoicesandallowingengineerstopursuedierentsolutionswithouteciencyconcerns[9].In[25]wendreportsofmanysuccessfulexperimentsofrapidprototyping.Multi-agentsystems(MASs,forshort)arehardertodesignthancentralisedsystems[38]andc2003KluwerAcademicPublishers.PrintedintheNetherlands.main.tex;19/11/2003;9:51;p.12W.Vasconcelosetal.toolsandmethodstosupportthedevelopmentofMASsareinurgentneed[30].InthispaperwedescribeamethodforrapidlybuildingprototypesoflargeMASsusinglogicprogramming.OurapproachisbasedonaglobalprotocoldepictingallinteractionsthattakeplaceintheMAS.Theformatandorderofallinteractionsareformallyspeciedasakindofnon-deterministicnitestatemachine.Thisformalismcanbeusedtocheckfordesirablepropertiesintheprotocol.Anadvantageweexploitisthatthisglobalprotocolcanbeusedtoautomaticallysynthesisetheagentsthatwillcomprisethesystem.OurapproachtoprototypingMASsreectsthemodellingmethodologyintroducedin[61]andconsistsofthefollowingsteps:1.DesignofaGlobalProtocol{inthisinitialstepweprescribethedesignofaglobalprotocol,thatis,aprecisedescriptionofthekindsandorderofmessagesthatthecomponentsoftheMAScanexchange.Forthisdescriptionwehaveusedaformofnon-deterministicnitestatemachines,calledelectronicinstitutions(orsimplye-institutions)[18,40].WeexplainmoreaboutthisinSection2.2.SynthesisandCustomisationofAgents{thisstepaddressestheautomaticsynthesisofagentsaslogicprogramscomplyingwiththeglobalprotocol.Althoughsimple,thesesynthesisedagentsareinstrictaccordancewiththeprotocolfromwhichtheyoriginate:theirbehavioursconformtothespecicationoftheglobalprotocol.ToallowforthevariabilityofthecomponentsofaMASandtohelpengineersexplorethedesignspaceofindividualagents,weoermeanstocustomisethesynthesisedagentsintomoresophisticatedpiecesofsoftware,usinglogicprogramtransformationtechniques.WeexplainthisstepinSection3.3.DenitionofPrototype{aprototypeconsistsofane-institutionandasetofcorrespondingcustomisedagents.Designersmaydelib-eratelyleaveemptyslotsinthecustomisedagentswheredierentdesignpossibilitiesmaybepursued.Theseslotscanbecompleteddierentlygivingrisetodistinctprototypes.InSection4wede-scribethisstep.4.SimulationandMonitoringofthePrototype{thelaststepisthesimulationoftheprototypeandthecollectionofresults.Weoermeansfortheenactmentofanelectronicinstitution:theagentsarestartedasself-containedandasynchronousprocessesthatcom-municatebymeansofmessage-passing.ThisstepisdescribedinSection5.main.tex;19/11/2003;9:51;p.2RapidPrototypingofLargeMASsthroughLogicProgramming3ThesestepsareillustratedinFigure1.Inthediagram,wealsoincludedsimulationMASprototypedefinitionofsynthesis&customisationResultsAgentGlobalProtocolResultsverificationFigure1.OverviewofProposedMethodforRapidPrototypingavericationactivity:thesamespecicationfortheglobalprotocolcanbeusedtocheckfordesirableproperties(ortheabsenceofundesirableproperties){weexplainthisstepinSection2.WedescribethestepsaboveinSections2to5.WecompareourapproachwithrelatedworkinSection6andinSection7wediscusstheideaspresented,drawconclusionsandgivedirectionsforfuturework.1.1.ATypicalScenarioforMASPrototypingMASsconsistofmanycomponentswhichinteractdynamically,eachwithitsownthreadofcontrol,andengagingincomplexcoordinationprotocols.MASsarem