Improving Local Search for Resource-Constrained Planning - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2010

Improving Local Search for Resource-Constrained Planning

Joerg Hoffmann
  • Function : Author
  • PersonId : 864556

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.
Fichier principal
Vignette du fichier
socs10.pdf (109.54 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

  • HAL Id : inria-00491129 , version 1

Cite

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⟩
70 View
77 Download

Share

Gmail Facebook X LinkedIn More