Overview
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 - in
- | Author: Alexander Nareyek
- | Publisher: Springer
- | Publication Date: Nov 07, 2001
- | Number of Pages: 176 pages
- | Binding: Paperback or Softback
- | ISBN-10: 3540428984
- | ISBN-13: 9783540428985
