• a novel segmentation-based approach to estimate intention of a mobile agent. • an efficient implementation of a new segmentation-based algorithm for continues or realtime intention recognition. • evaluation of the latency, stability, and accuracy of the proposed algorithm compared to other state-of-the-art online intention algorithms. This paper proposes and evaluates an efficient online algorithm for recognizing the movement intentions of mobile agents. As an agent reveals new movements, our algorithm continuously ranks various possible intentions, such as reaching a specific destination or avoiding a particular area, using a novel approach to semantic trajectory segmentation. We empirically validate the performance of our algorithm against state-of-the-art alternatives in the path planning using simulated movement data. The results show that our approach improves reliability and accuracy in identifying true intention in scenarios with an increased number of candidate destinations, or when a mobile agent takes less planned and predictable routes.

This paper explores the use of probabilistic and conventional qualitative spatial reasoning (QSR) in the context of geospatial question answering (GeoQA) systems. The paper presents a thorough empirical investigation of the performance of a probabilistic and a conventional qualitative spatial reasoner, across a range increasingly sophisticated scenarios with real data and synthetically generated questions. The results indicate the potential of probabilistic QSR to provide more detailed information about spatial configurations than conventional QSR; but at the cost of less frequent errors in estimating the relative likelihood of different reasoning conclusions. Errors in probabilistic reasoning also tend to be systematically associated with lower probability conclusions. The results have implications for reliable and flexible automated spatial reasoning systems, especially where neither conventional geographic information retrieval (GIR) techniques nor large language models (LLMs) are able to provide a satisfactory solution to GeoQA problems.

Probabilistic logics combine the ability to reason about complex scenes, with a rigorous approach to uncertainty. This paper explores the construction of probabilistic spatial logics through the combination of established qualitative spatial calculi together with Markov logic networks (MLNs). Qualitative spatial calculi provide the basis for automated representation and reasoning with complex spatial scenes; MLNs provide a rigorous basis for handling uncertainty and driving probabilistic inference. Our approach focuses specifically on the combination of an uncertain knowledge base with a certain spatial reasoning rule-base. The experiments explore how uncertain knowledge propagates through certain qualitative spatial inferences, using the specific example of reasoning with cardinal directions. The results provide a template for probabilistic qualitative spatial reasoning more generally, with applications to a wide range of common scenarios for situational awareness and automated reasoning under uncertainty.

Although geospatial question answering systems have received increasing attention in recent years, existing prototype systems struggle to properly answer qualitative spatial questions. In this work, we propose a unique framework for answering qualitative spatial questions, which comprises three main components: a geoparser that takes the input questions and extracts place semantic information from text, a reasoning system which is embedded with a crisp reasoner, and finally, answer extraction, which refines the solution space and generates final answers. We present an experimental design to evaluate our framework for point-based cardinal direction calculus (CDC) relations by developing an automated approach for generating three types of synthetic qualitative spatial questions. The initial evaluations of generated answers in our system are promising because a high proportion of answers were labelled correct.

This paper explores a class of qualitative-geometric relations between disjoint regions, embedded in the surface of a sphere or in the plane. These relations combine topological information about the configuration of the regions themselves as well as of the geometric Voronoi regions surrounding them. The method uses maptrees to construct a rigorous and exhaustive framework for n-ary relations between ensembles of regions. The resulting uniquely defined relations are akin to the verbal spatial relation ‘surrounds,’ in one common interpretation. The paper provides an exhaustive formal classification of such extended spatial relations between up to three regions. A further exhaustive computational exploration of up to seven regions in the sphere also provides an algorithm to enumerate all possible configurations. The results demonstrate how the approach can be used to provide fine-grained and salient descriptions of qualitative-geometric relations for complex scenes involving ensembles of multiple regions.

Understanding urban areas of interest (AOIs) is essential in many real-life scenarios, and such AOIs can be computed based on the geographic points that satisfy user queries. In this article, we study the problem of efficient and effective visualization of user-defined urban AOIs in an interactive manner. In particular, we first define the problem of user-defined AOI visualization based on a real estate data visualization scenario, and we illustrate why a novel footprint method is needed to support the visualization. After extensively reviewing existing “footprint” methods, we propose a parameter-free footprint method, named AOI-shapes, to capture the boundary information of a user-defined urban AOI. Next, to allow interactive query refinements by the user, we propose two efficient and scalable algorithms to incrementally generate urban AOIs by reusing existing visualization results. Finally, we conduct extensive experiments with both synthetic and real-world datasets to demonstrate the quality and efficiency of the proposed methods.

