Possibilistic Temporal Reasoning based on Fuzzy Temporal Constraints

1 Introduction

Representation and reasoning about time is a major issue to be considered in all those reasoning tasks which take account of a dynamic domain. Most of AI systems incor­ porating an explicit temporal representation are based in some manner on constraint-reasoning techniques [Allen, 1983; Malik and Binford, 1983; Valdes-Perez, 1986; Vilain and Kautz, 1986; Dean and McDermott, 1987; Knight and Jixin, 1992; Porto and Ribeiro, 1992; Vila, 1994a] 1 . Temporal constraints account for uncertainty in temporal knowledge up to a certain extent. Both qual­ itative [Allen, 1983; Vilain and Kautz, 1986; van Beek, 1989] and metric temporal constraints [Dechter et al., 1991] represent the set of "equally possible" precise tem­ poral relations between two time units. The larger is Nonetheless, this is not enough for domains where knowledge about time is highly pervaded with vague­ ness and uncertainty. Let's illustrate it with an example taken from a medical domain and supplied by an expert in the domain of lumbalgia pathologies. Brucelosis is one infectious pathology which may be the origin of serious lumbalgia problems. It has an evolution pattern which can be regarded as a particular instance of the common infectious evolution pattern. It is usually composed of an Inoculation event [I], an Initial Period [IP], a period of Ondulating Fever [OFP] and, finally, it reaches the state of an Intervertebml Affection [IA]. We reproduce here the temporal aspects of this knowledge without ab­ stracting the vagueness in terms of which it is obtained from experts. There is some (vague) knowledge about the temporal evolution of brucelosis cases:

*This work has been partially supported by Spanish MEC grant FPI-PN90 77909683, by CICYT project ARREL (TIC92-0579-C02-01) and by EC grant MUM (Copernicus 10053) .

tpresently at the University of California at Irvine, Infor­ mation and Computer Science Departement.

1 See [Vila, 1994b] for a comparative survey.

• The initial period usually starts at a time between one and three weeks after the inoculation event, al­ though extreme cases range from starting at the very inoculation time up to four weeks after.
• The initial period uses to be short: it lasts few days, although in unusual cases it may last up to two weeks at most.
• The ondulating fever period always occurs after the initial period. It uses to last between 20 and 25 days though other less possible cases range from 4 days as the lowest bound up to 45 days the uppest one.
• Finally, the intervertebml affection usually starts between 15 and 20 days after the start of the on­ dulating fever period, having extreme. cases where the intervertebml affection did not appear after 22 months. The intervertebml affection lasts more or less between 3 and 6 months. Extreme cases may range from the shortest case of 40 days and longer periods up to 12 months in cases where it is not properly treated.

Several pieces of work have considered the represen­ tation of approximate temporal knowledge. Among them we would stress those based on possibility the­ ory [Vitek, 1983; Dutta, 1988; Dubois and Prade, 1989; Kohlas and Monney, 1990; Console et al., 1991; Dubois et al., 1992; Marin et al., 1994; Barro et al., 1994;

Vila and Godo, 1995]. In particular, Barro et al. [1994] propose an straight forward redefinition of generaliza­ tion of the notion of metric temporal constraint based on fuzzy sets [Marin et al., 1994].

In this paper we propose an approximate temporal logic based on the embedding of fuzzy temporal con­ straints into a logical framework. It is provided with an inference system composed of specific inference rules for the fuzzy temporal constraints. For the sake of clarity, we have chosen a simple propositional language. Dealing with fuzzy temporal constraints leads to many-valued in­ terpretations of our formulas, but inference from fuzzy constraints also induces uncertainty as soon as they rep­ resent a kind of incomplete information. This induces to extending the whole language to handle both fuzziness and uncertainty. The natural framework where to model fuzziness and uncertainty in a unified way is the possi­ bilistic framework. Therefore this will be the model used througout this paper in accordance with using fuzzy sets for representing the temporal constraints. Uncertainty will be taken into account in the extended language by attaching certainty (necessity-like) degrees to formulas.

