Joint intentions as a model of multi-agent coopera

1JointIntentionsasaModelofMulti-AgentCooperationinComplexDynamicEnvironmentsbyNicholasRobertJenningsThesissubmittedforthedegreeofDoctorofPhilosophyintheFacultyofEngineeringDepartmentofElectronicEngineering,QueenMaryandWestfieldCollege,UniversityofLondon,MileEndRoad,LondonE14NSAUGUST19922ABSTRACTComputer-basedsystemsarebeingusedtotackleincreasinglycomplexproblemsinevermoredemandingdomains.Thesizeandamountofknowledgeneededbysuchsystemsmeanstheyarebecomingunwieldyanddifficulttoengineerintoreliable,consistentproducts.Oneparadigmforovercomingthisbarrieristodecomposetheproblemintosmallermoremanageablecomponentswhichcancommunicateandcooperateatthelevelofsharingprocessingresponsibilitiesandinformation.Untilrecently,researchinmulti-agentsystemshasbeenbasedonadhocmodelsofactionandinteraction;however,thenotionofintentionsisbeginningtoemergeasaprimecandidateuponwhichasoundtheorycouldbebased.Thisresearchdevelopsanewmodelofjointintentionsasameansofdescribingtheactivitiesofgroupsofagentsworkingcollaboratively.Themodelstressestheroleofintentionsincontrollingagents’currentandfutureactions;definingpreconditionswhichmustbesatisfiedbeforejointproblemsolvingcancommenceandprescribinghowindividualagentsshouldbehaveonceithasbeenestablished.Suchamodelbecomesespeciallyimportantindynamicenvironmentsinwhichagentsmaypossessneithercompletenorcorrectbeliefsabouttheirworldorotheragents,havechangeablegoalsandfallibleactionsandbesubjecttointerruptionfromexternalevents.Thetheoryhasbeenimplementedinageneralpurposecooperationframework,calledGRATE*,andappliedtothereal-worldproblemofelectricitytransportationmanagement.Inthisapplication,individualproblemsolvershavetotakedecisionsusingpartial,impreciseinformationandrespondtoaneverchangingexternalworld.Thisfertileenvironmentenabledthequantitativebenefitsofthetheorytobeassessedandcomparisonswithothermodelsofcollaborativeproblemsolvingtobeundertaken.TheseexperimentshighlightedthehighdegreeofcoherenceattainedbyGRATE*problemsolvinggroups,eveninthemostdynamicandunpredictableapplicationcontexts.3ACKNOWLEDGMENTSIwouldliketoexpressmygratitudetothefollowingpeoplefortheirhelpinthisthesis.FirstlytomysupervisorProfessorAbeMamdaniforhishelp,suggestionsandencouragementthroughoutthisresearch.OthermembersoftheKnowledgeEngineeringApplicationsGrouphavealsoassistedinmanydifferentways-especiallyJohnBigham,ClaudiaRoda,JeffPople,LaszloVargaandSimonParsons.ThanksarealsoduetoAndyMartinwhohasprovidedexcellentcomputersupport.ThisresearchhasbenefittedtremendouslyfrominteractionswithallthepartnersontheARCHONproject.Inparticular,InakiLaresgoiti,JuanPerezandJoseCorerahelpedmetounderstandtheelectricitytransportdomain;RobAarnts,JoachimFuchsandPaulSkarekprovidedvaluablefeedbackbyapplyingGRATEtotheproblemofcooperativefaultdetectionforparticleacceleratorbeams;andThiesWittiggavegeneralguidanceonsystemdesignissues.ErickGaussensdeservesaspecialmentionfortheinterestandenthusiasmhehasshowninmyresearch-readingpapersandchaptersofthisthesis,offeringhelpfulcommentsandinsights,andcriticisingwhenIhavebeenvague.IwouldalsoliketoacknowledgethecontributionofChrisWhitneyandothersatBTResearchLabs(MartleshamHeath)whoinvestigatedthefeasibilityofapplyingGRATEtothedomainoftelecommunicationsnetworkmanagement.Finally,butinnowayleast,IwouldliketothankmyparentsfortheirvaluedsupportandinterestinmyacademicactivitiesandJowhohasgivenmeconstantencouragement,supportandfriendshipthroughouteverystageofmyPh.D.4TABLEOFCONTENTSABSTRACTACKNOWLEDGMENTSTABLEOFCONTENTSLISTOFFIGURESCHAPTER1INTRODUCTION1.1MotivationForResearch1.2IntroductiontoDistributedAI1.2.1DefiningDistributedAI1.2.1.1DistributedProblemSolving1.2.1.2Multi-AgentSystems1.2.1.3ParallelAI1.2.2FormsofSocialInteraction1.2.3SystemDesignIssues1.2.4Intentions1.3IndustrialControlApplications1.3.1MonitoringElectricityTransportationNetworks1.3.2DetailedFunctionalityforElectricityTransportManagement1.3.3BenefitsofDistributedAIinElectricityTransportManagement1.4ObjectiveandContributionofResearch1.5OrganisationofThesisCHAPTER2DEVELOPINGMULTI-AGENTSYSTEMS2.1ExistingMulti-AgentSystemEnvironments234912121515171820202627293134353637393952.2ANewParadigmforBuildingMulti-AgentSystems2.3AgentModels2.3.1InformationContainedinAgentModels2.3.2AgentModelsinMACE2.3.3AgentModelsinCooperA2.3.4FormalAgentModels2.3.5GRATEAgentModels2.3.6LocationofAgentModels2.4AGRATESystem2.4.1GRATEAgents2.4.2ControlModule2.4.3SituationAssessmentModule2.4.4CooperationModule2.5AchievingGeneralityinGRATE2.5.1CooperativeKnowHow2.5.2ControllingDomainLevelTasks2.6UsingGRATEinElectricityTransportationManagement2.7ExperienceswithGRATECHAPTER3INTENTIONSANDJOINTINTENTIONS3.1TheRoleOfIntentionsinProblemSolving3.1.1ReactiveSystems3.2LogicalPreliminaries3.2.1PossibleWorldsandBelief3.2.2MutualBelief42454949505051545656585960626263656873737576767763.2.3TemporalandDynamicLogics3.3ExistingWorkonIndividualIntentions3.3.1CohenandLevesque’sModel3.3.1.1Evaluation3.3.2Pollack’sModel3.3.2.1Evaluation3.3.3Werner’sModel3.3.3.1Evaluation3.4LimitationsofIndividualIntentionAppro