Decentralized diagnosis: complexity analysis and Datalog encodings

Abstract

Diagnosis is an important field of Artificial Intelligence.<br />Recently, Console et al. proposed a framework for decentralized qualitative model-based diagnosis. The basic idea is to decompose a complex system into subsystems, each of which gets a local diagnoser assigned. The global diagnosis is computed by "asking" the local diagnosers, while some information may be private. However, some problems remained open, in particular a detailed complexity analysis and an implementation are missing. The goal of this work is to resolve some of these open problems. To this end, we introduce extended definitions, based upon which we will define several related problems and analyze their complexity. For each defined problem, an upper bound is presented.<br />Furthermore, we discuss slight modifications which allow us to prove the completeness of some problems. Using these theoretical results from the complexity analysis, we propose datalog encodings of the previously defined problems that match the complexity. Finally, the encodings are evaluated using the datalog system DLV.