Theme 2 (old):
Qualitative Functional Reasoning

Abstract

A goal of this research is developing methods for learning function of devices from a qualitative description of their structure and behavior using functional reasoning. Qualitative Function Formation (QFF) technique is introduced. In QFF, a function concept is defined as an interpretation of a persistence or an order in the sequence of qualitative states, using trace of qualitative state vector derived by simulation on a qualitative model of a device. Examples of application of QFF in categorization and learning function of components in engineering design are given.

1. INTRODUCTION

Functional Reasoning (FR), in its common sense use, enables people to reason about the presence and function of objects in a containing system, derive the purpose of the system and explain how it can be achieved. Functional reasoning is used to explain goal directed behavior of objects [MURAKAMI88], [KIRIYAMA92]. Such explanation includes two components: causal and functional explanations [NAGEL77], [NAGEL77B]. Functional explanation accounts for:

1. the presence of a component in a system in terms of certain effects it has on that system;
2. functional explanation explains the purpose of a system in terms of its structure and behavior or functions of its components.

(1) refers to an explanation of the presence of some component in the system in terms of its contributions or certain effects that the component produces in the system [NAGEL77B], or in terms of some capacity that the component has and contributes to the capacity of the containing system [CUMMINS74]. (2) addresses the traditional teleological process of means and end [ALLAN52].

Function of a system is usually mentioned along with its behavior, goal and purpose, with respect to system's inner and outer environments [SIMON69]. Also it has strong connections with the notion of making efforts to obtain a certain result (mainly in man-made objects), or a certain future event [BIGELOW87]. In the representational viewpoint of function, which is central in AI, function of a system is addressed with reference to intention of humans.

The focus of this research is on developing Functional Reasoning (FR) techniques for deriving and explaining function of a device from a qualitative description of its structure and behavior through systematic generation and reasoning with such a model at various level of abstraction; and applying FR techniques to real world engineering problems such as functional design and diagnosis. Qualitative Function Formation (QFF) technique is developed and implemented to verify the ideas.

Specifically, we address the following engineering design problems.

1. Identification problem:
   Given an object, explaining its function using knowledge of structure and behavior of its component and their organization.
2. Explanation problem:
   Explaining presence of a component in a containing system in terms of its contribution to the overall function of the system.
3. Selection problem:
   Given a set of components, selecting the proper components that if used together can achieve a desired function.

2. QUALITATIVE FUNCTION FORMATION TECHNIQUE

Here we briefly introduce the Qualitative Function Formation (QFF) technique, its underlying assumptions and model.

2.1 Assumptions

Functionality in State Transition

Any physical concept can be explained in terms of histories [HAYES79] and states. Intuitively, a history that leads to a function displays a certain pattern [BIGELOW87]. A basic feature of state representation is that it assigns a certain characteristic to its referred device [MATTHEN88], therefore it is possible to define function concepts with reference to discovery of an order in the state sequence. The key idea is that a function concept emerges from discovering a persisted state or an ordered pattern in a sequence of states. This is called functionality in state transition.

In biological systems persistence is considered to be the most interesting characteristic and is believed to be governed by natural selection law. In man-made devices besides persistence other kinds of ordered patterns such as oscillation may also be considered.

Functionality in Component Pair

It seems that humans have a data base in which a device is associated with several functionalities. Some of the theories and systems have considered the function as a property of a single component of a device. However there are certain difficulties in both logical formulation (see [WRIGHT73]) and actual implementation (see [TEZZA88], etc.) of such theories. It is suggested that function can be ascribed to a pair of components instead of one (see [FORBUS87], etc.). This is called Functionality in Component Pair (FCP), stating that at least a pair of components are required to interact functionally.

2.2 Model

