Model-based diagnosis is a generally applicable, principled approach to the systematic debugging of a wide range of system types such as circuits, knowledge bases, physical devices, or software. Based on a formal description of the system, it enables precise and deterministic reasoning about potential faults responsible for observed misbehavior. In software, such a formal system description can often even be extracted from the buggy program fully automatically. As logical reasoning is central to diagnosis, the performance of model-based debuggers is largely influenced by reasoning efficiency, which in turn depends on the complexity and expressivity of the system description. Since highly detailed models capturing exact semantics often exceed the capabilities of current reasoning tools, researchers have proposed more abstract representations. In this work, we thoroughly analyze system modeling techniques with a focus on fault localization in spreadsheets—one of the most widely used end-user programming paradigms. Specifically, we present three constraint model types characterizing spreadsheets at different abstraction levels, show how to extract them automatically from faulty spreadsheets, and provide theoretical and empirical investigations of the impact of abstraction on both diagnostic output and computational performance. Our main conclusions are that (i) for the model types, there is a trade-off between the conciseness of generated fault candidates and computation time, (ii) the exact model is often impractical, and (iii) a new model based on qualitative reasoning yields the same solutions as the exact one in up to more than half the cases while being orders of magnitude faster. Due to their ability to restrict the solution space in a sound way, the explored model-based techniques, rather than being used as standalone approaches, are expected to realize their full potential in combination with iterative sequential diagnosis or indeterministic but more performant statistical debugging methods.

Model-based diagnosis aims at identifying the real cause of a system's malfunction based on a formal system model and observations of the system behavior. To discriminate between multiple fault hypotheses (diagnoses), sequential diagnosis approaches iteratively pose queries to an oracle to acquire additional knowledge about the diagnosed system. Depending on the system type, queries can capture, e.g., system tests, probes, measurements, or expert questions. As the determination of optimal queries is NP-hard, state-of-the-art sequential diagnosis methods rely on a myopic one-step-lookahead analysis which has proven to constitute a particularly favorable trade-off between computational efficiency and diagnostic effectivity. Yet, this solves only a part of the problem, as various sources of complexity, such as the reliance on costly reasoning services and large numbers of or not explicitly given query candidates, remain. To deal with such issues, existing approaches often make assumptions about the (i) type of diagnosed system, (ii) formalism to describe the system, (iii) inference engine, (iv) type of query to be of interest, (v) query quality criterion to be adopted, or (vi) diagnosis computation algorithm to be employed. Moreover, they (vii) often cannot deal with large or implicit query spaces or with expressive logics, or (viii) require inputs that cannot always be provided. As a remedy, we propose a novel one-step lookahead query computation technique for sequential diagnosis that overcomes the said issues of existing methods. Our approach (1) is based on a solid theory, (2) involves a systematic search for optimal queries, (3) can operate on implicit and huge query spaces, (4) allows for a two-stage optimization of queries (wrt. their number and cost), (5) is designed to reduce expensive logical inferences to a minimum, and (6) is generally applicable. The latter means that it can deal with any type of diagnosis problem as per Reiter's theory, is applicable with any monotonic knowledge representation language, can interact with a multitude of diagnosis engines and logical reasoners, and allows for a quality optimization of queries based on any of the common criteria in the literature. We extensively study the performance of the novel technique using a benchmark of real-world diagnosis problems. Our findings are that our approach enables the computation of optimal queries with hardly any delay, independently of the size and complexity of the considered benchmark problem. Moreover, it proves to be highly scalable, and it outperforms the state-of-the-art method in the domain of our benchmarks by orders of magnitude in terms of computation time while always returning a qualitatively as good or better query.

A common issue for companies is that the volume of product orders may at times exceed the production capacity. We formally introduce two novel problems dealing with the question which orders to discard or postpone in order to meet certain (timeliness) goals, and try to approach them by means of model-based diagnosis. In thorough analyses, we identify many similarities of the introduced problems to diagnosis problems, but also reveal crucial idiosyncracies and outline ways to handle or leverage them. Finally, a proof-of-concept evaluation on industrial-scale problem instances from a well-known scheduling benchmark suite demonstrates that one of the two formalized problems can be well attacked by out-of-the-box model-based diagnosis tools.

