Temporal reasoning with constraints on fluents and events

发布时间:2021-11-29 06:13:06

Temporal Reasoning with Constraints on Fluents and Events 3
Eddie Schwalb, Kalev Kask, Rina Dechter

Department of Information and Computer Science University of California, Irvine CA 92717 feschwalb,kkask,dechterg@ics.uci.edu

Abstract

We propose a propositional language for temporal reasoning that is computationally effective yet expressive enough to describe information about uents, events and temporal constraints. Although the complete inference algorithm is exponential, we characterize a tractable core with limited expressibility and inferential power. Our results render a variety of constraint propagation techniques applicable for reasoning with constraints on uents.
1 Introduction

Consider the issues raised by the following \story". At 8:00 the micro lm was deposited in the safe and at 11:00 the micro lm was gone. John was at the bar between 8:10 - 8:30 and between 9:10 -12:00. He was also at the poker table between 8:35 - 9:00. Fred was at the bar between 8:30 - 10:00 and between 10:45 12:00. The bar opened at 7:30 and closed at 12:00. We know that at least 15 minutes are required to take the micro lm and return to the bar. Given the story above, we are interested in answering queries such as \Does the story entail that Fred took the micro lm ?" and \What are all the possible scenarios in this story ?". We wish to capture the human ability to answer such queries without information about speed of movement or distances. We wish to describe information conditioned on occurrences of events. For instance, a sentence like \at least 15 minutes are required to take the micro lm and return to the bar" should be accounted for only if someone took the lm; a query like \When did John take the micro lm ?" assumes that John took the micro lm.
This work was partially supported by NSF grant IRI9157636, by Air Force Oce of Scienti c Research grant AFOSR 900136 and by grants from TOSHIBA of America and Xerox
3

In classical propositional logic the atomic entities are propositions. In dynamic environments the atomic entities are called uents. They may repeatedly change their value as events occur and are functions of the situation or time. Our work builds upon temporal languages proposed by McDermott and Dean [11, 5], Allen [2], Kowalski and Sergot [9] and Shoham [14]. We accommodate various constructs proposed in these languages (time points and intervals). Our main goal, however, is to equip a temporal language with a computationally manageable inference engine. The primary task of any reasoning system is determining consistency of the given theory. For temporal languages this means determining the consistency of sentences involving a combination of temporal and propositional constraints. For example, consider the statement \Either Bob or Mary must tend the bar, but Bob has to leave on an errand and Mary has an appointment with the doctor". How do we infer that Bob's errand must be either before or after Mary's appointment ? In this paper we propose a temporal language whose inference engine is based on qualitative and quantitative temporal constraints [1, 6, 7, 12, 15, 16]. Decoupling the propositional and temporal constraints provides us with inference algorithms that are based on propositional satis ability and temporal constraint satisfaction, and allows us to identify a useful tractable core. The proposed language, called HOT, is de ned over Holds, Occurs and T emporal propositions. We assume that events are instantaneous and serve as the only time points at which uents may change their values. We use Holds(F; E1; E2) to state that the uent F is true between events E1 and E2, Occurs(E ) to state that event E occurred, and T ime(E ) for the time of its occurrence. We focus on the tasks of deciding consistency and computing consistent scenarios, which enables us to answer entailment and other queries of interest (such as inferring whether certain events must, might, or could not have occurred). Our language has a tractable core which allows us to make weak (sound but incomplete) inferences. When augmented with ad-

ditional axioms, our language yields sound and complete inference algorithms at the expense of increased computational complexity. The paper is organized as follows. Section 2 describes the syntax and semantics of our language. Section 3 gives an alternative propositional semantics for the language. Section 4 introduces a new model of conditional temporal constraint networks that serves as the computational engine.
2 The Language

with E and ends with E , (3) T ime(E ) fR1; . . . ; R g I j k where R1; . . . ; R 2 f before, starts; during, nishes, after g. 3. An interval-interval constraint I i j fR1; . . . ; R g I p q (4) where R1; . . . ; R ; m  13 are distinct and
j k i m E ;E m E ;E m m E ;E

