Preamble:The idea of organising a Dagstuhl seminar on representing and solving spatial problems started with a discussion between Paulo Santos and the late Christian Freksa over a pair of Erdingers during a previous Dagstuhl Seminar in 2015. In this discussion we tried to solve, once and for all, the underlying reasoning strategies for spatial problem solving, whether it is logical-formal-symbolic, or it is totally/partially grounded on the real world (on what Christian called “the spatial substrates”). Considering the contributions in this volume, we believe the answer lies in the spectrum of approaches and that the right choice is dictated by the application domain. Indeed, one of the concrete contributions of this meeting was a discussion of possible problem scenarios that should constitute a Spatio-temporal Problem Repository to guide the future development of this field.

Summary of the contributions: Spatio-temporal reasoning is a fundamental aspect of problem solving in general, and it occupies an ubiquitous place in AI and robotics, in the sense that almost all problem domains contain a spatio-temporal component. Paradoxically, despite its importance, the combination of spatial and temporal reasoning is one of the AI subfields with a wider gap between the current scientific progress and the human commonsense performance.

This seminar received contributions from researchers working in the various disciplines involved in investigating the problem of representing and reasoning about spatial problems (both in humans and artificial systems). The discussions were initially motivated by the following four main topics that are used below to organise the contributions in this collection:

1. Representation.
2. Formalisation.
3. Description.
4. Problem solving.

Representation

The discussions around the topic Representation were motivated by the following questions: How do humans conceptualise and mentally represent spatial problems? What is the role of high-level spatio-temporal structures for perceiving spatial problems, for manipulating spatial configurations, and for commonsense spatial problem solving?

In this volume, Cohn (Section 3.3) lists seven important problems that could be obstructing the development of automated commonsense spatial reasoning, including the lack of a proper definition of commonsense reasoning, the need for a foundational ontology of space, the problem of how to tackle vagueness and implicit knowledge and the need for suitable default reasoning mechanisms for dealing with spatial information. The acquisition of commonsense knowledge and the role of embodiment in perception and spatial awareness were also pointed out as key open research questions. Complementarily, Kuhn (Section 3.9) advocates for the following three conceptualisations for spatio-temporal phenomena: (i) space-time varying fields of attributes, (ii) objects and object collections, (iii) events over fields and objects. Wörgötter (Section 3.22) goes one step up in the abstraction level suggesting the investigation of the very idea of concepts and how stimulus-driven experience drives the formation abstract thought. Starting from a distinct standpoint, Sioutis’ arguments (Section 3.17) go in a similar direction with the proposal of a generic neurosymbolic framework for integrating qualitative spation-temporal reasoning with neural models from a probabilistic perspective. The idea for a “(symbolic) spatio-temporal knowledge base, naturally grounded on physics and human cognition” could be a good starting point for testing representation frameworks. Langley (Section 3.10) describes a cognitive architecture for embodied agents, whose recent extensions (towards more flexible representation of space and processes) could provide a fertile ground for the development of research into the core problems in the representation and reasoning about commonsense spatial information.

Formalisation

This topic was motivated by the investigation of what would be a suitable formalism for commonsense problem solving that allows an accurate, flexible and readable knowledge representation for spatio-temporal effects of actions performed by an intelligent agent.

Much work in spatio-temporal reasoning has focused on Qualitative Spatial Reasoning (QSR) [11], a field that attempts the formalisation of spatial knowledge based on primitive relations defined over elementary spatial entities. Although the combination of (qualitative) temporal and spatial reasoning is not infrequent in the literature in general (see for instance [1]), QSR approaches have traditionally overlooked a formal treatment of actions. Aiming to bridge the gap between commonsense reasoning, reasoning about actions and change and qualitative spatial representation and reasoning, some recent research has focused on spatial puzzles and games [2, 12, 3], as these domains offer a small number of objects requiring a minimum background knowledge about unrelated features, while they keep enough complexity to constitute a challenging problem of KR. This is in line with Cabalar’s contribution in this volume (Section 3.2), where the challenging problem of evidence analysis of digital forensics is proposed as a challenging domain for the application of spatio-temporal reasoning strategies. Calabar also suggests a set of minimum requirements for a KRR formalism about common sense, which includes simplicity, natural understanding, clear semantics, computability and elaboration tolerance, where logical formalisms allowing non-monotonic reasoning is pointed as the best candidate to fulfil these requirements.