The paper is organized as follows. In next section we describe the syntax -which is illustrated by formali~ing the example above introduced- and semantics of our ba­ sic language. In the third section an extended language and semantics to handle uncertainty is presented. In section 4 we present an inference system and prove its soundness. Finally, we sketch future lines of work.

2 The Basic Temporal Language

We start out from a language where the temporal and the atemporal parts are neatly separated. The atempo­ ral part is simply made over a set of classical crisp propo­ sitions. The temporal part is based on fuzzy temporal constraints over a set of temporal propositions. It con­ sists of the introduction of a single predicate FuzzDIST which states a fuzzy temporal constraint between a pair of time points. Whereas in the metric case, a temporal constraint is represented as an interval, now it is repre­ sented by a (convex) fuzzy set of time points, inducing a possibility distribution on the set of duration values . Although this approach is very simple in definition it is highly powerful in expressiveness. Some important' con­ straint based temporal representations, like point algebm [Vilain and Kautz, 1986], or the metric pointwise con­ stmints [Dechter et al., 1991] turn out to be a particular case of it. The link between the temporal propositions and the temporal constraints is performed through the duration-valued functions BEGIN(p) and END(p) that specify the initial and final instants of the period the proposition p holds throughout.

Regarding the underlying time structure, and for the sake of simplicity, we take a fix interpretation of the set of duration symbols VU as the set of rational numbers Q. Accordingly, the set :FVU of fuzzy durations will be taken as the set of fuzzy subsets of Q, i.e. :FVU = Q[O,l] . However, nothing would prevent us to take other particular either discrete or dense group structures of time.

2.1 Syntax

The sentences of our propositional language £ are built up over propositions and fuzzy temporal constraints. The following symbols are used:

Poo, a set of primitive atemporal propositional vari­ ables,

• 'Pt, a set of primitive temporal propositional variables and '

to, a special time point symbol.

We have two sorts of atomic formulas:

• Atemporal Propositions: the elements of P 00 ·
• Temporal constraints: consist of a set of propo­ sitional variables (indexed by 'Pt U {to} x 'Pt U { t0 } x :FVU) of the form

where t and t' are temporal expressions of the form BEGIN(p), END(q) or to, being p and q some tempo­ ral propositional variables from 'Pt, and 1r E :FVU is a fuzzy duration. The symbol t0 represents a common reference time point, BEGIN(p) the initial instant of the time interval where p holds, END(q) the ending instant for q, and 1r represents a soft con­ straint on the dumtion tempoml variable "t' - t ".

The well-formed formulas (wffs) of our basic language £ are of the form:

with m 2: 0, where Bi and Hare either literals from Poo or temporal constraints.

Like in definite clauses, the conjunction of Bi is called the body or antecedent and H is called the head or con­ clusion. We distinguish between two types of formulae according to the form of the body:

• fact, when m = 0 (empty body) and written simply H, and
• rule, otherwise.

To illustrate the usage of our language in formaliz­ ing domain knowledge let's consider the example in the introductory section. Figure 1 presents a graphical rep­ resentation of it. Events and properties being part of the temporal evolution description are taken as primitive temporal propositional variables. We shall approximate a soft constraint in :FVU by a trapezoidal function char­ acterized by four points 2 . From a knowledge adquisition point of view the second and third point determine the interval of those temporal values which are likely whereas the first and fourth points determine the interval out of which the values are absolutely impossible. For example, both the inoculation event and the initial period state are conceptualized as temporal propositional variables and the first statement related to the temporal distance be­ tween the inoculation event and the begin of the initial period will be formalized as a fuzzy temporal constraint described by [0, 7, 21, 28] where these values represent days. The heuristic rule formalizing the whole piece of knowledge would be as follows:"

2 Notice that this approximation is only feasible for uni­ modal fuzzy constraints.

where m stands for month (X m can be taken as a short hand of the value X* 30).

2.2 Semantics

