Large-Scale Temporal Data Bases for Planning in Complex Domains

I. Introduction

Rep~esenting and reasoning about time play a critical role in many facets of everyday problem solving. We contin­ ually have to make reference to what has happened, is happening, and might possibly happen. To make matters more difficult, we have to cope with the fact that the world is constantly changing around us. To plan for the future we must be able to predict change, propose and commit to actions on the basis of these predictions, and notice when certain predictions are no longer warranted. All of this requires handling an enormous amount of complexly interdependent information.

In the past , the problems of efficient deduction and reason maintenance in predicate-calculus data bases used for planning have largely been ignored as researchers have grappled with the basic issues of reasoning about dead­ lines, iteration, conditionals, backtracking, and the like.

1 This work was supported in part by the National Science Foun­ dation under grant IRI-8612644 and by an IBM faculty development award.

As our representations have become more sophisticated and our ambitions to tackle more realistic domains have grown, the problems inherent in managing large tempo­ ral data bases have become a major factor limiting growth [12] [11]. What is needed is a computational framework in which common-sense strategies for organizing temporal facts can be easily exploited to expedite the search needed to support basic temporal inference procedures. As a sim­ ple example, suppose that you are planning a business trip and you are trying to remember if the travel agent has al­ ready confirmed your airline reservation. It shouldn't be necessary to recall (i.e., search through) all of the events past , present, and future that involve your communicating with a travel agent . Only the most recent are likely to be of interest. Restricting attention to a particular time frame requires that facts that change over time are indexed tem­ porally, that is to say, stored in such a way that facts and events common to a given time frame are easily accessible from one another. You would also like to avoid expending energy on facts that have nothing to do with travel agents or airline reservations . This requires that facts be indexed syntactically.

Temporal indices, unlike their syntactic counterparts, are subject to frequent revision. Quite often the span of time associated with an event or fact is shifted, com­ pressed, or expanded to suit a change of plans or reflect new information. Suppose that you decide to leave on your business trip a week earlier than previously planned. From this change, it should be apparent that certain prerequisite tasks (e.g., ordering plane tickets) must also occur earlier. Often, such a change will not require a major revision of plans. Where modifications ate needed, however, the data base should clearly indicate just what parts of a plan have to re-thought and why (e.g., you might have to arrange for transportation to the airport in the event that the earlier departure will upset plans to share a ride with a friend).

To make accurate predictions about the future it is important to have access to information about the past. Information about the past helps us to understand what went wrong in situations where our actions fail to achieve their intended effect or our predictions fail to coincide with observation. Information about the past also helps us to resume interrupted or suspended tasks. Even if we were to reconcile ourselves to throwing away all record of the more distant past, we still have to consider that there are thousands of facts that we know are currently true and that are likely to figure in guiding our behavior. In addition, we generally keep track of a great many facts corresponding to long and short term goals and to predictions about the near and distant future. In any reasonably complex domain, the number of temporally dependent facts necessary for minimal competence is large. This paper describes how to go about organizing and maintaining these facts.

II. Thesis

[4) describes an approach to reasoning about time and a temporal data base management system that supports temporal reasoning of the sort necessary for planning. The temporal data base is called a time map [8), and the data base system is called a time map manager or TMM. In the TMM, the classical data base assertion is replaced by the notion of time token corresponding to a particular interval of time during which a general type of occurrence (a fact or event) is said to be true. For any given fact or event type, the time map will typically include many tokens of that type. The most expensive operation distinguishing temporal data base manipulations from those performed by static data base systems (e.g., Prolog) involves find­ ing tokens that satisfy certain temporal constraints 2 · This operation, which we will call token retrieval, is the tem­ poral analog of fetching assertions in the data base that match a given pattern. Token retrieval requires the sys­ tem to search through the data base for time tokens whose type matches a given pattern and whose associated inter­ val spans a specified reference interval. To support back­ ward chaining efficiently, token retrieval should be demand driven: a call to the token retrieval routine should return one token (if possible) and a suspended procedure call (or continuation) which, if resumed, will supply additional to­ kens by taking advantage of the effort expended in find­ ing previous tokens. To maintain integrity, all operations on the data base, including token retrieval, should supply succinct descriptions of the reasons why they are to be be­ lieved. This allows that all deductions performed by the system can be made contingent upon continued belief in the reasons supporting their component steps.

The primary claim of this paper is that, in many com­ mon situations, temporal data bases can be organized so that the cost of token retrieval is comparable with assertion retrieval in static data bases. Restricting our attention to the problem of retrieving a single token of ground type 3 P spanning the interval I:

