We present the conceptual and operational overview and architecture of a framework for semantic { high-level, qualitative { reasoning about dynamic geospatial phenomena. The framework is based on advances in the areas of geospatial semantics, qualitative spatio-temporal representation and reasoning, and reasoning about actions and change. We present the main operational modules, namely the modules for data quali cation and consistency, qualitative spatial data integration and con ict resolution, and high-level explanatory analysis.
Geographic information systems (GIS) and geospatial web applications are
confronted with massive quantities of micro and macro-level spatio-temporal data
consisting of precise measurements pertaining to environmental features, aerial
imagery, and more recently, sensor network databases that store real-time
information about natural and arti cial processes and phenomena. In many
applications multiple such data sets need to be combined on the y in order to provide an
adequate basis for high-level spatio-temporal analysis. Within next-generation
GIS systems, the fundamental information theoretic modalities are envisioned to
undergo radical transformations: high-level ontological entities such as objects,
events, actions and processes and the capability to model and reason about these
are expected to be a native feature of next-generation GIS [
Building on these existing foundations from the GIS and AI communities, we propose an overarching formal framework, and its corresponding conceptual architecture, for high-level qualitative modeling and analysis for the domain of geospatial dynamics. The input is assumed to consist of data sets from several data sources and the framework encompasses modules for di erent aspects such as quali cation, spatial consistency, data merging and integration, and explanatory reasoning within a logical setting.
We give a brief overview of the proposed architecture in the next section and then describe and discuss the di erent components in detail in the following sections. In doing so, we address basic representational and computational challenges within the formal theory of space, events, actions and change. 2
In the following, we propose and explain a formal framework and its corresponding conceptual architecture for high-level qualitative modeling and (explanatory) analysis for the domain of geospatial dynamics.
Fig. 1 illustrates the architecture with its di erent modules, which we explain in detail in Sections (3{5). The main aspects of the proposed architecture are the following: The input consists of data sets from several data sources such as remote sensing, spatial databases, sensors etc. These data sets are then processed to derive qualitative spatial observations associated with speci c time points to be handed over to the actual analytical reasoning component. This preprocessing is done by a module responsible for partitioning the input data into time points and merging data associated with the same time point including the resolution of spatial con icts between the di erent data sources and wrt. given spatial integrity constraints. This module is supported by other modules for performing quali cation and spatial consistency checking. The pre-processed temporallyordered observations constitute con gurational and narrative descriptions and serve as the input to the reasoning component, which embeds in the capability to perform explanatory reasoning. The knowledge derived by the reasoning component for a particular domain under consideration can be utilized by exQuali cation
Consistency checking Source 1 Source 2
Source n Data set 1 Data set 2
Data set n Temporal partitioning
+
Integration / Merging Integrity constraints
Observation 1 Observation 2 Observation m
Reasoning Domain independent spatial theory - spatio-temporal change - phenomenal aspects - geospatial events Domain Theory - observation - high-level abducibles
Query Processing
Database Domain dependent theory Geometric conditions ternal services (e.g., query-based services) and application systems that directly interface with humans (e.g., experts, decision-makers). 3
Logical frameworks for performing explanation with spatial information generally require that the input information is consistent, meaning that the combined input data is compliant with the underlying logical spatial theory. However, in the geographic domain, the input data often stems from multiple sources, for instance from di erent sensors, remote sensing data, map data, etc., and the data itself is a icted by measurement errors and uncertainty. Hence, the geo-referenced quantitative input data about spatial objects needs to be preprocessed in order to be used to perform explanation on a level of qualitative spatial relations. This preprocessing involves the temporal partitioning of the input data into an ordered sequence of time points and the formulation of consistent qualitative descriptions called observations for each time point. Crucial sub-components involved in the generation of these descriptions are modules for translating geo-referenced quantitative data into relations from several qualitative spatial models dealing with di erent aspects of space, a process referred to as quali cation, and for checking the consistency of the combined information. Both modules are utilized by the main preprocessing module responsible for qualitative integration including the resolution of contradictions as explained further in the next section.
The quali cation procedure needs to consider all data that concerns the same moment in time and compute relations for all n-tuples of objects where n corresponds to the arity of the relations in the given qualitative model (e.g., binary topological relations such as contained or disjoint, or cardinal directions rela(a) tions such as north-of ). If uncertainty of quantitative information is explicitly represented this needs to be taken into account and may lead to disjunctions on the qualitative level.
Due to the mentioned measurement errors and uncertainty of the quantitative input data, the qualitative descriptions resulting from quali cation for particular moments in time may contain contradictions or violate integrity constraints stemming from background knowledge about the application domain. Fig. 2 illustrates the case of a spatial inconsistency on the level of topological relations when combining the information from four di erent sources (all concerning the same time period): From combining the fact that objects c and d (e.g., two climate phenomena) are reported to overlap by one source (a) with the reported relations c is completely contained in a (b) and d is completely contained in b (c) (let us say a and b are two neighbored states) it follows that the two states a and b would need to overlap as well. This contradicts the information from the fourth source (d) which could for instance be a spatial databases containing state boundaries (or alternatively be given in the form of a general integrity constraint).
As a result of the possibility of inconsistent input information occurring in
geographic applications, frameworks for explanation and spatio-temporal analysis
need the ability to at least detect these inconsistencies in order to exclude the
contradicting information or, as a more appropriate approach, resolve the
contradictions in a suitable way. Deciding consistency of a set of qualitative spatial
relations has been studied as one of the fundamental reasoning tasks in
qualitative spatial representation and reasoning [
When con icts arise during the integration of spatial data, it is desirable to not
only detect the inconsistencies but also resolve con icts in a reasonable manner
to still be able to exploit all provided information in the actual logical reasoning
approach for explanation and analysis. Methods for data integration and con ict
resolution have for instance been studied under the term information fusion [
Fig. 3 shows an example from the domain of urban dynamics that illustrates the role of integration with con ict resolution as well as quali cation and consistency checking. Let us assume that we have spatial data from di erent sources: Source 1 provides information about di erent land use zones including parks, residential zones, industrial zones, which are derived analyzing aerial images. Source 2 provides information about natural reservoirs, that is about parks and mangroves, stemming from a spatial database. Let us furthermore assume that the land use types are de ned in a mutually exclusive way such that two different zones cannot overlap. We now follow the procedure for integrating this information sketched in Alg. 1 that takes a set of observations O, one for each source, containing object identi ers with associated geometries and a set IC of integrity constraints. Fig. 3(a) illustrates part of the combined information from all sources for a particular time point t. Source 1 and source 2 both contain geo-referenced polygons for a park but this information does not match. The rst step now is to qualify the geometric data from source 1 and 2 which results in the qualitative constraint network Q.3 Using RCC-8 this network looks as shown in Fig. 3(b) (p and p1 represent the di erent geometries for the same park object). If network Q is consistent and compliant with the integrity constraints, the result can directly be handed over as an observation to the reasoning module. However, as also shown in Fig. 3(b) this is not the case as integrity constraints 3 Alternatively, information for each data set could be quali ed separately resulting in several constraint networks that have to be combined by a suitable merging operator. iz1 rz2 (a) iz2 forest/nationalpark industrialzone ruralzone ec iz1 dc
po (ec,dc) ec po (eq) dc rz2 (b) ec p‘ ec
po ec (ec,dc) iz2 ec,dc iz1 p ec,dc ec eq dc ec
ec rz2 (c) p‘ ec ec ec iz2 (1) (2) are violated in three places indicated by listing possible relations following from the integrity constraint in brackets below the original relation. The relation between p and p1 should be eq simply because it is known that both represent the same object. The relation between rz2 and p should be either ec or dc because of our integrity constraint, and the same holds for the relation between p1 and iz2. Therefore, the qualitative con ict resolution component needs to be called to nd a qualitative representation that is as close as possible to the network from Fig. 3(b) but is overall consistent.
To achieve the con ict resolution, a resolution operator based on the idea of
distance-based merging operators for qualitative spatial representations [
‚ 1⁄i j⁄m dps; s1q dBpCij ; Ci1j q The resolved network pQq is then constructed by taking the union of those scenarios that are consistent, compliant with the integrity constraints and have a minimal distance to Q according to dps; s1q4: ⁄ pQq sPSpQq s with
SpQq t s P JQCN K | @s1 P JQCN K : dps1; Qq ¥ dps; Qqu (3)
and JQCN K standing for the set of all scenarios that are consistent and compliant
with the integrity constraints. Following the approach described in [
creation continuation
reappearance disappearance transformation
death transmission cloning can be computed by incrementally relaxing the constraints until at least one consistent scenario has been found. This is illustrated in Alg. 2 where we assume that the function relax(Q,i) returns the set of scenarios s which have a distance dps1; Qq i to Q.
The result of applying the resolution operator to the network from Fig. 3(b) is shown in Fig. 3(c): Both violations of integrity constraints have been resolved by assuming that instead of 'overlap' the correct relation is 'externally connected'. Interestingly, the resulting consistent qualitatively model contains two disjunctions basically saying that the relation between the park and iz1 is either ec or dc. This is a consequence of the fact that both qualitative models are equally close to the input model such that it is not possible to decide between the two hypotheses.
Algorithm 1: Qualify+Merge(O; IC) Q — qualifypOq if consistentpQ; ICq then
Q — pQ; ICq end if return Q
Algorithm 2: pQ; ICq i — 0, N — H while N H do
R — relaxpQ; iq for r P R do if consistentpr; ICq then N — N Yr end if end for i — i 1 end while return N 5
Our objective for the high-level reasoning module is to provide the functionality to enable reasoning about spatio-temporal narratives consisting of events and processes at the geographic scale. We do not attempt an elaborate ontological characterization of events and processes, a topic of research that has been addressed in-depth in the state-of-the-art (see Section 1). For the purposes of this paper, we utilize a minimal, yet rich, conceptual model consisting of a range of events such that it may be used to qualitatively ground metric geospatial datasets consisting of spatial and temporal footprints of human and natural phenomena at the geographic scale.
From an ontological viewpoint, spatial occurrences may be de ned at two levels: (O1) domain-independent, and (O2) domain-dependent : O1. Domain Independent Spatial Occurrences These occurrences are those that may be semantically characterized within a general theory of space and spatial change. These may be grounded with respect to either a qualitative theory, or an elaborate typology of geospatial events. Distinctions as per (A{B) are identi able:
In so far as a general qualitative theory of spatial change is concerned, there is only one type of occurrence, viz - a transition from one qualitative state (relation) to another as (possibly) governed by the continuity constraints of the relation space. At this level, the only identi able notion of an occurrence is that of a qualitative spatial transition that the primitive objects in the theory undergo. At the level of a spatial theory, it is meaningless to ascribe a certain spatial transition as being an event or action; such distinctions demand a slightly higher level of abstraction. For example, the transition of an object (o1) from being disconnected to another object (o2) to being a tangential part of it could either coarsely represent the volitional movement of a person into a room or the motion of a ball. Whereas the former is an action performed by an agent, the latter is a deterministic event that will necessarily occur in normal circumstances. Our standpoint here is that such distinctions can only be made in a domain speci c manner; as such, the classi cation of occurrences into actions and events will only apply at the level of the domain with the general spatial theory dealing only with one type of occurrence, namely primitive spatial transitions that are de nable in it.
At the domain independent level, the explanation may encompass behaviours such as emergence, growth & shrinkage, disappearance, spread, stability etc, in addition to the sequential/parallel composition of the behavioural primitives aforementioned, e.g., emergence followed by growth, spread / movement, stability and disappearance during a time-interval. Certain kinds of typological elements, e.g., growth and shrinkage, may even be directly associated with spatial changes at the qualitative level in (A).
Appearance of new objects and disappearance of existing ones, either abruptly
or explicitly formulated in the domain theory, is also characteristic of non-trivial
dynamic (geo)spatial systems. Within event-based GIS, appearance and
disappearance events are regarded to be an important typological element for the
modeling of dynamic geospatial processes [
O2. Domain-Speci c Spatial Occurrences At a domain-dependent level,
behaviour patterns may characterize high-level processes, environmental /
natural and human activities such as deforestation, urbanization, land-use
transformations etc. These are domain-speci c occurrences that induce a transformation
on the underlying spatial structures being modeled. Basically, these are domain
speci c events or actions that have (explicitly) identi able occurrence criteria
and e ects that can be de ned in terms of qualitative spatial changes, and the
fundamental typology of spatial changes. For instance, in the example in Fig.
5, we can clearly see that region a has continued to shrink over a three-decade
period, followed by a split, and eventually disappearing in the year 1990.
The following general notion of a `spatial occurrence' is identi able [
As an example, consider an event that will cause a region to split or make
it grow / shrink. Likewise, an aggregate cluster of geospatial entities (e.g., in
wildlife biology domain) may move and change its orientation with respect to
other geospatial entities. Thinking in agent terms, a spatial action by the
collective / aggregate entity, e.g., turn south-east, will have the e ect of changing the
orientation of the cluster in relation to other entities. In certain situations, there
may not be a clearly identi able set of domain-speci c occurrences with
explicitly known occurrence criteria or e ects that are de nable in terms of a typology
of spatial change, e.g., cluster of alcohol-related crime abruptly appearing and
disappearing at a certain time. However, even in such situations, an analysis of
the domain-independent events and inter-event relationships may lead to an
understanding of spatio-temporal relationships and help with practical hypothesis
generation [
Explanatory Reasoning in GIS: A Case for Practical Abduction Explanatory reasoning requires the ability to perform abduction with spatiotemporal information. In the context of formal spatio-temporal calculi, and logics of action and change, this translates to the ability to provide scenario and narrative completion abilities at a high-level of abstraction. Consider the GIS domain depicted in Fig. 5, and the basic conceptual understanding of spatial occurrences described in (O1{O2; Section 5). At a domainindependent level, the scene may be described using topological and qualitative size relationships. Consequently, the only changes that are identi able at the level of the spatial theory are shrinkage, splitting, and eventual disappearance { this is because a domain-independent spatial theory may only include a generic typology (appearance, disappearance, growth, shrinkage, deformation, splitting, merging etc) of spatial change. However, at a domain-speci c level, these changes could characterize a speci c event (or process) such as deforestation. The hypotheses or explanations that are generated during a explanation process should necessarily consist of the domain-level occurrences in addition to the underlying (associated) spatial changes (as per the generic typology) that are identi able. Intuitively, the derived explanations more or less take the form of existential statements such as: \Between time-points ti and ti, the process of deforestation is abducible as one potential hypothesis". Derived hypotheses / explanations that involve both domain-dependent and as well their corresponding domain-independent typological elements are referred to as being `adequate' from the viewpoint of explanatory analysis for a domain. At both the domainindependent as well as dependent levels, abduction requires the fundamental capability to interpolate missing information, and understand partially available narratives that describe the execution of high-level real or abstract processes. In the following, we present an intuitive overview of the scenario and narrative completion process.
Scenario and Narrative Completion Explanation, in general, is regarded as
a converse operation to temporal projection essentially involving reasoning from
e ects to causes, i.e., reasoning about the past [
Explanation problems demand the inclusion of a narrative description, which
is essentially a distinguished course of actual events about which we may have
incomplete information [
Given the set of observations resulting from the preprocessing which
constitutes a partial narrative of the evolution of a system in terms of high-level
spatio-temporal data, scenario and narrative completion corresponds to the
ability to derive completions that bridge the narrative by interpolating the
missing spatial and action / event information in a manner that is consistent with
domain-speci c and domain-independent rules / dynamics. Consider the
illustration in Fig. 6 for a branching / hypothetical situation space that characterizes
the complete evolution of a system [
In our research, we are addressing a broad question: what constitutes the (core)
spatial informatics underlying (speci c kinds) of analytical capabilities within a
range of dynamic geospatial domains [