The semantics of our propositional language £ involves, for each model, first the assignment of intervals of time points to the temporal propositional variables, and sec­ ond the interpretation in terms of truth-values of the formulas of the language. Atemporal propositional vari­ ables can be directly assigned to either 1 (True) or 0 (False), while temporal constraints expressions are as­ signed truth-values of [0, 1] via the fuzzy duration func­ tion they contain 3 . As for compound formulas, we have chosen to interpret conjunction by the min func­ tion and implication by the Gooel's many-valued impli­ cation function (see Definition 2). The choice of min for conjunction is the usual one in fuzzy logics and GOdel's implication is its corresponding residuum. In doing so, we assure a correct behaviour of the implication with respect to a suitable notion of logical consequence (see Proposition 1, next Section) and later on with respect to modus ponens (see Proposition 5, Section 4).

3 Without gain of complexity we could allow the atemporal propositions to be fuzzy as well and thus to have a more general language but, for the sake of clarity we prefer to only allow fuzziness in the temporal expressions, which is the focus of the paper.

Definition 1 An £-model is a pair w = (wt, w00), where

Definition 2 Let n denote the set of £-models. The satisfaction relation f= is a mapping

defined as:

F (w,p) = Woo(p), ifp E Poo

F (w, -.p) = 1-Woo(p), ifp E Poo

f= (w, FuzzDIST(t, t', 1r)) = 7r(Mw(t')- Mw(t)), where Mw is the interpretation function of tempoml terms defined as

f= (w, B => H) = Ia(w(B), f= (w, H)), where Ia is the Goael's many-valued implication function:

and, if B = B1 1\ ... 1\ Bn then w(B) = min(f= (w, B1), ... , f= (w, Bn)).

From now on, and for the sake of a simpler notation, we will write w(4>) for f= (w,4>).

2.3 Fuzzy Temporal Constraint Inference Rules

Now, we are interested in presenting a set of inference rules that deal exclusively with temporal constraints and that capture the completion operations performed in temporal constraint networks. Actually, they are the ex­ tension for fuzzy constraints of those proposed in [Vila and Escalada-Imaz, 1994] that, together with modus po­ nens, were proved to be complete for crisp constraints. We will show their soundness w.r.t. the following notion of logical consequence in accordance to the well-known Zadeh's entailment principle in fuzzy logic [Zadeh, 1979].

Definition 3 A well-formed formula 4> is valid, written F 4>, iff w(4>) = 1 for all wEn.

Definition 4 A well-formed formula 4> is a logical consequence of a set of other well-formed formulas 4>1, ... ,4>n, written {4>1, ... ,4>n} F 4> iff for any wEn, min(w(4>!), ... w(4>n)) ~ w(4>) .

An immediate consequence of this definition of logical consequence is the following proposition which is a kind of restricted deduction theorem.

Proposition 1 Let ¢1> ... , ¢n and ¢ be facts. Then it holds

The definition of the inference rules make use of the following two special fuzzy duration sets:

Null durntion function,

Universal durntion function,

and of the following three operations on the set of fuzzy durations:

Next we present the inference rules.

Proposition 2 The above inference rules are sound w. r. t. the previous semantics.

Proof: See [Godo and Vila, 1995].

3 The Possibilistic Temporal Language

To fully exploit the use of fuzzy expressions for tem­ poral durations in the language, it seems very natu­ ral to also allow for partial degrees of matching be­ tween fuzzy expressions. As a matter of example, con­ sider the following piece of knowledge: the duration of the Ondulat~ng Fever Period of a patient has been be­ tween 2 and 3 weeks, but it is known that in any case it has been not less than 17 days and not more than 32. This knowledge can be represented by the proposi­ tion FUZZDIST(BEGIN(OFP), END(OFP), 1r), being 1r the trapezoidal possibility distribution corresponding to the parameters [17, 22, 27, 32] and presented graphically in figure 2.

On the other hand, the example rule in Section 2.1, codifying the Brucelosis evolution pattern, has FUZZDIST(BEGIN(OFP), END(OFP), (4, 20, 25, 45]) as