Model-based diagnosis is a powerful, versatile and well-founded approach to troubleshooting a wealth of different types of systems. Diagnosis algorithms are both numerous and highly heterogeneous. In this work, we propose a taxonomy that allows their standardized assessment, classification and comparison. The aim is to (i) give researchers and practitioners an impression of the diverse landscape of available techniques, (ii) allow them to easily retrieve and compare the main features as well as pros and cons, and (iii) facilitate the selection of the “right” algorithm to adopt for a particular problem case, e.g., in practical diagnostic settings, for comparison in experimental evaluations, or for reuse, modification, extension, or improvement in the course of research. Finally, we demonstrate the value and application of the taxonomy by assessing and categorizing a range of more than 30 important diagnostic methods, and we point out how using the taxonomy as a common guideline for algorithm analysis would benefit the research community in various regards.

Model-based diagnosis is a principled and broadly applicable AI-based approach to tackle debugging problems in a wide range of areas including software, knowledge bases, circuits, cars, and robots. Whenever the sound and complete computation of fault explanations in a given preference order (e.g., cardinality or probability) is required, all existing diagnosis algorithms suffer from an exponential space complexity. This can prevent their application on memory-restricted devices and for memory-intensive problem cases. As a remedy, we propose RBF-HS, a diagnostic search based on Korf’s seminal RBFS algorithm which can enumerate an arbitrary fixed number of fault explanations in best-first order within linear space bounds, without sacrificing other desirable properties. Evaluations on real-world diagnosis cases show that RBF-HS, when used to compute minimum-cardinality fault explanations, in most cases saves substantial space while requiring only reasonably more or even less time than Reiter’s HS-Tree, one of the most influential diagnostic algorithms with the same properties.

Model-based diagnosis aims at identifying the real cause of a system's malfunction based on a formal system model and observations of the system behavior. To discriminate between multiple fault hypotheses (diagnoses), sequential diagnosis approaches iteratively pose queries to an oracle to acquire additional knowledge about the diagnosed system. Depending on the system type, queries can capture, e.g., system tests, probes, measurements, or expert questions. As the determination of optimal queries is NP-hard, state-of-the-art sequential diagnosis methods rely on a myopic one-step-lookahead analysis which has proven to constitute a particularly favorable trade-off between computational efficiency and diagnostic effectivity. Yet, this solves only a part of the problem, as various sources of complexity, such as the reliance on costly reasoning services and large numbers of or not explicitly given query candidates, remain. To deal with such issues, existing approaches often make assumptions about the (i) type of diagnosed system, (ii) formalism to describe the system, (iii) inference engine, (iv) type of query to be of interest, (v) query quality criterion to be adopted, or (vi) diagnosis computation algorithm to be employed. Moreover, they (vii) often cannot deal with large or implicit query spaces or with expressive logics, or (viii) require inputs that cannot always be provided. As a remedy, we propose a novel one-step lookahead query computation technique for sequential diagnosis that overcomes the said issues of existing methods. Our approach (1) is based on a solid theory, (2) involves a systematic search for optimal queries, (3) can operate on implicit and huge query spaces, (4) allows for a two-stage optimization of queries (wrt. their number and cost), (5) is designed to reduce expensive logical inferences to a minimum, and (6) is generally applicable. The latter means that it can deal with any type of diagnosis problem as per Reiter's theory, is applicable with any monotonic knowledge representation language, can interact with a multitude of diagnosis engines and logical reasoners, and allows for a quality optimization of queries based on any of the common criteria in the literature. We extensively study the performance of the novel technique using a benchmark of real-world diagnosis problems. Our findings are that our approach enables the computation of optimal queries with hardly any delay, independently of the size and complexity of the considered benchmark problem. Moreover, it proves to be highly scalable, and it outperforms the state-of-the-art method in the domain of our benchmarks by orders of magnitude in terms of computation time while always returning a qualitatively as good or better query.

