Spatial–temporal reasoning is an area of

artificial intelligence Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech ...

which draws from the fields of

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

, cognitive science, and

cognitive psychology Cognitive psychology is the scientific study of mental processes such as attention, language use, memory, perception, problem solving, creativity, and reasoning. Cognitive psychology originated in the 1960s in a break from behaviorism, which ...

. The theoretic goal—on the cognitive side—involves representing and reasoning spatial-temporal knowledge in mind. The applied goal—on the computing side—involves developing high-level control systems of automata for navigating and understanding time and space.

Influence from cognitive psychology

A convergent result in cognitive psychology is that the connection relation is the first spatial relation that human babies acquire, followed by understanding orientation relations and distance relations. Internal relations among the three kinds of spatial relations can be computationally and systematically explained within the theory of cognitive prism as follows: (1) the connection relation is primitive; (2) an orientation relation is a distance comparison relation: you being in front of me can be interpreted as you are nearer to my front side than my other sides; (3) a distance relation is a connection relation using a third object: you being one meter away from me can be interpreted as a one meter long object connected with you and me simultaneously.

Fragmentary representations of temporal calculi

Without addressing internal relations among spatial relations, AI researchers contributed many fragmentary representations. Examples of temporal calculi include

Allen's interval algebra ''For the type of boolean algebra called interval algebra, see Boolean algebra (structure)'' Allen's interval algebra is a calculus for temporal reasoning that was introduced by James F. Allen in 1983. The calculus defines possible relations be ...

, and Vilain's & Kautz's point algebra. The most prominent spatial calculi are mereotopological calculi, Frank's cardinal direction calculus, Freksa's double cross calculus, Egenhofer and Franzosa's 4- and 9-intersection calculi, Ligozat's

flip-flop calculus Flip-flops are a simple type of footwear in which there is a band between the big toe and the other toes. Flip-flop may also refer to: Entertainment * ''Flip-Flop'' (album), a 1989 album by Guadalcanal Diary * ''Flip-Flop'' (audio drama), a 2 ...

, various region connection calculi (RCC), and the Oriented Point Relation Algebra. Recently, spatio-temporal calculi have been designed that combine spatial and temporal information. For example, the spatiotemporal constraint calculus (STCC) by Gerevini and Nebel combines Allen's interval algebra with RCC-8. Moreover, the qualitative trajectory calculus (QTC) allows for reasoning about moving objects..

Quantitative abstraction

An emphasis in the literature has been on qualitative spatial-temporal reasoning which is based on qualitative abstractions of temporal and spatial aspects of the common-sense background knowledge on which our human perspective of physical reality is based. Methodologically, qualitative constraint calculi restrict the vocabulary of rich mathematical theories dealing with temporal or spatial entities such that specific aspects of these theories can be treated within decidable fragments with simple qualitative (non-

metric Metric or metrical may refer to: * Metric system, an internationally adopted decimal system of measurement * An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement Mathematics In mathe ...

) languages. Contrary to mathematical or physical theories about space and time, qualitative constraint calculi allow for rather inexpensive reasoning about entities located in space and time. For this reason, the limited expressiveness of qualitative representation formalism calculi is a benefit if such reasoning tasks need to be integrated in applications. For example, some of these calculi may be implemented for handling spatial GIS queries efficiently and some may be used for navigating, and communicating with, a mobile

robot A robot is a machine—especially one programmable by a computer—capable of carrying out a complex series of actions automatically. A robot can be guided by an external control device, or the control may be embedded within. Robots may be ...

Relation algebra

Most of these calculi can be formalized as abstract

relation algebra In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation. The motivating example of a relation algebra is the algebra 2''X''² of all binary relations ...

s, such that reasoning can be carried out at a symbolic level. For computing solutions of a

constraint network Constraint may refer to: * Constraint (computer-aided design), a demarcation of geometrical characteristics between two or more entities or solid modeling bodies * Constraint (mathematics), a condition of an optimization problem that the solution m ...

, the path-consistency algorithm is an important tool.

Software

GQR
constraint network solver for calculi like RCC-5, RCC-8, Allen's interval algebra, point algebra, cardinal direction calculus, etc.
qualreas
is a Python framework for qualitative reasoning over networks of relation algebras, such as RCC-8, Allen's interval algebra, and Allen's algebra integrated with Time Points and situated in either Left- or Right-Branching Time.

Notes

References

* * * * {{DEFAULTSORT:Spatial-temporal reasoning Cognitive science Knowledge representation Educational psychology Logical calculi Reasoning Time in life Spatial cognition Space and time