one of conditions, being the membership function 1-'A of the fuzzy duration represented by the tuple [4, 20, 25, 45] also shown in the figure 2. Of course 1r i 1-£A, and therefore FUZZDIST(BEGIN(OFP), END(OFP), 1r) does not entail FuzzDIST(BEGIN(OFP), END(0FP),J-£A), in the sense of Definition 4, but one would say that it nearly entails it. In such a context, if we want to use the above mentioned rule to conclude about the possi­ bility for that patient of having Brucelosis, it makes sense to think of a way to measure at what extent 1r is included in 1-'A and use this measure as a certainty degree with which that condition of the rule is satisfied 4 . Therefore, in reasoning with fuzzy constraints one is led to deal with partial degrees of certainty, mainly of propositions involving fuzzy duration constraints but also non-fuzzy propositions. On the other hand, many AI domains, being the medical one a good example, re­ quire the management of uncertainty from a knowledge representation language. Possibility theory [Dubois and Prade, 1988] offers a unified framework where to model both uncertainty and fuzziness. We would like to stress here again that the kind of uncertainty the possibilistic model deals with comes from the use of imprecise knowl­ edge modelled by a fuzzy set, and differs from other kinds of uncertainty, like probability, which are of different na­ ture. We present below an extension of the language decribed in the previous section where lower bounds of a necessity-like degree are attached to formulas, with a semantics based on ideas in [Dubois and Prade, 1990; 1992] and extending the Dubois, Lang and Prade's Pos­ sibilistic Logic semantics [Dubois et al., 1994] for crisp propositions.

Let us make more precise the above claim. Temporal constraint inference rules provide the tightest constraints between durations of events entailed by a given set of temporal facts. Such constraints can be used as inputs in heuristic rules that may help in turn to obtain addi­ tional temporal facts. Therefore, when trying to apply heuristic rules, we are interested in certainty qualifying the conditions of such rules given for granted the con­ straints provided by the temporal facts. Next subsection is devoted to discuss how such certainty evaluation can be performed.

4 Such certainty degrees should not be confused with the truth degrees arising from the many-valued approach intro­ duced in the previous section to evaluate fuzzy temporal ex­ pressions. There, £-models evaluate the truth degree of for­ mulas in a purely functional way. This is not the case with the certainty degrees we propose in the possibilistic temporal extension.

3.1 Certainty evaluation of fuzzy constraints

In technical terms, for a given duration variable X on VU, we aim at finding the certainty evaluation of a fuzzy proposition XisA (the condition of a rule), being A a fuzzy subset of VU, knowing that the values of X are restricted by a possibility distribution 1r (the constraint induced by the temporal fact base). Dubois and Prade [1992] have discussed this issue and they propose to use the following measure:

where I{} is the reciprocal of the Gooel's implication, i.e.:

and J.tA is the membership function of the fuzzy set A. It is remarkable to notice that £(J.£Ain) = 1 iff J.tA 2: 1r, and that £(J.£Ain) reduces, when A is non-fuzzy, to N1r(A) = inf{1-n(u)iu fl. A}, the necessity measure of A based on 1r and used in Possibilistic Logic . In fact, Dubois and Prade [1990,1992] discuss the inverse prob­ lem, that is, which possibility distribution corresponds to the semantical interpretation of the qualified proposi­ tion "(X is A) is a- certain", and to which evaluation of A is identified. This is also of much interest since it will allow us to use uncertain constraints derived from a set of heuristic rules as inputs in the temporal fact base. An interesting line of argumentation leads them to represent the above qualified proposition by the following family of inequalities

which, as expected, turns to be equivalent to

However, the certainty degree £(J.£Ain) provides not very natural results in very common situations. In particular, the existence of only one element u in the domain for which n(u) = 1 and J.£A(u) < 1 causes the certainty degree £(J.£Ain) to be 0, independently whether the value J.£A(u) is close to 0 or close to 1. For instance, this is the case depicted in Figure 2 where an easy computation shows that £(J.£Ain) = 0 while 1r is very close to entail A.