The qualitative model that we use in QFF is composed of a set of expressions involving three primitives: qualitative variables, ordinary- and coordinative- qualitative operations. Qualitative variables are counterpart of physical quantities, such as temperature and pressure, representing characteristics of the system's inner environment. Relation between the qualitative variables is defined by qualitative operations. Ordinary operations are monotonic increase (M⁺), monotonic decrease (M^-), positive influence (I⁺) and negative influence (I^-). Coordinative operations account for interactive or protocol-based interactions, such as when, until, set, reset, and default. The qualitative model is a set of expressions of either of the following forms:

[Y] = O[X] D [Lⁱ_N]
[Y] = O[X] D O[Z]

[Y], [X], [Z] and [N] are qualitative variables.
Lⁱ_N is the ith landmark value of [N].
O is an ordinary qualitative operation.

O= { M⁺, M^-, I⁺, I^- }

D is a coordinative operation (at this moment there are only 5 such operation, namely, when, until, set, reset and default).

• when operation: [Y] = O[X] when Lⁱ_N;
  implying that [Y] =O[X] only when the event Lⁱ_N is present.

• until operation: [Y] = O[X] until Lⁱ_N;
  implies that [Y] =O[X] until the event Lⁱ_N becomes absent.

• set operation: [Y] = O[X] set Lⁱ_N;
  implying that [Y] =O[X] only when setting [N] to Lⁱ_N.

• reset operation: [Y] = O[X] reset Lⁱ_N;
  implying that [Y] =O[X] only until resetting [N] to Lⁱ_N.

• default operation: [Y] = O[X] default O[Z];
  implying that [Y] =O[X], but only in case of [X] absent, then [Y]=O[Z].

The coordinative operations show a kind of data dependencies and can be processed in a different way than the ordinary simulation. Such dependencies can have only 4 possible types:

1. present (+1/-1): two events occur concurrently;
2. absent (0): two events do not occur concurrently;
3. true (+1): an event has occurred;
4. false (-1): an event has not occurred;

An algebra in which these 4 values can be represented by mod-3 integers is defined [BENVENISTE90]. Every qualitative variable, denoted by upper case characters such as w_CV1, has a pseudo- counterpart, denoted by lower case characters such as w_CV1, in this algebra. Each expression can be encoded in this algebra using temporal- and dependency- constraints.

A temporal constraint assigns the value (-1, 0, +1, +/-1) to a pseudo-qualitative variable, depending on being false, absent, true, or present, respectively.

A dependency constraint, on the other hand, derives the value for the related pseudo- qualitative variables as described in the model.

Table 1 depicts the temporal and dependency constraints for the coordinative operations. We will see later that only those operations that have their dependency constraint evaluated to (+1) can take part in the simulation [FAR92].

[X], [Y], [Z] and [N] are qualitative variables.
x, y, z and n are their mod-3 values (-1, 0, +1), respectively.
Lⁱ_N is the i^th landmark value of the variable [N].

Qualitative Flow Graph (QFG) is defined as a digraph embodying the qualitative model and temporal and dependency constraints. In QFG, nodes are qualitative variables and arcs are conditional ordinary qualitative operations, whose antecedents are dependency constraints. QFG shows indirect influences of qualitative variables.

QFG is represented by 4 sets:

QFG= {V, A, O, C}

V is the set of nodes standing for the qualitative variables.

A is the set of arcs relating the two nodes.

O is the set of qualitative operations.

C is the set of dependency constraints for coordinative qualitative operations given in Table 1.

All the arcs of the QFG are conditional. A conditional arc is:

A : {C --> O}

For each arc, A, if for C, E(C)= +1, then O is enabled.
E(C) is evaluation of the constraint C in mod-3.

Qualitative Processes (QPs) are defined as finite, connected, unidirectional string of arcs of the QFG, relating an input node to an output one. An input node is the one with an in-degree zero. Similarly, an output node is the one with an out-degree zero.

A key point is distinguishing the effects of an input node on the network of the overlapping processes. Using the conventional notion of process in qualitative reasoning, for each process a number of possible behaviors can be generated and removing the ambiguity is not trivial. In QFF processes are extracted from the QFG by decomposition, i.e., the merging nodes and the succeeding shared nodes and arcs between two processes are assigned to both.

