Dependency detection is syntactic and requires little knowledge of the planner or its environment; thus, it can be applied to any planner in any environment. To begin, we gather execution traces of the planner. To determine how the planner's actions might lead to failure, the execution traces include failures and the recovery actions that repaired them, as in the following short trace:
F's are failures (e.g., 
is the
Insufficient Progress failure in Phoenix) and R's are recovery
actions (e.g., 
is the Substitute Projection action in the
Phoenix Planner's recovery action set). It appears from this short
trace that the failure ip is always preceded by the recovery
action sp. We call disproportionately high co-occurrences
between failures and particular precursors dependencies. In this
example, the precursor of ip is the action sp, but
conceptually, it could be any combination of predecessors in the
trace: the preceding failure, the combination of the failure and the
recovery action that repaired it, or even longer combinations of
previous actions and failures. Currently, the analysis looks at only
singles (i.e., failures or recovery actions) and pairs (i.e., failures
and recovery actions) as precursors.
With more data, we can test whether the observed relationship between
sp and ip is statistically significant. We build a contingency table
of four cells: one for each combination of precursor and failure and
their negations. For example, the contingency table in Table 1 tests
whether depends on the precursor .
Table 1: Contingency table for testing the pattern 
.
We test the significance of the observed relationship, , with a G-test on the contingency table. A G-test
on this table is highly significant, G=42.86,p=.001, meaning that it
is highly unlikely that the observed dependence is due to chance or
noise.
We construct contingency tables for three types of immediate
precursors: failures, recovery actions, and a combination of a failure
and the recovery action that repaired it. We denote these cases 
, 
, and 
,
respectively. The three types overlap. In particular, is a special case of both and
(because they subsume all possible values of the missing member), so
if the former dependency is significant, we do not know whether it is
truly a dependency between a 
and the subsequent 
, or
between 
irrespective of the intervening action, or between R
with the initial failure playing no role. In practice, all three
dependencies might be present to varying degrees.
We sort out the strengths of the dependencies by running a variant on
the G-test called the Heterogeneity G-test [Sokal and Rohlf 81]. The
intuition is that we compare the contributions of subsets to that of
the superset; one can imagine looking at a Venn diagram (as in
Figure 1) to gauge whether the failure ner, the
recovery action sp or the combination seems to account for most
of the area in the intersection with the subsequent failure
ip. Both 
and overlap with part of the subsequent
, but it is easy to see that a larger proportion of
than overlaps with . Thus, is a more
reliable precursor for .
Figure did not convert
Figure 1: Venn diagram representing the data for the precursors and the
following failure.
Similarly, but somewhat harder to see, the proportion of
(the darker shaded area plus the cross hatched area)
that overlaps with (just the darker shaded area) is about the
same as the proportion of (the area in the heavy box) that overlaps
with (the two shaded areas), suggesting that we can generalize the
relationship without loss of information. To compute the overlap, we
add the G values for each of the subsets together (e.g., for , we add G values for all possible R's) and compare the
result to the G value for the superset; if the difference is
significant, then the subsets account for more of the variance in the
dependency and so cannot be generalized. For this example, the G
values for the subsets add to 45.89; the difference between that and G
for the superset is 3.035, which is not a significant
difference at the .05 level.