Given a system that does not work as expected, sequential diagnosis aims at suggesting a series of system measurements to isolate the true explanation for the system’s misbehavior from a potentially large set of possible explanations. To reason about the best next measurement, sequential diagnosis methods usually require a sample of possible fault explanations at each step of the iterative diagnostic process. The computation of this sample can be accomplished by various diagnostic search algorithms. Among those, Reiter’s HS-Tree is one of the most popular due to its desirable properties and general applicability. Usually, HS-Tree is used in a stateless fashion throughout the diagnosis process to (re)compute a sample of possible fault explanations per iteration, each time given the latest (updated) system knowledge including all so-far collected measurements. At this, the built search tree is discarded between two iterations, albeit often large parts of the tree have to be rebuilt in the next iteration, involving redundant operations and calls to costly reasoning services. As a remedy to this, we propose DynamicHS, a variant of HS-Tree that maintains state throughout the diagnostic session and embraces special strategies to minimize the number of expensive reasoner invocations. DynamicHS provides an answer to a longstanding question posed by Raymond Reiter in his seminal paper from 1987, where he wondered if there is a reasonable strategy to reuse an existing search tree to compute fault explanations after new system information is obtained. We conducted extensive evaluations on real-world diagnosis problems from the domain of knowledge-based systems—a field where the usage of HS-Tree is state-of-the-art—under various diagnosis scenarios in terms of the number of fault explanations computed and the heuristic for measurement selection used. The results prove the reasonability of the novel approach and testify its clear superiority to HS-Tree wrt. computation time. More specifically: (1) DynamicHS required less time than HS-Tree in 96 % of the executed sequential diagnosis sessions. (2) DynamicHS exhibited substantial and statistically significant time savings over HS-Tree in most scenarios, with median and maximal savings of 52 % and 75 %, respectively. (3) The relative amount of saved time appears to neither depend on the number of computed fault explanations nor on the used measurement selection heuristic. (4) In the hardest (most time-intensive) cases per diagnosis scenario, DynamicHS achieved even higher savings than on average, and could avoid median and maximal time overheads of over 175 % and 800 %, respectively, as opposed to a usage of HS-Tree. Remarkably, DynamicHS achieves these performance improvements while preserving all desirable properties as well as the general applicability of HS-Tree.

Statistical samples, in order to be representative, have to be drawn from a population in a random and unbiased way. Nevertheless, it is common practice in the field of model-based diagnosis to make estimations from (biased) best-first samples. One example is the computation of a few most probable fault explanations for a defective system and the use of these to assess which aspect of the system, if measured, would bring the highest information gain. In this work, we scrutinize whether these statistically not well-founded conventions, that both diagnosis researchers and practitioners have adhered to for decades, are indeed reasonable. To this end, we empirically analyze various sampling methods that generate fault explanations. We study the representativeness of the produced samples in terms of their estimations about fault explanations and how well they guide diagnostic decisions, and we investigate the impact of sample size, the optimal trade-off between sampling efficiency and effectivity, and how approximate sampling techniques compare to exact ones.

Various model-based diagnosis scenarios require the computation of most preferred fault explanations. Existing algorithms that are sound (i.e., output only actual fault explanations) and complete (i.e., can return all explanations), however, require exponential space to achieve this task. As a remedy, we propose two novel diagnostic search algorithms, called RBF-HS (Recursive Best-First Hitting Set Search) and HBF-HS (Hybrid Best-First Hitting Set Search), which build upon tried and tested techniques from the heuristic search domain. RBF-HS can enumerate an arbitrary predefined finite number of fault explanations in best-first order within linear space bounds, without sacrificing the desirable soundness or completeness properties. The idea of HBF-HS is to find a trade-off between runtime optimization and a restricted space consumption that does not exceed the available memory. In extensive experiments on real-world diagnosis cases we compared our approaches to Reiter's HS-Tree, a state-of-the-art method that gives the same theoretical guarantees and is as general(ly applicable) as the suggested algorithms. For the computation of minimum-cardinality fault explanations, we find that (1) RBF-HS reduces memory requirements substantially in most cases by up to several orders of magnitude, (2) in more than a third of the cases, both memory savings and runtime savings are achieved, and (3) given the runtime overhead is significant, using HBF-HS instead of RBF-HS reduces the runtime to values comparable with HS-Tree while keeping the used memory reasonably bounded. When computing most probable fault explanations, we observe that RBF-HS tends to trade memory savings more or less one-to-one for runtime overheads. Again, HBF-HS proves to be a reasonable remedy to cut down the runtime while complying with practicable memory bounds.