This is a requirement in QFF because the direct consequences of a certain process and its effect on the behavior of the whole system should be distinguished first, and then combined behavior of the process derived. This is where QFF departs from the main stream of the other qualitative techniques.

Behavioral Fragment (BF) is the characteristic behavior of a qualitative process and is defined as the record of landmark values for the displayed qualitative variables belonging to that process.

Behavioral fragment BF_Pj of a process P_j, is a finite sequence of landmark values (L^k_V), of the form:

L^k_V is the kth landmark value of the qualitative variable [V],

BFs are derived by qualitative simulation in two steps:

• Dependency constraint satisfaction on the arcs of the processes.
• Landmark value identification of the qualitative variables.

First, the simulator looks for the antecedents of the conditional arcs that can satisfy the given situation. Through temporal and dependency analysis one can verify which of the arcs of the processes are activated, i.e., the mod-3 value of its dependency constraint is (+1), and can take part in simulation. Then processes whose enabling conditions of their arcs are not yet satisfied are deleted and a conventional simulation program derives landmark values for each variable of the remaining processes. BFs are sequences leading to a function concept.

2.3 Function

A Function concept can be derived if a repetition cycle or an order (e.g., persistence, etc.) is detected on BF sequences. A function F has two attributes:

1. Operationality: the enabling conditions for the arcs of a process whose BF leads to the function.

2. Repetition cycle: for the behavioral fragment $BF_Pj of the process P_j, the repetition cycle is a finite sequence of landmark values (L^k_V), of the form:

F is a function concept.
S is a repetition cycle.
i and j are indices for landmark values. If i=j, the cycle is a persistence.
L^k_V is the k^th landmark value of the qualitative variable [V].

The repetition cycle or persistence can be derived for each of the variables, therefore different cycles can possibly be detected and each cycle may represent a function concept from a different viewpoint. The function derived by QFF is a direct consequence of the user interacting with the network representation of the underlying physical model of the device and physical constraints. This is a very useful characteristic of the technique and can be used directly in functional design. Particularly, by recording the goal(s) of the user on each step and comparing it with the derived function, one can easily verify whether the arrangement can satisfy the intended goal(s) of the user.

3. FUNCTIONAL DESIGN USING QFF

Here is an illustrative example of a pressure tank system in an oil refinery, parts of which shown in Figure 1. We use QFF to identify function of the components (i.e., identification problem) and explaining why a component is used in the design (i.e., explanation problem).

In this system, there are 4 tanks used to separate materials in a mixture of supplied material to T₂ through CV6. For the sake of easier understanding let's consider a portion of the system composed of tanks T₁ and T₂.

The core idea of the design in narrative form is:

Pressure in T₂ is controlled by the settings of CV4 and CV5. The overall amount of the two phase material (material A and B) in T₂ is controlled by CV1 and CV2. The pressure in T₁ is controlled by CV4. The level of material in T₁ is controlled by CV1 and CV3.

Figure 1: The pressure tank system.

3.1 Example 1: Identification of functions

This is a brief example showing how function of a pair of components can be derived from their qualitative model. Let's consider a portion of the system, composed of the object pair CV1 and T₁. The relation between them is constrained by rules of flow and conservation besides the set points given by the designer,

[F₁] = [G₁] = M⁺[w_CV1] set ( w_CV1 > 0)

[F_in/T1] = M⁺[G₁] set ( w_CV1 > 0)

[F_T1] = M⁺[F_in/T1]

[H_T1] = I⁺[F_T1]

[F₁] and [G₁] stand for the flow-in and flow-out for the valve CV1.
[F_in/T1] is material flow-in for T₁.
[F_T1] is the net flow and [H_T1] is the level of material in T₁.

Temporal constraints are given below and dependency constraints are shown in Figure 2.

Figure 2: Dependency constraints for Example 1.

f²₁ = g²₁ = w²_CV1(-w_CV1- w²_CV1)
f²_in/T1 = g²₁(-w_CV1- w²_CV1)
f²_T1 = f²_in/T1
hT₁² = f_T1²

