Automated Qualitative Domain Abstraction

1 Introduction

Model-based systems ([Hamscher et al., 1992; Weld and de Kleer, 1990]) represent knowledge about the structure and be­ havior of a physical system in terms of a behavior model, and use it to support engineering tasks such as behavior pre­ diction, diagnosis, planning and testing. When constructing model-based systems, one of the most difficult parts is mod­ eling the device. A fundamental idea to support and facilitate modeling is to compose models from model fragments, that is, re-usable elements of knowledge about a device that can be organized in a library ([Falkenhainer and Forbus, 1991]). This requires that model fragments have to be formulated, as far as possible, in a generic way and independent of their specific application context. However, it also means that in­ formation about the task a model will be used for cannot be anticipated in the model fragments.

But a model needs to be suited for the problem-solving task at hand in order to provide an effective and efficient solution to it. Using always the most accurate and most detailed model available may make the respective problem­ solving task intractable, or at least unnecessarily complex and

Peter Struss

TU Miinchen, FakuWit fiir Informatik 85748 Garching, Germany

struss@ in. tum. de

resource-consuming. For instance, for the task of diagnosing a device in an on-board environment, it is crucial to have a model that focuses only on those aspects that are essential to the goal of discriminating between its normal and faulty be­ havior. Any unnecessary details that are not relevant to this task impair its ability to meet the stringent time and space re­ quirements of this application. In general, models straightfor­ wardly composed from a library tend to be either inefficient, because they are overly detailed (that is, too fine-grained), or ineffective, because they are not detailed enough (that is, too coarse-grained) for the task they will be used for.

The approach pursued in this paper is therefore to auto­ matically re-formulate a behavior model, after it has been composed, to a level of abstraction that is adequate for the specified task. We focus on the abstraction of the domains of variables, that is, the problem of deriving sets of meaningful qualitative values. Although some work has been carried out on finding qualitative values within a specific context, such as simulation ([Kuipers, 1986]), the general problem of charac­ terizing and systematically deriving qualitative values for an arbitrary relational (constraint-based) behavior model is a rel­ atively unexplored area. However, much of the work in quali­ tative reasoning about physical systems ([Weld and de Kleer, 1990]) relies on this type of abstraction. The resolution of a behavior model's domains has a strong effect on the size of the model, the efficiency of reasoning with the model, and the size of the solutions. Furthermore, within an on-board or real-time setting, the number of qualitative values determines how many of the observations will be qualitatively different, and therefore it influences the frequency at which reasoning has to be initiated at all.

1.1 Example

Consider, for example, the system depicted in figure 1. The device is a simplified version of a pedal position sensor used in a passenger car. Its purpose is to deliver information about the position of the accelerator pedal to the electronic control unit (ECU) of the engine management system. The ECU uses this information to calculate the amount of fuel that will be delivered to the car engine.

The pedal position is sensed in two ways, via the poten­ tiometer as an analogue signal, Vpot, and via the idle switch as a binary signal, Vswitch· The idle switch changes its state at a particular value pas switching of the mechanically transferred pedal position. The reason for the redundant sensing of the pedal position is that the signals Vp ot and Vswitch are cross­ checked against each other by the on-board control software of the ECU. This plausibility check is a safety feature of the system, in order to avoid cases where a wrong amount of fuel injected evokes dangerous driving situations.

Assume we want to perform the plausibility check between the electrical signals Vpot and Vswi tch automatically by the means of a behavior model of the system. For the potentiome­ ter model fragment, this requires a distinction in the domain of Vpot that corresponds to the switching point posswitching of the switch. This is the only distinction in this domain that is required for the purpose at hand.

The problem is that this particular distinction cannot be an­ ticipated in a generic model fragment of the potentiometer component, because it would not make any sense in a dif­ ferent structure. It is only the specific combination of the potentiometer and the switch together with the pursued task that requires this distinction. In contrast, other tasks such as control or design might require more detailed domains that would allow to relate the position of the switch to particular potentiometer voltages.