1. In situations in which the set of tokens can be parti­ tioned into temporally distinct periods (e.g., months, years, factory work shifts), the cost of token retrieval is proportional to the sum of:

2 A temporal constraint is one that in some way restricts the order in which two points occur or the distance in time separating two points.

3 A type P is ground just in case P contains no variables.

• (a) the number of periods separating the period Pori gin containing the beginning of I and the first period Prlutination preceding the beginning of I containing a token of type P, and
• (b) the cost of determining if any token of type P in Prlutinllfion spans I.
• In situations in which the data base can be orga­ nized according to hierarchies of constraints (e.g., con­ straints between a task and its subtasks), and these constraint's are metric and reasonably tight 4 , then the cost of determining if any token of type P in a given period spans I is proportional to the number of tokens of type P within that period.

As with any scheme for speeding up retrieval, there is a cost associated with organizing the data to support these fast retrieval routines. Fortunately, much of the work re­ quired for organizing time tokens is already being handled by other routines in the time map. Whenever a new con­ straint is added or removed, the system has to determine how the changes affect the current set .of beliefs. This is the basic function of temporal rea& on maintenance, and it is es­ sential for almost any interesting application of temporal reasoning [4). The process of detecting changes in the set . of beliefs is performed by propagating constraints through the constraint network. Essentially the system tries to compute new estimates (tighter bounds) on the distance in time separating selected pairs of points in the time map. These new estimates, referred to as derived conJtraintJ, can be used to either license new deductions or undermine old ones. The (derivation) complexity of a derived constraint is proportional to the length of the shortest path through the constraint network from which the associated distance estimate can be computed. If we assume that there is some bound, call it maxderivedlength, on the complexity of de­ rived constraints necessary to catch all crucial changes in the set of beliefs, then we can perform constraint prop­ agation in 0( m 3 t log m,, ), where pt is one of the points being constrain:d and mpt is the number of pointR reach­ able from pt by paths of length =:; maxderivedlength. In practice, mpt is generally quite reasonable.

The organizational schemes described in this paper are integral with the basic functionality of the TMM; they instigate reorganization correctly in response to the addi­ tion of new information or the deletion of old, and they serve to expedite the basic operations used in temporal reason maintenance. The techniques involve methods for partitioning the set of time tokens both temporally and syntactically and for caching selected derived constraints and noticing when certain distance estimates become li­ censed by the current set of constraints or cease to be so. If we accept that the basic operation of temporal rea­ son maintenance is essential, then the additional overhead in time and space necessary to implement these organizational techniques is just a small constant factor times the number of tokens stored in the data base.

4Jn the framework being considered here, the distance between two points is represented by an upper and lower bound. By tight we simply mean that the difference between these bounds is small.

Complexity measures are generally misleading indi­ cators of expected performance. The basic problem of representing temporal information using linear constraints has been studied by a number of researchers [7] (4] (11] (3]; most of the proposed techniques· involve some sort of fairly straightforward polynomial-time algorithm. Unfor­ tunately, even n 3 is out of the question for large n, where n corresponds to the total number of points or intervals being considered, and our experience (10] indicates that n will typically be on the order of several thousand. As soon as you add disjunction, the problem becomes NP­ complete (13], but, again, asymptotic complexity doesn't tell the whole story. In the absence of a thorough analysis of the sorts of inference supported by a temporal reason­ ing system, evaluating such a system is impossible. In (4], we provide a detailed account of the inferential capabili­ ties of the TMM, including special purpose techniques for handling disjunctions, default rules, and both antecedent and consequent reasoning. In this paper, we are primarily interested in the techniques required to expedite retrieval in large temporal data bases. We take as given that token retrieval cannot be a function of the size of the entire data base.

III. Temporal Data Base Management

The TMM consists of:

1. A data base (called a time map) that captures what is known about events and their effects over time. In particular, time maps are used to record information about the truth of propositions that change over time.
2. A query language that enables application programs to construct and explore hypothetical situations. This language supports simple queries of the form, "Is P true at timet?", as well as more complicated queries of the form, "Find an interval satisfying some initial con­ straints such that the conjunction (and P1 ·.· Pn) is true throughout that interval."
3. A set of techniques for extending the information in the data base. These techniques allow for predictions on the basis of temporal antecedent conditions. Pre­ dictions added to the data base in this way are made to depend upon the antecedent conditions in a mean­ ingful way.
4. A mechanism for monitoring the continued validity of conditional predictions. This mechanism extends the functionality of reason maintenance systems (6] to temporal domains.

