Temporal Matching: Recognizing Dynamic Situations from Discrete Measurements

1 Introduction

Conventionally, in Qualitative Reasoning the term measurement interpretation stands for the task of explaining a given set of measurements by reconstructing a section of the system's envisionment that accounts for all of the measurements (for examples, see [Forbus83], [Forbus86], [Simmons82]). In a diagnostic setting measurement interpretation is useful when observations have already been made (e.g. by automatic sampling of quantities) but a hypothesis has not yet been formed.

Frequently, though, we are faced with the opposite situa­ tion: given a hypothesis we must determine a set of obser­ vations that will support it. Things become complicated when the hypothetical behavior is characterized by a specific sequence of events. We have found examples for this case while constructing MOL TKE, an expert system for the dia­ gnosis of CNC-machining centers [ANRR88]. A medical domain in which temporally distributed symptoms play a role is described in [Tsotsos85]. Verifying that such a behavior is occurring is the aim of temporal event recogni­ tion; it necessarily requires planning a measurement sequence that consists of observations at more than one time point. In this paper we discuss the problem of giving a meaningful definition of a 'successful match of a measurement sequence against a situation description' and present an algorithm for planning and matching an observation sequence.

2 An example

Consider the following example from MOLTKE's domain: One possible cause for an undefmed position of the tool magazine is a faulty limit switch. This cause can be ruled out if the status registers IN20 and IN30 of the CNC control system show the following behavior: at the begin­ ning both registers contain the value 1. Then IN20 drops to 0, followed by IN30. Finally, both return to their original values in the reverse order.

1 The work described was partially supported by Deutsche Forschungsgemeinschaft as part of SFB 314.

The situation is illustrated in the following figure:

If we want to recognize an occurrence of this situation we have to solve two problems:

• -We have to plan an observation sequence for IN20 and IN30 that can be observed only in this particular situation.
• If at any point partway through the plan we are confronted with an unexpected measurement we have to be able to decide whether this piece of information is compa­ tible with the situation or not.

The solution to the first problem depends on the assump­ tions we make about measurements. When we speak of a measurement we mean an observation of the amount of a specific quantity at a specific time point, made either by a human observer or by a sensor. For our purposes measure­ ments are characterized by the following properties:

• (Ml) No two measurements can take place at exactly the same time.
• (M2) All measurements are discrete, i.e. the amount of a quantity is measured at a time point rather than over an interval.

Axiom (M2) immediately poses the problem that the period over which a situation occurs cannot be covered with measurements. Consequently, we have to define a weaker criterion: we would like to be able to derive from the situa­ tion a specific measurement sequence such that if this sequence has been observed and all possible additional measurements fit in we are sure that no other situation can have occurred modulo the resolution of our measurement techniques. In our example, we would insist on observing IN30 = 1 again after IN20 = 0 has been measured to make sure that IN30 does not drop to 0 before IN20 does. If on the other hand our initial measurement for IN30 had been IN30 = 0, we would have rejected an occurrence of the situation because there is no way of fitting in this observa­ tion at the beginning of the situation.

All of these intuitive notions will be defined more for­ mally in the next section.

3 Situations, measurements, and matching

3.1 Situations

While figure 1 is a perfectly natural representation of the situation for a human reader, we adopt a representation that is better suited to algorithmic manipulation.

The basic vocabulary for the description of situations comprises quantities, intervals, episodes and value histories. As each of these terms have been used in the literature with varying meanings, we briefly summarize their intended interpretations within this paper.

Intervals are defined as in [Allen/Hayes85]. For the pur­ pose of mapping an interval I onto a global time line we assume the existence of a left (right) endpoint of I which is denoted by L(l) (R(I)).

We assume that Quantities q take on qualitative values1 from some set Dom(g) and change their value only a finite number of times during any situation. A pair <l,v>, where I is an interval of maximal extent during which the (qualitative) value of q is constantly equal to v, is called an episode. The values that a quantity q takes on over a period of time are represented as a value history which is a set of episodes in which the episode intervals form a linear chain related by the interval relation "meets".

