Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/inria-00491129
Contributor : Joerg Hoffmann Connect in order to contact the contributor
Submitted on : Friday, November 12, 2010 - 6:00:31 PM
Last modification on : Saturday, June 25, 2022 - 7:45:45 PM
Long-term archiving on: : Friday, October 26, 2012 - 3:32:00 PM

File

socs10.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨inria-00491129⟩

Share

Metrics

Record views

65

Files downloads

62