Incorporating Action into Diagnostic Problem Solving (An Abridged Report)

AAAI Conferences

Reasoning about action and change is integral to the diagnosis, testing and repair of many artifacts, and yet there is no formal account of diagnostic problem solving which incorporates a theory of action and change. In this abridged report, we provide a situation calculus framework for diagnostic problem solving. Using this framework, we present results towards a characterization of diagnosis for behaviorally static systems whose state can be affected by events which occur in the world, and which require world-altering actions to achieve tests and repairs. Diagnosis is defined more broadly in terms of what happened in addition to the traditional conjccture of what is wrong. Observations of events and actions in the world are used to diagnose some system malfunctions. By developing our characterization in terms of the situation calculus, we are able to contribute towards a formal characterization and semantics for this broader notion of diagnosis, testing and repair, in addition to dealing formally with issues such as the frame problem.

How Many Diagnoses Do We Need?

AAAI Conferences

A known limitation of many diagnosis algorithms is that the number of diagnoses they return can be very large. This raises the question of how to use such a large set of diagnoses. For example, presenting hundreds of diagnoses to a human operator (charged with repairing the system) is meaningless. In various settings, including decision support for a human operator and automated troubleshooting processes, it is sufficient to be able to answer a basic diagnostic question: is a given component faulty? We propose a way to aggregate an arbitrarily large set of diagnoses to return an estimate of the likelihood of a given component to be faulty. The resulting mapping of components to their likelihood of being faulty is called the system's health state. We propose two metrics for evaluating the accuracy of a health state and show that an accurate health state can be found without finding all diagnoses. An empirical study explores the question of how many diagnoses are needed to obtain an accurate enough health state, and a simple online stopping criterion is proposed.


AAAI Conferences

We describe IRS, a program that combines partialorder planning with GDE-style, model-based diagnosis to achieve an integrated approach to repair. Our system makes three contributions to the field of diagnosis. First, we provide a unified treatment of both information-gathering and state-altering actions via the UWL representation language. Second, we describe a way to use part-replacement operations (in addition to probes) to gather diagnostic information. Finally, we define a cost function for decision making that accounts for both the eventual need to repair broken parts and the dependence of costs on the device state.

Knowledge-Based Decision Model Construction for Hierarchical Diagnosis: A Preliminary Report Artificial Intelligence

Numerous methods for probabilistic reasoning in large, complex belief or decision networks are currently being developed. There has been little research on automating the dynamic, incremental construction of decision models. A uniform value-driven method of decision model construction is proposed for the hierarchical complete diagnosis. Hierarchical complete diagnostic reasoning is formulated as a stochastic process and modeled using influence diagrams. Given observations, this method creates decision models in order to obtain the best actions sequentially for locating and repairing a fault at minimum cost. This method construct decision models incrementally, interleaving probe actions with model construction and evaluation. The method treats meta-level and baselevel tasks uniformly. That is, the method takes a decision-theoretic look at the control of search in causal pathways and structural hierarchies.

Diagnosing Dynamic Systems in A-Prolog Michael Gelfond

AAAI Conferences

The main goal of this paper is to continue the investigation of applicability of A-Prolog (a loosely defined collection of logic programming languages under the answer set semantics (Gelfond & Lifschitz 1991)) knowledge representation and reasoning. In the first part of the paper we address the problem of diagnosing faulty behavior of a dynamic system. We are especially interested in such classical aspects of this problem as modeling of systems and their environments, interleaving of deliberation and action, and prioritizing typical causes of specific faults. We start with suggesting a new version of a definition of diagnosis. The roots of our definition go back to (Reiter 1987) and its recent modifications (Thielscher 1997; Band, McIlraith & Son 2000) which take into account the dynamics of system's behavior.