کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
403279 | 677077 | 2006 | 8 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On the use of OBDDs in model-based diagnosis: An approach based on the partition of the model On the use of OBDDs in model-based diagnosis: An approach based on the partition of the model](/preview/png/403279.png)
In this paper, we discuss how Ordered Binary Decision Diagrams (OBDDs) can be exploited for the computation of consistency-based diagnoses in model-based diagnosis. Since it is not always possible to efficiently encode the whole system model within a single OBDD, we propose to build a set of OBDDs, each one encoding a portion of the original model. For each portion of the model, we compute an OBDD encoding the set of local diagnoses; the OBDD encoding global diagnoses is then obtained by merging all the local-diagnoses OBDDs. Finally, minimal-cardinality diagnoses can be efficiently computed and extracted.The paper reports formal results about soundness, completeness and computational complexity of the proposed algorithm. Thanks to the fact that encoding diagnoses is in general much simpler than encoding the whole system model, this approach allows for the successful computation of global diagnoses even if the system model could not be compiled into a single OBDD. This is exemplified referring to a challenging combinatorial digital circuit taken from the ISCAS85 benchmark.
Journal: Knowledge-Based Systems - Volume 19, Issue 5, September 2006, Pages 316–323