One of the most modern computational tools for non-monotonic reasoning is Answer Set Programming (ASP). Ludäscher (Section 3.12) describes two technical challenges in the ASP encoding of QSR reasoning systems, namely the difficulty in distinguishing spatial configurations using the natural ASP encoding of pairwise relations; and the exploration of the hierarchical structure of various QSR formalisms. While Ludäscher describes the latter issue from an implementation perspective, Stell (Section 3.18) suggests a research program to investigate the interaction with hierarchical models of discrete space and time representing changes at different levels of detail. The key idea here is to combine granular change with temporal change for supporting reasoning about effects of actions at different levels of detail.

From a more foundational standpoint, Borgo (Section 3.1) argues for the creation of a systematic program for the formal study of spatial notions, such as between, convex, simplex, parallel etc. This program should include the comparison of distinct perspectives for such modelling, facilitating the understanding of cognitive representation and reasoning. The notion of path is given as an example of how this systematic program could be developed.

Pease (Section 3.14) proposes the formalisation of everyday concepts and facts in a high-level classical logic engine called Suggested Upper Merged Ontology (SUMO). This formalisation would constitute a collection of real-world spatio-temporal problems that could be used to test the sufficiency of spatial knowledge representation strategies.

Description

This topic deals with the development of human readable descriptions of the inputs, reasoning steps and solutions of spatial problems. In particular, it addresses whether (and to what extent) it would be possible to develop high-level representations or interfaces for dealing with natural language and/or diagrammatic descriptions that allow specifying both the input knowledge and the output conclusions in terms of textual descriptions of spatial problems.

Research on spatio-temporal language highlights the range of meanings across contexts [13] as well as patterns of usage in relation to mental representations [14] and problem-solving [15] in various domains. Part of the insight gained in this research concerns the significance of what can (or will normally) not be represented in language. Often, non-verbalised concepts are those that are best understood through features of the spatial world itself. For instance, we may verbalise only the high-level goal of an everyday action (such as dress up), because every detailed action is represented through a combination of world knowledge with the affordances of the actual objects in question. There is no need to learn or conceptualise how to handle every possible instance of these objects, because the affordances of each exemplar are sufficiently clear to act upon as required. Some of these issues feature in the contributions of Dobnik (Section 3.4), Lopes (Section 3.11), Scheider (Section 3.16), Stock (Section 3.19) and Tenbrink (Section 3.20).

The following three semantic representational dimensions are listed by Dobnik (Section 3.4), as a summary of the core aspects of spatial descriptions studied in areas of linguistics, psychology, and computer science: (i) scene geometry, (ii) world knowledge and (iii) dynamic aspects of interaction. Dobnik’s contribution also points out to a few open problems in this field, such as the lack of a unified computational language model that includes all of the cited dimensions, the limitation in the current research of grounding language in perception, that mostly deals with geometric perceptual context, and the need for experimental evaluation of models in real open domains.