DEFINITION: A situation is a triple <Q, H, C> where

• Q is a finite set of quantities;
• H = {Hq I q e Q} is a set of value histories and
• C = {CE,E' IE, E' episodes of histories in H} is a set of constraints specifying the relative positions of the histories w.r.t. each other. Each CE,E' is a disjunction of Allen interval relations ([Allen83])2 one of which is required to hold from the interval of E to the interval of E'.

In our example, IN20's value history is (E 1 =<11,1 >, E2=<I2,0>, E3=<l3,l>), IN30's value history is (E4=<I4,l>, Es=<Is,O>, E6=<16.1>). C contains CE,E' = {m} for each pair E, E' of consecutive episodes in the same history. The relative positions of the epsiodes in the two histories are specified by constraints such as CE 4 ,E 2 = CE2.E6 = {o}.

Actually the constraints in C are further restricted to convex relations, a subalgebra of Allen's full relation alge­ bra, which are defmed in [Nl>kel89].

The similarity between situations and the format of the envisionments generated by a number of qualitative simulation programs (e.g. HIQUAL [VoB87] or programs based on the episode propagators in [Williams86] and [Decker87]) is not accidental. One goal in a later stage of the project is to use one of these programs to generate the situation descriptions and use them later as complex symptoms in a rule-based diagnostic system. In this system the matching algorithm described in section 4 will be invoked by the rule interpreter whenever a situation is encountered in the condition part of a rule.

1 Stated in another way, all continuously changing quantities have been replaced by discrete ones by imposing an order-preserving equivalence relation on their values.

2 We abbreviate interval relations as usual, e.g. m for "meets", o for "overlaps" and so on.

We need some more terminology to formalize the relation between situations as patterns and actual occurrences of situations:

DEFINfi10N: For every set of value histories H let PfH) := { L(l) I Hq e H, <l,v> e Hq } u { R(l) I Hq e H, <l,v> e Hq } denote the set of (left and right) endpoints of all episode intervals in all histories of H.

DEFINITION: An instance of a situation S = <Q,H,C> is a mapping D: P(H) ~ T (T dense, totally ordered, without least or greatest element, e.g. T = IR), which respects the relations in C.

DEFINITION: An instanceD of a situation S = <Q, H, C> ~ in an interval 0 1: Tiff D maps into 0 and

\;;/ t E 0, q E Q: (M q t) = V

We say that a situationS has occurred when we are not interested in the properties of the particular instance.

3.2 Measurements

DEFINITION: A measurement is a triple <q, t, v>,where q is a quantity, t e T and v e Dom(q).

