Two PhDs Conferred by SCIS
The School of Information and Computing Science is proud to announce that on Saturday, May 14th, the school will be conferring the title of PhD to two students. Both Hengshan Li and Matthew Dube have worked very diligently on their dissertations, and have been hired to exciting new jobs after graduation. The following is a description of their dissertation research and future plans.
Evaluation of multi-level cognitive maps for supporting between-floor spatial behavior in complex indoor environments
By Hengshan Li
Advisor: Dr, Nicholas A. Giudice, Associate Professor in Spatial Informatics, School of Computing and Information Science
Abstract:
People often become disoriented when navigating in complex, multi-level buildings. To efficiently find destinations located on different floors, navigators must refer to a globally coherent mental representation of the multi-level environment, which is termed a multi-level cognitive map. However, there is a surprising dearth of research into underlying theories of why integrating multi-level spatial knowledge into a multi-level cognitive map is so challenging and error-prone for humans. This overarching problem is the core motivation of this dissertation.
This dissertation addresses this vexing problem in a two-pronged approach combining study of both basic and applied research questions. Of theoretical interest, we investigate questions about how multi-level built environments are learned and structured in memory. The concept of multi-level cognitive maps and a framework of multi-level cognitive map development are provided. We then conducted a set of empirical experiments to evaluate the effects of several environmental factors on users’ development of multi-level cognitive maps. The findings of these studies provide important design guidelines that can be used by architects and help to better understand the research question of why people get lost in buildings. Related to application, we investigate questions about how to design user-friendly visualization interfaces that augment users’ capability to form multi-level cognitive maps. An important finding of this dissertation is that increasing visual access with an X-ray-like visualization interface is effective for overcoming the disadvantage of limited visual access in built environments and assists the development of multi-level cognitive maps. These findings provide important human-computer interaction (HCI) guidelines for visualization techniques to be used in future indoor navigation systems.
In sum, this dissertation adopts an interdisciplinary approach, combining theories from the fields of spatial cognition, information visualization, and HCI, addressing a long-standing and ubiquitous problem faced by anyone who navigates indoors: why do people get lost inside multi-level buildings. Results provide both theoretical and applied levels of knowledge generation and explanation, as well as contribute to the growing field of real-time indoor navigation systems.
After UMaine, Hengshan will join in Singapore-ETH Centre, Future Cities Laboratory. He will take part in a research project aiming to understand the perceptual and cognitive processes underlying pedestrian movement and wayfinding behavior, provide design interventions informed by empirical research and simulations, and develop simulations for visualizing and validating empirical results and proposed design solutions.
Algebraic Refinements of Direction Relations Through Topological Augmentation
By Matthew P. Dube
Advisor: Dr. Max J. Egenhofer, Professor and Directior, School of Computing and Information Science
Abstract:
The world of spatial information has been painstakingly studied over the past forty years and, for the attainment of compact and meaningful systems, split into a triumvirate of domains for qualitative spatial reasoning: topology, direction, and distance. As advances in computation have led to quicker computation, the need for smaller, cognitively held systems is reduced, opening the door for larger reasoning systems that violate Occam’s Razor.
This dissertation attempts to bring separated concepts of qualitative spatial reasoning together by using the concept of spatial partitions. Partitions are mutually exclusive sets that exhaustively cover an embedding space. Qualitative direction relations over regions are currently constructed from these partitions and are based on intersection models. In this dissertation, topological relations are used to refine the qualitative direction relations over regions currently in the literature and graph theoretic definitions and theorems are presented to apply these concepts to arbitrary spatial partitions of co-dimension 0 to their embedding space.
This combination is called topological augmentation. Rather than computing binary set intersections between a figure object and ground tiling structure, topological augmentation expands this approach by computing a topological set intersection resulting in a topological relation from the region-region relations, providing additional insights into the qualitative extent of an object. Such an approach allows for a reasoning system with over 3,000 relations, relations that can be applied to particular semantic definitions based upon their context.
With the creation of such a verbose system, the interplay between direction and topology is explored and refined in a novel way by integrating the two separate forms of information before the reasoning task is attempted. While previous research has attempted combinations of direction and topology, the more verbose system presented in this work provides a transfer between direction and topology that is reduced in cardinality, a large benefit in the world of volunteered geographic information. A similar effect is also shown in the computation of converse relations and compositions using the verbose system as a guideline, moving the standard of composition in areal direction relations from the domain of weak composition to that of strong composition.
The key benefit of this approach is in the aspect of computing the composition of direction relation matrices. While a decade of research has attempted to solidify this result, numerous attempts have tried and failed to produce a systematic and verifiable composition for a given pair of objects, known as the strong composition, instead being successful only in the computation of the weak composition, that which can occur for at least one element of the set represented by the combination of objects. Through the use of topological augmentation, the strong composition of direction relation matrices is attained. Patterns in the composition are identified based on the coincidence of tile boundaries with object boundaries, a key insight that can produce crisper compositions at a minimal cost in complexity. This particular cost of complexity (from binary to topological) also serves the purpose of integrating direction relations into commercial GISs based on topological means through reverse engineering, given that the interface for computing topological relations and querying over them already exists.
Finally, composition is analyzed relative to the properties of a relation algebra, a fundamental question in the realm of artificial intelligence. It is demonstrated that the composition and converse properties of the direction relation matrix (with or without topological augmentation) do not produce a proper involution systematically, and thus the spatial representation cannot form a relation algebra. Many relation pairs as a composition are involutable, but not all. These properties are based on symmetry within the space relative to minimum bounding rectangle relations. The nature of involution in this case motivates the choices of particular forms of a relation between pairs of objects, one of the first scenarios in spatial literature where the choice of the order of the relation matters for a purpose other than a cosmetic one.
Future work is proposed to integrate direction relations into commercial GISs and to further explore the remaining properties of relation algebra relative to partition-based direction relations. Since the current gold standard is not involutable, a research agenda is proposed to determine whether or not a worthwhile direction-based information system can be developed that is endowed with universal involution, thus mitigating the effects of choices of relational order.
After UMaine, Matthew will join the faculty at the University of Maine at Augusta to become an Assistant Professor of Computer and Information Systems.
Congratulations to Hengshan and Matthew, we look forward to your impacts on your fields!
####