Qualitative process for this system is shown in Figure 2.

Behavior of the component pairs can be derived, for the set point (w_CV1 > 0). In temporal constraint terms this means that:

w_CV1= 1

By inserting its value in temporal constraints, one can derive that:

h_T1² = f_T1² = f_in/T1² = f²₁= g²₁= 1

This means that conditions for the arcs of this process are evaluated to 1, implying that all the arcs are active and can take part in the simulation. Simulation results are:

BF_P1 : { (w_CV1>0) --> (F_T1>0) --> (H^o_T1 < T₁ <= H_(T1)max) --> (H_T1 = H_(T1)max) }

This implies that the level of material in the tank will increase up to the maximum allowable level. The function of the pair (CV1, T₁) can be derived using the cycle detection algorithm. Clearly the persistence in the level of material in the tank is detectable, therefore, the function of this pair is to maintain the level at the H_(T1)max, that may be called FULL . Note that the term FULL is just a reference term, whose functionally relevant meaning is described by the landmark value H_(T1)max for the pair.

FULL :   H_T1=H_(T1)max

Similarly for the pair (CV3, T₁) and for the set point (w_CV3 > 0), one can derive that the level of material in the tank will decreases till the minimum level and the function of this pair is to make the tank EMPTY, described by,

EMPTY :   H_T1=H_(T1)min

3.2 Example 2: Explanation of functions

The reason for a component being selected to be a part of the designed system is explained in terms of its contribution to the desired function of the system. Again simulated behavior of the processes exhibits the way the components contribute to the functionality of the system.

Let's consider the system of Figure 1 and explain the why a given control valve, such as CV2, is used in this design. The model embodying the valve CV2 is:

[U₁] = M⁺[w_CV2] set (w_CV2 > 0)
[H_B/T2] = I^-[U₁] set (w_CV2 > 0)
[F_out/T2] = I⁺[U₁]
[H_T2] = M⁺[H_B/T2]
[K₁] = [U₁]

[U₁] and [K₁] are the flow-in and flow-out for CV2 whose state variable is [w_CV2].
[H_T2] is the overall level of material in T₂.
[F_out/T2] is the flow of material from T₂ and T₁.
[H_B/T2] is the level of B material in T₂.

The temporal constraints are:

u²₁ = w²_CV2(-w_CV2 - w_CV2)
h²_B/T2 = u²₁(-w_CV2 - w_CV2)
f²_out/T2 = u²₁
h_T2² = h_B/T2²
u₁² = k₁²

CV2 appears in three processes P₂, P₃ and P₄.

Dependency constraints in this case are given in Figure 3.

Again for the set point (w_CV2 > 0), or in temporal constraint terms (w_CV1 = 1), all the arcs are active and behavior of the processes are:

Figure 3: Dependency constraints for Example 2.

<2'> : u²₁(-w_CV2 -w²_CV2)

<3'> : h²_T2

<4'> : f²_out/T2

BF_P2 = { (w_CV2 > 0) --> (U₁ > 0) --> (0out/T₂ =< F_(out/T2)max) --> (F_out/T2 = F_(out/T2)max) }

BF_P3 = { (w_CV2 > 0) --> (U₁ > 0) --> (H_(T2)min =< H_T2o_T2) --> (H_(T2)min = H_T2) }

BF_P4 = { (w_CV2 > 0) --> (U₁ > 0) --> (K₁ > 0) }

When CV2 is opened, BF_P2 indicates that the flow of material out of T₂ (F_out/T2) can increase to its maximum level, and BF_P3 indicates that level of material in T₂ decreases to minimum. BF_P4 indicates that it helps material transfer to the reservoir tank. In qualitative terms, the effects of CV2 in the system are:

CV2 : { (F_out/T2 = F_(out/T2)max)   and   (H_(T2)min = H_T2)  and  (K₁ > 0) }

The reason of using CV2 in the system can be explained in terms of these three:

