Abductive diagnosis of complex active systems with compiled knowledge

An abduction-based diagnosis technique for a class of discrete-event systems (DESs), called complex active systems (CASs), is presented. Inspired by complexity science, according to which the essence of a complex system is the emergence of unpredictable behavior from interaction among components, the behavior of a CAS is stratified in a hierarchy of active units (AUs), where an AU is a sort of DES involving a set of interconnected components that are modeled as communicating automata. The collective interaction among components within an AU gives rise to the occurrence of emergent events that may affect the behavior of a superior AU. This allows for the modeling of a system at different abstraction levels, where emergent events are the means of communication between different layers of the hierarchy. In order to speed up the online diagnosis task, model-based reasoning on deep knowledge of the CAS is performed offline. This results in a more abstract compiled knowledge, which is then exploited online by the diagnosis engine based on a given temporal observation of the CAS. The correctness (soundness and completeness) of the technique is formally proven.