The problem is important, because it impairs the idea of using a model of the pedal position sensor as a common basis for different tasks. For engineered systems, it is typical that several tasks along the product's life cycle - such as fail­ ure modes and effects analysis (FMEA), on-board diagnos­ tics development, generation of repair manuals or workshop diagnosis - share a significant amount of common knowl­ edge about the behavior of the system under consideration. It would be inacceptable having to manually create models from scratch that are tailored to each of these tasks.

2 Task-dependent Distinctions

The example above has confronted us with the problem that simply picking model fragments from a library and compos­ ing the model is not enough. It is infeasible, in general, to an­ ticipate the required granularity in the domains of variables. Therefore, the ability to transform the domains to the right level of abstraction after composing the constraints of the model is a highly practical requirement. It means grouping together those domain values whose distinction is irrelevant for the task at hand.

The core idea of distinctions between domain values be­ ing redundant is captured by the concept of interchangeabil­ ity, first proposed by Freuder ([Freuder, 1991 ]). For a con­ straint satisfaction problem that consists of a set of variables, domains and constraints on these variables, two values val1, val2 of a variable v are said to be fully interchangeable, if for any solution where v = val1, substituting v = val2 produces another solution, and vice versa. That is, solutions involving val1 (val2) are identical to solutions involving val2 (vall) except for the value val1 (val2) itself.

Interchangeable values define equivalence classes on the domains of the variables, and grouping them together corre­ sponds to an abstraction of the constraint satisfaction problem that exactly preserves the set of its solutions. Freuder and Sabin ([Freuder, 1991 ], [Freuder and Sabin, 1995]) already observe that interchangeability is related to abstraction and the formation of "semantic groupings" within the domains of variables. However, it is also known that in practice, in­ terchangeability of domain values does not occur very fre­ quently.

A model-based problem solving task, such as behavioral prediction or diagnosis, can be cast as an instance of a con­ straint satisfaction problem. However, it is particular in two respects:

1. the input consists not only of the model, but also of the observations that it is confronted with, such as measure­ ments, hypothetical situations, etc. Typically, observa­ tions are restricted because not all of the variables in the device model are observable, or because domain values cannot be observed beyond a certain granularity.
2. the output involves not all feasible assignments of do­ main values to variables, but only certain aspects of the solutions are required. Typically, we might be interested in knowing whether values remain below or exceed a certain threshold, or what the values of mode variables of components are (for a diagnostic task), etc.

The idea pursued in this paper is to generalize the basic prin­ ciple of interchangeability, leveraging on this specific context of a model-based problem solving task. The notion of a task is captured as ( 1) observable distinctions that express what inputs to the problem solving process (for example, observa­ tions) can occur, and (2) target distinctions that express what aspects of the outcome we are after. They can be exploited to obtain so-called induced abstractions- domain abstractions that go beyond the low, generic level of interchangeability, but are still adequate for the given task.

We pursue the approach in the context of general, rela­ tional models that are not limited to restricted cases such as linear relationships or monotonic functions. A relational (or constraint-based) behavior model is a subset

that restricts the possible combinations of values for the vari­ ables v = ( v1 , v2, ... , Vn), where DO M ( v;) denotes the do­ main of a variable v;. We use join (t><1), projection (II), and selection ( u) as operators on relations.

Consider again the device shown in figure 1. Assume that the domain is

for variables involving voltage and

for variables involving position, and that the only parameter in the system, posswitching. equals 40%. Then the device can be modeled by a relation R that consists of 10 tuples:

Observable distinctions reflect the measurement granular­ ity or incomplete observability of variables. An observable distinction for a variable is expressed as a partition of its do­ main:

Definition 1 (Observable Distinction) An observable dis­ tinction for a variable v;, denoted 1r obs ,i. is a partition of its domain DOM(v;).