Lopes (Section 3.11) suggests the use of the differences and interrelations between maps and navigation instructions to instantiate three cognitive core strategies of problem solving (attributed independently to McCarthy and Sloman), which are solving problems by following instructions, by descriptive knowledge representation and by analogical reasoning. Complementary, Stock (Section 3.19) argues that the current modelling of relative location descriptions is too restricted, not taking into account important contextual factors such as physical environment and objects in it; the observer’s goals and expectations; the audience location and knowledge. Two main research advances were then proposed to push the boundaries of this field: (i) the incorporation of factors proved to be important in linguistic and cognitive science research and (ii) cognitive science investigation on some neglected factors that could be used in computational models, such as the influence of users’ goals in the use of spatial relation terms. Tenbrink (Section 3.20) discusses the gap between human descriptions of routes and the state-of-the-art in the automatic generation of such descriptions to motivate three main challenges that deserve further attention: the combination of visual and verbal information, the consideration of change over time, and the flexibility in the use of various reference systems. Scheider (Section 3.16) contributes to this discussion suggesting the study of transformation models for concepts that are constitutive of spatial information, such as the concept of location, field, object, event and network. Arguing that transformations lie at the core of spatial reference systems, the author suggests that transformation models could be used to handle the variability of spatial information conceptualisations.

Problem solving

The discussion about problem solving was initially motivated by questions about whether or not it would be possible (and desirable) to develop interfaces for dealing with spatial configurations including diagrammatic depictions and natural language descriptions to solve spatial puzzles in similar ways as humans do; and also, what are the commonsense problem solving capabilities involving spatio-temporal features including temporal explanation and planning under physical/geometric qualitative or semi-quantitative constraints. This issue also includes the investigation of appropriate problem solving algorithms and their potential applications to real-world domains that could be of interest to industry.

Calculi for qualitative temporal and spatial reasoning have a long history [4, 5]. More recently the relation between 2D and 3D structures of space (plus time) and their 1D formal descriptions have been investigated; the goal is a farther reaching exploitation of spatial structure for spatial problem solving. Cognitive architectures for robotic agents that make direct use of knowledge and spatial affordances in physical environments (‘knowledge in the world’) are currently being developed [10]. The knowledge in the mind of these agents controls their perception and action in ways that simplifies spatial configurations in order to reduce the difficulty of solving the spatial problem at hand, while knowledge about spatial relations is represented directly in perceivable and manipulable physical structures [9]. A principle underlying this approach is the use of mild abstraction [7] as employed in map navigation or in constructive geometry [8]. Much QSR and related reasoning research was originally motivated by the obvious discrepancy between logic-based metric computation (where spatial directions may be defined, for instance, by exact geometric angles and location specifications) and human concepts (such as “to the left”). Falomir’s contribution (Section 3.5) starts from a discussion of the need to use cognitive heuristics for problem solving directly acting in the physical world, and argues for an effective combination of machine learning with automated reasoning for spatial problem solving. Spatial reasoning problems based on Perceptual/Differential Ability tests (PAT/DAT) are suggested as test domain for this development. Instead of assuming PAT/DAT as test domain, but still advocating the investigation of cognitive heuristics, Kroll (Section 3.8) describes recent results on the use of gaze heuristics for guiding an autonomous agent, and suggests the use of these ideas to dexterous assembly tasks; whereas Zachmann (Section 3.23) describes several issues pertaining the development of 3D geometric simulation methods for discovering affordances.

Hazarika (Section 3.6) discusses the use of mental maps defined over the space-time information structures underlying spatial problems (the Spatial Substrate [6]) for understanding how objects and their affordances affect the way humans reason about space. Following a similar line, Nath (Section 3.13) suggests the use of diagrammatic representations and reasoning to express the spatial problems and their physical substrate.

More explicit representation tools for problem solving were described by Homem (Section 3.7) and Santos (Section 3.15), in which they propose extending their previous work on applying case-based reasoning combined with QSR techniques towards complex real-world problems, such as real-time strategy games (Section 3.7) and collaborative mission planning for autonomous maritime vehicles (Section 3.15). Similarly, Wolter (Section 3.21) advocates the investigation of spatial problem solving techniques in dynamic domains (e.g. physical manipulation games) that allow for the progressive development of systems towards humanlevel capabilities.

Spatio-temporal Problem Repository