This paper reports on a controlled experiment evaluating how different cartographic representations of risk affect participants’ performance on a complex spatial decision task: route planning. The specific experimental scenario used is oriented towards emergency route-planning during flood response. The experiment compared six common abstract and metaphorical graphical symbolizations of risk. The results indicate a pattern of less-preferred graphical symbolizations associated with slower responses and lower-risk route choices. One mechanism that might explain these observed relationships would be that more complex and effortful maps promote closer attention paid by participants and lower levels of risk taking. Such user considerations have important implications for the design of maps and mapping interfaces for emergency planning and response. The data also highlights the importance of the ‘right decision, wrong outcome problem’ inherent in decision-making under uncertainty: in individual instances, more risky decisions do not always lead to worse outcomes.

This article concerns the opportunities for analysis of data about movement past spatial checkpoints. Checkpoint data are generated by an object’s movement past fixed sensors (‘checkpoints’) distributed throughout geographic space. Example sources of checkpoint data include road-toll gantries, social media check-ins, WiFi hotspots, access swipe cards, and public transport smart cards. Many existing movement analytics techniques, which frequently rely on precise coordinate locations, are ill-suited to the inherent and variable spatial granularity of checkpoint data. However, this spatial granularity also brings advantages in linking movement more closely to its environmental context, in particular the characteristics of the regions through which an object is moving. In this article, we propose a general model for representing checkpoint data of moving objects, based on two fundamentally different types of sensors: transaction and presence. Experiments using real movement data illustrate the diversity of queries that can be efficiently supported by our model. An example movement classification task, identifying vehicle type from checkpoint data recording vehicle movement, provides an illustration of the opportunities for more closely linking movement with its environmental context through the use of checkpoint data analysis.

Redundancy checking is an important task in AI subfields such as knowledge representation and constraint solving. This paper considers redundant topological constraints, defined in the region connection calculus RCC8. We say a constraint in a set C of RCC8 constraints is redundant if it is entailed by the rest of C. A prime subnetwork of C is a subset of C which contains no redundant constraints and has the same solution set as C. It is natural to ask how to compute such a prime subnetwork, and when it is unique. While this problem is in general intractable, we show that, if S is a subalgebra of RCC8 in which weak composition distributes over nonempty intersections, then C has a unique prime subnetwork, which can be obtained in cubic time by removing all redundant constraints simultaneously from C. As a by-product, we show that any path-consistent network over such a distributive subalgebra is minimal.

Several algorithms have been proposed to generate a polygonal ‘footprint’ to characterize the shape of a set of points in the plane. One widely used type of footprint is the χ-shape. Based on the Delaunay triangulation (DT), χ-shapes guaranteed to be simple (Jordan) polygons. This paper presents for the first time an incremental χ-shape algorithm, capable of processing point data streams. Our incremental χ-shape algorithm allows both insertion and deletion operations, and can handle streaming individual points and multiple point sets. The experimental results demonstrated that the incremental algorithm is significantly more efficient than the existing, batch χ-shape algorithm for processing a wide variety of point data streams.

The paper investigates whether the methods chosen for representing uncertain geographic information aid or impair decision-making in the context of wildfire hazard. Through a series of three human subject experiments, utilizing 180 subjects and employing increasingly difficult tasks, this research evaluates the effect of five different visualizations and a text-based representation on decision-making under uncertainty. Our quantitative experiments focus specifically on the task of decision-making under uncertainty, rather than the task of reading levels of uncertainty from the map. To guard against the potential for generosity and risk seeking in decision-making under uncertainty, the experimental design uses performance-based incentives. The experiments showed that the choice of representation makes little difference to performance in cases where subjects are allowed the time and focus to consider their decisions. However, with the increasing difficulty of time pressure, subjects performed best using a spectral color hue-based representation, rather than more carefully designed cartographic representations. Text-based and simplified boundary encodings were among the worst performers. The results have implications for the performance of decision-making under uncertainty using static maps, especially in the stressful environments surrounding an emergency.

This paper develops a new mechanism to efficiently compute and compactly store qualitative spatial relations between spatial objects, focusing on topological and directional relations for large datasets of region objects. The central idea is to use minimum bounding rectangles (MBRs) to approximately represent region objects with arbitrary shape and complexity and only store spatial relations that cannot be unambiguously inferred from the relations of corresponding MBRs. We demonstrate, both in theory and practice, that our approach requires considerably less construction time and storage space, and can answer queries more efficiently than the state-of-the-art methods.