CV2 can ease the flow of material out of T2, reduce the level of material in this tank and transfer material to the reservoir tank.

3.3 Example 3: Selection of components

Yet another goal of the designer is maintaining the level of material in tank T2, for safety purposes. An arrangement of the components that can contribute to this is to be derived. The design specification in qualitative terms is given below.

GA = (H_(T2)Fix =< H_T2)
[F₁] = [G₁] = M⁺[w_CV1] set   ( w_CV1 > 0)
[U₁] = [K₁] = M⁺[w_CV2] set   ( w_CV2 > 0)
[S₁] = [E₁] = M⁺[w_CV6] set   ( w_CV6 > 0)
[F_in/T2] = M⁺[E₁] until   GA
[H_T2]d = I⁺[F_in/T2]
[H_A/T2] = I^-[G₁] when   GA
[H_B/T2] = I^-[U₁] when   GA
[H_T2] = M⁺[H_A/T2] + M⁺[H_B/T2]

[U₁], [K₁], [S₁] and [E₁] stand for the flow-in and flow-out for CV2 and CV6.
[w_CV1], [w_CV2] and [w_CV6] denote state variables of the valves.
[F_in/T2] is the flow of material into T₂.
[H_T2] is the overall level of material in T₂.
[H_A/T2] and [H_B/T2] are level of material of type A and B in T₂.
H_(T2)Fix is the desired level of the tank T₂.

This model is examined for validity. The temporal constraints are given below:

f²₁ = g²₁ = w²_CV1(- w_CV1- w²_CV1)
u²₁ = k²₁ = w²_CV2(- w_CV2- w²_CV2)
s²₁ = e²₁ = w²_CV6(- w_CV6- w²_CV6)
f_in/T2² = e²₁(- ga )
h_T2² = f_in/T2²
h_A/T2² = g²₁(- ga - ga²)
h_B/T2² = u²₁(- ga - ga²)
(h_T2² = h_A/T2²) or (h_T2² = h_B/T2²)

Dependency constraints are shown in Figure 4.

In this case some of the arcs in Figure 4 are not active due to the settings. Let's assume that there is no other design preference and verify which of the components are crucial to this arrangement.

Deleting CV6 and the process P₇ implies that the no process will be active when (ga =-1). Even if (ga =1), P₅ and P₆ become active and simulation and cycle detection verify that they both lead to the EMPTY function.

On the other hand, it can easily be shown that deletion of CV1 or CV2 (P₅ or P₆), but not both, can lead to the proper functioning. Therefore CV1 and CV2 are redundant for the given function. Let's add another preference that the level of B-liquid should not exceed a given level (in order to ensure that A-liquid cannot leak to the next tank). This adds the following expressions to the model.

Figure 4: Dependency constraints for Example 3.

TH = (H_B/T2 =< H_(B/T2)lim)

[H_B/T2] = { I^-[U₁] when GA } until TH

Additional temporal and dependency constraints are:

h_B/T2² = u²₁(- ga - ga²)(- th )

u²₁(- ga - ga²)(- th ) : [U₁] --> I^- --> [H_B/T2]

Here when GA is true (ga =1), the process P₆ becomes active and P₇ is inactive. This ensures the level will be maintained. But P₅ can be active only when TH is false (th =-1). Only in such case, it can help P₆ to regulate the level of material in T₂. Now the valves CV1 and CV2 contribute to the functionality of the system in different ways and cannot be deleted from the design. This example clearly shows that how additional goals of the designer can be incorporated in the model and how they affect the decisions.

4. Implementation

QFF is implemented in the experimental design system, QFF2, focusing on automating design verification by shifting the decisions and modifications to the higher design levels.

QFF2 is composed of:

1. a data translator for converting specified device model to frame data structure and vice-versa;
2. an implementation of QFF algorithm along with a qualitative simulator, customization and learning modules;
3. domain-oriented library of component models that is used for selecting a proper device model and customizing it; and
4. a window-based user interface that allows a user interactively select arrangement of components, and view simulation results.

