Case Adaptation with Qualitative Algebras

1 Introduction

Case-based reasoning (CBR) [Riesbeck and Schank, 1989] is a framework in which a new problem (the target case) is solved by first retrieving an older, similar problem to which the solution is known (the source case), and then adapting this solution to fit the new problem. While the retrieval stage has been thoroughly studied by the CBR community, the adaptation stage has received less attention until recently. One proposal to address the adaptation problem is to apply a belief revision operator, revising source knowledge by target knowledge [Lieber, 2007]. In this paper, we apply Lieber's proposal to case knowledge represented using a qualitative algebra, such as Allen's calculus [Allen, 1983] or RCC8 [Randell et al., 1992].

Qualitative spatial and temporal reasoning (QSTR) as a research domain has been active since the beginning of the 1980s. The paradigm has been exploited to help solve planning and constraint satisfaction problems, but rarely within CBR. Nevertheless, many domains in which QSTR is used could be addressed with CBR because the knowledge involved is usually contextual and incompletely formalised. This is the case in the domain of landscape agronomy, in which knowledge can be acquired from schematic descriptions of the spatial organisation of farmlands. Another example is the cooking domain, in which some knowledge is of a temporal nature.

In section 2, our approach is illustrated informally using a cooking example. Section 3 then introduces the formal notions required for the approach, namely in terms of CBR, Jean Lieber LORIA Universit´e de Lorraine CNRS UMR 7503, Inria F-54506 Vandœuvre jean.lieber@loria.fr

∗The paper on which this extended abstract is based was the recipient of the best paper award of the 2012 International Conference on Case-Based Reasoning [Dufour-Lussier et al., 2012].

Laura Martin

INRA UR055 ASTER-Mirecourt

F-88500 Mirecourt

laura.martin@mirecourt.inra.fr

revision-based adaptation, and QSTR. The approach is then defined in details in section 4, and an algorithm is described in section 5. Section 6 illustrates those formal notions and the results of the algorithm using the example introduced in section 2. Related work is discussed in section 7.

2 A cooking example

To illustrate temporal case adaptation, we use TAAABLE [Cojan et al., 2011], a CBR application for cooking. TAAABLE answers user queries, for instance: "I want a recipe for a carrot risotto." If no matching recipe is found in the cookbook (the case base), a recipe of the same type with similar ingredients will be retrieved, for instance a mushroom risotto. TAAABLE will then suggest the user replaces mushrooms with carrots. On the other hand, in its current form, it will not be able to help the user in adapting the recipe.

Suppose the mushrooms were added to the rice 2 minutes before the end, but the cooking domain knowledge indicates that carrots must be cooked for 25 minutes in order to be done, whereas the rice must be cooked for 18 minutes. A proper adaptation would require not only the lengthening of the cooking time of the vegetables, but also a reordering of the actions in the recipe. Therefore we expect the approach we will now introduce, given a retrieved recipe and a requested substitution, will be able to reorder the actions of the recipe in order to present TAAABLE users with a usable procedure.

3 Background

3.1 Case-based reasoning and case adaptation

In this paper, Source, Target and DK respectively denote the case to be adapted, the target case and the domain knowledge. Source and Target are required to be consistent with DK. Given Source and Target, the adaptation aims at building a new case, AdaptedCase. This case is built by adding some information to the target case (intuitively, Target specifies only the "problem part" of the query), and it has to be consistent with DK.

It is assumed that a matching step precedes the adaptation process, providing links between Source and Target. It is represented by a substitution σ, mapping descriptors of Source to descriptors of Target. As an example, in the system TAAABLE, matching is performed during retrieval. This process, applied to the cooking example of the previous section, would have returned σ = mushroom ⇝ carrot. In the following, this preprocessing step of adaptation is considered to be given and, thus, σ is an input of the adaptation process described in section 4.

3.2 Belief revision and revision-based adaptation

In a given representation formalism, a revision operator ∔ maps two knowledge bases ψ and µ to a knowledge base ψ ∔ µ, the revision of ψ by µ. Intuitively, ψ ∔ µ is obtained by making a minimal change of ψ into ψ′ , so that the conjunction of ψ′ and µ, ψ′ ∧ µ, is consistent. Then, ψ ∔ µ is this conjunction.

The notion of minimal change can be modelled in various ways, so there are various revision operators. However, postulates have been proposed for such an operator, such as the AGM postulates [Alchourr´on et al., 1985]. These postulates have been applied to propositional logic [Katsuno and Mendelzon, 1991] and well studied in this formalism. Given a distance dist on the set U of the interpretations, an operator ∔dist can be uniquely defined (up to logical equivalence) as: the set of models of ψ ∔dist µ is the set of models of µ that have a minimal distance to the set of models of ψ.

