ICAPS Conference 2008 Conference Paper
- Malte Helmert
- Hector Geffner
simpler and more general. The new heuristic reduces to Helmert’s heuristic when the causal graph is acyclic, but requires neither acyclicity nor the causal graph itself. Like the additive heuristic, the new heuristic is defined mathematically by means of a functional equation, which translates into a shortest-path problem over a poly-size graph that can be solved by standard algorithms. Indeed, the only difference between this account of the causal graph heuristic and the normal additive heuristic is that the nodes in this graph, which stand for the atoms in the problem, are labeled with contextual information. The new formulation of the causal graph heuristic suggests a number of extensions, all of which have to do with the exploitation of implicit or explicit precedences among an operator’s preconditions in order to capture side effects in the computation of the heuristic. Even without such extensions, we experimentally show that the new heuristic delivers considerably better heuristic guidance than both the causal graph heuristic and additive heuristic across a large suite of standard benchmarks. 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 approximating 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 depends on directly. Superficially, the causal graph heuristic appears quite unrelated to heuristics based on delete relaxation. In this contribution, we show that the opposite is true. Using a novel, declarative formulation of the causal graph heuristic, we show that the causal graph heuristic is the additive heuristic plus context. 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 additive 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 outperforms them across a wide range of standard benchmarks. Multi-valued Planning Tasks The causal graph heuristic is defined over a planning language with multi-valued variables based on the SAS+ language (Bäckström and Nebel 1995), where the basic atoms are of the form v = d where v is a variable and d ∈ Dv is a value in v’s domain Dv. Formally, a multi-valued planning task (MPT) is a tuple Π = hV, s0, s⋆, Oi where V is a set of variables v with associated finite discrete domains Dv, s0 is a state over V characterizing the initial situation, s⋆ is a partial state over V characterizing goal situations, and O is a set of operators that map one state into a possibly different state. A state is a function s that maps each variable v ∈ V into a value s(v) in Dv. A partial state s′ is a state restricted to a subset V ′ ⊆ V of variables. We write dom(s′) for the subset of variables on which s′ is defined. As it is common in the Boolean setting, we often represent and treat such functions as the set of atoms v = d that they make true. For an atom x, we write var(x) for the variable associated with x. For example, if x is the atom v = d, then var(x) = v. Given a state s and an atom v = d, s[v = d] denotes the state that is like s except for variable v, which it maps to d. We will also use similar notations like s[s′ ] where s′ is a partial state, to denote the state that is like s except for the