Model-based diagnosis has always been conceived as set-oriented, meaning that a candidate is a set of faults, or faulty components, that explains a collection of observations. This perspective applies equally to both static and dynamical systems. Diagnosis of discrete-event systems (DESs) is no exception: a candidate is traditionally a set of faults, or faulty events, occurring in a trajectory of the DES that conforms with a given sequence of observations. As such, a candidate does not embed any temporal relationship among faults, nor does it account for multiple occurrences of the same fault. To improve diagnostic explanation and support decision making, a sequence-oriented perspective to diagnosis of DESs is presented, where a candidate is a sequence of faults occurring in a trajectory of the DES, called a fault sequence. Since a fault sequence is possibly unbounded, as the same fault may occur an unlimited number of times in the trajectory, the set of (output) candidates may be unbounded also, which contrasts with set-oriented diagnosis, where the set of candidates is bounded by the powerset of the domain of faults. Still, a possibly unbounded set of fault sequences is shown to be a regular language, which can be defined by a regular expression over the domain of faults, a property that makes sequence-oriented diagnosis feasible in practice. The task of monitoring-based diagnosis is considered, where a new candidate set is generated at the occurrence of each observation. The approach is based on three different techniques: .1/ blind diagnosis, with no compiled knowledge, .2/ greedy diagnosis, with total knowledge compilation, and .3/ lazy diagnosis, with partial knowledge compilation. By knowledge we mean a data structure slightly similar to a classical DES diagnoser, which can be generated (compiled) either entirely offline (greedy diagnosis) or incrementally online (lazy diagnosis). Experimental evidence suggests that, among these techniques, only lazy diagnosis may be viable in non-trivial application domains.

An active system (AS) is a discrete-event system (DES) with asynchronous behavior, which is represented by a network of components that are modeled as communicating automata. When being operated, an AS performs a trajectory within its behavior space, while generating a sequence of observations, namely a temporal observation. The model of the AS and a temporal observation are the two key ingredients of the diagnosis task, which aims to find out possible faulty behavior via abductive reasoning. Among other knowledge, such reasoning requires knowing what is observable and what is not. This essential distinction constitutes the observability of the AS. In the literature, the observability of a DES boils down to qualifying each state transition either as observable or unobservable, which contrasts with the way humans observe reality, typically by mapping a collection of observations to a single, abstract perception. Moreover, the occurrence of single state transitions is not necessarily what we can observe or what we want to observe for diagnosis purposes. This paper presents an extended notion of observability, where each observation is associated with a behavioral scenario rather than a single state transition, where a scenario is defined as a regular language on state transitions. To speed up the online diagnosis engine, specific diagnosis-oriented knowledge is compiled offline. Eventually, the diagnosis technique based on abstract observability is extended to cope with temporal uncertainty.

Model-based diagnosis of discrete-event systems (DESs) generates a set of candidates upon the reception of a temporal observation. In the literature, a candidate is a set of faults produced by a trajectory of the DES that is consistent with the temporal observation. As such, a candidate does not convey any temporal relationship between faults, nor does it account for multiple occurrences of the same fault. To overcome the limitations of this set-oriented approach to diagnosis of DESs, the novel notions of temporal fault and temporal diagnosis are proposed, along with two diagnosis techniques. A temporal fault is the (possibly unbounded) sequence of faults produced by a trajectory. A temporal diagnosis is a (possibly infinite) set of temporal faults. Hence, in this new temporal-oriented approach to diagnosis of DESs, a candidate is a temporal fault. The fact that a temporal diagnosis turns out to be a regular language is key to coping with the infinity of candidates, which can be represented by a regular expression. The diagnosis task can be performed either by restricting the DES space to the trajectories that are consistent with the temporal observation, or by exploiting a temporal diagnoser which allows for fast online diagnosis. The claim of this paper is that the extra temporal information embedded in candidates may be essential in taking critical decisions based on the diagnosis results.