This article concerns the theoretical foundations of movement informatics. We discuss general frameworks in which models of spatial movement may be developed. In particular, the article considers the object–field and Lagrangian–Eulerian dichotomies, and the SNAP/SPAN ontologies of the dynamic world, and classifies the variety of informatic structures according to these frameworks. A major challenge is transitioning between paradigms. Usually data is captured with respect to one paradigm but can usefully be represented in another. We discuss this process in formal terms and then describe experiments that we performed to show feasibility. It emerges that observational granularity plays a crucial role in these transitions.

This article describes research into the design and analysis of decentralized algorithms for computing convoy patterns (a density-based movement pattern amongst moving point objects, previously formalized and computed in a centralized manner). A series of decentralized algorithms are presented and discussed (naïve, tree-based, and further devolved reactive approaches) for mobile geosensor nodes to share the necessary information to enable in-network detection and monitoring of convoys; these approaches require neither centralized control nor quantitative positioning. Empirical evaluation of algorithm characteristics and performance (via simulation experiments with synthetic and real movement data) demonstrate algorithm efficiency and effectiveness (with various strategies to structure information flow and devolve decision-making considerably improving communication efficiency).

We consider the problem of estimating the path taken by an object in a road network from sparse, noisy position measurements. Path estimation is posed in a Bayesian framework which allows the incorporation of prior information about vehicle movements. A carefully designed importance sampler is used to approximate the posterior path probabilities. The algorithm is demonstrated on simulated data.

In many applications, the environmental context for and drivers of movement patterns are just as important as the patterns themselves. This article adapts standard data mining techniques, combined with a foundational ontology of causation, with the objective of helping domain experts identify candidate causal relationships between movement patterns and their environmental context. In addition to data about movement and its dynamic environmental context, our approach requires as input definitions of the states and events of interest. The technique outputs causal and causal-like relationships of potential interest, along with associated measures of support and confidence. As a validation of our approach, the analysis is applied to real data about fish movement in the Murray River in Australia. The results demonstrate that the technique is capable of identifying statistically significant patterns of movement indicative of causal and causal-like relationships.

This article provides a decentralized and coordinate-free algorithm, called decentralized gradient field (DGraF), to identify critical points (peaks, pits, and passes) and the topological structure of the surface network connecting those critical points. Algorithms that can operate in the network without centralized control and without coordinates are important in emerging resource-constrained spatial computing environments, in particular geosensor networks. Our approach accounts for the discrepancies between finite granularity sensor data and the underlying continuous field, ignored by previous work. Empirical evaluation shows that our DGraF algorithm can improve the accuracy of critical points identification when compared with the current state-of-the-art decentralized algorithm and matches the accuracy of a centralized algorithm for peaks and pits. The DGraF algorithm is efficient, requiring O(n) overall communication complexity, where n is the number of nodes in the geosensor network. Further, empirical investigations of our algorithm across a range of simulations demonstrate improved load balance of DGraF when compared with an existing decentralized algorithm. Our investigation highlights a number of important issues for future research on the detection of holes and the monitoring of dynamic events in a field.

Event detection concerns identifying occurrence of interesting events which are meaningful and understandable. In dynamic fields, as time passes the attribute of phenomenon varies in spatial locations. Detecting events in dynamic fields requires an approach to deal with the highly granular data arriving in real time. This paper proposes a spatiotemporal event detection algorithm in dynamic fields which are monitored by wireless sensor networks (WSNs). The algorithm provides a method using probabilistic graphical models (PGMs) in WSNs to cope with the uncertainty of sensor readings. The algorithm incorporates the ability of Markov chains in temporal dependency modelling and Markov random fields theory to model the spatial dependency of sensors in a distributed fashion. Experimental evaluation of the proposed algorithm demonstrates that the decentralized approach improves the F1-score to 82% and 29% better precision than simple threshold technique. In addition, the performance of the algorithm was evaluated and compared with respect to the scalability (in terms of communication complexity). In comparison with the centralized approach the decentralized algorithm can substantially improve the scalability of communication in wireless sensor networks.

