Thenextsetofarticlesdealwithplanningsystemsthatareabletoinc- porateresourcereasoning. The?rstarticle,ofwhichIamtheauthor,makesit clearwhyconventionalplanningsystemscannotproperlyhandleplanningwith resourcesandgivesanoverviewoftheconstraint-basedExcaliburagent'spl- ningsystem,whichdoesnothavetheserestrictions. Thenextthreearticlesare aboutNASAJPL'sASPEN/CASPERsystem. The?rstone-byChien,Knight, andRabideau-focusesonthereplanningcapabilitiesoflocalsearchmethods, presentingtwoempiricalstudiesinwhichacontinuousplanningprocessclearly outperformsarestartstrategy. Thenextarticle,byEngelhardtandChien,shows howlearningcanbeusedtospeedupthesearchforaplan. Thegoalisto?nda setofsearchheuristicsthatguidethesearchaswellaspossible. Thelastarticle inthisblock-byKnight,Rabideau,andChien-proposesanddemonstrates, a technique for aggregating single search moves so that distant states can be reachedmoreeasily. VI Preface Thelastthreearticlesinthisbookaddresstopicsthatarenotdirectlyrelated tolocalsearch,butthedescribedmethodsmakeverylocaldecisionsduringthe search. RefanidisandVlahavasdescribeextensionstotheGRTplanner,e. g. ,a hill-climbingstrategyforactionselection. Theextensionsresultinmuchbetter performancethanwiththeoriginalGRTplanner. Thesecondarticle-byO- india, Sebastia, and Marzal - presents a planning algorithm that successively re?nes a start graph by di?erent phases, e. g., a phase to guarantee comp- teness. Inthelastarticle,HiraishiandMizoguchipresentasearchmethodfor constructingaroutemap. Constraintswithrespecttomemoryandtimecanbe incorporatedintothesearchprocess. Iwishtoexpressmygratitudetothemembersoftheprogramcommittee, whoactedasreviewersfortheworkshopandthisvolume. Iwouldalsoliketo thank all those who helped to make this workshop a success - including, of course,theparticipantsandtheauthorsofpapersinthisvolume. June2001 AlexanderNareyek WorkshopChair ProgramCommittee EmileH. L. Aarts PhilipsResearch Jos´eLuisAmbite Univ. ofSouthernCalifornia BlaiBonet UniversityofCalifornia RonenI. Brafman Ben-GurionUniversity SteveChien NASAJPL AndrewDavenport IBMT. J. Watson AlfonsoGerevini Universit`adiBrescia HolgerH. Hoos Univ. ofBritishColumbia AlexanderNareyek GMDFIRST AngeloOddi IP-CNR Mar´?aC. Ri? Univ. T´ec. Fed. SantaMar´?a BartSelman CornellUniversity EdwardTsang UniversityofEssex TableofContents InvitedPaper Meta-heuristics:TheStateoftheArt. 1 StefanVoß CombinatorialOptimization SolvingtheSportsLeagueSchedulingProblemwithTabuSearch. 24 Jean-PhilippeHamiez,Jin-KaoHao LagrangeMultipliersforLocalSearchonPlanningGraphs. 37 AlfonsoGerevini,IvanSerina PlanningwithResources BeyondthePlan-LengthCriterion. 55 AlexanderNareyek AnEmpiricalEvaluationoftheE?ectiveness ofLocalSearchforReplanning. 79 SteveChien,RussellKnight,GreggRabideau Board-LayingTechniquesImproveLocalSearch inMixedPlanningandScheduling. 95 RussellKnight,GreggRabideau,SteveChien EmpiricalEvaluationofLocalSearchMethods forAdaptingPlanningPoliciesinaStochasticEnvironment. 108 BarbaraEngelhardt,SteveChien RelatedApproaches TheGRTPlanner:NewResults. 120 IoannisRefanidis,IoannisVlahavas IncrementalLocalSearchforPlanningProblems. 139 EvaOnaindia,LauraSebastia,EliseoMarzal MapDrawingBasedonaResource-ConstrainedSearch foraNavigationSystem. 158 HironoriHiraishi,FumioMizoguchi AuthorIndex. 171 Meta-heuristics:TheStateoftheArt StefanVoß TechnischeUniversit¨a

Hersteller:
Springer Verlag GmbH
juergen.hartmann@springer.com
Tiergartenstr. 17
DE 69121 Heidelberg