A variable v; is not observable at all if 1r obs ,i is equal to the trivial domain partition "Trtriv,i := {DOM(v;)}. For in­ stance, the fact that for the pedal position sensor, the control unit observes the signal Vpot and the signal Vswitch can be expressed by the observable distinction

whereas all other variables receive the trivial domain parti­ tion.

Target distinctions reflect the granularity of solutions we are after. Analogously to observable distinctions, target dis­ tinctions are expressed as domain partitions:

Definition 2 (Target Distinction) A target distinction for a variable v;, denoted 7rtarg,i. is a partition of its domain DOM(v;).

A variable v; is said to have no target partition, if "Trtarg ,i is equal to the trivial partition. For instance, the target dis­ tinctions for the pedal position sensor are determined by the goal to distinguish between the domain values for the variable Vswitch (the plausibility check itself is not represented in the model):

2.1 Domain Abstractions

A domain partition 1r; can also be understood as a domain abstraction

that maps elements val from a base domain DO M ( v;) to a transformed domain DO M' ( v;) that consists of sets of values from the base domain such that val E 7; (val). Abstractions can be straightforwardly extended from single values to sets of values, by taking the union of the resulting sets. For two abstractions 7; and 7[, 7; is a refinement of rf, if

Two abstractions 7;, 7;' are comparable, if 7; is a refinement of 7;' or 7;' is a refinement of 7;. We apply the notion of refinement and comparability equally to abstractions and do­ mains. A vector of domain abstractions is denoted

A domain abstraction T is a refinement of r', if every 7; is a refinement of 7[. Two abstractions T, T 1 are piecewise com­ parable, if every 7; is comparable with 7[. If a join opera­ tion combines two relations that are defined on different, but piecewise comparable domains, we define, for convenience, that the result is a relation over the finer domains.

3 Qualitative Abstraction Problems

Given this representational apparatus, we can now formally define the problem of task-dependent qualitative abstraction.

Definition 3 (Qualitative Abstraction Problem) Let R be a relational behavior model, 0 B S a set of external restric­ tions, T obs a domain abstraction defined by observable dis­ tinctions, and Ttarg a domain abstraction defined by target distinctions. The qualitative abstraction problem consists of finding an induced domain abstraction T ind such that:

1. (Adequacy) For all external restrictions Robs E OBS, Robs s; DOM(v),

1. (Simplicity) lfTind is a refinement of a domain abstrac­ tion T ini and T ind' fulfills (1 ), then T ind = T ind '.

The first condition (adequacy) states that the abstracted model Tind(R) derives a solution on the level of target dis­ tinctions, if and only if the original model R derives the same solution on the level of target distinctions. We require this to hold for all the possible external restrictions (actual obser­ vations, design specifications, etc.) on the level of observ­ able distinctions. This guarantees that for any external re­ striction that can occur, the abstracted model will yield the same results as the original model. That is, if we apply Tind before carrying out our problem-solving task, it won't affect the result because this abstraction incorporates all the distinc­ tions that are necessary for this task. As a consequence, we can substitute the abstracted model Tind(R) for the original model R in problem solving.

In general, there may be many domain abstractions that ful­ fill the adequacy criterion. In particular, the identical domain abstraction Tid that retains all the distinctions in the model is an adequate abstraction according to the definition. How­ ever, among all adequate abstractions, we prefer those that are the "simplest" ones. Simplicity of an adequate abstrac­ tion is defined in the second condition of definition 3. The approach taken is to select the abstractions that are coarsest in the sense that there exits no other adequate abstraction of which they would be a strict refinement (an abstraction that would further merge at least two of the qualitative values). A domain abstraction that is both adequate and simple incorpo­ rates only distinctions that are both necessary and sufficient according to the target and observable distinctions. It rep­ resents a level of abstraction that neither makes any unnec­ essary distinctions, nor abstracts away any distinctions that are crucial to solve the problem. Definition 3 thus formal­ izes the problem of finding qualitative values for the domains of variables. Compared to interchangeability, which is con­ cerned with possibilities for abstraction within a single prob­ lem instance only, a qualitative abstraction problem (QAP) describes a whole class of instances defined by a model re­ lation, a set of external restrictions, and the task-dependent distinctions. Interchangeability enforces that the set of so­ lutions remains the same as for the original model. A QAP generalizes (or relaxes) this basic principle and demands that the set of solutions remains the same but only on the level of target distinctions, and only for inputs on the level of observ­ able distinctions.

