Spatial-temporal reasoning
Encyclopedia
Spatial–temporal reasoning is used in both the fields of psychology
and computer science
.
and mentally manipulate them over a time-ordered sequence of spatial transformations.
This ability is important for generating and conceptualizing solutions to multi-step problems that arise in areas such as architecture, engineering, science, mathematics, art, games, and everyday life.
. An emphasis 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 on the 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
) 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
.
Examples of temporal calculi include Allen's interval algebra
, 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, and various region connection calculi
(RCC). 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.
Most of these calculi can be formalized as abstract relation algebra
s, such that reasoning can be carried out at a symbolic level. For computing solutions of a constraint network, the path-consistency algorithm is an important tool.
Psychology
Psychology is the study of the mind and behavior. Its immediate goal is to understand individuals and groups by both establishing general principles and researching specific cases. For many, the ultimate goal of psychology is to benefit society...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
.
Spatial–temporal reasoning in psychology
Spatial-temporal reasoning is the ability to visualize spatial patternsPattern
A pattern, from the French patron, is a type of theme of recurring events or objects, sometimes referred to as elements of a set of objects.These elements repeat in a predictable manner...
and mentally manipulate them over a time-ordered sequence of spatial transformations.
This ability is important for generating and conceptualizing solutions to multi-step problems that arise in areas such as architecture, engineering, science, mathematics, art, games, and everyday life.
Spatial-temporal reasoning in computer science
Spatial-temporal reasoning is also studied in computer scienceComputer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
. An emphasis 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 on the physical reality is based. Methodologically, qualitative constraint
Constraint satisfaction
In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a vector of variables that satisfies all constraints.The techniques used in...
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
Decidability (logic)
In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas can be effectively...
fragments with simple qualitative (non-metric
Metric (mathematics)
In mathematics, a metric or distance function is a function which defines a distance between elements of a set. A set with a metric is called a metric space. A metric induces a topology on a set but not all topologies can be generated by a metric...
) 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
Geographic Information System
A geographic information system, geographical information science, or geospatial information studies is a system designed to capture, store, manipulate, analyze, manage, and present all types of geographically referenced data...
queries efficiently and some may be used for navigating, and communicating with, a mobile robot
Robot
A robot is a mechanical or virtual intelligent agent that can perform tasks automatically or with guidance, typically by remote control. In practice a robot is usually an electro-mechanical machine that is guided by computer and electronic programming. Robots can be autonomous, semi-autonomous or...
.
Examples of temporal calculi include Allen's interval algebra
Allen's Interval Algebra
For the type of boolean algebra called interval algebra, see Boolean algebra Allen's interval algebra is a calculus for temporal reasoning that was introduced by James F...
, and Vilain's & Kautz's point algebra. The most prominent spatial calculi are mereotopological calculi
Mereotopology
In formal ontology, a branch of metaphysics, and in ontological computer science, mereotopology is a first-order theory, embodying mereological and topological concepts, of the relations among wholes, parts, parts of parts, and the boundaries between parts....
, Frank's cardinal direction calculus, Freksa's double cross calculus, Egenhofer and Franzosa's 4- and 9-intersection calculi, Ligozat's flip-flop calculus, and various region connection calculi
Region Connection Calculus
The region connection calculus serves for qualitative spatial representation and reasoning. RCC abstractly describes regions by their possible relations to each other...
(RCC). 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.
Most of these calculi can be formalized as abstract relation algebra
Relation algebra
In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation...
s, such that reasoning can be carried out at a symbolic level. For computing solutions of a constraint network, the path-consistency algorithm is an important tool.
Overview of qualitative spatial and temporal calculi
| Calculus | Type | Domain | Arity of base relations | № of base relations | Permutations of base relations are base relations | Composition table has been proven | Calculus is a relation algebra | Calculus is a semi associative algebra | Calculus is a weakly associative algebra | Calculus is a non-associative algebra | Complexity Computational complexity theory Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other... of consistency problem Constraint satisfaction problem Constraint satisfaction problems s are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint... for atomic networks |
Complexity of consistency problem for arbitrary networks | a-closure decides consistency for atomic networks | Type of composition | Tractable Subsets |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Interval Algebra | Temporal | 1D Line Segments | 2 | 13 | yes | yes | yes | yes | yes | yes | P | NP-hard | yes | strong | ORDHorn |
| INDU | Temporal | 1D Line Segments × Size | 2 | 25 | no | NP-complete | no | weak | |||||||
| Calculus | Type | Domain | Arity of base relations | № of base relations | Permutations of base relations are base relations | Composition table has been proven | Calculus is a relation algebra | Calculus is a semi associative algebra | Calculus is a weakly associative algebra | Calculus is a non-associative algebra | Complexity Computational complexity theory Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other... of consistency problem Constraint satisfaction problem Constraint satisfaction problems s are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint... for atomic networks |
Complexity of consistency problem for arbitrary networks | a-closure decides consistency for atomic networks | Type of composition | Tractable Subsets |
See also
- Cerebral cortexCerebral cortexThe cerebral cortex is a sheet of neural tissue that is outermost to the cerebrum of the mammalian brain. It plays a key role in memory, attention, perceptual awareness, thought, language, and consciousness. It is constituted of up to six horizontal layers, each of which has a different...
- Diagrammatic reasoningDiagrammatic reasoningDiagrammatic reasoning is reasoning by means of visual representations. The study of diagrammatic reasoning is about the understanding of concepts and ideas, visualized with the use of diagrams and imagery instead of by linguistic or algebraic means....
- Qualitative reasoningQualitative reasoningQualitative Reasoning is an area of research within Artificial Intelligence that automates reasoning about continuous aspects of the physical world, such as space, time, and quantity, for the purpose of problem solving and planning using qualitative rather than quantitative information...
- Region connection calculusRegion Connection CalculusThe region connection calculus serves for qualitative spatial representation and reasoning. RCC abstractly describes regions by their possible relations to each other...
- Visual thinking