next up previous
Next: Explaining Dependencies Up: Identifying Contributors to Failure Previous: Identifying Contributors to Failure

Detecting Dependencies

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., displaymath255 is the Insufficient Progress failure in Phoenix) and R's are recovery actions (e.g., tex2html_wrap_inline259 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 tex2html_wrap_inline259 depends on the precursor displaymath255 .

Table 1: Contingency table for testing the pattern tex2html_wrap_inline253 .

We test the significance of the observed relationship, tex2html_wrap_inline253 , 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 table69, tex2html_wrap_inline283 , and tex2html_wrap_inline285 , respectively. The three types overlap. In particular, tex2html_wrap_inline285 is a special case of both tex2html_wrap_inline283 and table69 (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 tex2html_wrap_inline287 and the subsequent tex2html_wrap_inline295 , or between tex2html_wrap_inline297 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 tex2html_wrap_inline299 and tex2html_wrap_inline259 overlap with part of the subsequent displaymath255 , but it is easy to see that a larger proportion of tex2html_wrap_inline259 than tex2html_wrap_inline299 overlaps with tex2html_wrap_inline259 . Thus, tex2html_wrap_inline259 is a more reliable precursor for displaymath255 .

  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 figure98 (the darker shaded area plus the cross hatched area) that overlaps with displaymath255 (just the darker shaded area) is about the same as the proportion of tex2html_wrap_inline259 (the area in the heavy box) that overlaps with displaymath255 (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 table69 , 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 tex2html_wrap_inline259 is 3.035, which is not a significant difference at the .05 level.

next up previous
Next: Explaining Dependencies Up: Identifying Contributors to Failure Previous: Identifying Contributors to Failure

adele howe
Wed Oct 23 13:21:04 MDT 1996