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

Maximilian Fickert

PosterID: 54 PDF Slides Poster BibTeX

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.

Session E10: Heuristic Search Planning
Canb 10/28/2020, 21:00 – 21:45
10/30/2020, 04:00 – 04:45
Paris 10/28/2020, 11:00 – 11:45
10/29/2020, 18:00 – 18:45
NYC 10/28/2020, 06:00 – 06:45
10/29/2020, 13:00 – 13:45
LA 10/28/2020, 03:00 – 03:45
10/29/2020, 10:00 – 10:45