An issue that was of common agreement between the participants of the seminar is the need to create a Spatial Reasoning Problem repository. A few possible domain scenarios were discussed during the seminar, as listed below, but their full description is left for a future document.

1. Digital Forensics, cited in Section 3.2;
2. Puzzles such as Crazy Machines and Cut the Rope, cited in Section 3.2;
3. Angry birds, cited in Section 3.21
4. TPTP-style spatial problems, cited in Section 3.14
5. Perceptual/Differential Ability tests (PAT/DAT), cited in Section 3.5
6. Interpretation and generation of map descriptions (discussed during the seminar)
7. Multi step reasoning VQA (discussed during the seminar)
   • Ignore the images and concentrate on the scene graphs
   • Turn the scene graphs into logical formalism
8. From puzzle’s descriptions to solutions (discussed during the seminar)
   • Input: Puzzles described as diagrams, or described with words or both
   • Output: A solution
   • it involves: Multiple step reasoning, combining diagrams, language and problem solving

References

1. Bennett, B., Cohn, A. G., Wolter, F., and Zakharyaschev, M. (2002). Multi-dimensional modal logic as a framework for spatio-temporal reasoning. Applied Int., 17:239–251.
2. Cabalar, P. and Santos, P. E. (2011). Formalising the fisherman’s folly puzzle. Artificial Intelligence, 175(1):346–377.
3. Cabalar, P. and Santos, P. E. (2020). Spatial reasoning about string loops and holes in temporal ASP. In Calvanese, D., Erdem, E., and Thielscher, M., editors, Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020, Rhodes, Greece, September 12-18, 2020, pages 182–192.
4. Freksa, C. (1991). Cognitive and linguistic aspects of geographic space, chapter Qualitative spatial reasoning. Kluwer, Dordrecht.
5. Freksa, C. (1992). Temporal reasoning based on semi-intervals. Artificial Intelligence, 54(1):199 – 227.
6. Freksa, C. (2015). Computational problem solving in spatial substrates – A cognitive systems engineering approach. Int. J. Softw. Informatics, 9(2):279–288.
7. Freksa, C., Barkowsky, T., Dylla, F., Falomir, Z., Olteteanu, A.-M., and van de Ven, J. (2018a). Spatial problem solving and cognition. In Zacks J, T. H., editor, Representations in Mind and World, pages 156–183. New York: Routledge.
8. Freksa, C., Barkowsky, T., Falomir, Z., and van de Ven, J. (2018b). Geometric problem solving with strings and pins. Spatial Cognition & Computation. (in press).
9. Freksa, C., Olteteanu, A.-M., Ali, A. L., Barkowsky, T., van de Ven, J., Dylla, F., and Falomir, Z. (2016). Towards spatial reasoning with strings and pins. In Fourth Annual Conference on Advances in Cognitive Systems, volume 4.
10. Freksa, C., Vasardani, M., and Kroll, F. (2020). Dynamic problem solving in space. In ŠĶilters, J., Newcombe, N. S., and Uttal, D., editors, Spatial Cognition XII, pages 18–32, Cham. Springer International Publishing.
11. Ligozat, G. (2013). Qualitative Spatial and Temporal Reasoning. John Wiley & Sons.
12. Santos, P. E. and Cabalar, P. (2016). Framing holes within a loop hierarchy. Spatial Cognition & Computation, 16(1):54–95.
13. Tenbrink, T. (2007). Space, time, and the use of language: An investigation of relationships. Mouton de Gruyter, Berlin.
14. Tenbrink, T., Andonova, E., Schole, G., and Coventry, K. (2017). Communicative success in spatial dialogue: The impact of functional features and dialogic strategies. Language and Speech, 60:318–329.
15. Tenbrink, T. and Taylor, H. A. (2015). Conceptual transformation and cognitive processes in origami paper folding. Journal of Problem Solving, 8:2–22.

Creative Commons BY 4.0

Pedro Cabalar, Zoe Falomir, Paulo E. Santos, and Thora Tenbrink