Local search for planning and scheduling

Withtheincreasingdeploymentofplanningandschedulingsystems,developers oftenhavetodealwithverylargesearchspaces,real-timeperformancedemands, anddynamicenvironments. Completere?nementmethodsdonotscalewell,- kinglocalsearchmethodstheonlypracticalalternative. Adynamicenvironment alsopromotestheapplicationoflocalsearch,thesearchheuristicsnotnormally beinga?ectedbymodi?cationsofthesearchspace. Furthermore,localsearchis wellsuitedforanytimerequirementsbecausetheoptimizationgoalisimproved iteratively. Suchadvantagesareo?setbytheincompletenessofmostlocalsearch methods,whichmakesitimpossibletoprovetheinconsistencyoroptimalityof thesolutionsgenerated. Popularlocalsearchapproachesincludeevolutionary- gorithms,simulatedannealing,tabusearch,min-con?icts,GSAT,andWalksat. The?rstarticleinthisbook–aninvitedcontributionbyStefanVoß–givesan overviewofthesemethods.^ ThebookisbasedonthecontributionstotheWorkshoponLocalSearchfor Planning&Scheduling,heldonAugust21,2000atthe14thEuropeanCon- renceonArti?cialIntelligence(ECAI2000)inBerlin,Germany. Theworkshop broughttogetherresearchersfromtheplanningandschedulingcommunitiesto explorethesetopicswithrespecttolocalsearchprocedures. Aftertheworkshop, asecondreviewprocessresultedinthecontributionstothepresentvolume. Voß’soverviewisfollowedbytwoarticles,byHamiezandHaoandGerevini andSerina,onspeci?c“classical”combinatorialsearchproblems. Thearticleby HamiezandHaoaddressestheproblemofsports-leaguescheduling,presenting results achieved by a tabu search method based on a neighborhood of value swaps. GereviniandSerina’sarticleaddressesthetopicthatdominatestherest ofthebook:actionplanning. Itbuildsontheirpreviousworkonlocalsearch onplanninggraphs,presentinganewsearchguidanceheuristicwithdynamic parametertuning. 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¨atBraunschweig Institutfur ¨ Wirtschaftswissenschaften Abt-Jerusalem-Straße7 D-38106Braunschweig,Germany stefan. voss@tu-bs. de Abstract.