next up previous
Next: Finding Dependencies in Phoenix Up: Detecting Imperfect Patterns in Previous: Reducing the Search


Dependency detection, in its original form, has already been shown to be effective at finding interesting patterns in the Phoenix data. The two modifications described here extend the types of patterns found and search process for identifying significant patterns. The utility of the pattern extension remains to be seen; we are currently exploring it in another project on debugging different planners. The change in search process will only be an improvement if significant dependencies are surrounded by basins of attraction for directing the search. If the topology of the search space is relatively flat, then the number of random starts required to find significant dependencies will need to be large, thus reducing or eliminating any computational advantage over brute force exhaustive search.

Tests of the original dependency detection showed that similar patterns tended all to be significant. In other words, it was likely that if one pattern was significant, another pattern that shared all but one of the same elements would also be significant. In a sense, a strongly significant pattern is a basin of attraction in the search space; this characteristic is exploited by local search. To confirm whether such basins of attraction exist and can be exploited by the algorithm, the implementation was tested on execution traces from Phoenix and on synthetic data.

adele howe
Wed Mar 6 09:01:10 MST 1996