Unified Definition of Heuristics for Classical Planning

Abstract. In many types of planning algorithms distance heuristics play an important role. Most of the earlier works restrict to STRIPS operators, and their application to a more general language with disjunctivity and conditional effects first requires an exponential size reduction to STRIPS operators. I present direct formalizations of a number of distance heuristics for a general operator description language in a uniform way, avoiding the exponentiality inherent in earlier reductive approaches. The formalizations use formulae to represent the conditions under which operators have given effects. The exponentiality shows up in satisfiability tests with these formulae, but would appear to be a minor issue because of the small size of the formulae.