Since its appearance in AI, model-based diagnosis is intrinsically set-oriented. Given a sequence of observations, the diagnosis task generates a set of diagnoses, or candidates, each candidate complying with the observations. What all the approaches in the literature have in common is that a candidate is invariably a set of faulty elements (components, events, or otherwise). In this paper, we consider a posteriori diagnosis of discrete-event systems (DESs), which are described by networks of components that are modeled as communicating automata. The diagnosis problem consists in generating the candidates involved in the trajectories of the DES that conform with a given temporal observation. Oddly, in the literature on diagnosis of DESs, a candidate is still a set of faulty events, despite the temporal dimension of trajectories. In our view, when dealing with critical domains, such as power networks or nuclear plants, set-oriented diagnosis may be less than optimal in explaining the supposedly abnormal behavior of the DES, owing to the lack of any temporal information relevant to faults, along with the inability to discriminate between single and multiple occurrences of the same fault. Embedding temporal information in candidates may be essential for critical-decision making. This is why a temporal-oriented approach is proposed for diagnosis of DESs, where candidates are sequences of faults. This novel perspective comes with the burden of unbounded candidates and infinite collections of candidates, though. To cope with, a notation based on regular expressions on faults is adopted. The diagnosis task is supported by a temporal diagnoser, a flexible data structure that can grow over time based on new observations and domain-dependent scenarios.

Model-based diagnosis is typically set-oriented. In static systems, such as combinational circuits, a candidate (or diagnosis) is a set of faulty components that explains a set of observations. In discrete-event systems (DESs), a candidate is a set of faulty events occurring in a sequence of state changes that conforms with a sequence of observations. Invariably, a candidate is a set. This set-oriented perspective makes diagnosis of DESs narrow in explainability, owing to the lack of any temporal knowledge relevant to the faults within a candidate, along with the inability to discriminate between single and multiple occurrences of the same fault. Embedding temporal knowledge in a candidate, such as the relative temporal ordering of faults and the multiplicity of the same fault, may be essential for critical decision making. To favor explainability, the notions of temporal fault, explanation, and explainer are introduced in diagnosis of DESs. The explanation engine reacts to a given sequence of observations by generating and refining in real-time a sequence of regular expressions, where the language of each expression is a set of temporal faults. Moreover, to avoid total knowledge compilation, the explainer can be generated incrementally either offline, based on meaningful behavioral scenarios, or online, when being operated in solving specific diagnosis problems.

An abduction-based diagnosis technique for a class of discrete-event systems (DESs), called deep DESs (DDESs), is presented. A DDES has a tree structure, where each node is a network of communicating automata, called an active unit (AU). The interaction of components within an AU gives rise to emergent events. An emergent event occurs when specific components collectively perform a sequence of transitions matching a given regular language. Any event emerging in an AU triggers the transition of a component in its parent AU. We say that the DDES has a deep behavior, in the sense that the behavior of an AU is governed not only by the events exchanged by the components within the AU but also by the events emerging from child AUs. Deep behavior characterizes not only living beings, including humans, but also artifacts, such as robots that operate in contexts at varying abstraction levels. Surprisingly, experimental results indicate that the hierarchical complexity of the system translates into a decreased computational complexity of the diagnosis task. Hence, the diagnosis technique is shown to be (formally) correct as well as (empirically) efficient.

Single-agent pathfinding on grid maps can exploit online compiled knowledge produced offline and saved as a Compressed Path Database (CPD). Such a knowledge is distilled by performing repeated searches in a graph, where each node corresponds to a distinct grid cell, typically by algorithms such as Dijkstra's. All-pairs shortest paths (APSPs) are computed and the first move along a shortest path is persistently stored in the CPD. This way, an optimal move can efficiently be retrieved for any pair of source and target cells that is considered while the agent is navigating. However, a CPD supports a static grid, that is, a grid where each cell is permanently either traversable or non-traversable. Our work instead assumes that the cells in the map can undergo dynamic changes. Reasoning about the altered map would require a new CPD. As creating it from scratch is computationally expensive, we present techniques to repair an existing CPD. We prove that using our technique leads to correct and optimal solutions. Experiments demonstrate the benefits of our approach. When a single obstacle of a given size is added or removed, the repair costs often are a small fraction of a recomputation from scratch.

