A new local-search algorithm for forward-chaining planning
Andrew J. Coles, Maria Fox, Amanda J. Smith · 2007
Forward-chaining heuristic search is a well-established and popular paradigm for domain-independent planning. Its ef-fectiveness relies on the heuristic information provided by a state evaluator, and the search algorithm used with this in or-der to solve the problem. This paper presents a new stochastic local-search algorithm for forward-chaining planning. The algorithm is used as the basis of a planner in conjunction with FF’s Relaxed Planning Graph heuristic. Our approach is unique in that localised restarts are used, returning to the start of plateaux and saddle points, as well as global restarts to the initial state. The majority of the search time when us-ing FF’s ‘Enforced Hill Climbing ’ is spent using breadth-first search to escape local minima. Our localised restarts, in con-junction with stochastic search, serve to replace this expen-sive breadth-first search step. We also describe an extended search neighbourhood incorporating non-helpful actions and the ‘lookahead ’ states used in YAHSP. Making use of non-helpful actions and stochastic search allows us to restart the local-search from the initial state when dead-ends are encoun-tered; rather than resorting to best-first search. We present analyses to demonstrate the effectiveness of our restart strate-gies, along with results that show the new planning algorithm is effective across a range of domains.