When ontologies reach a certain size and complexity, faults such as inconsistencies, unsatisfiable classes or wrong entailments are hardly avoidable. Locating the incorrect axioms that cause these faults is a hard and time-consuming task. Addressing this issue, several techniques for a semi-automatic fault localization in ontologies have been proposed and extensively studied. One class of these approaches involve a human expert who provides answers to system-generated queries about the intended (correct) ontology in order to reduce the possible fault locations. To suggest as informative questions as possible, existing methods draw on various algorithmic optimizations as well as heuristics. However, these computations are often based on certain assumptions about the interacting expert. In this work, we demonstrate that these assumptions might not always be adequate and discuss consequences of their violations. In particular, we characterize a range of expert types with different query answering behavior and show that existing approaches are far from achieving optimal efficiency for all of them. In addition, we find that the cost metric adopted by state-of-the-art techniques might not always be realistic and that a change of metric has a decisive impact on the best choice of query answering strategy. As a remedy, we suggest a new – and simpler – type of expert question that leads to a stable fault localization performance for all analyzed expert types and effort metrics, and has numerous further advantages over existing techniques. Moreover, we present an algorithm which computes and optimizes this new query type in worst-case polynomial time and which is fully compatible with existing concepts (e.g., query selection heuristics) and infrastructure (e.g., debugging user interfaces) in the field. Comprehensive experiments on faulty real-world ontologies attest that the new querying method is substantially and statistically significantly superior to existing techniques both in terms of the number of necessary expert interactions and in terms of the query computation time. We find that relying on the new querying method can save an interacting expert more than 80% of their work, and can reduce the expert’s waiting time for the next query by more than three orders of magnitude. Beside these findings, we demonstrate that the efficiency of existing query-based tools can be significantly boosted by suggesting an appropriate query answering strategy to an expert; we also make recommendations in this regard. Further, we suggest optimal configurations of a debugger for situations where the new type of query is used. Remarkably, the proposed approach is not only applicable to ontologies, but to any monotonic knowledge representation language, and can even be adopted to solve general model-based diagnosis problems expressible using Reiter’s theory.

Optimal production planning in the form of job shop scheduling problems (JSSP) is a vital problem in many industries. In practice, however, it can happen that the volume of jobs (orders) exceeds the production capacity for a given planning horizon. A reasonable aim in such situations is the completion of as many jobs as possible in time (while postponing the rest). We call this the Job Set Optimization Problem (JOP). Technically, when constraint programming is used for solving JSSPs, the formulated objective in the constraint model can be adapted so that the constraint solver addresses JOP, i.e., searches for schedules that maximize the number of timely finished jobs. However, also highly specialized solvers which proved very powerful for JSSPs may struggle with the increased complexity of the reformulated problem and may fail to generate a JOP solution given practical computation timeouts. As a remedy, we suggest a framework for solving multiple randomly modified instances of a relaxation of the JOP, which allows to gradually approach a JOP solution. The main idea is to have one module compute subset-minimal job sets to be postponed, and another one effectuating that random job sets are found. Different algorithms from literature can be used to realize these modules. Using IBM’s cutting-edge CP Optimizer suite, experiments on well-known JSSP benchmark problems show that using the proposed framework consistently leads to more scheduled jobs for various computation timeouts than a standalone constraint solver approach.

Various model-based diagnosis scenarios require the computation of the most preferred fault explanations. Existing algorithms that are sound (i.e., output only actual fault explanations) and complete (i.e., can return all explanations), however, require exponential space to achieve this task. As a remedy, to enable successful diagnosis on memory-restricted devices and for memory-intensive problem cases, we propose RBF-HS, a diagnostic search based on Korf’s seminal RBFS algorithm. RBF-HS can enumerate an arbitrary fixed number of fault explanations in best-first order within linear space bounds, without sacrificing the desirable soundness or completeness properties. Evaluations using real-world diagnosis cases show that RBF-HS, when used to compute minimum-cardinality fault explanations, in most cases saves substantial space (up to 98 %) while requiring only reasonably more or even less time than Reiter’s HS-Tree, one of the most widely used diagnostic algorithms with the same properties.

Reiter's HS-Tree is one of the most popular diagnostic search algorithms due to its desirable properties and general applicability. In sequential diagnosis, where the addressed diagnosis problem is subject to successive change through the acquisition of additional knowledge about the diagnosed system, HS-Tree is used in a stateless fashion. That is, the existing search tree is discarded when new knowledge is obtained, albeit often large parts of the tree are still relevant and have to be rebuilt in the next iteration, involving redundant operations and costly reasoner calls. As a remedy, we propose DynamicHS, a variant of HS-Tree that avoids these redundancy issues by maintaining state throughout sequential diagnosis while preserving all desirable properties of HS-Tree. Evaluations in a problem domain where HS-Tree is the state-of-the-art diagnostic method reveal stable and significant time savings achieved by DynamicHS.

Sequential Diagnosis methods aim at suggesting a minimal-cost sequence of measurements to identify the root cause of a system failure among the possible fault explanations, called diagnoses. Hitting set algorithms are often used by such methods to precompute a set of diagnoses serving as a decision basis for iterative measurement selection.We show that there are two natural interpretations of the sequential diagnosis problem and argue that (1) existing methods consider only the more general definition of the problem and that (2) tackling the more specific problem might suffice under assumptions commonly met in practice. Thus, we present StaticHS, a novel variant of Reiter’s hitting set tree usable for solving both formulations of the sequential diagnosis problem. Like Reiter’s algorithm, StaticHS is logics- and reasoner-independent and thus generally applicable to various (diagnosis) domains. Theoretical and empirical analyses show the significant superiority of StaticHS to an application of Reiter’s tree in terms of measurement costs when solving both types of sequential diagnosis problems.

