Reasoning about qualitative temporal information
Artificial IntelligencePublished 1 December 1992
Peter van Beek
Citations274
SJR quartileQ1
SJR score1.84
SNIP3.30
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper defines computationally efficient procedures for solving two related reasoning tasks that arise in interval and point algebras: Given (possibly indefinite) knowledge of the relationships between some intervals or points, find one or more scenarios that are consistent with the information provided, and find all the feasible relations between every pair of interval or points.
Abstract
Representing and reasoning about incomplete and indefinite qualitative temporal information is an essential part of many artificial intelligence tasks. An interval-based framework and a point-based framework have been proposed for representing such temporal information. In this paper, we address two fundamental reasoning tasks that arise in applications of these frameworks: Given possibly indefinite and incomplete knowledge of the relationships between some intervals or points, (i) find a scenario that is consistent with the information provided, and (ii) find the feasible relations between all pairs of intervals or points. For the point-based framework and a restricted version of the interval-based framework, we give computationally efficient procedures for finding a consistent scenario and for finding the feasible relations. Our algorithms are marked improvements over the previously known algorithms. In particular, we develop an O(n2)-time algorithm for finding one consistent scenario that is an O(n) improvement over the previously known algorithm, where n is the number of intervals or points, and we develop an algorithm for finding all the feasible relations that is of far more practical use than the previously known algorithm. For the unrestricted version of the interval-based framework, finding a consistent scenario and finding the feasible relations have been shown to be NP-complete. We show how the results for the point algebra aid in the design of a backtracking algorithm for finding one consistent scenario that is shown to be useful in practice for planning problems.
Keywords
Computer Science
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
Communications of the ACMMaintaining knowledge about temporal intervals
7,550 Citations1983James F. Allen
An interval-based temporal logic is introduced, together with a computationally effective reasoning algorithm based on constraint propagation, which is notable in offering a delicate balance between space and time.
SIAM Journal on ComputingDepth-First Search and Linear Graph Algorithms
6,021 Citations1972Robert E. Tarjan
The value of depth-first search or “backtracking” as a technique for solving problems is illustrated by two examples of an improved version of an algorithm for finding the strongly connected components of a directed graph.
Artificial IntelligenceTowards a general theory of action and time
2,562 Citations1984James F. Allen
A formalism for reasoning about actions that is based on a temporal logic allows a much wider range of actions to be described than with previous approaches such as the situation calculus and a framework for planning in a dynamic world with external events and multiple agents is suggested.
Artificial IntelligenceConsistency in networks of relations
2,430 Citations1977Alan K. Mackworth
The primary aim is to provide an accessible, unified framework, within which to present the algorithms including a new path consistency algorithm, to discuss their relationships and the may applications, both realized and potential of network consistency algorithms.
Artificial IntelligenceTemporal constraint networks
1,800 Citations1991Rina Dechter, Itay Meiri +1 more
It is shown that the STP, which subsumes the major part of Vilain and Kautz's point algebra, can be solved in polynomial time and the applicability of path consistency algorithms as preprocessing of temporal problems is studied, to demonstrate their termination and bound their complexities.
Sorting and Searching
1,536 Citations1973Donald E. Knuth
IGI Global eBooksEncyclopedia of Artificial Intelligence
1,400 Citations2009Rabuñal Dopico, Juan Ramón 1973-
Information SciencesNetworks of constraints: Fundamental properties and applications to picture processing
1,248 Citations1974Ugo Montanari
Constraints are treated algebraically, and the solution of a system of linear equations in this algebra provides an approximation of the minimal network, and this solution is proved exact in special cases, e.g., for tree-like and series-parallel networks and for classes of relations for which a distributive property holds.
Artificial IntelligenceIncreasing tree search efficiency for constraint satisfaction problems
1,114 Citations1980Robert M. Haralick, Gordon L. Elliott
Analytically and experimentally show that a lookahead procedure called forward checking which employs the most likely to fail principle performs better than standard backtracking, Ullman's, Waltz's, Mackworth's, and Haralick's discrete relaxation in all cases tested, and better than Gaschnig's backmarking in the larger problems.
Constraint propagation algorithms for temporal reasoning
643 Citations1986Marc Vilain, Henry Kautz
Computing the consequences of temporal assertions is shown to be computationally intractable in the interval-based representation, but not in the point-based one, but a fragment of the interval language can be expressed using the point language and benefits from the tractability of the latter.
Artificial IntelligenceThe complexity of some polynomial network consistency algorithms for constraint satisfaction problems
616 Citations1985Alan K. Mackworth, Eugene C. Freuder
The time complexity of several node, arc and path consistency algorithms is analyzed and it is proved that arc consistency is achievable in time linear in the number of binary constraints.
Communications of the ACMSynthesizing constraint expressions
530 Citations1978Eugene C. Freuder
An algorithm is developed that can achieve any level of consistency desired, in order to preprocess the problem for subsequent back track search, or to function as an alternative to backtrack search by explicitly determining all solutions.
Artificial IntelligenceEnhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition
478 Citations1990Rina Dechter
An integrated strategy is described which utilizes the distinct advantages of each scheme and shows that, in hard problems, the average improvement realized by the integrated scheme is 20–25% higher than any of the individual schemes.
Artificial IntelligenceTemporal data base management
392 Citations1987Thomas Dean, Drew McDermott
The system described in this paper extends classical predicate-calculus data bases, such as those used by PROLOG, to deal with time in an efficient and natural manner to perform the temporal analog of (static) reason maintenance.
Elsevier eBooksConstraint Propagation Algorithms for Temporal Reasoning: A Revised Report
347 Citations1990Marc Vilain, Henry Kautz +1 more
The present paper departs from the original primarily in correcting claims made there about the point algebra, and in presenting some closely related results of van Beek [1989].
Planning using a temporal world model
254 Citations1983James F. Allen, Johannes A. G. M. Koomen
A world model based on a temporal logic allows the problem solver to gather constraints on the ordering of actions without having to commit to an ordering when a conflict is detected, and allows more general descriptions of actions that may occur simultaneously or overlap.
UR Research (University of Rochester)A formal theory of plan recognition
228 Citations1987Henry Kautz
The thesis develops the first formal description of the plan recognition process, and shows how problems of medical diagnosis can be cast in the framework, and an example previously solved by a medical expert system is worked out in detail.
Computational IntelligenceConstraint satisfaction algorithms1
214 Citations1989Bernard A. Nadel
A unified survey of tree search, arc consistency, and hybrid tree search/arc consistency algorithms, in terms of three classes, suggests several new algorithms to be the best algorithm so far.
Computational IntelligenceExact and approximate reasoning about temporal relations1
195 Citations1990Peter van Beek, Robin Cohen
This paper addresses a fundamental reasoning task that arises in applications of the algebra: Given (possibly indefinite) knowledge about the relationships between intervals, find all feasible relationships between two intervals, called the minimal labels problem.
Artificial IntelligenceSearch rearrangement backtracking and polynomial average time
167 Citations1983Paul W. Purdom
It is proved that there is no major advantage in using search rearrangement backtracking outside of the difficult region, and it is conjectured that search rearranged backtracking is exponentially faster than ordinary backtracking for nearly all of theicult region.
Artificial IntelligenceConsistent-labeling problems and their algorithms: Expected-complexities and theory-based heuristics
150 Citations1983Bernard Nudel
Expected-complexity analyses for the traditional backtrack algorithm as well as for two more recent algorithms that have been found empirically to be significant improvements: forward checking and word-wise forward checking are carried out.
Artificial IntelligenceA model for temporal references and its application in a question answering program
135 Citations1972Bertram C. Bruce
A formal model is presented which represents the structure underlying temporal references in natural language, and a computer question answering program, "Chronos", which uses the concepts of tense and time-segment relations, illustrates and supports the validity of the model.
International Joint Conference on Artificial IntelligenceApproximation algorithms for temporal reasoning
109 Citations1989Peter van Beek
New approximation algorithms for temporal relations between intervals introduced by James Allen are examined, their effectiveness is examined, and under what conditions the algorithms are exact are determined.
Experimental evaluation of preprocessing techniques in constraint satisfaction problems
101 Citations1989Rina Dechter, Itay Meiri
The results show that directional arc-consistency, a scheme which embodies the simplest form of constraint recording, outperforms all other preprocessing techniques and the results of the second part of the experiment suggest that the best variable ordering is achieved by the fixed max-cardinality search order.
International Joint Conference on Artificial IntelligenceA new method for solving constraint satisfaction problems
68 Citations1981Raimund Seidel
An algorithm for finding all the solutions of a constraint satisfaction problem with worst case time bound 0(m*kf+1) and space bound 0 (n*kF+1), where n is the number of variables in the problem and k the cardinality of the domain of the variables.
Reasoning in time and space
62 Citations1983Jitendra Malik, Thomas O. Binford
A wide variety of temporal and spatial specifications can be converted into linear inequalities relating the midpoints of events or boundary surfaces of objects respectively, Linear programming is then used to represent these constraints and perform deductions.
Artificial Intelligence in MedicineTemporal query processing with indefinite information
54 Citations1991Peter van Beek
This paper adopts Allen's influential interval algebra framework for representing temporal information and shows that when the representation language is sufficiently restricted it can develop efficient algorithms for answering interesting classes of queries.
National Conference on Artificial IntelligenceThe interpretation of temporal relations in narrative
53 Citations1988Fei Song, Robin Cohen
A more rigorous description for time relations of tenses is presented, which is able to express all the 16 tenses in English and incorporate the interval properties of events from the aspectual analysis into the tense relations.
National Conference on Artificial IntelligenceThe satisfiability of temporal constraint networks
38 Citations1987Raúl E. Valdés‐Pérez
This paper scrutinizes the interval representation and its mechanisms, makes explicit the unstated assumptions of the mechanisms, introduces several useful theorems regarding interval networks, and distinguishes three types of inconsistency exhibited by these networks.
Reasoning about the temporal structure of narratives
31 Citations1987Michael Joseph Almeida
This dissertation concentrates on the study of issues involved in understanding the temporal structure of narratives, and describes the implementation of a parser which can read a narrative-line which includes frame adverbs and adverbials of duration.
On Binary Constraint Networks
27 Citations2015Peter B. Ladkin, Roger D. Maddux
Lecture notes in medical informaticsA Representation of Time for Medical Expert Systems
20 Citations1987Ian Hamlet, Jim Hunter
How a “time specialist” is being developed to handle the temporal aspects of problem-solving, and in particular, how it might deal with uncertainty and ambiguity in temporal relationships by using a form of Truth Maintenance is described.
SciDok (Saarland University and State Library)Temporal Matching : Recognizing Dynamic Situations from Discrete Measurements
20 Citations1988Klaus Nökel
This paper presents an algorithm for planning an observation sequence based on the specification of the event and discusses the problem of giving a meaningful definition of a 'successful match of a measurement sequence against a situation description'.