A Novel Lookahead Strategy for Delete Relaxation Heuristics in Greedy Best-First Search

Abstract

Best-first width search (BFWS) is a recent approach to satisficing planning that combines traditional heuristics with novelty measures to achieve a balance between exploration and effective search guidance (exploitation). One such novelty measure is based on counting the number of subgoals achieved on the path from a state in which a relaxed plan was computed. We introduce a new lookahead strategy for greedy best-first search based on this idea, where after each expansion, a bounded lookahead search is guided by relaxed subgoal counting. Furthermore, we combine this technique with partial delete relaxation heuristics to improve the subgoals. Using the h^CFF heuristic with online-refinement of conjunctions, we obtain a planner that significantly outperforms the state of the art in satisficing planning on the IPC benchmarks.