When diagnosing a faulty system one is often confronted with a large number of possible fault hypotheses. Sequential Diagnosis (SD) techniques aim at the localization or identification of the ac- tual fault with minimal cost or effort. SD can be viewed as an Active Learning (AL) task where the learner, trying to find some target hypothesis, formulates sequential queries to some oracle, thereby e.g. requesting additional system measurements. Several query selection measures (QSMs) for de- termining the best query to ask next have been proposed for AL. To date, few of them have been translated to and employed in SD. In this work, we account for this and analyze various QSMs wrt. to the discrimination power of their selected queries within the diagnostic hypotheses space. As a result, we derive superiority and equivalence relations between these QSMs and introduce improved versions of existing QSMs to overcome identified issues. The obtained picture gives a hint about which QSMs should preferably be used in SD to choose a query from a pool of candidates. Moreover, we deduce properties optimal queries wrt. QSMs must satisfy. Based on these, we devise an efficient heuristic search for optimal queries. As (preliminary) evaluation results indicate, the latter is especially beneficial in applications where query generation is costly, e.g. involving logical reasoning, and hence a pool of query candidates is not (cheaply) available.

Model-Based Diagnosis (MBD) is a principled approach to fault localization in any type of system that can be described in a formal structured way. Knowledge Base Debugging (KBD) draws on concepts from MBD to find faults in a monotonic knowledge base. We show that KBD is a generalization of MBD in that any MBD problem can be reduced to a KBD problem and solutions of the former can be directly extracted from solutions of the latter. Moreover, we find that the sequential MBD problem is a special case of the sequential KBD problem in that the latter allows a user to provide more types of measurements. As a consequence of these results, KBD approaches can be applied to all systems amenable to MBD.

In this work we present strategies for (optimal) measurement computation and selection in model- based sequential diagnosis. In particular, assuming a set of leading diagnoses being given, we show how queries (sets of measurements) can be computed and optimized along two dimensions: expected number of queries and cost per query. By means of a suitable decoupling of two optimizations and a clever search space reduction the computations are done without any inference engine calls. For the full search space, we give a method requiring only a polynomial number of inferences and guarantee- ing query properties existing methods do not provide. Evaluation results using real-world problems indicate that the new method computes (virtually) optimal queries instantly independently of the size and complexity of the considered diagnosis problems.

Sequential diagnosis methods compute a series of queries for discriminating between diagnoses. Queries are answered by probing such that eventually the set of faults is identified. The computation of queries is based on the generation of a set of most probable diagnoses. However, in diagnosis problem instances where the number of minimal diagnoses and their cardinality is high, even the generation of a set of minimum cardinality diagnoses is unfeasible with the standard conflict-based approach. In this paper we propose to base sequential diagnosis on the computation of some set of minimal diagnoses using the direct diagnosis method, which requires less consistency checks to find a minimal diagnosis than the standard approach. We study the application of this direct method to high cardinality faults in knowledge-bases. In particular, our evaluation shows that the direct method results in almost the same number of queries for cases when the standard approach is applicable. However, for the cases when the standard approach is not applicable, sequential diagnosis based on the direct method is able to locate the faults correctly.

Effective debugging of ontologies is an important prerequisite for their broad application, especially in areas that rely on everyday users to create and maintain knowledge bases, such as the Semantic Web. In such systems ontologies capture formalized vocabularies of terms shared by its users. However in many cases users have different local views of the domain, i.e. of the context in which a given term is used. Inappropriate usage of terms together with natural complications when formulating and understanding logical descriptions may result in faulty ontologies. Recent ontology debugging approaches use diagnosis methods to identify causes of the faults. In most debugging scenarios these methods return many alternative diagnoses, thus placing the burden of fault localization on the user. This paper demonstrates how the target diagnosis can be identified by performing a sequence of observations, that is, by querying an oracle about entailments of the target ontology. To identify the best query we propose two query selection strategies: a simple "split-in-half" strategy and an entropy-based strategy. The latter allows knowledge about typical user errors to be exploited to minimize the number of queries. Our evaluation showed that the entropy-based method significantly reduces the number of required queries compared to the "split-in-half" approach. We experimented with different probability distributions of user errors and different qualities of the a priori probabilities. Our measurements demonstrated the superiority of entropy-based query selection even in cases where all fault probabilities are equal, i.e. where no information about typical user errors is available.