The twin plant method is central in every research whose focus is checking the diagnosability of discrete-event systems (DESs). Although the property of diagnosability has been extended over time, and several proposals have been advanced to perform a distributed analysis, diagnosability checking still relies on the exploitation of the twin plant method. However, the twin plant structure is redundant, which is a drawback, above all if the considered DES observation is uncertain: in such a case, several distinct twin plants have to be built in order to check the diagnosability for increasing levels of uncertainty. A higher uncertainty level requires a twin plant of larger size. The paper first gives some preliminary thoughts to the reduction of the twin plant size. Next, on the ground that no contribution in the literature has altered the original state-based representation of the twin plant, the paper shows how to transform such a representation into a transition-based one. Finally, it reports some investigations aimed at reducing the effort needed to produce each twin plant: a twin plant inherent to a higher uncertainty level can be produced by incrementing the twin plant relevant to the lower level.

The determinization of a nondeterministic finite automaton (FA) is the process of generating a deterministic FA (DFA) equivalent to (sharing the same regular language of) . The minimization of is the process of generating the minimal DFA equivalent to . Classical algorithms for determinization and minimization are available in the literature for several decades. However, they operate monolithically, assuming that the FA to be either determinized or minimized is given once and for all. By contrast, we consider determinization and minimization in a dynamic context, where augments over time: after each augmentation, determinization and minimization of into is required. Using classical monolithic algorithms to solve this problem is bound to poor performance. An algorithm for incremental determinization and minimization of acyclic finite automata, called IDMA, is proposed. Despite being conceived within the narrow domain of model-based diagnosis and monitoring of active systems, the algorithm is general-purpose in nature. Experimental evidence indicates that IDMA is far more efficient than classical algorithms in solving incremental determinization and minimization problems. Copyright © 2015 John Wiley & Sons, Ltd.

The high abstraction level of Spectrum-based Fault Localization (SFL) reasoning, on the one hand, offers the advantage of a model-free approach to diagnosis, while, on the other, reduces the inherently limited testability of many hardware and software systems. Thus, along with substantial complexity gains, SFL exhibits limited diagnostic performance, compared to Model-Based Diagnosis. This paper describes two algorithms (Lion and Tiger) that exploit low cost heuristics to determine the best location to insert additional test oracles (monitors, probes, invariants) so as to increase the observability within the systems. Experiments show that even simple algorithms can considerably improve SFL's diagnostic accuracy.

Since the seminal work of Sampath et al. in 1996, despite the subsequent flourishing of techniques on diagnosis of discrete-event systems (DESs), the basic notions of fault and diagnosis have been remaining conceptually unchanged. Faults are defined at component level and diagnoses incorporate the occurrences of component faults within system evolutions: diagnosis is context-free. As this approach may be unsatisfactory for a complex DES, whose topology is organized in a hierarchy of abstractions, we propose to define different diagnosis rules for different subsystems in the hierarchy. Relevant fault patterns are specified as regular expressions on patterns of lower-level subsystems. Separation of concerns is achieved and the expressive power of diagnosis is enhanced: each subsystem has its proper set of diagnosis rules, which may or may not depend on the rules of other subsystems. Diagnosis is no longer anchored to components: it becomes context-sensitive. The approach yields seemingly contradictory but nonetheless possible scenarios: a subsystem can be normal despite the faulty behavior of a number of its components (positive paradox); also, it can be faulty despite the normal behavior of all its components (negative paradox).

In monitoring-based diagnosis of active systems, the observation is fragmented over time: at the occurrence of each fragment, the internal representation of the observation received so far is updated, new monitoring states are estimated, and a new set of candidate diagnoses is output. When the observation is temporally uncertain, a problem arises about the dependability of the monitoring output: Two consecutive sets of diagnoses, relevant to two consecutive observation fragments, may be unrelated to one another, and, even worse, they may be unrelated to the actual diagnosis. To cope with this problem, the notion of monotonic monitoring is introduced, which is supported by specific constraints on the fragmentation of the uncertain temporal observation, leading to the notion of stratification. Stratified observations support monotonic monitoring of active systems.

