Qualitative Reasoning and EndState

Introduction to Qualitative Reasoning

To be completed.

Background

To be completed.

EndState

Application of QR to EndState

The goal being to discover dependencies and correlations arising from the interconnection of different commodity flow models, the application of QR aims to generate a simple (i.e. qualitative) scenario to understand these interactions. The basic premise is: the interactions among the different submodels do not require of a high fidelity simulation to me distinguishable, and once they have been discovered, they can be further displayed with the help of more accurate simulators. The area of Qualitative Reasoning is especially well suited for this task, since infinite amounts of possible scenarios can be grouped in a single qualitative behavior. QR also allows us to focus no the quantities that make a difference, which will become the landmark values of the model. The simulation becomes tractable, as the numerous different numerical simulations are packed in a single behavior.

One of such networks under consideration is shown in the figure below:

It shows the flow of Energy, Oil and Coal between two major cities, CoalVille and PortVille. An important abstraction is that of a node as a consumer and producer of commodities. Furthermore, given a node N, and a commodity C, the following constraints can be derived by reasoning qualitatively:

• The amount of commodity C (which we will call amount) is a positive integer. This is trivial except for the fact that it bounds to the interval (0,inf) (where inf represents positive infinity) the values that it can take. This in turn makes 0 a landmark value for the variable. It can be further refined if we say that the domain of amount is the interval (0,max-amount) where max-amount is the maximum capacity of the node for certain commodity.
• Three other variables that we use in order to state all of the proper constraints follow similar restrictions, in-flow, out-flow, net-flow, (the in, out and net flows of commodity C on node N).
• Not knowing the amount of each of these variable, we can still infer that the amount of commodity C in node N increases when the net flow increases, stays constant when it is zero and decreases otherwise. That is the same as saying that there is a monotonically increasing function M+ that relates amount and net-flow: net-flow = M+(amount).
• Also, by definition, the net amount of commodity C that goes through node N is the addition of the in and out flow.
• Finally, the net flow of commodity C inside the node represents the rate of change of the amount of the commodity, or that the derivative of amount with respect to time equals net-flow.

The previous constraints all have to do with the node itself, in isolation from the network. Once we considered two nodes of the network, N1 and N2, and the flow of commodity C among them (from N1 to N2), then one more simple constraint can be added (under the assumption that we ignore any other connections these nodes may have):

• The amount of C that flows out of N1 is equal to the amount that flows into N2.

