Improving the determination of minimal hitting sets in model-based diagnosis using constraint databases

Abstract

In model-based diagnosis, minimal hitting sets are usually used to identify which components may fail in a system. This work presents a set of algorithms to improve the determination of all Minimal Hitting Sets. Our proposal uses the minimal conflict sets to obtain, in an efficient way, the diagnosis of a system. The improvement consists of three algorithms which analyse only the relevant options. This proposal builds an equivalent system in order to obtain all minimal hitting sets depending on the location of the sensors. At the same time, all the information of the process is stored in a Constraint Database, keeping the information persistent and recoverable. Some empirical results are presented in order to show how the proposal improves the process in order to obtain all minimal hitting sets.