Unifying the causal graph and additive heuristics

Many current heuristics for domain-independent planning, such as Bonet and Geffner’s additive heuristic and Hoffmann and Nebel’s FF heuristic, are based on delete relaxations. They estimate the goal distance of a search state by approx-imating the solution cost in a relaxed task where negative consequences of operator applications are ignored. Helmert’s causal graph heuristic, on the other hand, approximates goal distances by solving a hierarchy of “local ” planning problems that only involve a single state variable and the variables it de-pends on directly. Superficially, the causal graph heuristic appears quite unre-lated to heuristics based on delete relaxation. In this contribu-tion, we show that the opposite is true. Using a novel, declar-ative formulation of the causal graph heuristic, we show that the causal graph heuristic is the additive heuristic plus con-text. Unlike the original heuristic, our formulation does not require the causal graph to be acyclic, and thus leads to a proper generalization of both the causal graph and addi-tive heuristics. Empirical results show that the new heuristic is significantly better informed than both Helmert’s original causal graph heuristic and the additive heuristic and outper-forms them across a wide range of standard benchmarks