A New Local-Search Algorithm for Forward-Chaining Planning

A New Local-Search Algorithm for Forward-Chaining Planning,Andrew Coles,Maria Fox,Amanda Smith

A New Local-Search Algorithm for Forward-Chaining Planning   (Citations: 2)
BibTex | RIS | RefWorks Download
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. a comprehensible forward-chaining approach to planning. This has lead to it being used as the basis for a large number of modern planning systems (MIPS-XXL (Edelkamp, Jab- bar, & Nazih 2006), Marvin (Coles & Smith 2007), Macro- FF (Botea, M¨ uller, & Schaeffer 2005)) and for the evaluation of many new ideas in planning. LPG, however, uses a more complex search paradigm, which is more difficult to build upon but does make use of more sophisticated local search techniques, thus avoiding the large amount of time spent do- ing exhaustive search in planning using FF. In this paper we present a new local search algorithm for forward-chaining planning. This algorithm combines the strengths of FF and LPG: the intuitive and efficient forward- chaining search paradigm, and powerful heuristic of FF; and the principle of using stochastic local-search with restarts from LPG, avoiding the necessity to resort to exhaustive search.The stochastic local-search used in this work differs from that in LPG, both in its application to forward-chaining search and the local-search techniques themselves. The aim is to produce a flexible framework for local- search forward-chaining planning, demonstrating how ad- ditional local search techniques can be applied and push- ing the boundaries of current forward-chaining planners. To augment the proposed forward-chaining planning algorithm, we present a novel neighbourhood for use with it, based on applying neighbourhood sampling techniques to the appli- cable actions. The algorithms described are used as the ba- sis for a planner, 'Identidem'. We present empirical results to show that the algorithms proposed are effective across a range of domains, and how the performance of Identidem is influenced by the use of restarts. In the next section, an overview of the area of forward- chaining planning on which this work builds is presented. This is followed by details of the kernel of the new local- search algorithm for forward-chaining planning, and how it can be used to escape local minima. Having described this, the neighbourhood used for search with this algorithm is de- fined, followed by details of how fail-bounded restarts can be incorporated into search. Results are then presented indi- cating the performance of Identidem in a range of domains, and the effect of restarts on search performance. Finally, some concluding remarks are made and potential directions for future work are given.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...3.3 Successor Selection and Filters This practical continues the line of exploring the use of hill-climbing techniques in forward-chaining planning, following the ideas of the planner IDENTIDEM (Coles, Fox, & Smith 2007)...

    Andrew Coleset al. Teaching Forward-Chaining Planning with JAVAFF

Sort by: