Using Learning to Improve Multi-Agent Systems for

1Ph.D.DissertationProposalUsingLearningtoImproveMulti-AgentSystemsforDesignDanL.Grecu(Ph.D.Candidate)DepartmentofComputerScienceWorcesterPolytechnicInstituteDecember10,1997Advisor:Dr.DavidC.Brown–DepartmentofComputerScience,WPICommittee:Dr.LeeA.Becker–DepartmentofComputerScience,WPIDr.StanleyM.Selkow–DepartmentofComputerScience,WPIDr.DianaGordon–AdaptiveSystemsGroup,NavyCenterforAppliedResearchinAI,Washington,DCUsingLearningtoImproveMulti-AgentSystemsforDesign2TableofContents1.Motivation31.1Whydesign?31.2Agents–anAIanswertocomplexproblems41.3Performanceofmulti-agentsystems61.4Anticipatinteverything71.5Relyingonchange91.5.1Individuallearningvs.multi-agentlearning91.5.2Onelearningprocessvs.severallearningprocesses111.6Whereliesthechallenge?122.Problemdefinition142.1Specificelementsofdesignproblem-solving142.2Thestaticanddynamicsidesofthemulti-agentsystem172.2.1Thestaticsideofthemulti-agentsystem172.2.2Thedynamicsideofthemulti-agentsystem182.3Learningwhiledesigning203.Relatedresearch233.1Researchinmulti-agentdesign233.2Researchinlearningindesign253.2.1Learningfrompreviousdesigns263.2.2Learningaboutthedesignproces273.3Multi-agentlearning294.Possibleapproachesforthemulti-agentmodels325.Proposedapproach355.1Themulti-agentarchitecture355.1.1Theagentmodel355.1.2Teamdesign375.2Thelearningframework395.2.1Thecomponentsofthelearningprocess405.2.2Thegloballearningmodel415.3Discussionoftheapproach436.Evaluation457.Implementation478.Contributions489.Schedule4910.References50UsingLearningtoImproveMulti-AgentSystemsforDesign31.MotivationAsArtificialIntelligence(AI)systemsattempttosolveproblemsthatareclosertoreallife,systemdesignersareconfrontedwiththeneedtomanageincreasingamountsofknowledgeandtocombinevariousreasoningstrategies.Designisamajorapplicationfieldthatoffersmanychallengesinthisrespect.Designprojectstypicallyincorporatecon-siderabledomainknowledgeandproblem-solvingpower.AIsystemsfordesignarelarge,complex,andverydifficulttodevelop,testandmaintain.ThesearethereasonswhyonlyfewAIsystemshavesucceededinsolvingindustrialleveldesigntasks(e.g.,R1[McDer-mott1982]).Humansoftendealwithproblemcomplexitybyorganizingteamsandcooperatinginthesearchforsolutions.Groupproblemsolvingtechniqueshaveevolvedintopowerfulstrate-giesinareaswhereanysingleindividualwouldsimplybeoverwhelmed.AIresearchhasparalleledthisapproachbydevelopingthedistributedproblem-solvingparadigm.Prob-lem-solvingsystemscandistributeamongthemtheprocessesneededtoaccomplishagiventask.Humansarealsoabletoquicklydevelopskillsallowingthemtosuccessfullycooperateandproducebetterresultsovertime.Thisevolutiontransformsagroupofpeopleintoateam.DistributedAIsystemsarestillweakinthisrespect.Machinelearninghasdevel-opedpowerfultechniquesthatallowustoimprovespecificaspectsofproblem-solving.However,wedonothavetoomuchinsightyet,astohowthesealgorithmscanbeusedortransformedtogloballyimprovedistributedproblem-solvingtasks.Inthisproposalwearguefordesignasafieldthatrequiresandoffersextensiveexperi-mentalopportunitiesforthedistributedproblem-solvingapproach.WealsodiscusshowdesignagentsystemsimplementtheAIcounterpartofhumandesignteams.Wewilllookintohowdistributeddesignsystemscansignificantlyimprovetheirperformancethroughlearning,andwewilloutlinealearningmodelthatcanmakemulti-agentdesignmoreeffi-cient.Finally,weproposeaframeworkthatwillallowustoimplement,testandevaluatetheimpactofthelearningmodelondistributeddesignproblem-solving.1.1Whydesign?TherearemanycomplexproblemdomainsthatcallforsophisticatedAIproblemsolving.WhyshouldwechoosedesignasatestinggroundforAItheories?Afirstreasonisthatdesignisaparticularlyrichexperimentalfieldforvarioustheoriesofproblem-solving.Manydesignareasareassociatedwithrichrepositoriesofdomainknowledgeandproblem-solvingexperience.ThesecollectionsrepresentagoodbasisforsettingupautomateddesignsystemsthatcanimplementandtestAItechniques.Second,itishardlynecessarytostressthepotentialutilityofdesignsystemsthatcantakeovertheburdenoftediousandslowtasksfromtheshouldersofthedesigners.Thesuccessofsystemsthatonlyassistdesigners(computer-aideddesignsystems)isasolidargumentfortheextenttowhichautomatedhelpisneededindesign.UsingLearningtoImproveMulti-AgentSystemsforDesign4TheavailabilityofinformationandthefinalutilityoftheproductarenottheonlyreasonsforbringingtogetherAIanddesign.TherearealsospecificfeaturesofthedesigndomainthatmakethefieldparticularlyappealingtoAIresearchingeneral,andtodistributedproblem-solvinginparticular.Oneneedlooknofurtherthantheintroductorypartofanyclassicaldesigntextbooktofindstatementsaboutdesignsuchas:...designingisacreativeactivitythatcallsforasoundgroundinginmathematics,physics,chemistry,mechanics,thermodynamics,hydrodynamics,electricalengineer-ing,productionengineering,materialstechnologyanddesigntheory,togetherwithpracticalknowledgeandexperienceinspecialistfields.(Pahl&Beitz1988,pp.1-2)andIt[designing]callsforclosecollaborationwithworkersinmayotherspheres.Thus,tocollectalltheinformationheneeds,thedesignermustestablishcloselinkswithsales-men,buyers,costaccountants,estimator