Explicit Conjunctions without Compilation: Computing hFF(PiC) in Polynomial Time

Abstract

A successful partial delete relaxation method is to compute h^FF in a compiled planning task PiC which represents a set C of conjunctions explicitly. While this compilation view of such partial delete relaxation is simple and elegant, its meaning with respect to the original planning task is opaque. We provide a direct characterization of h⁺(Pi^C), without compilation, making explicit how it arises from a "marriage" of the critical-path heuristic h^m with (a somewhat novel view of) h⁺. This explicit view allows us to derive a direct characterization of h^FF(Pi^C), which in turn allows us to compute a version of that heuristic function in time polynomial in |C|.