A Lookahead Strategy for Heuristic Search Planning

Relaxed plans are used in the heuristic search planner FF for computing a numerical heuristic and extracting helpful actions. We present a novel way for extracting information from the relaxed plan and for dealing with helpful actions, by considering the high quality of the relaxed plans in numerous domains. For each evalu-ated state, we employ actions from these plans in order to nd the beginning of a valid plan that can lead to a reachable state. We use this lookahead strategy in a complete best-rst search algorithm, modied in order to take into account helpful actions. In numerous plan-ning domains, the performance of heuristic search plan-ning and the size of the problems that can be handled have been drastically improved