×

Automatic component abstraction for model-based diagnosis on relational models. (English) Zbl 1291.68379

Summary: In the present paper, we address the problem of automatically synthesizing component abstractions by taking into account the level of observability of the system as well as restrictions on its operating conditions. Compared with previous work, the proposed approach can be applied to a significantly wider class of systems, namely those whose nominal and faulty behaviors can be modeled with finite-domain relations.
The computed abstractions are specifically tailored for the Model-Based Diagnosis task, with the main goal of getting fewer and more informative diagnoses through the use of abstract models. To this end, we define a spectrum of indiscriminability relations among the states of subsystems, and formally prove that respecting indiscriminability is both a necessary and sufficient condition for abstracting the original model without losing any relevant diagnostic information.
We present an algorithm for the computation of abstractions that implements two specially important cases of indiscriminability, namely local and global-indiscriminability. The implemented system is exploited to collect experimental results that confirm the benefits of using the abstractions for diagnosis, in terms of both the number of returned diagnoses and the computational cost.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q60 Specification and verification (program logics, model checking, etc.)
PDFBibTeX XMLCite
Full Text: DOI