| Model-based diagnosis is a way of intelligent reasoning. Its appearance is to make up the shortcoming of the traditional fault-diagnosis method. Model-based diagnosis has already applied in communications, aerospace, gas turbine monitoring, transportation electronic equipments and so on. The primary theory is to create a model of system which is diagnosed, and to observe the actual behavior of the system. If observed behavior and predict system behavior is different, we confirm the fault-diagnosis. Four processes involved are model building, conflict identification, diagnosis and diagnostic candidates. Now the 2 research priorities of MBD are abduction diagnosis and consistency-based diagnosis, and this thesis focuses on consistency-based diagnosis. Solving minimal hitting sets of model-based diagnosis is proved NP-complete. so lots of researchers continuously put forward new ideas and optimization method for solving the hitting sets, to reduce its time consumption.BDD is short for binary decision diagrams, which is proposed in 1959. It is a structure of rooted acyclic graph. For now. BDDs have a wide range of applications in many fields, such as computer networks, logic synthesis and verification. Randel made the point of view in 1986, the order of BDD variables has a great impact in the size of the resulting BDDs. Since then, many researchers at home and abroad made a lot of n-depth study in the order of BDDs variables. Since the optimal variable ordering problem has been proved to be NP-complete, so many researchers through the research of application fields design appropriate heuristic ordering method to make the algorithm to meet the efficiency of time and space requirements of problems in the application. This article is used the ROBDD algorithm of combination of heuristic annotation. In recent years, there have been many domestic and foreign scholars applied OBDDs to model-based diagnosis. This paper also proposes a new idea of using ROBDDs to solve the problem of minimal hitting sets in model-based diagnosis.Focus our attentions to the candidate diagnosis process (i.e.. the process of minimal hitting sets derived by minimal conflict sets), and propose ROBDD method to solve minimal hitting sets. Our main idea is given here:first of all, make the problem system to the form of disjunction equations. Second, apply VCD-Order and FD-Order operation to sort the variables in the conflict set cluster according to the high compression of data structure of OBDDs, operation efficiency and the representation of Boolean expressions and other properties. Then compile the conflict set into the form of separate ROBDD using the order made. Logical product and we will obtain the hitting sets of the system. Last, minimize and the minimal hitting set is turned up. The algorithm does not lose of solutions because of pruning liking other algorithms. Because OBDD is the kind of high compressed data structure, it takes up less space, and the algorithm is easy to understand and implement. As the algorithm does not apply the random algorithm, so we can get all the minimal hitting sets. It said that ROBDD algorithm is complete. But using ROBDDs to solve the hitting set needs the operations of minimize to get the minimal hitting set of fault-systems. This operation reduces the overall efficiency of the algorithm. At the same time, we both mentioned in this article 2 ROBDDs algorithms for solving minimal hitting sets, which are ordered the variables based on their relations and frequency. We through theoretical analysis proved ROBDDs validity and completeness, and through a large number of comparative experiments, we can see ROBDD algorithm has obvious efficiency advantages in randomly generated sets of conflict. And through the research and experiments of ROBDDs algorithms based on relations of variables and frequency of variables, we concluded that the use of two methods.The proposed methods also have some places to be improved, for example, we can combine the two methods to make more optimal ROBDDs for solve the hitting sets. |
PDF Full Text Request