Spatio-Temporal Reasoning and Linear Inequalitites
Raúl E. Valdés‐Pérez · 1986
Abstract : Time and space are sufficiently similar to warrant in certain cases a common representation in Al problem-solving systems. What is represented is often the constraints that hold between objects, and an concern is the overall consistency of a set of such constraints. This paper scrutinizes two current approaches to spatio-temporal reasoning. The suitableness of Allen's temporal algebra for constraint networks is influenced directly by the mathematical properties of the Algebra. These properties are extracted by a formulation as a network of set-theoretic relations, such that some previous theorems due to Montanari apply. Some hew theorems concerning consistency of these temporal constraint networks are also presented. It is argued that the linear programming approach to reasoning in time and space is needlessly complex, and is otherwise unsuitable as a submodule for a task that performs search. In the spirit of the thematic tradeoff between expressivity and tractability, simple linear inequalities are adequately expressive and provide known algorithms which are amenable to a search regimen. Moreover, another known algorithm captures the real physical constraint of disjointness, and is therefore relevant to layout and planning tasks.