Cost-Sharing Approximations for h~+

摘要

Relaxations based on (either complete or partial) ignoring delete effects of the actions provide the basis for some seminal classical planning heuristics. However, the palette of the conceptual tools exploited by these heuristics remains rather limited. We study a framework for approximating the optimal cost solutions for problems with no delete effects that bridges between certain works on heuristic search for probabilistic reasoning and classical planning. In particular, this framework generalizes some previously known, as well as suggests some novel, tools for heuristic estimates for Strips planning.