Definition 4 (Properties of QAP) A QAP with a set of ex­ ternal restrictions 0 B S is said to be obs-complete, if {Tobs (Robs ) I Robs E OBS} = 2Tob·(DOM(V))_ It is said to be sol-complete, if for all v; : Tt arg, ;(DOM( v;)) s;; IT; ( { Ttarg(R 1><1 T obs (Robs)) I Robs E OBS} ).

Obs-completeness means that all the possible observations on the level of observable distinctions can actually occur or have to be considered during problem-solving (consequently, induced abstractions can be derived without knowing the ex­ act set OBS ). Sol-completeness means that all the possible solutions defined by the target distinctions can indeed be dis­ tinguished based on the model and the external restrictions. In addition, we demand that T obs and Tt arg are piecewise com­ parable. Note that this is not actually a restriction, because it can be established for any QAP by possibly introducing ad­ ditional variables that separate the target and observable dis­ tinctions.

Intuitively, under these conditions, we expect that we have to keep all the target distinctions, because we need them to distinguish the solutions, but we can eliminate the distinc­ tions between observations that would lead to the same set of solutions. If QAP is obs-complete, the T obs (Robs ) are given by the possible subsets of Tobs(DOM(v)) . For each tuple valobs,j E Tobs(DOM(v)), define R sol,obs, j to be the solu­ tion it derives on the level of target distinctions:

Let Robs,k denote the sets of valobs, j that obtain the same solution, i.e. those for which R sot,obs ,j is equal:

Then the Robs,k form the elements of a partition of T obs (DOM( V )) :

Figure 2 shows the resulting partition E(R , T obs, Tt arg ) for the pedal position sensor example, given the observable and target distinctions stated in Sec. 2 (all variables except Vpot and Vswitch have no distinction and have been omitted from the figure; values [2V,4V), [4V,6V) and [6V,8V) for Vswitch do not appear in Rand have been omitted from its domain) .

Theorem 1 (Solution to QAP) Let QAP be a qualitative ab­ straction problem that is obs-complete and sol-complete. Let TFJ ,A,i be the domain abstraction that aggregates the in­ terchangeable values of a relation A, that is, two values val1 , val2 E DO M ( v; ) are combined if

Then the simplest domain abstraction that is a refinement of Tt arg,i and every domain abstraction

is an induced abstraction for QAP.

For the pedal position sensor example, Theorem l derives three qualitative values for Vpot (see Fig. 2):

The first qualitative value {[OV,2V),[2V,4V)} corresponds to situations where Vswitch equals ground voltage, the third qualitative value {[6V,8V),[8V,lOV)} corresponds to situa­ tions where Vswitch equals battery voltage, and the second qualitative value {[4V,6V)} corresponds to situations where the position of the switch and, hence, the voltage of Vswitch. is ambiguous.

Theorem 1 shows that the basic concept of interchangeabil­ ity plays a central role in the determination of solutions to a qualitative abstraction problem. In particular, the problem of finding interchangeable values in a relation can be recast as a special case of a QAP, where one distinguishes only empty from non-empty solutions:

Corollary 1 (Interchangeability as QAP) Let QAP = ( R, T obs, T targ ) be an obs-complete qualitative abstraction problem such thatTobs = T ;d, T targ = Ttriv· Then TFJ ,R,i is an induced abstraction for QAP.