Given a revision operator ∔, ∔-adaptation consists simply in using this revision operator to perform adaptation, taking into account the domain knowledge:

The intuition behind revision-based adaptation is to reduce adaptation to an inconsistency repair.

3.3 Qualitative representation of temporal knowledge

Definitions

A qualitative algebra is a relation algebra that defines a set B of binary relations applicable between two variables, usually representing points, intervals or regions. Allen interval algebra [Allen, 1983], for instance, introduces 13 basic relations between intervals, corresponding to the 13 possible arrangements of their lower and upper bounds. 7 relations are illustrated in figure 1. The 6 others are the inverse of the first 6 (eq is symmetric).

INDU [Pujari et al., 1999] extends the set of Allen relations by combining them with relations over the interval durations. For 7 Allen relations, there is only one possible duration relation (e.g. i {d} j implies that the duration of i is shorter than the duration of j). For the other 6, all three duration relations <, = and > are possible. This yields a total of 25 basic relations. They are written as rs , where r is an Allen relation and s is a duration relation.

Qualitative knowledge can be represented as qualitative constraint networks (QCNs). A QCN is a pair (V, C), where V is a set of variables, and C is a set of constraints of the form Vi Cij Vj with Vi, Vj ∈ V , and Cij is a set of the basic relations defined by the algebra (Cij is a relation that is a disjunction of the basic relations, i.e. i {r1, r2} j means that i is related to j with either r1 or r2). In INDU, shortcut notations r? and ?s respectively represent the Cartesian product of r and all possible duration relations and the product of s and all possible Allen relations (e.g., {m}?= {m<, m=, m>};

{d}?= {d<}; {?}== {b=, m=, o=, eq=, oi=, mi=, bi=}). A scenario is a QCN S = (VS,CS) such that for each Vi, Vj ∈ VS, there exists one constraint Vi {r} Vj ∈ CS. S satisfies the QCN N = (VN , CN ) if S and N have the same set of variables and each constraint relation in S is a subset of the corresponding constraint relation in N. A scenario is consistent if a valuation can be provided for the variables such that all constraints are observed, and a QCN is consistent if it has a consistent scenario. Two QCNs are said to be equivalent if every scenario of the former is a scenario of the latter and vice-versa.

Revision of QCNs

A QCN is a knowledge base and thus, the issue of revising a QCN ψ by a QCN µ can be addressed. Building on the work of [Condotta et al., 2008], we defined a revision operator for QCNs, following the idea of an operator ∔dist (cf. section 3.2), where an interpretation is a scenario, a model of a QCN is a scenario that satisfies it, and a distance dist between scenarios/interpretations is defined as follows.

First, a distance d between basic relations of the considered algebra is defined. Formally, a neighbourhood graph whose vertices are the relations of the algebra is given, and d(r, s) is the distance between r and s in the graph. It represents closeness between relations. For instance, b and m are close (d(b,m) = 1) since they express similar conditions on the boundaries of the intervals (for the lower bounds: = for both; for the upper bounds: < for b and = for m). d makes it possible to define dist, a distance between two scenarios S = (V,CS) and T = (V,CT ) based on the same set of variables V, as:

where rS(Vi, Vj) is the relation r such that Vi {r} Vj ∈ CS.

Given two QCNs ψ and µ, the revision of ψ by µ returns the set R of scenarios satisfying µ that are the closest ones to the set of scenarios satisfying ψ. 1

1 This slightly differs from the definition of revision given in section 3.2 where ψ ∔ µ is a knowledge base, not a set of models.

4 Formalisation

4.1 Representation of the adaptation problem Parametrised QCNs

It is assumed that the variables of the considered QCNs can be parametrised by elements of a given set P. A parameter p ∈ P is either a concrete parameter, p ∈ CP, or an abstract parameter, p ∈ AP: P = CP ∪ AP, CP ∩ AP = ∅. A concrete parameter denotes a concept of the application domain, e.g. mushroom ∈ CP for the cooking example. In this example, the formal interval cooking(mushroom) represents the temporal interval of the mushroom cooking. The domain knowledge DK = (VDK,CDK) is a set of constraints, for example:

where rice ∈ CP and x ∈ AP, represents the facts that rice requires 18 minutes of cooking, that x is cooked as soon as the action of cooking x is finished, and that 18 minutes are shorter than 25 minutes. An abstract parameter must be understood with a universal quantification over the concrete parameters; e.g. cooking(x) {m}? cooked(x) entails cooking(mushroom) {m}? cooked(mushroom).

