Local Search for Planning and Scheduling: ECAI 2000 Workshop, Berlin, Germany, August 21, 2000. Revised Papers

ISBN-13: 9783540428985 / Angielski / Miękka / 2001 / 176 str.

Alexander Nareyek

Opis

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 aninvitedcontributionbyStefanVoss givesan overviewofthesemethods. ThebookisbasedonthecontributionstotheWorkshoponLocalSearchfor Planning&Scheduling, heldonAugust21,2000atthe14thEuropeanCon- renceonArti?cialIntelligence(ECAI2000)inBerlin, Germany. Theworkshop broughttogetherresearchersfromtheplanningandschedulingcommunitiesto explorethesetopicswithrespecttolocalsearchprocedures. Aftertheworkshop, asecondreviewprocessresultedinthecontributionstothepresentvolume. Voss 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 JoseLuisAmbite Univ. ofSouthernCalifornia BlaiBonet UniversityofCalifornia RonenI. Brafman Ben-GurionUniversity SteveChien NASAJPL AndrewDavenport IBMT. J. Watson AlfonsoGerevini UniversitadiBrescia HolgerH. Hoos Univ. ofBritishColumbia AlexanderNareyek GMDFIRST AngeloOddi IP-CNR Mar?aC. Ri? Univ. Tec. Fed. SantaMar?a BartSelman CornellUniversity EdwardTsang UniversityofEssex TableofContents InvitedPaper Meta-heuristics: TheStateoftheArt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 StefanVoss 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 StefanVoss TechnischeUniversit]atBraunschweig Institutfur ] Wirtschaftswissenschaften Abt-Jerusalem-Strasse7 D-38106Braunschweig, Germany stefan. voss@tu-bs. de Abstract."

Spis treści

Invited Paper.- Meta-heuristics: The State of the Art.- Combinatorial Optimization.- Solving the Sports League Scheduling Problem with Tabu Search.- Lagrange Multipliers for Local Search on Planning Graphs.- Planning with Resources.- Beyond the Plan-Length Criterion.- An Empirical Evaluation of the Effectiveness of Local Search for Replanning.- Board-Laying Techniques Improve Local Search in Mixed Planning and Scheduling.- Empirical Evaluation of Local Search Methods for Adapting Planning Policies in a Stochastic Environment.- Related Approaches.- The GRT Planner: New Results.- Incremental Local Search for Planning Problems.- Map Drawing Based on a Resource-Constrained Search for a Navigation System.