Given a network of nodes with any number of commodities flowing among them, the state of the netweork will be fully represented by three of variables for each node shown above (that is the amount, the in-flow and the out-flow). Since we Are only interested in landmark values of these variables, that are going to define qualitative state, those landmark values have to be defined. Normally, some exogenous variables get a landmark value, and values such as the maximum capacity of the node for a certain commodity and the maximum capacity of flow between two nodes will also receive a landmark value. Zero is almost always a landmark value on its own merit. It is also possible that as a simulation takes place, there are new landmark values introduced (such as "the amount that was present in node 2 when the pipeline between node 1 and 2 reached its maximum capacity". A qualitative state consists of qualitative values, and a qualitative value is defined by a qualitative magnitude and a direction (or obsence of) of change ([Kuipers:1994]). A valid qualitative value for the amount variable could be <(0,max),inc>, which means the quantitative value of amount is somewhere between 0 and its maximum possible value, and it is increasing. There are four possible successors for such a state: either <(0,max),inc> (the same), <(0,max),std> (the quantity is still within the same interval, but the direction of change is now steady), <max,inc> or <max,std>.

The case where a certain commodity C1 is consumed to be transformed in another commodity C2 (the case of coal being consumed to produce energy) yields more constraints, namely, there is a monotonically decreasing relation between the consumption of commodity C1 and the production of C2.

Very Simple Qualitative Model for EndState

The image below shows a very simple model, where Coal is extracted from the ground at the CoalVille Mine factory, then it is consumed at the CoalVille PowerPlant and finally the produced Electric Energy is sent to the city in order to be consumed. If we assume the demand for energy in the city can absorb all the Electric Energy being produced, we can explore the possible behaviors for the system.

If we set up an scenario where all of the nodes are empty and there is a constant stream of coal coming from the mine, by using all the previous constraints and a constraint satisfaction algorithm we are able to derive a unique single qualitative state, which is shown below:

As time goes by, the amount of Coal in the mine increases, the net flow decreases (since at the start point the out flow was zero). The net amount of Coal at the power plant increases as Coal starts arriving and all the other quantities stay constant (at zero as it happens).

The Qualitative Simulator produces a tree of possible behaviors, depending on what constraints are met and which ones are not. At the time step 1, a state tree will look like:

This unique behavior is represented as:

Which is what would expect, as the Coal flows from the mine to the Power Plant, the amounts of everything start increasing in the different nodes. The final state tree is shown below:

This tree contains some incosistent branches. These can occur when a possible next state of the simulation is pruned by some restricting constraint. So although the tree looks complex, there is only one possible behavior, as we would have expected:

What the behavior shows is that as time goes by all the amounts in the nodes start increasing up to the point where an equilibrium is reached and from then on, all the states are qualitatively the same one.

Qualitative Reasoning and Prediction

After completing a Qualitative Simulation we will have a description of all possible behaviors of the system. All of the behaviors may be analyzed to achieve a subset of those that comply with the expected end state. At the same time, each of those behaviors contain a qualitative description of the behavior of the network in order to achieve that end state. Those behaviors may contain desirable and undesirable side effects, which can in turn be analyzed. In practice, those desirable effects that take place would be part of the expected end state if we did know about them prior to performing the simulation. The same statement holds for the negation (or absence of) the undesirable effects. The advantage of a Qualitative Simulation is the abstraction of all those effects into a tractable amount of behavior, where they can be understood. Refining the end states expected and more qualitative simulation can bring the selection of interventions in the network to a small set (small in some sense). The size of the solutions, and the way in which they are presented make for a system that is easy to explain and comprehend, opposed to heavily numeric simulators.

Behaviors can be achieved in different ways. And they can also be used for different purposes. One of such is understanding how and when the system reaches equilibrium, as in the simple example shown before. Even more interesting might be to assume there is an equilibrium and see what a perturbation does to it. Assuming and creating an equilibrium is specially easy in QR, since we are not worried about the numeric magnitude of certain quantities, only about its qualitative behavior. An equlibrium is then described by some variables that have a steady state, and the steady state propagates according to the constraints defined. Once this is in place, perturbing the system can be done by changing the direction of change of one or more variables, and/or setting some variables to a landmark value. This is an effective way of testing the result of perturbations to the system. For example, cutting the flow of coal from one city to the other can be achieved by setting the rate of flow to zero across that edge.

Another interesting use of Qualitative Reasoning is for explanation generation. The reduced number of behaviors and its qualitative nature are naturally conducent for plugging into a system that generates explanations.

Explanation Generation

See [Kumar:2000], [Liu:1993] and [Lester:1997].

References

[Falkenhainer, 1990]

Falkenhainer, B. A Unified Approach to Explanation and Theory Formation. Computational Models of Scientific Discovery and Theory Formation. Morgan Kaufmann Publishers, San Mateo, CA. 1990 (HTML, PDF, PS).

[Forbus, 1984]

Forbus, Kenneth D. Qualitative Process Theory. Artificial Intelligence, 24 PP. 85-168, 1984

[Forbus, 1988]

Forbus, Kenneth D. Introducing Actions into Qualitative Reasoning Report No. UIUUCDCS-R-88-1452 Qualitative Reasoning Group, Department of Computer Science, University of Illinois. 1988

[Iwasaki, 1986]

Iwasaki, I. and Simon H. Causality in Device Behavior. Artificial Intelligence, 29 PP. 3-32, 1986

[Koning, 1995]

Koning, K. and Bredeweg, B. Qualitative Reasoning in teaching systems: means or end? The use of Qualitative Reasoning techniques in interactive learning envionments. AIED'95.

[Liu:1991a]

Liu, Zheng-Yang (with Arthur M. Farley), 1991. Structural Aggregation in Common-Sense Reasoning. Proceedings of the Ninth National Conference on Artifical Intelligence. pp. 868-873, AAAI, Anaheim, CA, July 1991. (HTML).

[Liu:1991b]

Liu, Zheng-Yang, 1991. Tailoring Tutorial Explanations via Model Switching. Proceedings of the 1991 Conference on Intelligent Computer-Aided Training. pp. 383-403, Houston, TX November 1991. (HTML).

[Kuipers:1994]

Kuipers, Benjamin J., 1994. Qualitative Reasoning: Modeling and Simulation with Incomplete Knowledge. MIT Press, Cambridge, MA. (HTML).

[Nayak, 1993]

Nayak, P, 1993 Order of Magnitude Reasoning using Logarithms Proceedings of &th Int. Workshop on Qualitative Reasoning Orcas Island, WA.

Unpublished Copyright © 1999-2000, SRI International