How does complex spatiotemporal behavior arise from, and from which, spatiotemporal knowledge? In an attempt to answer this question, we extend Valentino Braitenberg's thought experiment [3] by describing and implementing vehicles with explicit, and increasingly sophisticated, spatiotemporal knowledge. We then observe the corresponding spatiotemporal behavior that can result. These spatiotemporal vehicles are able to move about their environment. The paper shows how vehicles can be incrementally equipped with three fundamental spatial constructs: knowledge of places, of neighborhoods, and the ability to communicate with other nearby vehicles. In turn we demonstrate, using agent-based simulations, how the fundamental spatial concepts of fields, networks, objects, and reference frames can emerge from these basic constructs. Our approach contributes to ongoing efforts of identifying the core concepts of spatial information [11] and of understanding the relationships between interaction with space and spatial computation [6].

This paper examines efficient and decentralized monitoring of objects moving in a transportation network. Previous work in moving object monitoring has focused primarily on centralized information systems, like moving object databases and geographic information systems. In contrast, in this paper monitoring is in-network, requiring no centralized control and allowing for substantial spatial constraints to the movement of information. The transportation network is assumed to be augmented with fixed checkpoints that can detect passing mobile objects. This assumption is motivated by many practical applications, from traffic management in vehicle ad hoc networks to habitat monitoring by tracking animal movements. In this context, this paper proposes and evaluates a family of efficient decentralized algorithms for capturing, storing and querying the movements of objects. The algorithms differ in the restrictions they make on the communication and sensing constraints to the mobile nodes and the fixed checkpoints. The performance of the algorithms is evaluated and compared with respect to their scalability (in terms of communication and space complexity), and their latency (the time between when a movement event occurs, and when all interested nodes are updated with records about that event). The conclusions identify three key principles for efficient decentralized monitoring of objects moving past checkpoints: structuring computation around neighboring checkpoints; taking advantage of mobility diffusion and separating the generation and querying of movement information.

Qualitative information about topological events, like the merging or splitting of spatial regions, has many important applications in environmental monitoring. Examples of such applications include detecting the emergence of ‘hot spots’ in sea temperature around a coral reef; or the break up and dispersion of an environmental pollution spill. This paper develops and tests an efficient, decentralized spatial algorithm capable of detecting high-level topological events occurring to spatial regions monitored by a wireless sensor network. The algorithm, called In-Network Qualitative Identification of Region Evolution (INQUIRE), is decentralized because at no point does any single system element possess global knowledge of the entire system state. Instead, INQUIRE relies purely on a sensor node's local knowledge of its own state and the state of its immediate network neighbors. Experimental evaluation of the INQUIRE algorithm demonstrates that our decentralized approach can substantially improve scalability of communication when compared with efficient centralized alternatives.

With the development of miniaturized sensor and communication technologies, there is an ever-growing demand for algorithms to derive high-level spatiotemporal events from large amounts of sensed data. Our previous work has already defined a decentralized, in-network approach to identifying topological relation changes between continuously evolving regions monitored by a geosensor network. However, our previous work relies on a number of strong continuity assumptions, concerning the temporal granularity of sensor observations and the type of region deformations. This paper presents an improved algorithm which demonstrates how these key simplifying assumptions can be relaxed. Empirical testing of the algorithm demonstrates how this algorithm can operate at higher levels of scalability than both the previous algorithm, and smart centralized alternatives.

This article presents an algorithm for decentralized (in-network) data mining of the movement pattern flock among mobile geosensor nodes. The algorithm DDIG (Deferred Decentralized Information Grazing) allows roaming sensor nodes to ‘graze’ over time more information than they could access through their spatially limited perception range alone. The algorithm requires an intrinsic temporal deferral for pattern mining, as sensor nodes must be enabled to collect, memorize, exchange, and integrate their own and their neighbors' most current movement history before reasoning about patterns. A first set of experiments with trajectories of simulated agents showed that the algorithm accuracy increases with growing deferral. A second set of experiments with trajectories of actual tracked livestock reveals some of the shortcomings of the conceptual flocking model underlying DDIG in the context of a smart farming application. Finally, the experiments underline the general conclusion that decentralization in spatial computing can result in imperfect, yet useful knowledge.

The capability to query the topology of spatial regions is fundamental to today's centralized spatial computing systems, like spatial databases and GIS. By contrast, this paper explores decentralized algorithms for computing the topology of spatial regions in wireless sensor networks. The approach generates global topological information about regions, using only the local knowledge of nodes and their immediate network neighbors aggregated up through spatial boundary structures. Using three basic boundary structures (boundary nodes, boundary cycles, and boundary orientation), a family of decentralized algorithms is defined that can respond efficiently to snapshot queries about the topology of spatial regions, including containment and adjacency queries. The communication complexity of the algorithm is O(n) for realistic inputs. Empirical investigation of the performance of the approach, using simulation, also confirms the efficiency, scalability, and robustness of this approach.

