Local search for planning and scheduling : ECAI 2000 Workshop, Berlin, Germany, August 21, 2000 : revised papers
著者
書誌事項
Local search for planning and scheduling : ECAI 2000 Workshop, Berlin, Germany, August 21, 2000 : revised papers
（Lecture notes in computer science, 2148 . Lecture notes in artificial intelligence）
Springer, c2001
大学図書館所蔵 件 / 全31件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
注記
Includes bibliographical references and index
Based on the contributions to the Workshop on Local Search for Planning & Scheduling, held during ECAI 2000
内容説明・目次
内容説明
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 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 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 ...9
5 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.
目次
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.
「Nielsen BookData」 より