LM-Cut Heuristics for Optimal Linear Numeric Planning

Abstract

While numeric variables play an important, sometimes central, role in many planning problems arising from real world scenarios, most of the currently available heuristic search planners either do not support such variables or impose heavy restrictions on them. In particular, most admissible heuristics are restricted to domains where actions can only change numeric variables by predetermined constants. In this work, we consider the setting of optimal numeric planning with linear effects, where actions can have numeric effects that assign the result of the evaluation of a linear formula. We extend a recent formulation of Numeric LM-cut for simple effects by adding conditional effects and second-order simple effects, allowing the heuristic to produce admissible estimates for tasks with linear numeric effects. Empirical comparison shows that the proposed LM-cut heuristics favorably compete with the currently available state-of-the-art heuristics and achieve significant improvement in coverage in the domains with second-order simple effects.