Domain Structure and the Complexity of Diagnostic Problem Solving

Thomas De Wu MIT Laboratory for Computer Science 545 Technology Square Cambridge, Massachusetts 02139 approach offers increased efficiency for the diagnosis of This paper provides a quantitative analysis of domain structure and its effects on the complexity of diagnostic problem solving. It introduces a hypothesis about the modular structure of domains and proposes a measured called explanatory power. The distribution of explana tory power reveals the inherent structure of domains. We conjecture that such structure might facilitate problem solving, even when the problem solver does not exploit it explicitly. To test this hypothesis, we create a domain without structure by randomizing the distribution of explanatory power. We use the structured and randomized knowledge bases to study the effect of domain structure on two diagnostic algorithms, candidate generation and symptom clustering. The results indicate that inherent domain structure, even when not encoded explicitly, can facilitate problem solving. Such facilitation occurs for both the candidate generation and symptom clustering algorithms. Moreover, domain structure appears to benefit symptom clustering more than candidate generation, suggesting that the efficiency of symptom clustering derives in part from exploiting domain structure.

Authors

• Thomas D. Wu

Keywords

No keywords are indexed for this paper.