In general, however, the granularity of induced abstrac­ tions is different from the granularity of interchangeable val­ ues. T ind can be either more coarse or more fine-grained than T FI,R· The latter case occurs if target distinctions are speci­ fied between domain values that are interchangeable with re­ spect to the model relation.

Theorem 1 constitutes also a starting point for finding use­ ful approximations of qualitative values. One approach is to use only necessary conditions for interchangeability. In order for two domain values to be aggregated by T FI ,A, it is necessary that they appear in the same elements of L;(R, T obs, Ttarg ):

Proposition 1 (Approximate Solution to QAP) Let QAP be a qualitative abstraction problem that is obs-complete and sol-complete. Let Tapp,i be the simplest domain abstraction that is a refinement of Ttar g, i and every domain abstraction

Then the induced abstractions are a refinement ofrapp,i·

The approximation T app considers only the projection of each A on the individual variables. This yields a granularity that is simpler than or equal to the induced abstractions. For the pedal position sensor example, the distinctions derived by Tapp, i are identical to those derived by Theorem 1. Obtaining Tapp,i is easier than determining Tind ,i , because it involves only the projection and intersection of sets and does not re­ quire to determine the interchangeable values in A. However, because it considers only restrictions for individual variables, the approximation T app is not adequate. In general, a restric­ tion might lead to a different solution only if it is combined with additional restrictions for the other variables.

4 AQUA: A Prototypic System for Task-dependent Domain Abstraction

The computation of induced abstractions for a QAP in­ volves, based on the results above, the subproblems of constructing the model relation R, computing the partition L;(R, T obs, Tt arg ), and determining interchangeable values within the elements of this partition.

Our prototypic system AQUA (Automated Qualitative Ab­ straction) ([Sachenbacher, 2001]) determines the relation R through structural decomposition of the constraint network that is defined by the set of model fragments it is com­ posed of. The basic principle of structural decomposition ([Gottlob et al., 2000]) is to transform a constraint network into an equivalent acyclic (tree-structured) instance. AQUA then iterates over the partition elements of the observable and target distinctions and labels the tuples of the relation R that are consistent with the respective partition elements. Since directional arc consistency is sufficient for establish­ ing consistency in a tree-structured network ([Dechter and Pearl, 1988]), this step can be performed efficiently by lo­ cal constraint propagation. This step yields the partition L;(R, T obs , Ttarg ). Interchangeable values in the partition el­ ements of L;(R, T obs , T targ) can then be found using the ba­ sic algorithm described in [Freuder, 1991]. Alternatively, the partition elements can be projected on the individual variables to obtain the approximate solution. AQUA also performs fur­ ther optimizations in that it can automatically remove redun­ dant values (domain values that do not appear in any con­ straint) and eliminate variables that have no distinction at all. The decomposition step is independent of the particular task in terms of observable and target distinctions; hence, the re­ sulting tree can be re-used for different combinations of ob­ servable or target distinctions.

AQUA builds on components of an existing model-based reasoning framework that consists of a development system for composing a device model from of a library of model fragments, and a runtime system for performing behavioral prediction and diagnosis based on actual measurements for the device. Using AQUA, several tasks can be supported in the context of building model-based systems that are of­ ten carried out manually or solved on an ad hoc-basis. The common theoretical basis is to find suitable domains for the variables in a model. However, in different contexts this ba­ sic task can have different interpretations, depending on what the terms variable and domain refer to, including magnitudes, modes of components, and deviations from reference behav­ iors ([Sachenbacher, 2001]).

In a larger, real-world application taken from the automo­ tive domain [Sachenbacher et al., 2000], AQUA was used to obtain abstractions of behavior models of a turbo con­ trol subsystem that involved several hundred (initially, real­ valued) variables. The qualitative level of abstraction of the derived model was instrumental to meet real-time require­ ments, and allowed for keeping up with the rate of the mea­ surements in an on-board diagnostic context. In this context, task-dependent abstraction proved useful as a precompilation method that guaranteed adequacy of the results.

