Artificial Intelligence search algorithms search discrete systems. To apply such algorithms to continuous systems, such systems must first be discretized, i.e. approximated as discrete systems. Action-based discretization requires that both action paramete
Iterative-Re nementforActionTimingDiscretization
DepartmentofComputerScience
GettysburgCollegeGettysburg,PA17325,USAtneller@gettysburg.edu
…… 此处隐藏0字 ……
ToddW.Neller
Abstract
Arti cialIntelligencesearchalgorithmssearchdiscretesys-tems.Toapplysuchalgorithmstocontinuoussystems,suchsystemsmust rstbediscretized,i.e.approximatedasdis-cretesystems.Action-baseddiscretizationrequiresthatbothactionparametersandactiontimingbediscretized.Wefocusontheproblemofactiontimingdiscretization.
Afterdescribingan-admissiblevariantofKorf’srecursivebest- rstsearch(-RBFS),weintroduceiterative-re nement-admissiblerecursivebest- rstsearch(IR-RBFS)whichofferssigni ckofknowledgeofagoodtimediscretizationiscompensatedforbyknowledgeofasuitablesolutioncostupperbound.
Introduction
Arti cialIntelligencesearchalgorithmssearchdiscretesys-tems,yetweliveandreasoninacontinuousworld.Con-tinuoussystemsmust rstbediscretized,i.e.approximatedasdiscretesystems,toapplysuchalgorithms.Therearetwocommonwaysthatcontinuoussearchproblemsaredis-cretized:state-baseddiscretizationandaction-baseddis-cretization.State-baseddiscretization(Latombe1991)be-comesinfeasiblewhenthestatespaceishighlydimensional.Action-baseddiscretizationbecomesinfeasiblewhentherearetoomanydegreesoffreedom.Interestingly,biologi-calhigh-degree-of-freedomsystemsareoftengovernedbyamuchsmallercollectionofmotorprimitives(Mataric2000).Wefocushereonaction-baseddiscretization.
Action-baseddiscretizationconsistsoftwoparts:(1)actionparameterdiscretizationand(2)actiontimingdis-cretization,i.e.howandwhentoact.SeeFigure1.Forex-ample,considerrobotsoccer.Searchcanonlysampleactionparametercontinuasuchaskickforceandangle.Similarly,searchcanonlysamplein nitepossibleactiontimingssuchaswhentokick.Themostpopularformofdiscretizationisuniformdiscretization.Itiscommontosamplepossibleactionsandactiontimingsat xedintervals.
Inthispaper,wefocusonactiontimingdiscretization.Experimentalevidenceofthispaperandpreviousstud-ies(Neller2000)suggeststhata xeduniformdiscretiza-tionoftimeisnotadvisableforsearchifonehasadesired