A time map is a graph. Its vertices refer to point$ (or in$tants) of time corresponding to the beginning and ending of events. One point is related to another using con$traints where a constraint is represented as a directed edge linking two points. Each edge is labeled with an upper and lower bound on the distance separating the two points in time. These bounds allow us to represent incomplete in­ formation concerning the duration and time of occurrence of events (e.g., unloading the truck will take between 20 and 25 minutes). Any two points can be related by finding a path from one point to the other, where a path from pt0 to ptn is just a sequence ptoc1pt1 . . . CnPtn such that pt0 through ptn are points and c; is a constraint relating pt;_1 to pt;. New constraints are added to the time map by making assertions of the form (elt (distance pt1 pt2 ) low high) where this is meant to indicate that the quan­ tity corresponding to (distance pt1 pt2 ) is an element of ( elt) the closed interval low to high.

An interval is just a pair of points. A type is denoted by a formula like (location obj73 loc14) or (move obj73 loc14 loc17). A time token (or simply token in situations where it should cause no confusion) is an in­ terval together with a type. (begin tok) and (end tok) denote the begin and end points the time token tok. Pred­ ications of the form (occurs type token-name) are used to create new time tokens and refer to existing time tokens of a given type. The token-name gives us a handle so we can speak about the interval associated with a particular time token.

IV. Indexing Time Tokens

In this section, we will be concerned primarily with strate­ gies for discriminating on data in order to expedite re­ trieval. A discrimination corresponds to a question (or deduction) concerning the form or content of the data. On the basis of the answer to such a question, the data is usually partitioned into disjoint sets so that if a pro­ gram attempts to retrieve an item whose content depends on the answer to this question, then the system will know exactly where to look. This process of discriminating on data, asking questions and then partitioning according to the answer, can be thought of as caching the results of deductions that are likely to be frequently needed. To be useful, discriminations should substantially reduce search with a minimum overhead. Not all discriminations can be depended upon to remain valid as the data changes over time. Where the data is subject to change, there is an additional expense involved in keeping track of valid de­ ductions.

The information content of a time token corresponds to the syntactic form of the token's type and the temporal extent (or scope) of the associated interval of time. De­ ductions corresponding to syntactic discriminations on the type of time tokens are never invalidated (though their utility may be undermined as tokens are removed from the database) . All time tokens are indexed through what is called a di$crimination tree or dtree (2]. Each nonterminal node in a dtree corresponds to a discrimination: a question whose answer determines which subtree various data items are stored in. Each terminal node in a dtree corresponds to a set (or bucket) of data items determined by the dis­ criminations on the path leading from the root of the dtree to the terminal node.

Discrimination is demand based in the TMM. If the size of a bucket exceeds some fixed threshold, the TMM will attempt to subdivide the bucket by adding an additional discrimination node and some number of terminal nodes as dictated by the chosen partitioning scheme. If it is pos­ sible, partitioning a bucket of tokens is based upon a syn­ tactic discrimination according to the types of the tokens stored in the bucket. If further syntactic discrimination is either impossible or undesirable, the system attempts to discriminate on the basis of the temporal scope of tokens . Temporal discrimination in the TMM involves choosing a temporal partitioning scheme and subdividing the overly large bucket of tokens according to this scheme. In the TMM, the application program is required to supply a set of hierarchically arranged temporal partitions of a time line (i.e., the real numbers) such that all of the partitions can be related via a single global frame of reference (i .e., 0). Attempts to derive an adequate partitioning scheme solely on the basis of the current contents of a bucket have proven difficult (9]. The partitioning scheme chosen must essen­ tially anticipate the sort of questions that will frequently be asked during token retrieval. In the factory domain, the partitions supplied by the FORBIN planner [10] corre­ spond to weeks, days, eight-hour work shifts, and one-hour intervals. The system discriminates as demand dictates, starting with the coarsest partitions and refining only as required.

The partitioning scheme described above corresponds to a set of successively finer partitions of time with re­ spect to a single clock. This is enormously useful as a coarse grained filter. Unfortunately, many events cannot be tied to a precise time, though they can be related pre­ cisely to one another. For instance, in reasoning about a chemical process, you may not know exactly when a catalyst was added to a reactor vessel, but you do know that within 8 .to 10 minutes following the addition of the catalyst the reaction was complete. The TMM provides a mechanism for specifying hierarchies of event relations that can serve to guide search in determining temporal or­ derings among points that are not precisely known with respect to. the global frame of reference of the partitioning scheme. The most common strategy involves the use of the event/subevent hierarchy. If e1 is specified as a subevent of e2 , then the TMM can guarantee (within certain limita­ tions) that there exists an edge in the time map connecting the beginning of e1 and the beginning of e2 labeled with the best bounds on the distance in time separating the two points.

