Computing Hitting Sets And Configurations Based On BDD

Binary Decision Diagrams are a symbolic representation of Boolean functions. Its ordered and reduced form provides compact and canonical representations of Boolean functions. Over the past decades, the basic theories and algorithms of BDDs had been presented. A number of operations on Boolean functions can be implemented as effective algorithms on BDDs. Using BDDs, we can quickly test the equivalence and satisfiability of Boolean functions. Because of these properties, its advantage in representing formal models of very large systems becomes more and more obvious. As a well-know mathematical tool, BDDs has been used in several areas of computing (including Artificial Intelligence) such as model-based diagnosis and product configuration which mentioned in this paper.Model-based diagnosis is a new kind of intelligent reasoning technology. It overcomes the traditional fault-diagnosis methods'shortcomings. And model-based diagnosis is one of the active branches of Artificial Intelligence. It gives an enormous impetus to the whole study about Artificial Intelligence. The basic principle of model-based diagnosis is employing the model of a device to judge faults logically, according to the difference between the model's prediction and the observation. Firstly, minimal conflict sets are computed by system description and observation, and then the candidate diagnoses are obtained by computing minimal hitting sets for the collection of all the minimal conflict sets. The procedure of computing all minimal hitting sets is proved as an NP-complete problem. Many researchers have studied the problem. However, some solutions may be lost by pruning in some methods, or occupying too much space when construct a complicate data structure, or the efficiency of computing hitting sets is bad. In order to overcome the shortcomings mentioned above, we use conflict sets in the form of BDD to calculate hitting sets. First we give the concept of disjunction equations, and map the collection of conflict sets into disjunction equations, then we compile the system into a BDD, further we compute the minimal hitting sets by solving the BDD and minimizing hitting sets. The reliability and completeness of the algorithm are proved. In additional, the BDD method won't generate redundant diagnosis. And when the new conflict sets are inserted, it is unnecessary to rebuild the BDD. This property is very useful for the actual diagnosis. Variable ordering and construct controlling of BDD are used to further reduce the size of final BDD and the number of non-minimal hitting sets to be generated. We have implemented a program in Visual C++6.0, and used an ROBDD package named BuDDy version 1.9. The experimental results show that the algorithm isn't restricted by the structure of system and conflict sets, compared with three algorithms in the references, it can generate all the minimal hitting sets, and it works well in random circumstances. Specifically, when the solution space is large, the running time of BDD algorithm is 10% of the one of Boolean Algebra algorithm. In additional, we gave a brief summary about methods of computing minimal hitting sets. And we have a simply discussion finally.In theory and reality, many problems can be classified as a kind of minimal hitting set problem, such as the minimum set cover problem, arranging courses, and minimum spanning tree problem. So the BDD method can also be applied to the fields mentioned above.Product configuration problem is an important branch of Artificial Intelligence too. With the development of society, more and more problems can be represented as configuration problems. And people's requirements become higher and higher. This situation promotes the study and development of the configuration problem. In recent years, many researchers employ BDD to solve configuration problem. The BDD-based product configuration can be divided into two phase. In the first phase, the data structure representing the configuration model can be generated offline. In the second phase, this representation is embedded in an online configurator. The configurator is fast, complete and backtrack-free. The problem in the first phase is that if we don't use some strategy such as variable ordering, we will get a BDD of exponential size possibly. The second phase is an interactive phase. In order to make the users have a smooth configure processing, the configurator must offer some help. First, after user assignment, the configurator needs to report the valid domains to the user. Second, an explanation facility is required when the user wants to know why a choice is deleted. Some researchers do many works about variable ordering and calculate valid domains. But the work about gave explanation is not many.In this paper we propose a method of generating explanation. We analyze the interactive configurate process and find that, during calculating valid domains(CVD), it will generate some information which useful for giving explanation. If we record these information in the process about CVD, we can give explanation by searching. Based on this idea, we give a modified interactive configuration algorithm(IC*). IC* combines the CVD and explain process. First we need a kind of data structure to store deletion information. In this paper, we propose a table DelT as the data structure. We construct DelT during CVD. We assume that the user needs the explanation about (xk,dk), where xk is a variable ,and dk is a deleted value about xk. The explanation is in the form of a assignment (xi,di), which is given by the user, and makes (xk,dk) invalid. Subbarayan had presented a method to give explaination. Subbarayan's method is linear in the number of nodes, and our method's worst-case running time is O(n2+|Dk|), where n is the number of variables, and Dk is the domain about xk. Because of the size of DelT has something to do with , so our method is applied to the situation when the domains of variables is not too big. Finally, we give two instances (N-queens problem and the bike model) to verify the effectiveness of the improved process IC~*.Both the works about computing minimal hitting sets and interactive configurate process need to improve. And it needs further researches and efforts. Nowadays, as an efficient mathematical tool, BDD has received considerable attention. And it has been widely used in many fields.