This counter-intuitive behaviour has led us to look for an alternative definition of the certainty degree. If one wants to keep the property that £(J.£Ain) = 1 iff 1r :::; J.tA, one is forced to stay either with residuated many-valued implications 5 or with their reciprocals. Residuated im­ plications, in general, share the problem that the result­ ing certainty degree does not collapse to the necessity de­ gree in the non-fuzzy case (actually it becomes a trivial {0, 1 }-valued measure) , and thus the resulting semantics is not an extension of that of Possibilistic Logic. On the other hand, the reciprocal implications, in general again, share the above mentioned problem of the Gooel 's recip­ rocal implication. However, among these two families of implication functions, there is one exception (up to isomorphisms), the well-known Lukasiewicz implication

5 Residuated many-valued implications are binary opera­ tions in (0, 1) defined as I(x,y) = Sup{c E (O,l)jx®c::; y}, where ® stands for a t-norm, i.e. a a binary operation in [0, 1] which is associative, commutative, non-decreasing in each variable, with 1 as neutral element and 0 as absorbent element.

that avoids the above problems. Namely, defining

we keep most of the interesting properties of the previous definition while solving the main problem with it. Now the interpretation of" given n, (X is A) is (at least} a­ certain" as E(J.£Ain) 2: a is semantically equivalent to

This representation can be provided with practically the same argumentation used in [Dubois and Prade, 1992] to justify their proposal, only a slight modification in one step is needed. The agreement of this proposal with the original one in the non-fuzzy case is easy to establish by noticing that IL(a, J.tA(u)) = max(1- a,J.tA(u)) when A is non-fuzzy.

3.2 Possibilistic Semantics

Now, we are prepared to define our Possibilistic Tempo­ ral Language and show that captures the above require­ ments.

Definition 5 The set of possibilistic temporal formulas is the set LT = {4>[a]l4> E C and a E [0, 1]}.

Definition 6 A Possibilistic Temporal model II is a possibility distribution over the set n of £-models, II: n __. [o, 1] 6 .

Definition 7 (Possibilistic Entailment) A possi­ bilistic temporal model rr satisfies a wff 4> with a certainty degree a, written rr FT </>[a], iff

where we have identified the £-formula 4> with its corre­ sponding fuzzy subset of the set of £-models n defined as J.£¢(w) = w(</>). The notion of logical consequence is the natural one, i.e. a possibilistic tempoml formula G is a logical consequence of a set of possibilistic tempoml formulas F1, ... , Fn, written {F1, ... , Fn} i=T G, iff for any possibilistic model IT, II FT F1, ... , rr FT Fn imply rr I=T c.

The possibilistic entailment FT in £7 is related to the entailment relation I= of the basic language C (without uncertainty) as follows.

Proposition 3 Let ¢1, ... , <Pn and 4> well-formed for­ mulas of C. Then it holds that { </>1, ... , </>n} I= </> iff { </>1[1], ... , </>n[1]} FT </>[1].

6 These possibilistic models differ from those of Possibilis­ tic Logic in that the possibility distributions are defined on (0, I)-valued .C-models, rather than on {0, 1}-valued !­ models.

This proposition shows that the possibilistic entail­ ment FT actually extends f= in a natural way, as it could be expected. In particular, the set of inference rules for fuzzy constraints presented in section 2.3 are then also sound w.r.t. for f=T, once the fuzzy tempo­ ral constraints appearing in those rules are attached the certainty value 1.

A possibilistic temporal knowledge base is a pair KB = (:FB, RB) of a set of weighted facts :FB and a set of weighted rules RB. The temporal fact base will be rep­ resented as a network of fuzzy temporal constraints.

4 Inference

In this section we supply the set of inference rules which compose the deductive system of our logic. The sepa­ ration between the non-temporal and the temporal part also holds for them: we distinguish between rules specific for temporal propositions and rules applied to arbitrary well-formed forms in the KB.