These edges constitute cached deductions and are han­ dled by the s~e mechanisms used in (4] to ensure correct behavior with regard to the addition and removal of in­ formation. The token retrieval machinery takes advantage of these cached deductions to speed search in determining the relative ordering of tokens which are not distinguished in the dtree by temporal discriminations. These combined searching and caching techniques guarantee that under certain condi tions 5 the machinery for determining the bounds on the distance between two points will always return the best bounds and will do so in time proportional to the depth of the hierarchy. It is also possible to show that the system never reports false bounds and that the behav­ ior of the system degrades gracefully as the information becomes less precise and the maxderivedlength increases beyond the fixed threshold. For most problems the depth of the hierarchy is seldom greater than 20 and the alterna­ tive exhaustive search would cost on the order of n 3 where n is the total number of tokens in the partition (often on the order of several hundred).

Token retrieval routines use the dtree to provide a set of candidate tokens and then determine the relative or­ dering of the beginning of these tokens using the search methods described in the previous paragraph. Determin­ ing the duration of a fact token relative to a reference inter­ val is also accomplished using search methods that exploit the hierarchical partitions and cached distance estimates. All the search routines return the information requisite for setting up appropriate data dependencies. Searches corresponding to different token retrieval requests can be coroutined to support efficient backtracking during back­ ward chaining.

V. Algorithmic Details

The TMM employs a heuristic graph traversal routine to compute bounds on the distance separating pairs of points in the time map. These bounds are used to determine re­ lations between pairs of points and intervals. Estimates of the distance between pairs of points are computed by finding paths through the network of constraints. Re­ call that a path in the time map is a sequence of points and directed edges corresponding to constraints. Each edge c is labeled with an upper and lower bound, de­ noted LOW(c) and HIGH(c) respectively. For each path p = ptoc1pt1 ... CnPtn we have BOUNDS(p) = (low, high) where low= L:7=1LOW(c;) , and high= L:7=1HIGH(c;). In computing the best bounds, the heuristic graph traverser tries to find the paths with the greatest lower and least upper bounds. The details of the TMM's graph traverser are described in [4], and won't be repeated here. For a discussion and analysis of existing constraint propagation techniques for applications in artificial intelligence see [3].

In addition to asserting constraints between pairs of points corresponding to the begin and end of time tokens, it is also possible to constrain the begin or end of a time token with respect to the global frame of reference (men­ tioned in the previous section). Figure 1 shows a time map and the time line corresponding to a fixed global frame of reference; five tokens (notated T1 ... Ts) and their corre­ sponding beginning points (pt1 ... pts) are labeled for easy reference. Constraints are depicted as curved lines (e.g., those labeled C1 and C2). The points in the shaded area

5 The set of tokens must be totally ordered and the mazderived/ength (see Section II.) must be fixed.

(e.g., pt2 and pt3 ) can be related to points outside the shaded area (e.g., pt1 or pt4 ) only through the constraints cl and c2 and the point in time corresponding to the frame of reference of the global time line. Given that one or both of T2 and T3 are of type P, paths through the global frame of reference will be important in determining if P is true throughout the interval associated with T1. For relating pairs of points isolated in the same cluster of tokens (e.g., pt1 and pt5 ), the global frame of reference may not help in establishing the necessary distance estimate, but, as we will see, the global frame of reference provides an invalu­ able service by allowing the search routines to ignore large portions of the time map.

In order to expedite token retrieval, the TMM pre­ computes and stores (i.e., cache$) certain point-to-point distance estimates. Caching is performed as part of the constraint propagation routines used to implement tem­ poral reason maintenance. The TMM can maintain an es­ timate, guaranteed exact under certain assumptions (see [4]), of the distance in time separating selected pairs of points. Obviously, it would be wasteful to cache distance estimates for all pairs of points. Selective caching, on the other hand, can provide real benefits. In Section VI., we will see how caching estimates of the distance between each point and the global frame of reference forms the basis for an effective temporal discrimination scheme. In [5], we demonstrate how a strategy for caching distance estimates between points corresponding to related tokens can expe­ dite search within portions of the time map that are not highly constrained with respect to the global frame of ref­ erence.