Our language, called HOT, is a set of sentences over Holds, Occurs and T emporal propositions. We use two (disjoint) sets of symbols, uent symbols and event symbols. A uent is a propositional function of time and a uent literal is either a uent symbol or its negation. An event E is a pair (Occurs(E ); T ime(E )), where Occurs(E ) is a propositional variable that is assigned true i E occurred, and T ime(E ) is a real valued variable that speci es the time E occurred. We use two special events: E , for \the beginning of the world", and E , for \the end of the world". Unless otherwise noted, we use right-sided half open intervals [a; b) for reasons to be clari ed later. In addition to Occurs propositions there are Holds and Temporal propositions. A Holds proposition has the form Holds('; E ; E ) (1) where E and E are event symbols and ' = F1 _1 1 1_F is a disjunction of uent literals. We also use the following abbreviations: If E = E we write (1) as Holds('; E ). If E = E we write (1) as Holds('; before E ). If E = E we write (1) as Holds('; after E ). If E = E = E or E = E = E or both E = E and E = E we write (1) as initially ', eventually ', always ' respectively. A Temporal proposition is a qualitative or quantitative temporal constraint over time points and time intervals [12]. Given a pair of events E ; E , I i j denotes an half-open interval that begins with (includes) T ime(E ) and ends with (excludes) T ime(E ). A temporal proposition is a constraint having one of three forms: 1. A point-point constraint T ime(E ) 0 T ime(E ) 2 I1 [ I2 [ 1 1 1 [ I (2) where I1 ; . . . ; I are intervals (over real numbers), speci ed by their end points. We also use the shortcuts T ime(E ) 2 I1 [ I2 [ 1 1 1 [ I , T ime(E ) = t and T ime(E )  T ime(E ) to have the obvious meaning. 2. A point-interval constraint between the time point at which event E occurred and the interval that begins
begin end i j i j k i j i i begin j j end j i i begin i j end i begin j end i j E ;E i j j i k k j k j j i i

R1 ; . . . ; R

m

8 before; after; meets; met0by; 9 > overlaps; overlapped0by; > < = 2 > during; contains; equals; > : starts; started0by; : ;
nishes; nished0by

Sentences in HOT are conjunctive normal form (CNF) formulas over Holds, Occurs and Temporal propositions as their atoms. Example 1: Consider the story in the introduction. The sentence \At 8:00 the lm was deposited in the safe and at 11:00 the lm was gone" is described by
Holds(Film in safe; Film deposited) ^ (Time(Film deposited) = 8 : 00) ^ Holds(:Film in safe; Film checked) ^ (Time(Film checked) = 11 : 00):

The sentence \at least 15 minutes are required to take the micro lm and return to the bar" is described by A similar sentence can be described for Fred.
2.1 Semantics
f e

Occurs(John take film) ! (Time(end John go safe) 0Time(begin John go safe) 2 [15; 1])

< F ; M ; E ; M >, where F is a set of two-valued functions of time; M is a mapping M : F 7! F
f f e e

An interpretation of a formula in HOT is a quadruple

of uent symbols into functions in F; E is a subset of event symbols and M is a mapping M : E 7! < of events in E into real valued time points. The value of M (') may change only when events occur, namely at a time point t = M (E ) for some event E . Intuitively, F is a set of uents that corresponds to uent symbols used in the formula and E is the set of events that actually occurred, mapped to the time points at which each of them occurred. De nition 1: An interpretation is a scenario (or a model) of a formula if all its clauses are assigned the truth value true under the following rules of evaluation: 1. Occurs(E ) is true i E 2 E. 2. We extend M to disjunction and negation, M (F1 _ 1 1 1 _ F ) = M (F1) _ 1 1 1 _ M (F ), M (:F ) = :M (F ).
f e f f k f f k

3. A holds proposition Holds('; E ; E ) is true i E ; E 2 E, and (a) in case E = E then M (')(M (E )) is true, (b) in case E 6= E then M (E ) < M (E ) and for any t such that M (E )  t < M (E ), M (')(t) is true. 4. A temporal proposition is true i the events speci ed occurred and the temporal constraint is satis ed, namely (a) a point-point temporal proposition (2) is true i E ; E 2 E, and M (E ) 0 M (E ) 2 I1 [ I2 [ 1 1 1 [ I . (b) a point-interval temporal proposition (3) is true i E ; E ; E 2 E and M (E ) < M (E ) and one of the relations R1; . . . ; R holds. (c) an interval-interval temporal proposition (4) is true i E ; E ; E ; E 2 E and M (E ) < M (E ) and M (E ) < M (E ) and one of the relations R1; . . . ; R holds. 5. The truth value of the clauses and the CNF formula is evaluated with respect to the truth values of occurs, holds and temporal propositions using standard rules of evaluation.
i j i j i j f e i j e i e j e i e j f i j e j e i k i j k e j e k m i j p q e i e j e p e q m

For the rest of this paper we will restrict our treatment to HOT sentences whose Holds('; E ; E ) propositions we call simple, namely holds propositions in which ' is a single uent literal unless E = E and E = E (i.e. Holds('; always)). General holds propositions introduce computational complications which we will not address in this paper.
i j i begin j end

3 Propositional Semantics for HOT

A formula is s-satis able i it has a scenario. Note that Holds('1 ^ '2 ; E ; E )  Holds('1 ; E ; E ) ^ Holds('2 ; E ; E ). However, Holds('1 _ '2; E ; E ) is obviously not equivalent to Holds('1 ; E ; E )_ Holds('2 ; E ; E ). Also note that Holds(:'; E ; E ) is not equivalent to :Holds('; E ; E ). The formula Holds(F; E ; E )^ Holds(:F; E ) is inconsistent but Holds(F; E ; E )^ Holds(:F; E ) is consistent because the interval I i j is half-open. If we used closed intervals, Holds(F; E ; E ) ^ Holds(:F; E ; E ) would have been inconsistent and the values of the uents would not be allowed to change when events occur. If we had used open intervals, specifying Holds(F; E ) would have been useless since it does not induce a constraint on the value of M (F )(t) for the open interval t 2 (T ime(E ); T ime(E )). An occurs, holds, or temporal proposition q is entailed by 9, denoted 9 j= q, i it is true in all scenarios of 9. As usual, 9 j= q i 9 ^ :q is inconsistent.
i j i j i j i j i j i j i j i j i j i i j j E ;E i j j k i f i j

In this section we address the task of deciding whether a formula is s-satis able. We wish to show that the task of deciding s-satis ability and nding a scenario reduces to a two-step process of propositional satis ability and temporal constraint satisfaction. Although both of these tasks are NP-complete, such a reduction opens the way for using known heuristics and known tractable classes. The idea is to view 9 as a propositional CNF formula. Once a propositional model is available, using temporal constraint satisfaction we can determine whether all temporal constraints, speci ed by temporal propositions assigned true by the model, can be satis ed simultaneously. De nition 2: [ p-model ] Given a set of event and uent symbols, a p-interpretation is a truth value assignment to holds, occurs and temporal propositions when viewed as propositional variables. A p-interpretation is a p-model of a HOT formula 9 i it is a propositional model of 9 and the set of temporal constraints speci ed by the temporal propositions assigned true is consistent. Upon trying this approach we see immediatelythat this process may yield p-models that do not correspond to any real scenario. The reason is twofold: holds propositions impose implicit temporal constraints that are not explicit in the formula, and temporal propositions should be assigned true i the temporal constraint they induce is satis ed (p-models capture only one-way implication). For instance, a formula consisting of just one holds proposition Holds(F; E ; E ) will have a pmodel that allows any assignment to temporal variables T ime(E ) and T ime(E ), since there is no explicit temporal proposition specifying T ime(E ) < T ime(E ). In order to avoid these super uous p-models, we augment 9 with axioms that explicate the intended meaning. In the following paragraphs we will augment a formula 9 with additional HOT sentences that will be called axioms. The resulting augmented theory 9 describes the same set of scenarios as the original theory 9. However, every p-model of 9 corresponds to a set of scenarios of 9 and every scenario of 9 corresponds to a p-model of 9 . De nition 3: [ axiom set A1 ] Given a formula 9, the axiom set A1 has four parts:
i j i j i j 0 0 0

Consider the statement \John was at the bar from 8:10 to 8:30". It is described by the formula 9 = Holds(John at bar; 8:10; 8:30).1 9 j= Holds(John at bar; 8:15; 8:25) but 9 6j= Holds(John at bar; 8:15; 8:35) because the value of the uent John at bar is not constrained after 8:30 and thus it can be either true or false.
Example 2 :
For the sake of convenience we will use real time points as events.
1

1. For all events add T ime(E ) < T ime(E ) < T ime(E ), and for all pairs of events E ; E add I i j fequalsgI j i . 2. For every event E speci ed in a temporal proposition T we add the axiom T ! Occurs(E ). 3. For every holds proposition Holds('; E ; E ) of 9 we include sentences stating that if a holds proposition is true, the corresponding events should have occurred and in the intended order:
begin end i j E ;E E ;E i j

and John was not at the bar at 10 : 00" which can be represented by the formula The axiom set A1 includes T ime(E ) < 8:00 < 10:00 < T ime(E ), and the axiom set A2 includes
begin

Holds(John at bar _ Fred at bar; always) ^ Holds(:Fred at bar; after 8:00) ^ Holds(:John at bar; 10:00)
end

Holds('; E ; E ) ! Occurs(E ) ^ Occurs(E ); Holds('; E ; E ) ! (Time(E )fstartsgI i j ); Holds('; E ; E ) ! (Time(E )ffinishesgI i j ):
i j i j i j i E ;E i j j E ;E

4. For every pair of holds propositions with opposing uents, Holds(F; E ; E ) and Holds(:F; E ; E ), we add a sentence stating that the two intervals are disjoint. In general we will add
i j p q

although there are special cases that are simpler. The next set of axioms deals with the complications introduced by disjunctive holds propositions. Here is an example. Example 3: Consider the example statement \Either Bob or Mary must tend the bar, but Bob has to leave on an errand and Mary has an appointment with the doctor". It can be represented by the formula 9 = In order to guarantee consistency of (5), it is necessary that the intervals of Bob's errand and Mary's appointment be disjoint. Otherwise, there will be a time point at which both Bob tend bar and Mary tend bar are false, contradicting Holds(Bob tend bar _ Mary tend bar; always): The set of axioms A2 , de ned next, includes a constraint that enforces those intervals to be disjoint. De nition 4: [ axiom set A2 ] Given a formula 9, if there exists a holds proposition h0 = Holds(F1 _ . . . _ F ; always) then for any set of k holds propositions fh = Holds(:F ; E i ; E i ) j 1  i  kg we include the sentence
k i i p q

Holds(F; E ; E ) ^ Holds(:F; E ; E ) ! (I i j fbefore; meets;met0by; aftergI
i j p q E ;E

E

p ;Eq )

:

Holds(Bob tend bar _ Mary tend bar; always) ^ Holds(:Bob tend bar; begin errand; end errand) ^ (5) Holds(:Mary tend bar; begin apnt; end apnt)

Since, the constraints introduced by A1 and A2 are inconsistent, the statement is inconsistent. The set of axioms A1 and A2 is not sucient to eliminate all super uous p-models. They do guarantee that for every holds proposition Holds(F; E ; E ) assigned true we can assign M (F )(t) = true for every t 2 I i j without creating con icts. However, A1 and A2 do not guarantee that when the holds proposition is assigned false, the negation of the intended constraint is satis ed in every p-model. To guarantee completeness we provide yet another set of axioms, denoted A3 , which specify that the truth value of a holds proposition is inherited by sub- and super-intervals and that a temporal proposition is assigned true i the temporal constraint is satis ed. De nition 5: [ axiom set A3 ] Given a formula 9, for every disjunction of uent symbols ' = F1 _ ::: _ F used in the formula, all uent symbols F , every set of events E , E , E , E and every temporal proposition T we include:
i j f E ;E k i j p q

Holds(John at bar _ Fred at bar; E ;E ) ^ Holds(:Fred at bar; 8:00; E ) ^ Holds(:John at bar; 10:00) ! (I8:00 end fbefore; meets;met0by; afterg10:00):
begin end end ;E

:Holds( ;E ; E ) ^ Occurs(E ) ^ Occurs(E ) ! W f(I  I ) ^ Holds(: ; E ; E )g p q i j 8
i j i j p;q E ;E E ;E p q i j E

(6)

Holds( ;E ; E ) ^ (I
2

:T

^

p ;Eq

I

E ;E

i

Holds( ;E ; E )
p q

j)

!

(7) (8)

8E

Occurs(E ) ! T

specif ied in T

where 2 f'; F g,  stands for the constraint fstarts, during, nishes, equalsg and T denotes the complement of the temporal constraint T . For example, if T = (I1 fstarts,during, nishesgI2 ) then T = (I1 fbefore, after, meets, met-by, overlaps, overlapped-by, contains, nished-by,started-by,equalsgI2).
Lemma 1: The size of axiom sets A1 ; A2 and A3 is at most O(n2), O(nk2 ( ) ) and O(n 1 n4) respectively, where n is the size of the theory axioms are added to, n is the number of event symbols and k is the maximum number of uent literals in a disjunctive holds proposition.
n k k e e

although there are special cases that are simpler. Example 4: To illustrate the utility of axioms A1 and A2 , consider the statement \John or Fred was always at the bar, but Fred was not at the bar after 8 : 00

hW^ h1 ^ . . . ^ h ! 0  (I pi qi fbefore; meets; met0by; after gI
k i<j k E ;E

Ep ;Eq ) j j

This axiom enables contrapositive reasoning with temporal propositions.

2

Propositional Constraints

Conditions (Buffer) Temporal Network

The truth values of conditions control the temporal subnetwork that needs to be satis ed. Clearly as more conditions are assigned true the corresponding temporal network is more constrained. We can conclude:
Theorem 2: A conditional temporal network N is
consistent i there exists a minimal model of the propositional part of N such that the set of temporal constraints whose condition is assigned true is satis able.

Figure 1: The structure of CTNs. We use 9 [ A1 [ A2 [ A3 to denote the closure under axioms A1; A2 and A3 . Lemma 2: The HOT formulas 9 and 9 = 9 [ A1 [ A2 [ A3 are equivalent with respect to s-satis ability. Theorem 1: Every p-model of 9 [ A1 [ A2 [ A3 corresponds to a set of scenarios of 9 and every scenario of 9 corresponds to a p-model of 9 [ A1 [ A2 [ A3 .
0

4 Conditional Temporal Networks The notion of p-models decouples the propositional

This suggests a procedure for determining the consistency of a CTN. We enumerate all minimal models of the propositional part of a CTN and for each of them determine whether the applicable temporal network is consistent. The task of computing the minimal models of a CNF formulahas been investigated and is known to be hard [4, 3]. For Horn formulas, the minimal model is unique and can be computed in polynomial time, thus tractability depends on the temporal constraints.
is Horn and temporal part is tractable, consistency can be determined in polynomial time.

constraints from the temporal constraints and enables us to discuss them in isolation. We call this framework conditional temporal networks. De nition 6: A conditional temporal network (CTN) has two types of variables: propositional and temporal (point and interval), and two types of constraints: propositional and temporal. Every temporal constraint T is associated with a unique propositional variable C , called its condition. A conditional temporal constraint is a pair (C : T ). A propositional constraint is a propositional CNF formula over propositional variables and temporal conditions. A solution to a CTN is a truth value assignment to the propositional variables and temporal conditions, an assignment of values to the temporal point variables and a selection of a single relation from every qualitative temporal constraint, such that every propositional constraint and all temporal constraints whose condition is assigned true are satis ed simultaneously. Using these de nitions, we can intuitively divide every CTN into propositional and temporal parts. Propositional constraints impose certain restrictions on the conditions that act as a bu er and allow us to perform computations on the propositional and temporal parts of the network separately (see Figure 1). Example 5: Consider a network with seven variables: a propositional variable P , a point variable X1 , two interval variables I2 ; I3 , and three conditions C1; C2; C3, with the constraints One solution is P = C1 = C2 = C3 = true, X1 = 1:0, X1 fstartsgI2 , X1 ffinishesgI3 , I2 fmet0bygI3 .
P $ C 1 $ C2 $ C 3 ; (C1 : X1 fstartsgI2 ); (C2 : X1 ffinishesgI3 ); (C3 : I2 fbefore; after; meets;met0bygI3 ):

Corollary 1: Given a CTN whose propositional part

4.1 Tractable Core

We determine the consistency of 9 = 9[ A1 [ A2 [ A3 by checking the consistency of a CTN in which propositional constraints are the propositional clauses of 9 , conditions are the temporal propositions of 9 and temporal constraints are speci ed by those temporal propositions. Axiom set A1 introduces Horn clauses and tractable temporal constraints. Axiom set A2 and axioms (6) and (8) of A3 are intractable since they introduce non-Horn clauses. If we do not add axiom sets A2 and A3, p-satis ability and p-entailment become tractable for Horn temporal formulas.
0 0 0

Theorem 3: If 9 is a Horn temporal formula in which every holds proposition speci es a single uent literal and every temporal proposition speci es either single interval (if point-point) fstartsg or f nishesg (if point-interval), fequalsg, fbefore,meetsg,fafter,metbyg or any of their disjunctions (if interval-interval), then p-consistency of 9 [ A1 can be determined in O(j9j2 + n3) steps, where n is the number of event symbols.
e e

We will examine the inferences that 9 [ A1 is capable of making. We use 9 j= to denote s-entailment and 9 j= to denote p-entailment. Clearly, for every sentence , if 9[ A1 j= then 9[ A1 [ A2 [ A3 j= and thus 9 j= . However, it might be that 9 j= and 9 [ A1 6j= . Still, if there is a clause ! in 9 and 9 [ A1 j= then 9 [ A1 j= .
p p p p p p

Example 6: When adding only A1,
Holds(F; always) j= Holds(F; always) 6j= Holds(F1; E ; E ) j= Holds(F1; E ; E ) 6j=
i j i j p p

Acknowledgments
i j j

p

p

:Holds(:F; E ; E ); Holds(F; E ; E ); :Holds(:(F1 _ F2); E ; E ); Holds(F1 _ F2 ; E ; E ):
i i j i j

We would like to thank Andre Trudel for his comments on an earlier version of this paper.
References
[1] Allen, J.F., 1983. Maintaining knowledge about temporal intervals, CACM 26 (11):832-843. [2] Allen, J.F., 1984. Towards a general Theory of Action and Time, Arti cial Intelligence 23:123-154. [3] Ben-Eliyahu, R., Dechter, R., 1993. On computing minimal models, In Proc of AAAI-93, 2-8. [4] Cadoli, M., 1992. On the complexity of model nding in nonmonotonic propositional logics, In Proceedings of the Fourth Italian Conference on Theoretical Computer Science, October 1992. [5] Dean, T.M., McDermott, D. V., 1987. Temporal data base management, Arti cial Intelligence 32:155. [6] Dechter, R., Meiri, I., Pearl, J., 1991. Temporal Constraint Satisfaction Problems, Arti cial Intelligence 49:61-95. [7] Golumbic, C.M., Shamir, R., 1991. Complexity and Algorithms for Reasoning about Time: A graph theoretic approach, Rutcor Research Report 22-91 (May 1991). [8] Kautz, H., Ladkin, P., 1991. Integrating Metric and Qualitative Temporal Reasoning, In Proc. of AAAI91, pages 241-246. [9] Kowalski, R., Sergot, M., 1986. A Logic-based Calculus of Events, New Generation Computing 4:6795. [10] Ladkin, P.B., Reinefeld, A., 1992. E ective solution of qualitative interval constraint problems, Arti cial Intelligence 57: 105-124. [11] McDermott, D.V., 1982. A Temporal Logic for Reasoning about Processes and Plans, Cognitive Science 6:101-155. [12] Meiri, I., 1991. Combining Qualitative and Quantitative Constraints in Temporal Reasoning, In Proc. of AAAI-91, pages 260-267. [13] Schwalb, E., Dechter, R., 1993. Coping with Disjunctions in Temporal Constraint Satisfaction Problems, In Proc. AAAI-93, 127-132. [14] Shoham, Y., 1986. Reasoning about Change: time and causation from the stand point of arti cial intelligence, Ph.D. dissertation, Yale Univ. [15] Van Beek, P., 1992. Reasoning about Qualitative Temporal Information, Arti cial Intelligence 58:297326. [16] Vilain, M., Kautz, H., Van Beek, P., 1989. Constraint Propagation Algorithms for Temporal Reasoning: A revised Report. In Readings in Qualitative Reasoning about Physical Systems, J. de Kleer and D. Weld (eds).

The anomalies of the second and fourth inference can be avoided by adding some subsets of axioms A3 . In principle, as a topic for future research, it would be worthwhile to associate classes of queries with a subset of axioms A1 ; A2 and A3 that, if added, will guarantee sound and complete inferences with respect to these queries. Qualitative and quantitative Temporal constraint networks can be processed with a variety of algorithms, presented in [1, 6, 12, 10, 15, 13]. In particular, it was reported in [10] that qualitative temporal networks can be eciently solved using path-consistency as a preprocessing procedure before backtracking. In [13] an e ective preprocessing procedure for quantitative temporal networks is presented.
5 Conclusion

We have proposed a propositional language for temporal reasoning that is computationally e ective yet is expressive enough to describe information about uents, events and temporal constraints. The language, called HOT, is a set of propositional CNF formulas over Holds, Occurs and Temporal propositions as their atoms. A model (or a scenario) of an input theory determines what events happened and speci es the value of every uent at every point in time. We de ne an alternative propositional semantics for HOT that decouples propositional constraints from temporal constraints and allows to consider them separately. We call this framework conditional temporal networks. A conditional temporal network is consistent i there exists a minimal model of the propositional constraints such that the set of temporal constraints whose condition is assigned true is satis able. These results render a wide variety of temporal constraint propagation techniques applicable to reasoning about events and uents. In particular, we identify a syntactically characterized tractable core for which a weaker (sound but incomplete) tractable inference procedure exists. This tractable core can be used as an upper bound approximation. Additional axioms yield more inferential power but at the cost of increased computational complexity. In practice, when it is known which queries are of interest, a user can add only an appropriate subset of the axioms. 6


相关文档

  • On Reasoning with Default Rules and Exceptions
  • Temporal reasoning with classes and instances of events
  • Representation and reasoning with disjunctive temporal constraints
  • 4D deformable models with temporal constraints application to
  • Situated nonmonotonic temporal reasoning with BABY-SIT
  • (英文文献)Optimization of structures with uncertain constraints based on convex model and satisfacti
  • Quantitative Structural Temporal Constraints on Repeating Events
  • Campenhout. Reasoning with temporal logic on truncated paths
  • Optimal FPGA Module Placement with Temporal Precedence Constraints
  • The Use of Temporal Reasoning and Management of Complex Events in Smart Homes
  • 猜你喜欢

  • 八年级语文下册课件18吆喝 (共19张PPT)
  • 英文版——大话西游剧本。
  • 刍议新闻传播的制约因素与传播策略
  • Android App:获取屏幕旋转角度
  • 天津财经大学国际经济01.第一讲 绪论
  • 打造阳光心态培训课件课件
  • 动感时尚MG动画图文介绍宣传动态ppt模板
  • 汽油发动机起动困难原因分析与探微
  • 新生命的诞生(知识点整理)
  • 英国留学签证面试官常问问题
  • 【精品模板】c038TGp_education_diagram_v2文化教育类PPT模板
  • 公文写作提速的方法
  • 治疗老年人风湿痛的药酒
  • 2019年牛津译林版九年级英语 上册Unit 3 Teenage problems单元测试卷(含答案)
  • 【公文范文】大学生村官年度考核情况报告
  • 微信零钱提现手续费
  • 四川省2016年下半年监理工程师执业资格:工程师的口头指示试题
  • 老人怎样保护心脏
  • 期中考试语文反思作文
  • 【IT专家】为什么我的ajax请求将空对象发送到服务器
  • 汽机实操题集
  • 江西省金溪县第一中学2018_2019学年高二历史12月月考试题(含解析)
  • 益气熄风汤对高血压大鼠AngⅡ和ALD的干预作用
  • 运行Hadoop自带的wordcount单词统计程序
  • 幼儿简笔画:可怕的小恐龙
  • 湖南省益阳市2016-2017学年高一下学期3月月考试题 数学 Word版含答案
  • 云南省2018年保育员三级考试试题试卷及答案
  • (技术合同)设计委托合同书
  • 2011届高考政治第一轮复习课件9
  • 三星s8home键隐藏设置
  • 北师大版 二年级数学上册 《5.6回家路上》 精品PPT课件 (2)
  • 职业培训工作计划通用4篇
  • 初中语文阅读教学提问策略研究
  • 广州市声皇音响设备有限公司(企业信用报告)- 天眼查
  • 江苏省扬州市高邮市车逻镇九年级数学上册第1章一元二
  • 最新-市人大机关扶贫工作计划 精品
  • 05第五章 内燃机混合气的形成与燃烧partI
  • 2017_2018学年高中地理第三章防灾与减灾第一节自然灾害的监测与防御课件新人教版选修5
  • 【精品】最新组织变革中的HR战略
  • [小初高学*]XX六年级数学下册总复*第六单元集体备课上课学*上课学*教案
  • 2020年大学学生会各部门工作计划【精品】
  • 2014年1-6月青海省及全国农用氮、磷、钾化学肥料总计(折纯)月度产量
  • 电脑版