Preface
INTRODUCTION
Qualitative Spatio-Temporal Representation and Reasoning: Trends and Future Directions is a contribution to the emerging discipline of Qualitative Spatial Information Theory within Artificial Intelligence (AI). The research reported in this collection covers both theory and application-centric work in the area of qualitative spatial and temporal reasoning and provides a comprehensive perspective on the emerging area of Qualitative Spatio-Temporal Representation and Reasoning (QSTR).
WHAT IS QSTR?
Moving around the environment is one of the primary tasks, which human beings and animals accomplish equally well. In the animal kingdom as a whole, reasoning about space is probably the most common and basic form of intelligence (Davis, 1990). For human beings, spatial reasoning, the representation and reasoning about space, is a particularly powerful and accessible mode of cognition (Piaget & Inhelder, 1967; Davis, 1990). Our every day interaction with the physical world is through spatial reasoning which appears to be driven by qualitative abstractions rather than complete quantitative knowledge a priori (Escrig & Toledo, 1998). Therefore, Qualitative Reasoning holds promise for developing formal theories for reasoning about space.
The desire to reason about space more akin to the cognitive process led to the birth of Qualitative Spatial Reasoning (QSR) within Knowledge Representation and Reasoning (KR & R). One of the central topics within AI, in general, and KR & R, in particular, is our ability to represent and reason with common-sense knowledge (McCarthy, 1959). Of our commonsensical abilities, those involving space and spatial attributes are perhaps the most basic ones. The physical world in which we live has a spatial extent and all physical objects are located in space. Space is an important part of common-sense reasoning. Driven by the motivation for a qualitative approach for the embodiment of commonsense spatial knowledge in intelligent systems, Qualitative Spatial Information Theory has emerged as a discipline within AI. Work within this discipline is designed to formulate formal frameworks to represent and reason about space, time, action, and change.
Space and time are inextricably linked. Spatial configurations change over time. Reasoning about space often involves reasoning about change in spatial configurations. Actions and events form the crucial connecting link between space, time, and spatial change, i.e., spatial configurations change as a result of actions and events within the environment. Spatial change is spatio-temporal.
Spatio-temporal reasoning is so common in our daily life that we rarely notice it as a particular concept of spatial analysis. When applied to computer information systems, spatio-temporal reasoning attempts to solve problems that deal with objects that occupy space and change over time (Egenhofer & Golledge, 1998).
Taking time into account is a central issue for GIS (Egenhofer & Golledge, 1998) and spatial databases (Peuquet, 1999). A lot of effort is devoted to providing useful and well-grounded models to be used as high-level qualitative description of spatio-temporal change (Hornsby & Egenhofer, 2000). Driven by cognitive approaches that characterize the processing of spatial information in QSR, there has been considerable influx of people from other areas within AI such as computer vision, robotics, etc. working on spatial change and spatial interactions (Fernyhough, et al., 2000; Galata, et al., 2002; Stock, 1997; Bhatt, et al., 2011). QSTR encompasses all such techniques.
Ambient Intelligence, Ubiquitous Computing, Intelligent Assistive Systems, and many other emerging fields will benefit immensely from the vast body of representation and reasoning tools that have been developed in QSR, in general, and the sub-field of QSTR, specifically. QSTR is increasingly becoming a core issue within Mobile Computing, GIS / Spatial Information Systems, Databases, and Computer Vision, as well as Knowledge Discovery and Data Mining. Attempts are already underway to explicitly utilize qualitative spatial calculi pertaining to different spatial domains for modeling the spatial aspect of an ambient environment (e.g., smart homes and offices); as well as to utilize a formal basis for representing and reasoning about space, change, and occurrences within such environments.
Qualitative Spatio-Temporal Representation and Reasoning: Trends and Future Directions covers both theory and applications with QSTR. The thrust is on research that focuses on formalizing commonsense spatial and temporal knowledge and directs the integration of qualitative spatial reasoning with general approaches for reasoning about spatio-temporal change. Applications that demonstrate the utility of well-established qualitative spatial and temporal calculi are also covered.
THE INSIDE STORY
Formal region based theories of space date back to the early part of the 20th century. Whitehead, in his book The Concept of Nature proposed the construction of a geometry in which spatial regions rather than points would be basic entities (Whitehead, 1920). In Process and Reality he suggested that a general theory of objects, events, and processes could be developed based on the primitive relation of connectedness (Whitehead, 1929). The book begins with a chapter on region-based theories of space. Hahmann and Grüninger gathered and organized the knowledge about ontological commitments for the wealth of region-based theories that have been proposed for representing space qualitatively. The chapter discusses the underlying ontological choices of a variety of first-order axiomatizations proposed and different ways of systematically looking at them. This gives a broader picture of mereotopology and how the different theories fit into this bigger picture regardless of their concrete axiomatization. It is made clear that the actual differences between the various mereotopologies are usually only minor and that there are only a handful of substantially different approaches.
Takahashi put forwards a framework called PLCA for QSR based on the connection patterns of regions. PLCA provides a simple but expressive and feasible representation for qualitative data with sufficient reasoning ability. PLCA also provides semantical reasoning incorporated with spatial reasoning and can be extended to handle shapes of regions.
Continuity of change is the perception of being seamless and is dependent on the granularity. What seems as continuous at some level of granularity may be discontinuous at a finer level. Nevertheless, continuity may be thought of as the intuitive idea of a gradual variation with no abrupt jumps or gaps. Characterization of such an intuitive notion of continuity for a qualitative theory of motion is referred to as qualitative spatio-temporal continuity (Hazarika, 2005). In his chapter on “Qualitative Reasoning and Spatio-Temporal Continuity,” Davis discusses the use of transition graphs for reasoning about continuous spatial change over time. Putting forward a general definition of a transition graph for a partition of a topological space, path-connected and homogeneous refinements of such a partition is defined. The qualitative behavior of paths through the space corresponds to the structure of paths through the associated transition graphs, and of associated interval label sequences; and a number of metalogical theorems that characterize these correspondences in terms of the expressivity of associated first-order languages are proved. The chapter then turns to specific real-world problems and shows how this theory can be applied to domains such as rigid objects, strings, and liquids.
The field of QSTR started with Allen's Interval Calculus (Allen, 1983) introduced some 25 years. Thereafter, a number of calculi have been developed to encapsulate commonsense knowledge about space and time. New research aims at combining existing qualitative calculi for improving the expressiveness; bringing with it an increasing complexity. Further, there is a trend towards emergence of integrated spatiotemporal calculi in order to deal with dynamic phenomena such as motion. Van de Weghe (2004) introduced the Qualitative Trajectory Calculus (QTC) as a qualitative calculus to represent and reason about moving objects. Delafontaine et al. present a general overview of the principal theoretical aspects of QTC, focusing on the two most fundamental types of QTC. It is shown how QTC deals with important reasoning concepts, and how the calculus can be employed in order to represent raw moving object data.
QSTR is an active field of research that has developed many representation and reasoning approaches so far, but only comparatively few applications exist that actually build on these QSTR techniques. For QSTR application development, a number of critical barriers to QSTR application development must be addressed, including methodologies for developing or analysing QSTR applications. Schultz, Amor, and Guesgen develop methodologies for QSTR application design. A theoretical foundation for QSTR applications that includes the roles of application designers and users is established. Their chapter adapts formal software requirements that allow a designer to specify the customer’s operational requirements and the functional requirements of a QSTR application. Design patterns for organising the components of QSTR applications and a methodology for defining high-level neighbourhoods that are derived from the system structure is presented.
Alboody, Sedes, and Inglada enrich RCC-8, the set of base relations for the spatial representation language Region Connection Calculus (Randell, et al., 1992). In their chapter, multi-level topological relations are introduced by using concepts such as separation number and the type of spatial elements of the boundary-boundary intersection spatial set to enrich RCC-8. Definitions for the generalization of the detailed topological relations are developed. Examples for GIS applications are provided to illustrate concepts developed in this chapter.
Santos et al. describe an initial region-based formalisation of some concepts about neuroanatomy into ontological and epistemic terms, as part of a major e?ort into the formalisation of the knowledge contained in neuroimages of patients with schizophrenia.
Temporal interval algebra has generated strong interest for both theoretical and practical reasons. All its Maximal Tractable Subalgebras (MTS) have been identified. Formalism on how to classify an input temporal network in one of these MTSs, or decide its intractability, has been proposed. Mitra and Launay present a linear algorithm for checking consistency when the input belongs to one of the seventeen MTS, and for finding out the constraints responsible for inconsistency in case the network is unsatisfiable.
Application of QSTR in realistic (relevant) domains, e.g., in the form of spatial control and spatial planning in cognitive robotics, for spatial decision-support in intelligent systems and as explanatory models in a wide-range of systems requiring the formulation of hypothesis, e.g., diagnosis requires integration of QSTR techniques within general commonsense reasoning frameworks in AI. The chapter by Bhatt is an attempt to position such integrated reasoning as a useful paradigm for the utilization of QSTR in relevant application domains.
Ontologies are not only suitable for describing static scenes with static objects (e.g., in photographs) but also enable representation of dynamic events with objects and properties changing in time (e.g., moving objects in a video). Representation of both static and dynamic scenes by ontologies, as well as querying and reasoning over static and dynamic ontologies are dealt with by Batsakis and Petrakis. Different types of temporal and spatial representations are all integrated into a unique spatio-temporal ontology representation capable of representing temporal and spatio-temporal information.
Wolter and Wallgrun approach QSTR from an application perspective. According to them, considering the exemplary application domains of robot navigation, GIS, and computer-aided design, reasoning must be interpreted in a broader sense than the often-considered constraint-based reasoning and that supporting tools must become available. Their chapter discusses these newly identified reasoning tasks and how they can be supported by QSTR toolboxes to foster the dissemination of QSTR in applications. Furthermore, the chapter explains the aim to overcome the lack-of-tools dilemma through the development of the QSTR toolbox SparQ.
Mastrogiovannet et al. introduce a framework for enabling context-aware behaviors in smart environment applications, with a special emphasis on smart homes and similar scenarios. The chapter describes an ontology-based architecture that allows system designers to specify non-trivial situations the system must be able to detect on the basis of available sensory data. The ontology encodes temporal operators that, once applied to sensory information, allow efficient recognition and correlation to different human activities and other events whose temporal relationships are contextually important. Special emphasis is devoted to actual representation and recognition of temporally distributed situations and the proof of concept is validated through a thoroughly described example of system usage.
Web databases evolve over time. Therefore, it is important that the database content summaries remain fresh so that they are able to serve all user queries. Database content summary construction need to take a step further so that content summaries do not pertain only to the topics covered in the database records but also represent the spatial and the temporal orientation of the database contents. Domain-specific ontologies can be utilized for deducing the thematic, the spatial, and the temporal orientations of the database contents. Zotos and Stamou propose a novel framework for the support of multi-faceted searches over distributed web-accessible databases. A method for analyzing and processing a sample of the database contents in order to deduce the topical, the geographic and the temporal orientation of the entire database contents is introduced.
FINAL COMMENTS
The QSTR approaches presented in the above chapters are by no means exhaustive and prescriptive, but rather they provide examples of various frameworks. The chapters in this book are thus intended as an invitation to further exploration of relevant theories to study QSTR within KR & R. While much of the work discussed above or work very close to what is reported here has individually received attention in prior QSTR literature, they have not been collectively brought together into a single book. We believe that each of the chapters in this book offers its own focus and explanation, and distinctive framework for the study and understanding of QSTR from multiple perspectives.
Shyamanta M Hazarika
Tezpur University, India
REFERENCES
Davis, E. (1990). Representations of commonsense knowledge. San Mateo, CA: Morgan Kaufmann.
Piaget, J., & Inhelder, B. (1967). The child’s conception of space. New York, NY: Basic Books.
Escrig, M. T., & Toledo, F. (1998). Qualitative spatial reasoning: Theory and practice - Application to robot navigation: Frontiers in AI and applications. Amsterdam, The Netherlands: IOS Press.
Egenhofer, M. J., & Golledge, R. G. (1998). Spatial and temporal reasoning in geographic information systems. Oxford, UK: Oxford University Press.
Peuquet, D. J. (1999). Making space for time: Issues in space-time data representation. In Proceedings of the 10th International Workshop on Database and Expert Systems Applications, (pp. 404–408). DEXA.
Hornsby, K., & Egenhofer, M. J. (2000). Identity-based changes: A foundation for spatio-temporal knowledge representation. International Journal of Geographical Information Science, 14(3), 207–224.
Fernyhough, J. H., Cohn, A. G., & Hogg, D. (2000). Constructing qualitative event models automatically from video input. Image and Vision Computing, 18(2), 81–103.
Galata, A., Cohn, A. G., Magee, D., & Hogg, D. (2002). Modeling interaction using learnt qualitative spatio-temporal relations and variable length Markov models. In F. van Harmelen (Ed.), Proceedings of the 15th European Conference on AI (ECAI 2002), (pp. 741–745). ECAI.
Stock, O. (Ed.). (1997). Spatial and temporal reasoning. London, UK: Kluwer Academic Publishers.
Bhatt, M., Guesgen, H., Woelfl, S., & Hazarika, S. (2011). Qualitative spatial and temporal reasoning: Emerging applications, trends, and directions. Spatial Cognition & Computation: An Interdisciplinary Journal, 11(1), 1-14.
Whitehead, A. N. (1920). The concept of nature. Cambridge, UK: Cambridge University Press.
Whitehead. A. N. (1929). Process and reality. New York, NY: The MacMillan Company.
Whitehead, A. N. (1978). Process and reality: Corrected edition. New York, NY: MacMillan.
Hazarika, S. M. (2005). Qualitative spatial change: Space time histories and continuity. PhD Thesis. Leeds, UK: University of Leeds.
Allen, J. F. (1983). Maintaining knowledge about temporal intervals. Communications of the ACM, 26(11), 832–843.
Van de Weghe, N. (2004). Representing and reasoning about moving objects: A qualitative approach. PhD Thesis. Ghent, Belgium: Ghent University.
Randell, D. A., Cui, Z., & Cohn, A. G. (1992). A spatial logic based on regions and connection. In B. Nebel, C. Rich, & W. Swartout (Eds.), Proceedings of 3rd International Conference on Knowledge Representation and Reasoning (KR 1992), (pp. 165–176). San Mateo, CA: Morgan Kaufmann.