VI. Hierarchical Partitioning Schemes

In the following, let R denote the set of real numbers, and [a, b) the interval defined by {xI x E R,a ~ x < b}. For our purposes, a partition P of an interval I (subset of R) is just a set {[x, y) I x, y E I} such that I1 n h = 0 for all distinct I1 and I 2 in P, and for each x E I there exists an I' in P such that x E I'. A hierarchical partitioning $Cherne consists of a sequence of partitions 'Po'P1 ... Pn of R such that for each i < n if I E 'Pi then there is a set intervals in 'Pi+1 that partitions I. In addition, we insist that Po is always the set consisting of just R. 'Pi is said to be more reJtrictive than 'Pj with respect to I just in cas I E P · and there is a subset S of 'Pi such that I S I > and S 1 partitions I. A hierarchical partitioning scheme i $trict if it is the case that for any i such that 0 ~ i < n, i I E 'Pi, then 'Pi+l is more restrictive than 'Pi with respec to I. All the partitioning schemes we will be looking at i this paper are strict.

A time-line partition is just a partition of R such tha 0 is identified with a particular frame of reference (e.g. midnight on April 30, 1777) and each real number x corre sponds to an offset in time from this global frame of refer ence as measured by a particular clock. The global frame of reference simplifies internal bookkeeping and provid a basis for using dates in specifying constraints. Figur 2 shows part of a. strict hierarchical time-line partition i which the partitions consist of weeks, shifts (eight hour pe riods), half-shifts (four hour periods), and one hour period offset from a fixed zero point. In Figure 2, Cis containe in A and B, and is partitioned by {D,E,F,G}.

Specifying constraints with respect to the global fram of reference is made particularly easy using dateJ. date is just an offset from the global frame of refer ence specified in terms of the current partitioning scheme For instance, in the scheme mentioned in the previ ous paragraph, the date ((weeks 2)(days 3)(shi:tt 2) (hours 1) (minutes 15)) 6 is easily converted into a offset in minutes from the current global frame of refer ence. Often, it is convenient to specify a default dat (e.g., noon today) and then specify offsets, called rel dateJ relative to the default. Dates and reldates ca appe~ anywhere in a formula that a point can. A an example, if the default date is noon today, assert ing (elt (distance (begin task41) (reldate (hour 2)(minutes 30))) -10 10) determines that task41 be gins between 2:20 and 2:40 this afternoon. The T~M e~ ploys simple rewrite rules to translate between var1?us m ternally used partitioning schemes and computatiOnall cumbersome (but familiar) methods of dating based upo the modern calendar.

Every point is identified with a tuple (low, high} called its relative offset, indicating the best (lower an upper) bounds over all paths through the network of con­ straints on the distance in time separating the point from the global frame of reference. Relative offsets are updated during constraint propagation. The constraint propaga­ tion routines ensure that, if additions or deletions to the set of constraints require that the relative offset of a point be updated (i.e., the bounds made either more or less re­ strictive), then the system can easily detect this and re­ spond appropriately. The relative offset determines how tokens are indexed in the TMM discrimination tree. To sim­ plify the discussion of temporal indexing, we will assume that all tokens are syntactically · indexed down to atoms according to type, and consider only those nodes in the discrimination tree corresponding to temporal indices. A temporal index is implemented as a data structure called a TBUCKET consisting of a set (possibly empty) of tokens that can't be further discriminated upon, a partition inter­ val [a, b), and a set of subindices (i.e., TBUCKETs) sorted by their associated partition intervals. For efficiency reasons, subindexing is usually postponed until the set of tokens stored at an index exceeds some fixed threshold. Figure 3, shows a simple hierarchical partitioning scheme and a table indicating the relative offsets for five tokens of the same type. Figure 4 shows a portion of a discrimination tree. (Recall that Po is the singleton set corresponding to the entire time line.) Note that T5 could be further discriminated, but is not in this case since the TBUCKET containing it would otherwise be empty. If the relative off­ set of the beginning of T2 was changed from {1.2, 2. 7) to {1.2, 1.8), then T2 would be further discriminated ending up in the same bucket with T3 · If, on the other hand, the relative offset was changed to {1.2, 3.5) or {1.2, +oo), then T2 would end up (respectively) in the same bucket with Tt or in the top-most index corresponding to Po.

6 Partition divisions not mentioned in a date default to 0.

