zbMATH — the first resource for mathematics

Temporal constraints: A survey. (English) Zbl 0911.68186
Summary: 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.

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text: DOI