LM-cut and Operator Counting Heuristics for Optimal Numeric Planning with Simple Conditions

Authors

  • Ryo Kuroiwa University of Toronto
  • Alexander Shleyfman University of Toronto
  • Chiara Piacentini University of Toronto
  • Margarita P. Castro University of Toronto
  • J. Christopher Beck University of Toronto

DOI:

https://doi.org/10.1609/icaps.v31i1.15964

Keywords:

Continuous State And Action Spaces Based Planning

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.

Downloads

Published

2021-05-17

How to Cite

Kuroiwa, R., Shleyfman, A., Piacentini, C., Castro, M. P., & Beck, J. C. (2021). LM-cut and Operator Counting Heuristics for Optimal Numeric Planning with Simple Conditions. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 210-218. https://doi.org/10.1609/icaps.v31i1.15964