DEFINfi10N: A measurement seQ.Uence M is a fmite set of measurements { <qi. ti, Vi> li=1, ... ,n where t1 < t2 < ... <

tn. Let ln.t(M). := [t1 ; tn] (i; T.

DEFINITION: A measurement sequence

M = { <Qi,ti,Vi>} i=1, ... ,n is compatible with a situation S if there is an instance D of S that maps into Int(M) and Vi: 3 <1, v> E Hqj: D(L(I) ~ ti ~ D(R(I)) II v =Vi.

3.3 Matching

The problem of recognizing an occurrence of a situation can be split into two tasks:

• (a) planning a desired sequence of observations
• (b) matching the actual observations against the situation.

We will discuss (b) first and return to (a) in section 4. Ideally, we would like to define a relation 'matches' between measurement sequences M and situations S in such a way that the following two properties hold:

Completeness: VS VM: M determines S:::) matches (M, S)

3 (M q t) is borrowed from QPT notation and means "the (magnitude of the) amount of q at timepoint t" . M is a total function.

where M determines S if the observation of M implies that S has indeed occurred in Int(M).

Soundness: \IS VM: matches (M, S) => M determines S.

Evidently, with this definition we run into problems regarding the granularity of measurement sequences and situations. Consider our example and the measurement sequence indicated by the arrows in figure 2:

Although the observations are compatible with an instance of S, we cannot guarantee that it has occurred. For all we know, the situationS' in figure 3

may equally well have occurred. Hence, matches(M, S) must not hold.

As long as we are committed to discrete measurements the dilemma cannot be resolved. If we want to capture the way that discrete measurements do act as filters on situations, we have to replace "M determines S" by a weaker notion. We therefore define the granularity of a situation's instance and of a measurement sequence.

DEFINITION: The granularity of an instanceD of a situation .S. (written gran(D)) is the shortest duration among all epi­ sode intervals in the instance.

DEFINTI10N: The granularity of a measurement sequence M (written gran(M)) is the longest gap between any two consecutive measurements of the same quantity in M.

DEFINTI10N: A measurement sequence M weakly deter­ mines S if the following implication holds: M has been observed=>

[(3 D instance of S: D occurs in lnt(M)) v (\IS': \f D' instance of S': D' occurs in Int(M) => gran(D') ~ gran(M))].

The intention behind this definition is that if we have the extra knowledge that the episodes over which the quantities remain (qualitatively) constant do not become arbitrarily short, then a suitably chosen measurement sequence which is denser than the minimal duration of the episodes can indeed determine a situation in the stronger sense. Notice the similarity of this argument to the discussion in [Forbus86].

We next give a definition of 'matches' that satisfies the weak versions of the completeness and soundness proper­ ties.

DEFINITION: A measurement sequence

M=( <qi,ti,Vi> li=l, ... ,n matches a situation S=<Q,H,C>, iff there is an instance D of S that satisfies the following conditions:

• (i) D maps into Int(M) .
• (ii) \f <q, t, v> E M: 3 <l,v> E Hq: D(L(I)) ~ t ~ D(R(I)) (all measurements are compatible with the instance)
• (iii) \f q E Q: \f <1, v> E Hq: 3 <q, t, V> E M: D(L(I)) ~ t ~ D(R(I))

(there is at least one observation for each episode)

• (iv) \f q, q' E Q; \f E = <l,v> E Hq, E' = <I',v'> E Hq': E necessarily overlaps E' 1 =>

3 <q, t, v>, <q', t', v'> E M: D(L(I')) ~ t' ~ t ~ D(R(I)) (each overlap of two episodes required by C is verified by observing the overlapping episode at a point of1£L the observation of the overlapped episode)

For the sketch of a proof for the claim that this definition satisfies the completeness and soundness properties the reader is referred to [Nokel88].

If we take a second look at the measurement sequence M in figure 2, we find that it satisfies all of (i)-(iii), but not (iv). By adding two additional measurements for IN30 = 1 and one for IN20 = 0 we get the measurement sequence M' in figure 4 which indeed matches the situation.

There is an interesting asymmetry in the definition: (iv) makes sure that every overlap specified in the constraints of the situation is actually observed; there is no analogous condition which ensures that two episode transitions speci­ fied to take place simultaneously actually do so. In fact, given the limitations of discrete, one-at-a-time measure­ ments there cannot be such a condition. How, then, can we detect that the measurement set M' in figure 4 does not match a situation where IN20 and IN30 change values simultaneously? As we see in figure 5, there is no consistent mapping that associates measurements with epi­ sodes and condition (ii) is violated. Hence, we do not have a positive condition for the occurrence of simultaneous transitions, but we know that given a measurement sequence of sufficiently fine granularity we would detect an overlap if there were one instead.

1 Formally: CE,E' is any subset of { o, oi, d, di, f, fi, s, si, =).

4 The matching algorithm

We are now ready to tackle problem (a) above. In order to implement the matching definition we have to add a mechanism which suggests the observations and tum the static match of the complete measurement set against the situation, into an incremental match which minimizes effort by detecting irreparable deviations from the situation as early as possible.

Recall that we want to verify (i) that all episodes mentioned in the situation actually occur and (ii) that their relative positions satisfy the interval relations in the con­ straint part. Verifying (i) is relatively easy: all we have to watch out for is not to associate a measurement with an episode E unless we have an observation for every episode E' that precedes E according to C 1. As for (ii), imagine starting with an Allen interval graph G containing the epi­ sode intervals as nodes and having all edges labelled with "no-info"2.3 Each pair of measurements in a sequence rules out some of the initial relations according to the observa­ tion rule: if m1 = <q}, t}, vp.and m2 = <q2, t2, v2>, ti < t2 are associated with episodes Et and E2, respectively, then it follows that E2 cannot possibly precede Et.

If we can find a measurement sequence which narrows down the labels in the interval graph from the initial state to subsets of the corresponding relations in the constraint part C of a situation S and contains at least one observation for each episode, then it matches S. The intermediate stages of the interval graph can be used to plan the next measure­ ment: if the relation from episode E 1 to E2 in the interval graph contains < and/or m but the relation. in C does not, then plan to observe E2 and Et -in that order- to get rid of the unwanted relations. Furthermore, all episodes that have not been observed at all are candidates for observation. This initial candidate set can be pruned using rules which are detailed in the algorithm below.

1 i.e. CE.E' is one of ( <}, (m}, or ( <,m}.

2 The disjunction of all 13 primitive interval relations.

3 Well, not quite no-info. Since simultaneous transitions can be observed only via negationis (by failing to detect an overlap instead, as discussed at the end of section 3.3), we cannot expect to narrow down the edge labels from no-info to a simultaneous transition such as ( m} or ( <, m} just by applying the observation rule (fig. 6). We therefore initialize the edge labels in G with no-info except where the relation inC is one of (m} or{<, m}; these we take over unchanged and propagate them using Allen's algorithm to arrive at the initial state of G. In this case a mismatch is detected when an application of the observation rule to the offending overlap results in the empty disjunction as the new edge label, signalling an inconsistent state of G.

The algorithm that we are about to describe (see next page) operates in a cycle with alternating suggestions and measurements until the candidate set is empty. We report a match iff at this point the labels of the interval graph are subsets of the constraints in C and no episode has been skipped unobserved. The algorithm is of the "sweep-line" type and at any point during the matching process divides the set of episodes into three classes:

• sleeping: episodes that have not yet been observed;
• open: episodes which have been observed at least once, but the following episode has not been observed.
• closed: episodes which precede an episode in open.

As shown in [N6kel89], the test for global consistency in line (*) can be carried out in polynomial time (w.r.t. the number of episodes in the situation), if we restrict ourselves to convex interval relations. This result is very similar in nature to the one in [Vilain/Kautz86], although the sub­ algebra is defmed differently.

In our example, this algorithm suggests the measurement sequence M' from figure 4 which indeed matches the situa­ tion. Sequence M from figure 2, however, is rejected.

To find a matching measurement sequence for a situation S = <Q,H,C> do: Initialize interval graph G as described above; open~0; closed~0; sleeping ~ the set of all episodes in H; suggest a set N of quantities one of which should be measured next; while N "# 0 do end; obtain a measurement (m); fit_in_measurement (m); if m does not fit, then report failure, .s.tQU; suggest a set N of quantities one of which should be measured next;

if the relations in G are subsets of the relations in C, then report match else report failure; end.

To suggest a set of quantities to be measured next do:

!*Episodes which should be observed next are accumulated in candidates. Follow-ups contains the second episodes where a planned application of the observation rule forces the first episode into the candidate set; it is used for pruning the candidate set. *I

Find candidates:

• (a) follow-ups~ 0; candidates~ sleeping;
• (b) For each pair of episodes E1, E2 such that< and/or m occurs in the relation from E1 to E2 in G but not inC do:
• !* To get rid of the unwanted relations, observe first E2 and then E J, so that the observation rule can be applied. If E2 has not been observed before then add it to the candidate set (EJ will be added the next time around) else add E]. *I

ifE2 e sleeping then follow-ups ~follow-ups u (EI};

else candidates ~ candidates u (E 1);

Prune candidates:

Repeatedly apply the following deletion rules:

• (a) ifE1 E candidates, E2 e (follow-ups u candidates), E2 precedes E1 in C 1 then delete E1 from candidates; !*It is no use trying. to observe an episode, if there is another

in the candidate set which necessarily has to be observed before. *I

• (b) ifEI. E2 e candidates, E1 e open, E2 ends before the end ofE1 in c2 then deleteE1 from candidates;
• !* "EJ e open" means that EJ has been observed before and is to be observed again to make sure it is still c ontinuing. If there is another candidate E2 that ends before EJ does, we can postpone the observation of E] because after E2 has ended we will have to verify anyway that E] is going on even then. *!
• (c) ifE1, E2 e candidates, E1 e sleeping, E2 ends before the end ofE1 inC and E1 starts before the end ofE2 in c3 then delete E2 from candidates;
• I* Again, E 1 has to be observed before E2 so that the overlap can be verified. This case is not caught by (a) because E2 does not completely precede EJ. *I

Suggest the quantities to which the episodes in candidates belong; end.

1 i.e. CEE' is one of{<}, {m}, or {<,m}.

2 i.e. CE 2 ,E 1 . is any subset of { <,m,o,d,s}.

3 i.e. CE 1 ,E 2 is any subset of {oi,si,di}.

To fit in measurement (m) do:

Let m; <q,t.v>; Find the earliest episode E = <l,v> in Hq \closed;

if E E sleeping

then if there exists E' E sleeping u candidates u follow-ups from latest suggestion that precedes E in C then report "m does not fit", S1Q12;

I* In this case the observation sequence was not dense enough and we have missed an observation forE' which cannot be made up for after E has been observed. *I

for each preceding measurement m' do

let E' be the episode that m' has been associated with;

add E { <,m} c) E' to G and propagate according to Allen;