Since temporal inference rules deal exclusively with temporal constraints which certainty degree is 1, for the sake of completeness, additional inference rules are needed to state the degree of fulfillment for a temporal proposition and viceversa.

Fuzzy Constraint Inference Rules. As already mentioned, the Reflexivity, Universal Constraint, Sym­ metry, Transitivity, Intersection and Inclusion inference rules, with the certainty value [1] attached to premises and conclusions, are sound rules w.r.t. to the possibilis­ tic semantics, and they capture constraint network pro­ cedures.

Constraint Certainty Inference Rules. The fol­ lowing inference rules show how uncertainty influences fuzzy temporal constraints, and thus how they provide a kind of bridge between knowledge from the temporal constraint network and knowledge from a heuristic rule set. In other words they provide a way to infer certain fuzzy constraints from uncertain ones, and viceversa.

And the converse inference rule is defined as follows:

Taking back the example of the beginning of Sec­ tion 3 and applying the R1 inference rule, from FUZZDIST(BEGIN(OFP), END(OFP), [4, 20, 25, 45]), with certainty 1, we can derive the fuzzy constraint FUZZDIST(BEGIN(OFP), END(OFP), [17, 22, 27, 32]), with certainty E(J.LA!11') = 0.9 (see Figure 2). This cer­ tainty value could be used after to conclude Brucelosis from the rule when applying the modus ponens inference rule introduced below.

Proposition 4 The above two inference rules Rl and R2 are sound.

Proof: See [Godo and Vila, 1995].

General Inference Rule. General inference is per­ formed through a single inference rule which is a sort of possibilistic modus ponens (PMP) and extends the one for necessity-valued formulas in Possibilistic Logic [Dubois et al., 1994]:

Proposition 5 (soundness) The above possibilistic modus ponens inference rule PM P is sound

Proof: For simplicity, we take m = 1. Thus we will show that H[min(,B, a)] is a logical consequence of {(B ===} H)[a], B[,B]}. Suppose then E(B ===} HITI) 2:: a and E(B!TI) 2:: ,B. This implies, for all w E n, that

IL(TI(w),I0 (w(B),w(H)) 2:: o: and

IL(TI(w),w(B)) 2:: ,B.

Therefore, since IL is non-decreasing in the second vari­ able, we have

min( a, ,B) ~ IL(TI(w), min(Ia(w(B), w(H)), w(B))), and since the inequality min(x,Ia(x,y)) ~ y always holds, we also have min( a, ,B) ~ IL(TI(w), w(H)). Fi­ nally, taking infimum w.r .t. w, we get

It is interesting to observe that in the above proof, concerning the certainty degrees, we only make use of the monotonicity of IL, and so, the possibilistic modus ponens rule would be valid also for other definitions of E(.!.) using other implications, in particular for the reciprocal of G&iel 's implication -used in [Dubois et al., 1994] to define an extended resolution-like inference rule-, largely discussed in a previous section.

5 Concluding Remarks

We have presented a propositional temporal language based on fuzzy temporal constraints, and able to deal also with uncertainty within the possibilistic framework. Although this is a very restricted language, it turns out to be expressive enough for a large set of applications in the medical domain and, eventually, in other domains where knowledge is of propositional nature, yet explicit account of temporallity and uncertainty are required. This language is provided with:

1. A formal semantics based on possibilistic models to account for the uncertainty issued by the fuzziness of our temporal constraints.
2. A sound inference system composed of a set of fuzzy temporal constraint inference rules, a possibilistic modus ponens and a pair of constraint certainty in­ ference rules. An overall picture of the way this in­ ference system can operate is graphically presented in figure 3.

We are currently studying the completeness of our logic. Previous results on the non-fuzzy case [Vila and &calada-Imaz, 1994] seem to be a guarantee on the way to proving it. We are also working in developing correct and efficient deductive algorithms to make our language operational.

The approach we have presented here allows for fur­ ther work on two main lines. First the extension to first­ order Horn clauses, incorporating relations on the Fuzzy Duration functions, and second, to involve more general types of constraint networks which will be a matter of study for fuzzy networks as well.