HCBPS: Combining Structure-Based and TMS-Based Approaches in Model-Based Diagnosis
STANFORD UNIV CA KNOWLEDGE SYSTEMS LAB
Pagination or Media Count:
Model-based diagnosis can be formulated as the combinatorial optimization problem of finding an assignment of behavior modes to all the components in a system such that it is not only consistent with the system description and observations, but also maximizes the prior probability associated with it. Because the general case of this problem is exponential in the number of components, we try to leverage the structure of the physical system under consideration. Traditional dynamic programming techniques based on the underlying constraint network like heuristics derived from maximum cardinality ordering do not necessarily supplement or do better than algorithms based on using truth maintenance systems like conflict-directed best first search. In this paper, we compare the two approaches and examine how we can incorporate the dynamic programming paradigm into TMS-based algorithms to achieve the best of both the worlds. We describe an algorithm called hierarchical conflict-directed best first search HCBFS to solve a large diagnosis problem by heuristically decomposing it into smaller sub-problems. We also delve into some of the implications of HCBFS with respect to 1 precompiling the system description to a form that can amortize the cost of a diagnosis call and 2 facilitating other hybrid techniques for diagnosis.
- Operations Research