• (*) if the new G is not globally consistent. then report "m does not fit", .s.tQll;

I* An overlap was detected instead of a simultaneous transition. *I

ifE E sleeping then/* update sweep-line *I

closed ~ closed u (open n Hq);open ~ (open\ Hq) u {E} ;sleeping ~ sleeping\ {E}; Associate m withE; Report "m fits";

end.

5 Status of the implementation and further work

Following an early prototype [Lamberti88] the algorithms described have been fully implemented using the temporal extension ofProlog described in [Hrycej88]. Currently, they are being incorporated into the MOL TKE diagnostic system.

One of the system's severest limitations at the present moment is its incapability to deal with duration constraints. The following example demonstrates how absolute upper bounds on the episodes' duration could greatly improve the system's ability to abort the matching process when it encounters a non-instance of a situation. Recall our earlier example and assume that both IN20 and IN30 remain stuck at 0 indefinitely instead of returning to 1. The algorithm would cycle forever, suggesting to look for IN30 = 1 and accepting IN30 = 0 readings without a chance to recognize a time-out. Clearly, an upper bound on the duration of the IN30 = 0 episode would solve the problem, so adding this feature is our next step in the project.

Our plans also include applying the technique in an entirely different area. In reactive planning, feedback is gained by monitoring the plan execution and comparing the observations to the predicted behavior. If the predictions could be described in the form of a situation, temporal matching might be an instrument in designing efficient monitoring schedules.

Acknowledgements

I wish to thank Rainer Decker, Bernd Hellingrath, Tomas Hrycej, Robert Rehbold, Michael M. Richter, and Hans VoB for their constructive criticism. Special thanks go to Hans Lamberti and Johannes Stein for numerous contribu­ tions during the implementation work.