5 Discussion

While several pieces of work have addressed the problem of automatically deriving appropriate models ([Nayak, 1994; Levy et al., 1997; Rickel and Porter, 1997]), the work pre­ sented here is distinctive in that it focuses specifically on the granularity (resolution) of the domain values, and uses rela­ tions and partitions as a common and concise representational framework. This has several important implications.

The narrowed focus allows us to represent the space of pos­ sible candidate models implicitly and compactly as the space of possible domain partitions. In contrast, [Nayak, 1994; Rickel and Porter, 1997] define this space as the possible combinations of model fragments. Candidate models are then defined by different choices (selections) of possible frag­ ments. Because in our framework, the difference between different candidate models is well-defined (by means of op­ erators r ; ), we can in contrast take on the view of transform­ ing (re-formulating) models instead of selecting them. The general relational representation subsumes both infinite and finite constraints, and is not limited to specific types of con­ straints and special-purpose reasoning methods. It allows us to capture the conditions for a solution in a single, con­ cise formula (Definition 3) and, more importantly, allows to determine the solutions analytically and in closed form (Theorem 1). In contrast, [Nayak, 1994; Levy et al., 1997; Rickel and Porter, 1997] all devise search procedures that start from an initial model and backtrack until they find a so­ lution. In general, it can be said that our limited scope al­ lows us to assume a less knowledge-based, more mathemati­ cal view of automated modeling.

QSIM ([Kuipers, 1986]), a system for performing quali­ tative simulation of device behavior over time, incorporates methods for refining the domains of variables by deriving new distinctions ("landmarks") during the simulation pro­ cess. However, except for signs, the mapping of qualitative values to their base domain is only partially known, since only information on the ordinal relationship and knowledge about values that must be assumed simultaneously ("corre­ sponding values") is provided. Therefore, the derived distinc­ tions can in general not be used to simplify the model. Ex­ tensions of QSIM that deal with semi-quantitative reasoning [Berleant and Kuipers, 1997]) allow to further constrain the landmark values to numeric intervals, but are specific to the context of simulation, and the constraints are limited to alge­ braic relationships and monotonic functions. For the specific task of diagnosis, Torasso and Torta [Torasso and Torta, 2002] recently presented an approach for merging together behav­ ior modes that are indistinguishable, given the granularity of the observations. However, the method does not incorporate a notion of target distinctions.

While the theory of task-dependent domain abstraction is applicable both to finite and infinite domains, an important area for future work is to efficiently derive induced abstrac­ tions for real-valued base models. [Sachenbacher, 2001] out­ lines a method for iterative refinement of qualitative values given a real-valued base model. [Struss, 2002] investigates cases where distinctions can be obtained for monotonic re­ gions of real-valued functions.

6 Conclusion

The increasing complexity of engineered devices has lead to an increased demand for computer-supported behavior pre­ diction, diagnosis, and testing. Given the maturity and scale of model-based systems applications, the question of how to re-use behavior models is of growing interest. It has been shown that a model composed from a library cannot be ex­ pected to have a level of granularity suitable for different tasks right away. Instead, the ability to re-formulate the model after composing it is a crucial requirement. We iden­ tified, within a common relational framework, fundamental properties of re-formulation that is based on abstraction of domain values. Observable distinctions and target distinc­ tions allow to capture important aspects of a task. They are the starting point for deriving qualitative values that are both adequate for the task and as simple as possible. Our analy­ sis reveals that the degree of domain abstraction that can be achieved is strongly dependent on the characteristics of the task. Task-dependent qualitative domain abstraction is a con­ tribution to further bridging the gap between quantitative and qualitative modeling, as it allows to express knowledge about component behavior without being committed early to a spe­ cific abstraction level of the domains. It can help to make model-based system more efficient and more cost-effective due to automating steps that are currently done by hand.