Analyzing Search Topology Without Running Any Search: On the Connection
  Between Causal Graphs and h+
  The ignoring delete lists relaxation is of paramount importance for both
satisficing and optimal planning. In earlier work, it was observed that the
optimal relaxation heuristic h+ has amazing qualities in many classical
planning benchmarks, in particular pertaining to the complete absence of local
minima. The proofs of this are hand-made, raising the question whether such
proofs can be lead automatically by domain analysis techniques. In contrast to
earlier disappointing results -- the analysis method has exponential runtime
and succeeds only in two extremely simple benchmark domains -- we herein answer
this question in the affirmative. We establish connections between causal graph
structure and h+ topology. This results in low-order polynomial time analysis
methods, implemented in a tool we call TorchLight. Of the 12 domains where the
absence of local minima has been proved, TorchLight gives strong success
guarantees in 8 domains. Empirically, its analysis exhibits strong performance
in a further 2 of these domains, plus in 4 more domains where local minima may
exist but are rare. In this way, TorchLight can distinguish easy domains from
hard ones. By summarizing structural reasons for analysis failure, TorchLight
also provides diagnostic output indicating domain aspects that may cause local
minima.
