YAHSP

YAHSP (which stands for “Yet Another Heuristic Search Planner”) is a planning system for non-optimal STRIPS planning. It is based on recent ideas from the planning as heuristic search framework, initiated by the planners ASP and HSP from Blai Bonet and Hector Geffner.

The heuristic is computed in a way very similar to Jörg Hoffmann’s FF planner, but used in different ways. We introduce a novel way for extracting information from the computation of the heuristic and for tackling with helpful actions, by considering the high quality of the plans computed by the heuristic function in numerous domains. For each evaluated state, we employ actions from these plans in order to find the beginning of a valid plan that can lead to a reachable state, that will often bring us closer to a solution state. The lookahead state thus calculated is then added to the list of nodes that can be chosen to be developed following the numerical value of the heuristic. We use this lookahead strategy in a complete best-first search algorithm, modified in order to take into account helpful actions by preferring nodes that can be developed with such actions over nodes that can be developed with actions not considered as helpful.

We provide below an empirical evaluation which demonstrates that in numerous planning benchmark domains, the performance of heuristic search planning and the size of the problems that can be handled have been drastically improved, while in more “difficult” domains these strategies remain interesting even if they sometimes degrade plan quality.