Now, it is straightforward to describe the algorithm used in the TMM for token fetching during temporal back­ ward chaining. The algorithm makes use of two sorts of indexing in performing the requisite search: direct-path indexing and indexing relative to the global frame of ref­ erence. The steps in the algorithm are:

1. Determine a partition P and an interval I belong­ ing to P such that the fetch interval is constrained to (necessarily) begin during I and cannot be shown to (necessarily) begin during any interval belonging to a partition more restrictive than P.
2. Using the heuristic graph searching routines, try each matching token whose associated partition interval ei­ ther is contained in I or contains I. In Figure 5, the shaded areas correspond to the partition intervals searched during this step. If a token is found that either begins before or can be constrained to begin before the fetch interval, then an attempt is made to determine whether or not that token persists through­ out the fetch interval. Relative offsets and the heuris­ tic search routines are used to determine the relative ordering of the end point of the found token and the end point of the fetch interval.
3. If the previous step fails to find an appropriate token or set of tokens then we search through the remaining tokens of the desired type as follows:
4. (a) Set the variable early-termination to false.
5. (b) Determine a partition interval, call it .N, preced­ ing I such that there is no other unexamined par­ tition interval preceding I which is either later than .N or in a less restrictive partition.
6. (c) For each matching token in .N, use the relative offset from the global frame of reference to deter­ mine if the token persists long enough.
7. (d) Mark .N as examined.
8. (e) If a matching token is found that fails to persist throughout the fetch interval because it has been

• clipped by a contradictory token, then set early­ termination to true.
• (f) If early-termination is true and /If is an element of the most restrictive partition, then stop, oth­ erwise return to step 3b.

Figure 5 illustrates the order in which partition inter­ vals are examined during step 3 of the fetch. The starred partition interval is meant to indicate where the variable early-termination was set to true.

The above indexing scheme relies heavily upon their being a single global frame of reference and a rather simple and restrictive hierarchy of partitions. The fact that the partitions are strictly nested (i.e., for each i < n, if I E 'P;, then there is a set of intervals in 'Pi+l that partitions I) can result in certain inefficiencies at the boundaries of par­ tition intervals. Points that are slightly unordered with respect to a major time break will be assigned a fairly unrestrictive partition interval even though their relative offset is known with considerable precision. For instance, an event constrained to begin at midnight January 1 give or take a minute will end up in the bucket corresponding to the decade partition, assuming a partition according to decades, years, months, weeks, days, and hours. Such events cause the system to do a bit more work, but since they are relatively rare, the overall effect is negligible. To­ kens whose begin points are known with some precision (i.e., the difference between the lower and upper bound of the relative offset is small), but which, nevertheless, are unordered with respect to major time breaks might be han­ dled by considering pairs of partition intervals adjacent to the time break and indexing the token in more than one interval, but no attempt has been made to implement such a strategy in the current system. Similarly, the beginning of fetch intervals can also span major time breaks and for this reason it is often useful to split the fetch and perform the requisite search on a case-by-case basis.

VII. Related Work

The techniques described in this paper have profited from many sources. [9] describes a discrimination network ca­ pable of indexing spatial objects on the basis of metric information. Methods for organizing intervals hierarchi­ cally have appeared quite frequently in the literature [1] [7]. There have also been a number of strategies suggested for guiding search in reasoning about time [12] [11]. A careful reading of the discussion of constraint propagation techniques in [3] convinced us that, while the general prob­ lem of reasoning in large constraint networks is hopeless, in most practical situations involving time, the requisite search can be directed with amazing precision.

VIII. Conclusion

The TMM provides a wide range offunctionality (backward and forward temporal inference, dependency directed de­ fault reasoning, temporal reason maintenance) in a simple­ to-use system (predicate-calculus syntax and PROLOG compatibility) in which routine temporal reasoning is opti­ mized using sophisticated caching and search techniques to speed inference. Straightforward partitioning schemes supplied by an application program are used to fragment a temporal data base into non-overlapping periods. Under situations that arise frequently in everyday reasoning, to­ ken retrieval, the basic operation common to most forms of temporal inference, can be performed in time proportional to the sum of (a) the number of periods separating the period containing the beginning of the reference interval and the first previous period that contains a token of the desired type, and (b) the number of tokens of that type beginning in that previous period. The result is that the performance of the temporal inference engine corresponds roughly to our expectations given the distribution of to­ kens of the underlying fact types being manipulated. The discussion of techniques in this paper is necessarily cursory. A technical report [5] provides additional detail concerning both the algorithms and their expected performance.