Improving Local Search for Resource-Constrained Planning

Hootan Nakhost 1 Joerg Hoffmann 2 Martin Müller 1
2 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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.
Type de document :
Communication dans un congrès
3rd Annual Symposium on Combinatorial Search (SOCS'10), Jul 2010, Atlanta, United States. 2010
Liste complète des métadonnées

Littérature citée [4 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00491129
Contributeur : Joerg Hoffmann <>
Soumis le : vendredi 12 novembre 2010 - 18:00:31
Dernière modification le : jeudi 11 janvier 2018 - 06:19:51
Document(s) archivé(s) le : vendredi 26 octobre 2012 - 15:32:00

Fichier

socs10.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00491129, version 1

Collections

Citation

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. 2010. 〈inria-00491129〉

Partager

Métriques

Consultations de la notice

171

Téléchargements de fichiers

101