Improving Local Search for Resource-Constrained Planning - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

Improving Local Search for Resource-Constrained Planning

Joerg Hoffmann
  • Fonction : Auteur
  • PersonId : 864556

Résumé

A ubiquitous feature of planning problems -- problems involving the automatic generation of action sequences for attaining a given goal -- is the need to economize limited resources such as fuel or money. While heuristic search, mostly based on standard algorithms such as A*, is currently the superior method for most varieties of planning, its ability to solve critically resource-constrained problems is limited: current planning heuristics are bad at dealing with this kind of structure. To address this, one can try to devise better heuristics. An alternative approach is to change the nature of the search instead. Local search has received some attention in planning, but not with a specific focus on how to deal with limited resources. We herein begin to fill this gap. We highlight the limitations of previous methods, and we devise a new improvement (smart restarts) to the local search method of a previously proposed planner (Arvand). Systematic experiments show how performance depends on problem structure and search parameters. In particular, we show that our new method can outperform previous planners by a large margin.
Fichier principal
Vignette du fichier
socs10.pdf (109.54 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00491129 , version 1 (12-11-2010)

Identifiants

  • HAL Id : inria-00491129 , version 1

Citer

Hootan Nakhost, Joerg Hoffmann, Martin Müller. Improving Local Search for Resource-Constrained Planning. 3rd Annual Symposium on Combinatorial Search (SOCS'10), Jul 2010, Atlanta, United States. ⟨inria-00491129⟩
69 Consultations
75 Téléchargements

Partager

Gmail Facebook X LinkedIn More