Improving Local Search for Resource-Constrained Planning
Mueller, Martin, Jöerg Hoffmann, Hootan Nakhost · 2010
A ubiquitous feature of planning problems – problems involv-ing the automatic generation of action sequences for attain-ing 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 crit-ically resource-constrained problems is limited: current plan-ning 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 in-stead. Local search has received some attention in planning, but not with a specific focus on how to deal with limited re-sources. We herein begin to fill this gap. We highlight the limitations of previous methods, and we devise a new im-provement (smart restarts) to the local search method of a previously proposed planner (Arvand). Systematic experi-ments 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.