Recent Ph.D. Dissertations Available
In the Spring 2015 semester, several Ph.D. candidates successfully presented and defended their dissertations, including Liping Yang, Qinghan Liang, Francis Neville, and Lisa Walton. The Abstracts of these dissertations are below, and full texts are available for review in written form through the School of Computing and Information Science, and will soon be available for download at http://www.library.umaine.edu/theses/.
“Theories and Models of Indoor Space”
Liping Yang (Advisor: Dr. Kate Beard)
Although people’s daily lives are situated in both outdoor and indoor space, they actually spend most of their time in indoor environments. However, traditional geospatial science focuses mainly on outdoor space. Also, when we consider informatic assistance for the task of navigation, GPS has been indispensable for assisting navigation in outdoors. Up to now, navigation assistance for indoor space is much less well developed. But applications need to consider both outdoor and indoor spaces. Therefore, research on providing theories and models of indoor space is necessary.
This dissertation provides the development of theories and models representing the structure of indoor space and supporting navigation within it. A fundamental technique used is ontology development, which is the computerized specification of the meaning of terms used in specific domains. After investigating the similarities and differences between outdoor and indoor spaces in the context of navigation, the ontology of indoor space that can be integrated with outdoor space is developed. Four levels of ontologies are constructed based on the idea of modularization: upper ontology (the most general concepts), domain ontologies (concerned with the specific structure of the spaces), navigation task ontology, and application ontologies (specific user types and applications). We also work on making extensions to existing formal spatial models and developing related computational algorithms. A pure topological structure combinatorial map is extended to consider geometric information. A new formal concept dual map is proposed in order to make a correct dual connection between the structure of an indoor space and its navigation construct. Using the theories and algorithms developed in this research, we develop an approach to automatic construction of navigation graphs (underlying data structures that systems use to support human wayfinding) from building plans. The approach integrates topology, geometry, and semantics.
To demonstrate and evaluate the proposed navigation graph generation approach, a case study was developed using OpenStreetMap (OSM) based on Boardman Hall and its surroundings, which serves as a test-bed for the developed constructions and algorithms. A simple human subject experiment was also conducted to partially evaluate the case study. Ontologies are also evaluated by the developed case study. The results of the case study and human experiment showed that the generated navigation graph provides a collection of appropriately positioned navigation nodes, as well as appropriate connecting navigation edges.
“Towards The Continuous Spatio-Temporal Field Model for Sensor Data Streams”
Qinghan Liang (Advisor: Dr. Silvia Nittel)
Today, with the availability of inexpensive, wireless enabled sensor nodes, we encounter a massive amount of geo-referenced sensor streams, which are collected continuously, spatially dense, and in real-time. Continuous geographic phenomena such as pollen distribution, extreme weather events, a toxic chemical leak or radioactive fallout now can be observed live and needs to be analyzed in real-time. However, the high volume of continuous sensor data streams pushes the capabilities of traditional sensor data management beyond their limits. Over the last decade, data stream engines (DSE) have been introduced as data management technology, which provide real-time query support for applications with very high throughput rates. However, users are better supported if they would be able to interact with higher-level abstractions of the real-world phenomena, rather than analyzing observations based on individual measurement streams. Dealing with individual streams requires that users need to write code that not only copes with the real-time nature of streams but also that fact that the streams need to be integrated and analyzed, continuously, which is a non-trivial task.
This dissertation introduces the Stream Field Data Model, a DSE data model extension that is based on the concept of a field to represent continuous phenomena over space and time and is formally integrated with the relational and relational-based stream models. Using the high-level abstraction of fields provides an easy-to-use, flexible, mathematically defined and concise data model support for both sensor data streams as well as continuous phenomena. Furthermore, a Stream Query Language for the Field Stream Data Model is proposed with a novel set of stream query operators specifically for spatio-temporal fields. The approach is to lift relational operator to fields, and the semantics of this set of operators are discussed and formalized.
The feasibility of extending DSE for visualizing fields in near real-time based on 100,000 of streams has been investigated. This dissertation proposes and evaluates different strategies to optimize a pipelined stream operator framework to achieve near real-time spatial interpolation throughput, considering the memory footprint, runtime efficiency and interpolation quality.
“Spatiotemporal Wireless Sensor Network Field Approximation with Multilayer Perceptron Artificial Neural Network Models”
Francis Neville (Advisor: Dr. Silvia Nittel)
As sensors become increasingly compact and dependable in natural environments, spatially-distributed heterogeneous sensor network systems steadily become more pervasive. However, any environmental monitoring system must account for potential data loss due to a variety of natural and technological causes. Modeling a natural spatial region can be problematic due to spatial nonstationarities in environmental variables, and as particular regions may be subject to specific influences at different spatial scales. Relationships between processes within these regions are often ephemeral, so models designed to represent them cannot remain static. Integrating temporal factors into this model engenders further complexity.
This dissertation evaluates the use of multilayer perceptron neural network models in the context of sensor networks as a possible solution to many of these problems given their data-driven nature, their representational flexibility and straightforward fitting process. The relative importance of parameters is determined via an adaptive backpropagation training process, which converges to a best-fit model for sensing platforms to validate collected data or approximate missing readings. As conditions evolve over time such that the model can no longer adapt to changes, new models are trained to replace the old.
We demonstrate accuracy results for the MLP generally on par with those of spatial kriging, but able to integrate additional physical and temporal parameters, enabling its application to any region with a collection of available data streams. Potential uses of this model might be not only to approximate missing data in the sensor field, but also to flag potentially incorrect, unusual or atypical data returned by the sensor network. Given the potential for spatial heterogeneity in a monitored phenomenon, this dissertation further explores the benefits of partitioning a space and applying individual MLP models to these partitions. A system of neural models using both spatial and temporal parameters can be envisioned such that a spatiotemporal space partitioned by k-means is modeled by k neural models with internal weightings varying individually according to the dominant processes within the assigned region of each. Evaluated on simulated and real data on surface currents of the Gulf of Maine, partitioned models show significant improved results over single global models.
“Bigraphs for Goal-directed Indoor Navigation”
Lisa Walton (Advisor: Michael Worboys)
Formal models of indoor space for reasoning about pedestrian navigation tasks should capture key static and dynamic properties and relationships between agents and indoor spaces, and provide an effective framework for reasoning about change. Of particular interest are changes in properties or relationships that affect an agent’s ability to carry out a goal directed navigation task. We focus on changes that occur in response to key indoor events, especially those that modify locality or connectivity relationships between agents and physical or functional spaces. This thesis presents a framework for formally representing indoor environments, the events that occur in them, and their effects on the topological properties and relationships between indoor spaces and agents. The main goal is to provide a computational foundation for qualitative spatiotemporal reasoning about indoor pedestrian navigation by modeling the effects of key indoor events on agent behaviors and relationships in indoor environments. To this end, we capture important aspects of agent wayfinding behaviors in the context of spatial image schema, which are abstractions of spatiotemporal perceptual patterns (e.g., an agent can perceive a room as a CONTAINER that she can move IN and OUT of), and spatial affordances, which are objectively measurable actions an agent can take given their current capabilities and environment (e.g., a stairway affords an ambulatory adult the ability to move between floors). The framework has three major components: (i) an indoor space ontology, (ii) an indoor bigraph model, and (iii) an indoor event calculus.
The indoor space ontology formally captures the typology of agents, objects, places and events that are utilized in the indoor bigraph model and event calculus. The indoor bigraph model provides formal algebraic specifications of indoor environments that independently represent agent and place locality (e.g., building hierarchies) and connectivity (e.g., path based navigation graphs). A typed indoor event calculus provides a logic-based formalism for representing the effects of indoor space events on key indoor relationships. By defining indoor fluents IN and LINKED with associated events INTO, LINK, and UNLINK and appropriate effect axioms we construct narratives about indoor navigation tasks as potential sequences of events and their consequences in indoor environments. For example, given an agent’s starting situation and a particular goal-directed navigation task we determine potential sequences of events that would lead to satisfying her goal (e.g., if a fire occurs in the building, how can she straightforwardly reach an exit?). Next, we show that the indoor bigraph model together with the indoor event calculus can be used to describe scenes and narratives with incomplete information, and that bigraph composition and joining operations can be used to adjust the granularity of scenes and to compose partial scenes to provide additional context. Finally we evaluate the framework by implementing the indoor event calculus in an abduction planner and running case studies based on human subject experiments designed for a companion study (NSF grant IIS-0916219) to determine if effective goal-directed navigation plans can be derived for an indoor environment. The goal is to evaluate the thesis framework by comparing the planning narratives produced by reasoning in the calculus to actual navigation strategies produced by humans or software agents in the experimental settings.