h m ( P ) = h 1 ( P m ): Alternative Characterisations of the Generalisation From h max To h m

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 1 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.