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

Authors

  • Maximilian Fickert Saarland University

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 hCFF 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.

Downloads

Published

2020-06-01

How to Cite

Fickert, M. (2020). A Novel Lookahead Strategy for Delete Relaxation Heuristics in Greedy Best-First Search. Proceedings of the International Conference on Automated Planning and Scheduling, 30(1), 119-123. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/6652