Brought to you by EarthWeb
IT Library Logo

Click Here!
Click Here!

Search the site:
 
EXPERT SEARCH -----
Programming Languages
Databases
Security
Web Services
Network Services
Middleware
Components
Operating Systems
User Interfaces
Groupware & Collaboration
Content Management
Productivity Applications
Hardware
Fun & Games

EarthWeb Direct EarthWeb Direct Fatbrain Auctions Support Source Answers

EarthWeb sites
Crossnodes
Datamation
Developer.com
DICE
EarthWeb.com
EarthWeb Direct
ERP Hub
Gamelan
GoCertify.com
HTMLGoodies
Intranet Journal
IT Knowledge
IT Library
JavaGoodies
JARS
JavaScripts.com
open source IT
RoadCoders
Y2K Info

Previous Table of Contents Next


3.5. MODEL-BASED DIAGNOSIS

The requirements from diagnostic tasks have been a major driving force in developing MBR technology. The original motivation was presented in Section 2, and consisted of the dissatisfaction with purely heuristic diagnostic systems. Much of the early work on model-based diagnosis (MBD) was in the area of faultfinding of electronic circuitry. We can use an example from that domain to illustrate the reasoning strategies adopted in MBD (Faltings, 1996).

Consider a simple digital circuit, shown in Figure 1, comprising three multipliers and two adders. Values of measurements taken at various ports are shown.


FIGURE 1 Example circuit and measurements.

In a heuristic expert system for finding faults in the circuit, one would have rules like:

IF incorrect(F) AND incorrect(G) THEN faulty(M2) CF = 0.5

where CF is a certainty factor meaning that the rule is valid with 50% certainty. The rule will have been obtained from an expert who "guesses" that M2 is the culprit if both F and G outputs are faulty, since M2 is a common input point to both A1 and A2.

In an MBD approach, knowledge about the circuit would be expressed by models, for example:

IF multiplier(m, x, y, z) AND NOT faulty(m) THEN equal(x * y, z)

stating that if a multiplier has inputs x and y, output z, and is not faulty, then z = x * y. This is a universally true statement about the device. The diagnostic problem can now be stated as follows: find the set of faulty components (each such set is a candidate) such that the relations implied by the model are consistent with the observations. Usually, the initial observations are not sufficient to allow only a single solution to the diagnostic problem. For the device shown, the measurements

Inputs: A = B = C = 2, D = E = 3

Outputs: F = 8, G = 10

allow many different diagnostic candidates. Since F depends on A, B, C, and D through components M1, M2, and A1, and the result does not agree with the model, at least one component in the set {M1, M2, A1} must be faulty. Similarly, since G is also incorrect, at least one of {M2, M3, A2} must also be faulty. A diagnostic candidate is a combination of components that contains at least one element from the first set and one from the second. For example, all the following are candidates:

{M2}, {M1, M3}, ..., {M1, M2, M3, A1, A2}

In order to narrow down this set of candidates, an MBD system requires additional machinery to rank diagnostic candidates, and to decide on a strategy for taking measurements. For example, an initial ranking might select {M2} since a single fault is more likely than a multiple fault. The optimal next measurement is y. Since this again turns out to be false, we now know that M2 must be faulty, which also explains both other faults.

The example illustrates that reasoning capabilities required in MBD include:

  • Simulate or predict which observations are implied by the normal behavior of the target system. The qualitative simulation techniques described earlier have been used for this, as have other simulation techniques.
  • Record dependencies between internal model variables and predicted observations. In some implemented systems, assumption-based truth maintenance systems (de Kleer, 1986) have been used for this and the next reasoning capability.
  • Upon detection of unexpected actual observations, use the dependencies to identify (minimal combinations of) model assumptions that conflict with the observations.
  • In the presence of multiple candidates, propose a measurement strategy that will reduce the number of candidates as cost effectively as possible.

A typical representative for the dependency-recording approach to MBD is the GDE (General Diagnosis Engine) (de Kleer and Williams, 1987).

4. APPLICATIONS OF MBR

4.1. INTRODUCTION

In Section 2 on the history and background of MBR, we motivated model-based reasoning techniques by certain deficiencies in the "expert mining" approach to building expert systems, such as inability to reason about situations not covered by the expert's knowledge, lack of transparency, and difficult maintenance. Consequently, many examples exist for applying MBR techniques to real-world problems.

However, it must be admitted that MBR techniques are not as widespread and in general use as some would have expected 10 years ago. In particular, the applications seem to be in a limited number of problem domains. We therefore start this section by a brief overview of expert system application areas, and point to those where MBR seems to be most successful. Then we present some examples of applications in these areas: monitoring, control, and diagnosis.

4.2. WHERE IS MBR USED?

It is common to categorize expert system applications according to the tasks the perform. One such task list is:

  • Design: Create a new structure according to goals and constraints
  • Configuration: Combine elements according to goals and constraints
  • Prediction: Infer consequences of a situation
  • Planning: Create a sequence of actions from an initial state to a goal state
  • Monitoring*: Track and compare observations to expectations
  • Control*: Govern system behavior to meet goals
  • Diagnosis*: Infer system malfunctions from observations

Of the task categories on this list, by far the most examples of MBR techniques can be found in those that are marked by an asterisk. Before going into details of those application areas, a few remarks on the other areas are in order.

Using models in design is of course nothing new. Most engineering design of artifacts involves building and experimenting with a model (or models) of the artifact. Models are useful both in synthesis of new designs, and in analysis of existing or redesigned ones. Very sophisticated methods and tools exist for supporting the use of numerical and other "classical" models. So ingrained are these methods and tools that MBR (as we understand it here) may have problems of being recognized as adding new value. We think this is an explanation of the relative paucity of reported design applications of MBR, in spite of the plausibility of, e.g., using qualitative simulation to check out the behavior of a proposed new mechanism.

For the configuration and planning tasks, the situation is that AI has produced some very efficient methods, including constraint-based reasoning and partial-order planning. One could argue that these are model-based, in that they rely upon an explicit domain model. However, they are usually not categorized as MBR, and are therefore not included here.


Previous Table of Contents Next

footer nav
Use of this site is subject certain Terms & Conditions.
Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details.