LM-cut and Operator Counting Heuristics for Optimal Numeric Planning with Simple Conditions
Citations Over TimeTop 16% of 2021 papers
Abstract
We consider optimal numeric planning with numeric conditions consisting of linear expressions of numeric state variables and actions that increase or decrease numeric state variables by constant quantities. We build on previous research to introduce a new variant of the numeric hmax heuristic based on the delete-relaxed version of such planning tasks. Although our hmax heuristic is inadmissible, it yields a numeric version of the classical LM-cut heuristic which is admissible. Further, we prove that our LM-cut heuristic neither dominates nor is dominated by the existing numeric heuristic hmax(hbd). We show that admissibility also holds when integrating the numeric cuts into the operator-counting (OC) heuristic producing an admissible numeric version of the OC heuristic. Through experiments, we demonstrate that both these heuristics compete favorably with the state-of-the-art heuristics: in particular, while sometimes expanding more nodes than other heuristics, numeric OC solves 19 more problem instances than the next closest heuristic.
Related Papers
- → Admissible heuristic search in and/or graphs(1983)33 cited
- Learning heuristic functions through approximate linear programming(2008)
- → Study on Dual Bi-Directional Heuristic Development Framework(2021)1 cited
- A study of the accuracy of heuristic functions(2004)
- Choice of Heuristic Function and Analysis of Heuristic Power in Intelligent Search(2007)