Heuristics and metaheuristics in forward-chaining planning
Andrew J. Coles · OpenGrey (Institut de l'Information Scientifique et Technique) · 2007
Forward-chaining heuristic search is a well-established and popular paradigm for planning. It is, however, characterised by two key weaknesses. First, search is guided by a domain-independent heuristic which although applicable in a wide range of domains, can often give poor guidance. Second, the metaheuristics used to control forward-chaining planning are often weak, using simple local-search or exhaustive-search algorithms. This thesis contributes work to address both of these issues. To improve the quality of the domain-independent heuristic used, the ‘generic type’ information provided by an existing static analysis tool is used to provide the basis to address known weaknesses in the heuristic concerning the behaviour of recognised generic types. To improve search control, a local-search algorithm based on hill-climbing search is introduced, making use of restarts and a powerful neighbourhood function. This local-search planning algorithm is then used within a multi-point constructive search framework. These two approaches are used to produce two planners, based on Marvin— an existing forward-chaining heuristic-search planner. Results presented indicate that the two approaches are able to improve the performance of the planner. The local-search planner is able to provide better performance across a range of domains; and the use of multi-point constructive search is able to improve the performance of the local-search planner further in some domains. The planner making use of the generic type information is able to provide better performance in domains in which the known generic types can be recognised, having addressed known weaknesses of the heuristic.