LEARNING SITUATION-SPECIFIC CONTROL IN MULTI-AGENT

LEARNINGSITUATION-SPECIFICCONTROLINMULTI-AGENTSYSTEMSADissertationPresentedbyMARAMV.NAGENDRAPRASADSubmittedtotheGraduateSchooloftheUniversityofMassachusettsAmherstinpartialfulfillmentoftherequirementsforthedegreeofDOCTOROFPHILOSOPHYMay1997DepartmentofComputerSciencecCopyrightbyMaramV.Nagendraprasad1997AllRightsReservedLEARNINGSITUATION-SPECIFICCONTROLINMULTI-AGENTSYSTEMSADissertationPresentedbyMARAMV.NAGENDRAPRASADApprovedastostyleandcontentby:VictorR.Lesser,ChairPaulUtgoff,MemberShlomoZilberstein,MemberGeorgeZinsmeister,MemberSandipSen,MemberDavidW.Stemple,DepartmentChairComputerScienceTomymotherD.VimalaandmyfatherV.LakshmanaReddyACKNOWLEDGMENTSWhenIcametoUMass,IneverheardaboutDistributedAI.Iamdeeplyindebtedtomyguru,VictorLesserformoldingaDistributedAIresearcheroutofclay.Theintellectualexcitementduringmycollaborationwithhimisa‘high’thatwilllastmealifetime.Iusetheword“guru”initstruestsensewhenIaddressVictor.Hewasthere,likeasignpostinadesert,whenIwaslostexploringnewfrontiers.Hehasanuncannysenseoftherightdirectionandaneversaydieattitudewhenfacedwithhardproblems.Hewasthere,likeafriend,whenIhadpersonalproblems.Iconsidermyselftobetrulyfortunatetobeamemberofthe“Victor’sacademicfamily”.Manythanksgotomycommitteemembers:SandipSen,PaulUtgoff,ShlomoZilberstein,andGeorgeZinsmeister.SandipSenguidedmeinmyresearch,andservedasarolemodelandafriend.Sandipprovideddeepandinsightfulcommentsatvariousstagesofthisresearch.Ourlatenightdiscussions,atconferencesandworkshops,onthestateofthefieldandwhereitshouldbegoingservedtospurmeoninmanyinterestingdirections.Iwouldliketoexpressmydeepsenseofgratitudetohimforallthisandmore.Also,thanksgotohimforputtinglearninginmulti-agentsystemsontheresearchmapofMulti-agentSystemsandArtificialIntelligencecommunities.PaulUtgoffaskedmetherightquestionsandmadesurethatInoticedtheappropriateconnectionstotherestoftheresearchcommunityintheareaoflearning.Hereadmydocumentscarefullyandprovidedkeenfeedback.HenailedhomethepointthatIshouldwritetomakeothersunderstandratherthantodazzlethemwithanarrayofDistributedAIjargon.ThanksPaul,forbeingsuchaninfluenceonhowIpresentmyideas.IamindebtedtoShlomoZilbersteinforbeingextremelysupportiveandprovidinginsightsintotherelevanceofmythesisalongfacetsthatIneverthoughtof.Henudgedmetomakemyideasmorecrispandavoidad-hocnessinmywritingstyle.IamthankfultoProfZ(GeorgeZinsmeister)forvbringinganoutsideperspectiveandcontributingtowardsamorebalancedtreatmentofthetopics.AveryspecialthanksgoestoSusanLanderforaveryproductivecollaborationandfriendlyadviseatvariousstagesofthiswork.SueprovidedmetheTEAMsystemonwhichIperformedtheworkintwoofmythesischapters.Shegavemetechnicalassistanceevenwhenshewasbusywithfinishingherthesis,patientlylistenedtomethroughmyexcitedramblingswhenIhadideasandprovidedthemuchneededencouragementandguidance.Manyofthefollowonideasfrommythesisowetheirorigin,eitherdirectlyorindirectly,tomycollaborationwithher.ThanksSue,forbeingthebestcollaboratorIeverhad.LaterpartofmyworkreliedonKeithDecker’sGPGPsystem,AlanGarvey’sDesign-to-timescheduler.KeithneversaidnowhenIaskedforhelp.ItwasnoeasytaskgoingthroughtensofthousandsoflinesofLISPcodewrittenbysomeoneelsehaditnotbeenforhisreadinesstohelp.Keithwasthecrutchwe(allofusinthelab)leanedonwhenwecouldnotwalk.FromLatextoBabylon5,orfromcoordinationtobeer-making,wehaditallfortheasking.ThanksKeithforbeingsuchascholarandarolemodel.Alan(Bart)Garvey’shelpwiththeschedulerwasessentialtothesuccessofmyexperimentsonlearningcoordination.WhenIneededtochangesomethingorneededhishelp,hewouldalwaysdoitanddoitwithoutmuchado.Duringthelaterpartofmystay,hebecameasourceoftrustedadviseaboutlabaffairsandtechnicalmatters.IamgratefultoBartforhiscompanionship.IwouldliketothankothercurrentandformermembersoftheDAIgroupattheUniversityofMassachusetts:MaliniBhandaru,NormCarver,MikeChia,FrankKlassner,QuinLong,DorothyMammen,DanNeiman,TuomasSandholm,ToshiSugawara,ThomasWagner,andBobWhitehair,formakingourgroupsuchlivelyandexcitingplacetobe.SpecialthanksgotoDanforsufferingthroughmyinnumerabledraftsandprovidingincisivecriticismsandtoFrankforsharinghisexpertisein“gettingathesisdone”.IwouldalsoliketothankMicheleRobertsforherefficientsecretarialassistancedespitealmostalwaysbeinginundatedwithwork.IamindebtedtoKishoreSwaminathanofAndersenConsultingforhisfrankcriticismofvimypresentationstyleandfordrivinghometheimportanceofclarityofpresentationintalkingaboutideas.Eventhoughourassociationsofarhasbeenbrief,he,alongwithPaul,hashadatremendousinfluenceonmystyleofwritinginthisthesisandingeneral.FewpeopleoutsideseemtorealizehowgoodtheDepartmentofComputerScienceatUniversityofMassachusettsreallyis.IhadexposuretosomeofthefinestmindsinMulti-agentSystems,MachineLearning,Case-basedReasoning,NLP,InformationRetrieval,Planning,RoboticsandVision-allunderoneroof!!!OneofthebestdecisionsinmylifeismydecisiontomoveherefromMIT(incaseyourjawhasdropped,Ireallymeanit).ThanksgotosomeofpeerswithwhomIhavehadespeciallycloseassociationinmydepartment:TimOates(Iwouldlovetocollaboratewithyouagain),ArvindNithrakashyapandJayavelSh