Research On Some Problems About Model-Based Diagnosis Of Discrete Event Systems

There are some severe shortcomings for diagnosis by traditional expert systems. In the middle of 1970s, a new type of intelligent diagnosis method was emerging– model-based diagnosis (MBD). After R. Reiter gave a formalization of MBD with first-order logic, MBD has been widely studied. Earlier, static systems were studied by researchers, and then researches on dynamic systems have begun since the last decade. Especially, model-based diagnosis of discrete-event systems (DESs) has arisen increasing interests, as DESs cover continuous-variable systems which, after quantization, are represented as discrete systems for the purpose of diagnosis at a higher level of abstraction, as well as"discrete by nature"systems.Several diagnosis methods and diagnosability of DESs are mainly concerned in this paper. In addition, we do some preliminary studies on the way to process the imcomplete DES model.(1) In the approach to diagnosis of active systems (one kind of DESs) proposed by G. Lamperti et al., only the order of observations of each component is considered, while the order of observations of different components is not concerned. Therefore, the combination of the number of different orders is very large. In addition, there may be some more detailed temporal information in practice, such as the more precise time point or time interval of some observations, the related order of different component events, etc. As a result of the not well-used time information, the search space becomes larger.Time interval algebra is introduced for representing detailed time information into automata. And active systems can be modeled by this kind of timed automata. At the same time, the corresponding time information is added to observation. As a result of detailed time information, space of the interpretation of the active system is more reduced, and diagnosis efficiency is improved as well.(2) Computational complexity of multiple fault diagnosis is one of the well-known problems in real-world applications of MBD. And hierarchical diagnosis has been advocated as one of the main remedies for this issue. A hierarchical method of diagnosing DESs is based on the concept"D-holon"presented in by A. Mohammadi Idghamishi and S. Hashtrudi Zad, and each higher hierarchy is a D-holon. But how to produce good D-holons by breaking the system model is not given yet. As we know, there are not many more hierarchical methods to diagnosis for DESs.The monitor based on silent closures can be seen as a way to decompose a system. As each silent closure in the monitor is built on line, the efficiency would not be very good.In this paper, we present a novel hierarchical approach to diagnosis of DESs, well combining the concept"D-holon"as the basis of hierarchy, and the concept"silent closure"as each hierarchy. All the new silent closures are built off line, and only the relevant D-holons are used when on line diagnosing the system, thus the efficiency will be improved as well.(3) Model-based diagnosis of DESs consists in finding what happened to the system from existing observations, under the assumption that the system model is complete. A classical formal way of representing the diagnosis problem is to express it as the synchronized product of the system model automaton and an emitted observation automaton. However, the observations are often uncertain, especially the uncertainty caused by the orders of emission and reception mainly concerned in this paper. The methods of"diagnoser"or its extended variants mainly consist in the compilation of diagnostic information in a diagnoser, which maps observations to failures for on-line diagnosis. These approaches depend on really certain emitted observation sequences, as well as the bridged diagnostic method, otherwise some diagnostic results may be lost; however, it is unrealistic to suppose that observations can be totally ordered according to their emission dates. Moreover, an automata chain of observations for off-line incremental diagnosis, whereas it depends on so-called"sound window"(i.e. each observation emitted in it is required to be received in it, too), just like the decentralized incremental diagnosis, especially in on-line situations. In addition, there is no good approach given to build, on-line and incrementally, the observation automata chain to ensure that the slicing is"correct"whenever the future observations are unknown. How to choose the so-called sound temporal windows is fundamental, or else some diagnostic results may be lost.In order to obtain the sound windows, an idea proposed by Y. Pencoléis to use domain knowledge, especially knowledge on the properties of the communication channels, in order to split the flow of observations in sound windows. But as said by G. Lamperti and M. Zanella in papers that it is still an unsolved problem by now: how to frame temporal windows in order to achieve completeness of diagnostic results.In addition, the monotonicity of incremental diagnosis is analyzed from conceptual standpoint in papers by G. Lamperti et al. It is claimed that the criterion of soundness and completeness of results is not meaningful for monitoring-based diagnosis in case the considered observation is affected by temporal uncertainty, since it does not guarantee an important property of monotonicity (Note: the so-called"monotonicity"means monitoring is a shrink and expand process, where one of the previous diagnostic results ?i is first shrunk and then the remaining candidates are possibly extended with additional faults, to eventually make up ?i+1. However, it is thought as non-monotonic when there is not any previous diagnostic result ?i being included by a new diagnostic result ?i+1). And it is proposed that monitoring will be monotonic when an observation is stratified, else it would produce some useless diagnostic results. But, a stratified observation is only a sufficient condition for monotonicity, not necessary. Moreover, there is not a sound approach to make an observation stratified yet. Though the approach of an automata chain of observations proposed by A. Grastien et al. is monotonic, as said before, it is a-posteriori, and there is not any approach proposed for correctly slicing an automaton on-line yet.In order to overcome the drawbacks of the methods mentioned above, in this paper, an approach to on-line incremental diagnosis of DESs based on two successive temporal windows is proposed. It considers two successive temporal windows at one time to make sure that the observation sequences are sound, complete, and monotonic. It is also timely (the max temporal delay is not more than 2*dmax– here dmax is the maximal transmission delay). In comparison with other related approaches, it is really on-line incremental diagnosis under uncertainty situations universally; especially it is suitable for on-line diagnosis of DESs, when the received observations are too dense to find sound time points (or sound windows) in time.(4) Generally, diagnosability analysis of DESs is a very important step before online diagnosing DESs. Many researchers have studied this topic from theoretical or practical view, such as global diagnosability, decentralized diagnosability, modular diagnosability, etc. Especially, in recent time, Y. Wang et al. have given a hierarchical framework of a lot of decentralized diagnosability, according to their inner restriction, from theoretical view mainly in the Control Engineering community.However, in the AI community, there are also emerging many novel definitions of diagnosability for the need of practical diagnosis in literatures. In order to give a deep insight into diagnosability, we have firstly extended the hierarchical framework based on the original one. Then we have studied the evolution of several kinds of finite-state machines (FSMs) from the system model G for diagnosability test, followed by comparing nearly all the approaches to test diagnosability, and so on.(5) There has been always an assumption in the previous works that the model of the given DES is complete, including all nominal behaviors and all possible failure behaviors. Generally speaking, the assumption is very restrictive, as it is difficult to be assured that the model is complete practically. Also inspired from the way proposed by L. Console et al. to cope with an incomplete system model for static diagnosis, in this paper, we mainly concern model-based diagnosis of a DES with an incomplete system model similarly. A novel concept of"P-synchronization product"for finite state automata is proposed, by which the diagnosis of the DES with an incomplete system model is easily presented. It is also shown that the traditional synchronization product can be seen as a special situation of P-synchronization product. In addition, an approach to completing the system model is discussed as well.