Local Search for Planning and Scheduling

indgår i serie Lecture Notes in Computer Science


Studiebog
Local Search for Planning and Scheduling
Du sparer Spar kr. 40,00 med Shopping-fordele
  • Leveringstid 5-8 hverdage
  • Forventet levering 28-04-2021
For at købe bogen til fordelspris skal du have et medlemskab med Shopping-fordele. Du kan prøve medlemskabet gratis de første 30 dage. Medlemskabet fornyes automatisk og kan altid opsiges. Læs mere om medlemskaber og Shopping-fordele her.
Format:
Bog, paperback
Udgivelsesdato:
01-11-2001
Sprog:
Engelsk
Udgave:
2001 ed..
  • Beskrivelse
  • Yderligere info
  • Anmeldelser

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 ...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.

Vis mereVis mindre

Udgivelsesdato:
01-11-2001
ISBN13:
9783540428985
Vægt:
320 g
Dybde:
10 mm
Bredde:
155 mm
Højde:
235 mm
Nummer i serien:
2148
Format:
Paperback
Forfattere

    Vis mereVis mindre

    Vis mereVis mindre

    Fandt du ikke hvad du søgte?

    Hvis denne bog ikke er noget for dig, kan du benytte kategorierne nedenfor til at finde andre titler. Klik på en kategori for at se lignende bøger.

    Velkommen til Saxo – din danske boghandel!

    Hos os kan du handle som gæst, Saxo-bruger eller Premium-medlem – du bestemmer helt selv. Skulle du få brug for hjælp, sidder vores kundeservice-team klar ved både telefonerne og tasterne.

    Om fordelspriser hos Saxo

    For at købe bøger til fordelspris, skal du være medlem af Premium, Premium Shopping eller Premium Studie. De første 30 dage er gratis for nye medlemmer. Medlemskabet fornyes automatisk og kan altid opsiges. Læs mere om fordelene ved vores forskellige medlemskaber her.

    Machine Name: SAXO082