hm(P) = h1(Pm): Alternative Characterisations of the Generalisation From hmax To hm

Abstract

The h^m (m = 1 ...) family of admissible heuristics for STRIPS planning with additive costs generalise the h^max heuristic, which results when m = 1. We show that the step from h¹ to h^m can be made by changing the planning problem instead of the heuristic function. This furthers our understanding of the h^m heuristic, and may inspire application of the same generalisation to admissible heuristics stronger than h^max. As an example, we show how it applies to the additive variant of h^m obtained via cost splitting.