Temporal Constraints: A Survey |
| |
Authors: | Eddie Schwalb Lluís Vila |
| |
Affiliation: | (1) Information and Computer Science, University of California, Irvine, USA;(2) Institute for Research in Artificial Intelligence (IIIA)–CSIC, Catalonia, Spain |
| |
Abstract: | Temporal Constraint Satisfaction is an information technology useful for representing and answering queries about temporal occurrences and temporal relations between them. Information is represented as a Constraint Satisfaction Problem (CSP) where variables denote event times and constraints represent the possible temporal relations between them. The main tasks are two: (i) deciding consistency, and (ii) answering queries about scenarios that satisfy all constraints. This paper overviews results on several classes of Temporal CSPs: qualitative interval, qualitative point, metric point, and some of their combinations. Research has progressed along three lines: (i) identifying tractable subclasses, (ii) developing exact search algorithms, and (iii) developing polynomial-time approximation algorithms. Most available techniques are based on two principles: (i) enforcing local consistency (e.g. path-consistency) and (ii) enhancing naive backtracking search. |
| |
Keywords: | temporal constraints temporal reasoning constraint processing |
本文献已被 SpringerLink 等数据库收录! |
|