In order to extract domain-independent heuristics from the specification of a planning problem; it is necessary to relax the given problem and then solve the relaxed one. In this paper; we present a new planning graph; Merged Planning Graph(MPG), and GD heuristics for solving contingent planning problems including both uncertainty about the initial state and non-deterministic action effects. MPG is a new version of the relaxed planning graph for solving the contingent planning problems, In addition to the traditional delete relaxations of deterministic actions, MPG makes the effect-merge relaxations of both sensing and non-deterministic actions. Parallel to the forward expansion of MPG, the computation of GD heuristics proceeds with analysis of interactions among goals and/or subgoals. OD heuristics estimate the minimal reachability cost to achieve the given goal set by excluding redundant action costs. Through experiments in several problem domains, we show that GD heuristics are more informative than the traditional max and additive heuristics. Moreover, in comparison to the overlap heuristics, GD heuristics require much less computational effort for extraction.
