Scalable Computation of Optimized Queries for Sequential Diagnosis
This work addresses the scalability issue in model-based diagnosis for systems where multiple fault candidates exist, offering a more efficient solution for users in diagnostic applications.
The paper tackles the inefficiency of existing sequential diagnosis methods, which rely on expensive logical reasoners and generate many unnecessary query candidates, by proposing heuristic query search methods that enable reasoner-free query generation while guaranteeing optimality conditions like minimal cardinality. Experiments on real-world problems show the new approach is highly scalable and outperforms existing methods by orders of magnitude.
In many model-based diagnosis applications it is impossible to provide such a set of observations and/or measurements that allow to identify the real cause of a fault. Therefore, diagnosis systems often return many possible candidates, leaving the burden of selecting the correct diagnosis to a user. Sequential diagnosis techniques solve this problem by automatically generating a sequence of queries to some oracle. The answers to these queries provide additional information necessary to gradually restrict the search space by removing diagnosis candidates inconsistent with the answers. During query computation, existing sequential diagnosis methods often require the generation of many unnecessary query candidates and strongly rely on expensive logical reasoners. We tackle this issue by devising efficient heuristic query search methods. The proposed methods enable for the first time a completely reasoner-free query generation while at the same time guaranteeing optimality conditions, e.g. minimal cardinality or best understandability, of the returned query that existing methods cannot realize. Hence, the performance of this approach is independent of the (complexity of the) diagnosed system. Experiments conducted using real-world problems show that the new approach is highly scalable and outperforms existing methods by orders of magnitude.