5. CONCLUSION

This report places functional reasoning (FR) in the context of other common sense theories by putting together the results of diverse FR researches in a variety of disciplines.

Qualitative Function Formation (QFF), a technique for deriving a function from a qualitative model is introduced. This puts together the viewpoints on qualitative model, behavior and function, allowing systematic derivation of function from structure and behavior. QFF has been successfully tested and used in engineering design, tool utilization [FAR92] and fault diagnosis[FAR93].

REFERENCES

1. [ALLAN52]
   D.M. Allan, Towards a Natural Teleology, J. of Philosophy, vol. 49, pp. 449-459, 1952.

2. [BENVENISTE90]
   A. Benveniste and P. LeGuernic, Hybrid Dynamical Systems Theory and the SIGNAL language, IEEE Trans. Automatic Control, vol. 35, no. 5, pp. 535-546, May 1990.

3. [BIGELOW87]
   J. Bigelow and R. Pargetter, Functions, J. of Philosophy, vol. 84, no. 4, pp. 181-197, 1987.

4. [CUMMINS74]
   R. Cummins, Functional Analysis, J. of Philosophy, vol. 72, no. 20, pp. 741-765, 1975.

5. [FAR92]
   B.H. Far, Functional Reasoning, Explanation and Analysis, Technical Report JAERI-M 91-225, Japan Atomic Energy Research Institute, Jan. 1992.

6. [FAR93]
   B.H. Far and M. Nakamichi, A Subjective Approach to Qualitative Fault Diagnosis in System with Nonintermittent Concurrent Faults, IEEE Trans. System, Man, Cybernet., vol. SMC-23, no. 1, pp. 14-30, 1993.

7. [FORBUS87]
   K.D. Forbus, P. Nielsen and B. Faltings, Qualitative Kinematics: A Framework, in Proc. 10th Int. Joint Conf. on Artif. Intell. (IJCAI' 87), Milan, Italy, 1987, pp. 430-435.

8. [HAYES79]
   P. Hayes, The Naive Physics Manifesto, in Phil. of Artif. Intell., M.A. Boden, ed., Oxford Univ. Press, 1990, ch. 8.

9. [KIRIYAMA92]
   T. Kiriyama, T. Tomiyama and H. Yoshikawa, Qualitative Reasoning in Conceptual Design with Physical Features, in Recent Advances in Qualitative Physics, B. Faltings and P. Struss, eds., MIT Press, 1992, pp. 375-386.

10. [MATTHEN88]
    M. Matthen, Biological Functions and Perceptual Content, J. of Philosophy, vol. 85, pp. 5-27, 1988.

11. [MURAKAMI88]
    T. Murakami and N. Nakajima, Computer-Aided Design- Diagnosis Using Feature Description, in Artif. Intell. in Engineering: Diagnosis and Learning, J.S. Gero, ed., Elsevier, 1988, pp. 199-226.

12. [NAGEL77]
    E. Nagel, Teleology Revisited: Goal Directed Processes in Biology and Functional Explanation in Biology, J. of Philosophy, vol. 74, no. 5, pp. 261-301, 1977.

13. [NAGEL77B]
    E. Nagel, Teleology Revisited: Functional Explanation in Biology, J. of Philosophy, vol. 74, no. 5, pp. 280-301, 1977.

14. [SIMON69]
    H.A. Simon, The Sciences of the Artificial, MIT Press, 1969.

15. [SORABJI64]
    R. Sorabji, Function, Phil. Quarterly, vol. 14, no. 57, pp. 289-302, October 1964.

16. [TEZZA88]
    T. Tezza and E. Trucco, Functional Reasoning for Flexible Robots, in Artificial Intelligence in Engineering: Robotics and Processes, J.S. Gero, ed., pp. 3-19, Elsevier, 1988, pp. 3-19.

17. [WRIGHT73]
    L. Wright, Functions, Phil. Review, vol. 82, no. 2, pp. 139-168, April 1973.