Heuristics for Planning with Penalties and Rewards Using Compiled Knowledge

The automatic derivation of heuristic functions for guiding the search for plans in large spaces is a fundamental technique in planning. The type of heuristics that have been considered so far, however, deal only with simple planning models where costs are associated with actions but not with states. In this work we address this limitation by formulating a more ex-pressive planning model and a corresponding heuristic where preferences in the form of penalties and rewards are associ-ated with fluents as well. The heuristic, that is a generaliza-tion of the well-known delete-relaxation heuristic proposed in classical planning, is admissible, informative, but intractable. Exploiting however a correspondence between heuristics and preferred models, and a property of formulas compiled in d-DNNF, we show that if a suitable relaxation of the theory is compiled into d-DNNF, the heuristic can be computed for any search state in time that is linear in the size of the compiled representation. While this representation may have exponen-tial size, as for OBDDs, this is not necessarily so. We report preliminary empirical results, discuss the application of the framework in settings where there are no goals but just pref-erences, and assess further variations and challenges