Let N1 and N2 be two QCNs. N1 ∧ N2 is the QCN N = (V,C) such that V = V1 ∪ V2 and C contains the constraints of C1, the constraints of C2, and the constraints that are deduced by instantiation of the abstract parameters by concrete parameters appearing in N1 and N2 For example, if N1 = CDK defined by equation (4.1) and N2 = ({cooking(tomato), cooked(tomato)}, ∅), then N1 ∧ N2 = (V, C) with C = CDK ∪ {cooking(tomato) {m}? cooked(tomato)}.

Substitutions

The atomic substitution σ = p ⇝ q, where p, q ∈ P, is the function from P to P defined by σ(a) = {q if a = p a otherwise . A substitution is a composition σ1 ; . . . ; σn of atomic substitutions σi.

Let σ = p ⇝ q be an atomic substitution. σ is concrete if p, q ∈ CP. σ is an atomic abstraction if p ∈ CP and q ∈ AP. σ is an atomic refinement if p ∈ AP and q ∈ CP. A concrete substitution (resp., an abstraction, a refinement) is a composition of concrete atomic substitutions (resp., of atomic abstractions, of atomic refinements). Any concrete substitution σ can be written σ = α ; ϱ where α is an abstraction and ϱ is a refinement, as the following equation illustrates:

mushroom ⇝ carrot = mushroom ⇝ x ; x ⇝ carrot

where mushroom, carrot ∈ CP and x ∈ AP. This can be shown as follows. First, σ can be written p1 ⇝ q1 ; . . . ; pn ⇝ qn with pi, qi ∈ CP and pi ̸= pj if i ̸= j. Let x1, . . . , xn be n abstract parameters, let αi = pi ⇝ xi, let ϱi = xi ⇝ qi, let α = α1 ; . . . ; αn, and let ϱ = ϱ1 ; . . . ; ϱn. α is an abstraction, ϱ is a refinement and σ = α ; ϱ.

Let σ be a substitution. σ is extended on qualitative variables by applying it to their parameters. For example, if σ =

mushroom ⇝ carrot then σ(cooking(mushroom)) = cooking(carrot). Then, σ is extended to a constraint c = (Vi Cij Vj) by σ(c) = (σ(Vi) Cij σ(Vj)). Finally, σ is extended on a QCN by applying it to its variables and constraints: σ((V,C)) = (σ(V ), σ(C)) where σ(V ) = {σ(Vi) | Vi ∈ V } and σ(C) = {σ(c) | c ∈ C}.

Adaptation problem

An adaptation problem is given by a tuple (Source, Target, DK, σ). Source and Target are the representations of the source and target cases by QCNs with concrete variables (i.e. not parametrised by any abstract parameter). DK is a QCN representing the domain knowledge. σ = p1 ⇝ q1 ; . . . ; pn ⇝ qn is a concrete substitution such that each pi (resp., qi) parametrises a variable of Source (resp., Target). DK∧Source and DK∧Target are assumed to be consistent (cf. section 3.1). The goal of adaptation is to build a consistent QCN AdaptedCase that entails DK ∧ Target, whose qualitative variables are obtained by applying σ on the qualitative variables of Source, and that is obtained thanks to minimal modification of DK ∧ Source.

4.2 Principles of revision-based adaptation of a QCN

A first idea to perform the adaptation, given a tuple (Source, Target, DK, σ), is to apply σ on Source, thus obtaining a QCN DK ∧ σ(Source) that may be inconsistent, and then restoring consistency. Although this gives a good intuition of the revision-based adaptation of a QCN, it is not consistent with the irrelevance of syntax principle. (Indeed, any two inconsistent knowledge bases are equivalent: their sets of models are both empty.) Thus, at a semantic level, repairing an inconsistent knowledge base is meaningless. By contrast, revision aims at modifying a consistent knowledge base with another consistent one, the conjunction of which may be inconsistent.

Therefore, the revision-based adaptation consists first in decomposing σ in an abstraction α and a refinement ϱ: σ = α ; ϱ. Then, α is applied to Source: a QCN DK ∧ α(Source) is built that is necessarily consistent since DK ∧ Source is consistent and every constraint of DK ∧ α(Source) corresponds to a constraint of DK ∧ Source. In other words, DK ∧ Source is consistent and is more or equally constrained as DK∧α(Source), so DK∧α(Source) is consistent.

The third step involves revision. The idea is to make a revision of ψ by µ where ψ = DK ∧ α(Source) and µ = DK ∧ Target ∧ Nϱ where Nϱ represents the following statement: "Each qualitative variable Vi of α(Source) is constrained to be equal to its refinement ϱ(Vi)." For this purpose, the relation eq for equality is used (eq = in INDU): Vi eq ϱ(Vi). Therefore, Nϱ = (Vϱ, Cϱ) where

µ is consistent since DK ∧ Target is and since each constraint Vi eq ϱ(Vi) of Nϱ either is a tautology (when Vi does not contain any abstract parameter refined by ϱ) or links a variable Vi that does not appear in DK∧Target with ϱ(Vi).

Then, ψ ∔ µ gives a set of scenarios and AdaptedCase is chosen among them.

5 Algorithm and implementation

The revision algorithm takes as input ψ = DK∧α(Source), µ = DK∧Target∧Nϱ, as well as a relation neighbourhood graph and a transitivity table for the algebra used. The neighbourhood graph enables to define a distance d between relations and the transitivity table defines a relation composition function ◦ : B×B → 2B , for example, m ◦ mi = {eq, f, fi} in Allen algebra.

First, it is necessary to ensure that all variables in either QCN are present in the other QCN as well. All pairs of variables that have no relation associated to them are given the relation B-the unspecified relation.

The algorithm must then search within the scenarios of µ the ones that minimise the distance to ψ. The distance between the QCNs ψ and µ is the smallest distance between any scenario of ψ and a scenario µ, computed using equation (2). Considering that the minimum of sums is never less than the sum of minimums, a lower bound on the distance between two QCNs can be obtained in time O(|V |2 · |B|2 ) by computing the pair-wise minimal distance for each constraint and summing those. This defines an admissible heuristic which is used to instantiate an A∗ search. The initial state is µ and a goal state is a scenario of µ. A successor state is obtained by selecting one constraint and keeping only one relation on this constraint. The QCN ψ is used in the cost in the heuristic functions.

The amount of scenarios for a QCN is of the order of O (|B| |V |·(|V |-1) 2 ).

6 Result

This section revisits the example from section 2.

Most temporal aspects of recipes can be represented in INDU by reifying cooking actions, ingredient states, and durations as intervals. For instance, the following could be included in the domain knowledge: cooking(carrot) {m}? cooked(carrot) and cooking(carrot) ? = 25 min, with the provision that, e.g. 18 min ?< 25 min.

To limit the amount of variables shown, we simplify the representation by replacing duration intervals with duration relations between the relevant action intervals. In this representation, ψ contains

In TAAABLE, there is no firm adaptation constraint from Target (CTarget = ∅) therefore µ contains simply the constraints

The revision algorithm returns two scenarios which are predictably distinguished only by the duration relation between serve and the other actions, since this relation is defined as being unimportant in the domain knowledge. One scenario T = (VT ,CT ) is such that CT is

In both scenarios, the lengthening of the vegetable cooking is associated with the inversion of the relation between the vegetable and the rice, i.e. f< becomes fi>, which corresponds to the expected order inversion between the start of both actions. Therefore, the adaptation is successful.

7 Related work

Several research work focused on the representation of time within the CBR framework. Most were interested in the analysis or in the prediction of temporal processes (e.g. breakdown or disease diagnosis starting from regular observations or successive events). The temporal aspect is generally taken into account from sequences of events or sometimes from relative or absolute time stamps [Dojat et al., 1998; Ma and Knight, 2003; S´anchez-Marr´e et al., 2005]. Particularly, the problem of temporal adaptation has been given much attention in CBR with a workflow representation [Minor et al., 2010]. Only a few work [Jaczynski and Trousse, 1998; Dørum Jære et al., 2002] adopted a qualitative representation. In [Dørum Jære et al., 2002], cases are represented by temporal graphs and the retrieval step is based on graph matching. In [Jaczynski and Trousse, 1998], cases are indexed by chronicles and temporal constraints, which are represented with a subset of Allen relations.

Some recent work also dealt with a combination of CBR and spatial reasoning, for instance in order to improve web services for spatial information [Osman et al., 2006], or for spatial event prediction in hostile territories [Li et al., 2009].

8 Conclusion

Qualitative algebras are important to the field of knowledge representation and are especially useful for qualitative reasoning on space and on time, but their use in CBR has received very little attention so far. This paper focuses on the adaptation of cases represented in a qualitative algebra. A cooking example uses the temporal algebra INDU. This adaptation uses the principles of revision-based adaptation and combines it with a matching between the source and target cases.

A prototype for adaptation of cases represented in a qualitative algebra has been implemented in Perl 2 and applied to the examples of this paper, but it is time-consuming and still requires improvements in order to be integrated into an operational system like TAAABLE.

2 The Perl library and Java bindings for this and other revision tools are available at http://revisor.loria.fr.