This paper proposes an efficient, decentralized algorithm for determining the topological relationship between two regions monitored by a geosensor network. Many centralized algorithms already exist for this purpose (used for example in spatial databases). However, these algorithms are not suited to decentralized spatial computing environments, like geosensor networks, which must operate without global knowledge of the system state and without centralized control. Unlike many existing decentralized spatial algorithms, the proposed algorithm is also able to operate in the absence of information about a node's coordinate location. This makes the algorithm suitable for applications of geosensor networks where GPS or other positioning systems are unavailable or unreliable. The algorithm approach is founded on the well-known 4-intersection model, using in-network data aggregation and spatial filtering (involving nodes only at some region boundaries). This ensures only a relatively small proportion of the network is involved in computation, thus increasing efficiency. Our analysis shows that while the overall communication complexity of the algorithm is O(n), the load balancing is optimal leading to a constant O(1) communication complexity for individual nodes. This expectation is confirmed with empirical investigation using simulation, which demonstrates the practical efficiency of the algorithm.

This paper addresses the analysis and design of a decentralized algorithm for computing the area of spatial regions, like regions of high temperature or environmental pollution. The algorithm is suitable for application to distributed spatial monitoring systems, like geosensor networks. In such systems, conventional algorithms that rely on centralized control are acknowledged to present substantial constraints to network scalability. The algorithm presented in this paper requires no global knowledge, relying instead purely on a local knowledge about a node and its immediate one-hop neighbors. The paper then indicates avenues for further research, including relaxing strong assumptions about connectivity and region shape (e.g., simple region boundaries), and the application of the algorithm to related problems, such as computing region centroids.

The present paper examines whether the formal topological characterisation of spatial relations between moving geographic regions provides an adequate basis for the human conceptualisation of motion events for those regions. The paper focuses on gradual changes in topological relationships caused by continuous transformations of the regions (specifically, translations). Using a series of experiments, the conceptualisation and perception of conceptual neighborhoods is investigated. In particular, the role of conceptual neighborhoods in characterising motion events is scrutinised. The experiments employ a grouping paradigm and a custom‐made tool for presenting animated icons. The analysis examines whether paths through a conceptual neighborhood graph sufficiently characterise the conceptualisation of the movement of two regions. The results of the experiments show that changes in topological relations—as detailed by paths through a conceptual neighborhood graph—are not sufficient to characterise the cognitive conceptualisation of moving regions. The similarity ratings show clear effects of perceptually and conceptually induced groupings such as identity (which region is moving), reference (whether a larger or a smaller region is moving), and dynamics (whether both regions are moving at the same time).

This short paper presents early work on the development of a formal model of mobility and process in locationaware sensor networks. The formalism is based on Milner’s ð process calculus, which allows the modeling of mobile processes. The formal development is going hand-in-hand with development of a "process-relational" database system, with application to sensor networks. We argue that such a formal model of process complements research on movement simulation.

Recent technological advances in geosensor networks demand new models of distributed computation with dynamic spatial information. This paper presents a computational model of spatial change in dynamic regions (such as may be derived from discretizations of continuous fields) founded on embeddings of graphs in orientable surfaces. Continuous change, connectedness and regularity of dynamic regions are defined and local transition rules are used to constrain region evolution and enable more efficient inference of a region's state. The model provides a framework for the detection of global high‐level events based on local low‐level ‘snapshot’ spatiotemporal data. The approach has particular relevance to environmental monitoring with geosensor networks, where technological constraints make the detection of global behaviour from local conditions highly advantageous.

This paper presents a new technique for information fusion. Unlike most previous work on information fusion, this paper explores the use of instance‐level (extensional) information within the fusion process. This paper proposes an algorithm that can be used automatically to infer the schema‐level structure necessary for information fusion from instance‐level information. The approach is illustrated using the example of geospatial land‐cover data. The method is then extended to operate under uncertainty, such as in cases where the data are inaccurate or imprecise. The paper describes the implementation of the fusion method within a software prototype. Finally, the paper discusses several key topics for future research, including applications of this work to spatial‐data mining and the semantic web.

This paper presents a new method for assessment of error in digital vector geographic data, where the features represented can be modelled closely by fractal geometry. Using example hydrological data from Ordnance Survey of Great Britain maps at a range of scales, a resolution smaller than which the digital representation of the feature does not exhibit fractal characteristics can be calculated. It is proposed that this resolution reflects the minimum ground resolution of the map, which in turn can be related to the source map scale.