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.4. QUALITATIVE SIMULATION

In building expert system applications, we will be interested in using a model of a particular target system to support the reasoning behavior of the application. We therefore need effective reasoning techniques that can utilize the model. Here, we concentrate on the two types of techniques that are used: applications (viz. qualitative simulation) and model-based diagnosis.

Of course, simulation as understood in engineering or computer science presupposes a model, most often of the purely procedural, quantitative variety. This type of simulation has a role to play in expert system building, but most frequently in the form of components of hybrid systems, where for example an expert system helps to formulate the simulation model, or to interpret the simulation output. The model itself is usually not accessible to the expert system, due to its nondeclarative and closed representation. We will not delve into this type of architecture here, since it falls outside of what is normally called "model-based reasoning."

If the model belongs to the family of qualitative models described in the previous section, the situation is different. In this case, the model is declarative and can be reasoned about. Prominent among the reasoning requirements, is the ability to simulate and predict behavior. Using qualitative models for this capability means that we obtain less precision than we would have obtained if we had used a more accurate quantitative model. Why would one be willing to give up precision in simulation? Some possible reasons are:

  • The full quantitative model may be prohibitively computationally expensive to run, and the less precise results from the quantitative model may still be satisfactory for their intended use.
  • To develop the full quantitative model may be either impossible, due lack of knowledge, or unrealistic, due to the scope of the problem (e.g., a large-scale chemical plant). Again, a qualitative model may be viable and sufficient.
  • Especially in knowledge-based systems, we may wish to have models that correspond to common sense, rather than more abstract mathematical models. For example, this will facilitate explanation of simulation results to end-users.
  • Finally, qualitative models may produce simulation results that "collapse" related behaviors into principally different classes, while quantitative models always produce an exact "point" solution.

The actual algorithm used to perform qualitative simulation depends of course on the particular model formalism. In general, these algorithms perform some sort of iterative propagation of values, using the elements of the model (e.g., constraints) to direct the propagation. Each propagation step takes one qualitative state as input and produces its successor state (S). We will use QSIM (Kuipers, 1984) as an example. The main steps of the QSIM algorithm are repeated execution of the following steps (details in the reference):

  1. Select a qualitative state from among the active set of states for which successors need to be determined.
  2. Determine the set of transitions that are possible from the current state.
  3. For each constraint, generate the set of tuples of transitions of its arguments. Filter for consistency with the constraint.
  4. Perform pairwise consistency filtering of the sets of tuples associated with the constraints, making sure that adjacent constraints must agree on transitions involving a shared variable.
  5. Generate all possible global interpretations from the remaining tuples. If none is left, the behavior is inconsistent. Create new qualitative states resulting from each interpretation, and make them successors to the current state.
  6. Apply global filtering rules to the new qualitative states, and place any remaining states in the active set of states for which successors need to be determined.

QSIM has the property that it produces all possible behaviors, a very strong and useful property for gaining an understanding of a system's behavior. Unfortunately, QSIM may also produce additional spurious behaviors that are not consistent with any real possible behavior. This is due to a combination of locality of computation with qualitative model descriptions. Finally, QSIM is not guaranteed to halt, since it may create new successor states ad infinitum.

QSIM is perhaps the best developed of the qualitative simulation algorithms, and the one that is closest to practical application. It is fair to state, though, that the use of qualitative models for simulation has remained a somewhat academic discipline, with relatively few and still experimental real-word applications (but see Section 4 of this chapter).


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.