In similarity-based diagnosis of discrete-event systems the knowledge generated for solving a previous diagnostic problem can be reused to solve a new one, provided the two problems are similar. Problem-similarity requires that the temporal observation relevant to the new problem be subsumed by the temporal observation relevant to the old one. A temporal observation encompasses the (uncertain) events observed over a time interval and their (uncertain) reciprocal temporal order. Such an observation has been produced by one out of several distinct certain sequences of observable events, with each of such sequences being a sentence of the regular language of the observation. An observation subsumes another if its regular language contains the regular language of the other. However, checking observation-subsumption by following its formal definition is time consuming. In order to speed up the process, an alternative technique is proposed, which is based on the notion of coverage and exploits a number of necessary conditions, as well as a sufficient condition, for subsumption to hold. Such conditions can be directly checked on the properties of the given observations, without any need to appeal to the language theory. Experimental evidence confirms the efficiency of subsumption-checking via coverage.

In discrete-event system monitoring, a set of candidate diagnoses is output at the reception of each observation fragment. However, when the observation is uncertain, this result may be not dependable: the sets of diagnoses, relevant to consecutive observation fragments, may be unrelated to one another, and, even worse, they may be unrelated to the actual diagnosis. To cope with this problem, the notion of monotonic monitoring is introduced, which is supported by specific constraints on the fragmentation of the uncertain observation, leading to the notion of stratification.

Abstract Automated diagnosis of communicating‐automaton networks (CANs) is a complex task, which is typically faced by model‐based reasoning, where the behavior of the network is reconstructed based on its observation. This task may take advantage of knowledge‐compilation techniques, where a large amount of reasoning is anticipated off‐line (when the diagnostic process is not active), by simulating the behavior of the network and by constructing suitable data structures embedding diagnostic information. This (general‐purpose) compiled knowledge is exploited on‐line (when the diagnostic process becomes active), so as to generate the solution to the problem. Additional reusable (special‐purpose) compiled knowledge is generated on‐line when solving new problems. A software environment for the diagnosis of CANs has been developed in the C programming language with the support of the PostgreSQL relational database management system, under the Linux operating system. It supports the modeling and preprocessing of CANs as well as the solution of diagnostic problems, including on‐line knowledge compilation. The environment has been tested through a variety of experiments. Results are encouraging and provide a valuable feedback for further work. Copyright © 2006 John Wiley & Sons, Ltd.

Discrete-event modeling can be applied to a large variety of physical systems, in order to support different tasks, including fault detection, monitoring, and diagnosis. The paper focuses on the model-based diagnosis of a class of distributed discrete-event systems, called active systems. An active system, which is designed to react to possibly harmful external events, is modeled as a network of communicating automata, where each automaton describes the behavior of a system component. Unlike other approaches based on the synchronous composition of automata and on the off-line creation of the model of the entire system, the proposed diagnostic technique deals with asynchronous events and does not need any global diagnoser to be built. Instead, the current approach features a problem-decomposition/solution-composition nature whose core is the online progressive reconstruction of the behavior of the active system, guided by the available observations. This incremental technique makes effective the diagnosis of large-scale active systems, for which the one-shot generation of the global model is almost invariably impossible in practice. The diagnostic method encompasses three steps: (1) reconstruction planning; (2) behavior reconstruction; and (3) diagnosis generation. Step 1 draws a hierarchical decomposition of the behavior reconstruction problem. Reconstruction is made in Step 2, where an intensional representation of all the dynamic behaviors which are consistent with the available system observation is produced. Diagnosis is eventually generated in Step 3, based on the faulty evolutions incorporated within the reconstructed behaviors. The modular approach is formally defined, with special emphasis on Steps 2 and 3, and applied to the power transmission network domain.