Model-Based Diagnosis Under Non-Monotonic Reasoning

Model-based diagnosis is a novel artificial intelligencetechnique. It can overcome the serious shortcomings oftraditional diagnostic expert system methods. Model-baseddiagnostic methods employ the model of the internal structure andbehavior of the device to be diagnosed. This model is availablewhen the device is first designed and manufactured. Theincreasing use of computer aided design and manufacturing alsomeans that the model is available as explicit description inelectronic form, rather than implicit in the head of the designer,or sketched informally on a scattered collection of paper.Therefore, this approach can be less costly to use. Moreover, thismethod is strongly device independent. That is to say, given amodel of a device, diagnosing work on the device can begin rightaway, and if given a new model of a different device, work canstart on that one just as quickly. Struss called model-baseddiagnosis as an important challenge and verify for artificialintelligence.Since model-based diagnosis systems developed until nowadays,in the theory of diagnosis, the process of diagnosis has beenformalized, and brings several definitions of logic; and in thathave two representative schools: consistency-based diagnosis andabductive diagnosis. Reiter has put forward the method ofconsistency-based diagnosis, the weakness of the method ofconsistency-based diagnosis is that it provides us with a verylarge space of potential solutions, and so one needs to constrainsuch a space of solutions in order to find the true faults. Onemethod is that we can make use of fault theory-consistency-basedminimal abnormal diagnosis method to constrain the space ofsolutions; Another method is that we can use abductive diagnosisto reduce the space of solutions。Abductive diagnosis constrainstrongly to the diagnostic space, it postulates that diagnosesmust entail the observations logically. In the case of diagnosissystems to be dealt with are not perfected, it may lose the truefault solutions; The weak constraint of consistency-baseddiagnosis to diagnostic space does not postulate that diagnosesmust entail the observation logically, it may induce lots of nouse solutions in diagnostic space. Console and Torasso havedefined a spectrum of diagnostic definitions which integratesabductive diagnosis to consistency-based diagnosis, and regardeddiagnostic problems as abductive problem with consistency-basedconstraint. They proposed a united definition which can integratedifferent diagnostic definitions into it; we can also compare thedefinition with the known problem and pick out which logicaldefinition is fit for the problem. In this situation, the uniteddefinition's extremes are consistency-based diagnosis andabductive diagnosis. In Fr?hlich's PhD dissertation, heproposed a new model-based diagnosis system DRUM-II, whichachieves flexibility by embedding diagnosis in a general logicalframework. He developed a novel formalization of model–baseddiagnosis based on circumscription. This makes DRUM-II moreflexible than previous diagnosis engines. We studied the work of Fr?hlich, as we discussed most previoussystems for model-based diagnosis are based on conflictrecognition and candidate generation. Despite theirapplication-specific algorithms, they suffer from combinatorialexplosion of internal data structures during the computation ofdiagnoses. Thus, it is worthwhile to consider alternatives to theconflict-based algorithms motivated in Reiter's work. This isthe DRUN-II general logical inference engines that Reiter hasproposed, it utilized a non-monotonic logic—Circumscription inits general logical engines. Fr?hlich has set up a relationbetween minimal diagnosis and minimal model. By thecircumscription of fault predicate, it accelerated thegeneration of minimal model. It computed the minimal model bymodel repair function and got the minimal diagnosis. Themodel-based diagnostic framework that Fr?hlich has proposedinclude two steps: model revision and model filter, model filteralgorithm is the simplified version of model revision algorithm.Its main idea is: at the beginning of diagnostic process, giventhe system description, we can get a normal behavior model, then,we can get the result diagnosis by the normal behavior model andobservation. At the same time, we can decide whether a formulais right or not by the filter step. In the text, we propose aconcrete algorithm to implement this step-revision functionRevp , it compute effectively the minimal diagnosis. We can usethe revision function directly to compute a transversal of theminimal models by executing the revision function Revp(φ,{φ},Τ).In other applications we want to compute minimal models inmultiple steps. That is, we already have a transversal M of theminimal models for a part Τ0 of the theory and we useRevp (T0 ,M, T1) to compute the minimal models of T0 UT1 . Onereason for doing so can be the appearance of new knowledge.Another reason for computing minimal model models in severalsteps is efficiency. Using the filtering function, we can decidewhether an arbitrary formula ? follows from the circumscriptionby first computing a transversal of the minimal models and thenfiltering with ?? . If no equivalence class remains after thefiltering, there is by definition no minimal model, in which ??holds. Thus, ? follows from the theory. Then we apply thefunction to the temporal reasoning field, where non-monotonicreasoning is used to infer intuitively correct conclusion fromlogical axioms formalizing the effects of actions. Moreover, we applied the model-based diagnosis method on faultdiagnosis of mobile communication networks. We can constructnetwork model from the communication network connection aspect ;this accords with the common sense about network of ours. Thus,we can analyze the connection between manager and networkcomponent intuitively. We transferred the network model topredication logic description. We use a set of facts to describenetwork components and their types. Network topology is composedwith connection fact set. In this way, we create the formalismof system behavior. And then, we can acquire the diagnostic resultby the DRUN-II introduced in this text. At last, we will show that integrating the idea to use initialmodels from DRUM-II system into the hyper tableau calculus. The...