Research Group Geoinformation


Home | Research | Publications | Download | Projects | Teaching | Staff



... to the Cartography Group

Car Adrijana

General Principles of Hierarchical Spatial Reasoning

by Adrijana Car
Proposal

This study proposes the general principles of hierarchical spatial reasoning. This theme belongs to the spatial information theory as it investigates hierarchical structurization of space and its use for reasoning.
Humans are able to organize and structure space in various ways to simplify spatial reasoning. There is evidence that humans use here and in other similar cases hierarchical structures, which they impose on space to reduce the cognitive load and to improve performance. The experimental observation leads to a framework of hierarchical reasoning, but the models are not sufficiently detailed to allow programming in a GIS. The impediment is an inadequate, insufficient, or not implementable formalization of human's representation of spatial knowledge and research in formalizing spatial hierarchical reasoning is necessary. We propose a conceptual model of hierarchy of space based on cognitive approach, introduce an efficient hierarchical algorithm (in that case for wayfinding), and explain the underlying heuristics.
Hierarchical spatial reasoning is any reasoning process, which applies hierarchy either to subdivide the task or space. A strategy of breaking the problem into manageable subproblems seems reasonable in the context of spatial memory. To understand how spatial hierarchies are formed and used is one of the most important questions in spatial reasoning research.
Hierarchical spatial reasoning is just one particular case of hierarchical data structures and algorithms (e.g., tree walk or merge sort). According to the human experience conceptual hierarchization of space has proven useful as a spatial concept and as such is transferred metaphorically to other domains and used generally.
Hierarchical structuring can be used to refine the general problem to a more particular task. This leads to a hierarchical structure, where objects of a different type occur on different levels. The object considered in this study is 'level-independent' hierarchical structure, where objects and operations are the same on each level and the difference is only in resolution or detail.
The approach to the problem of representing knowledge needed for hierarchical spatial reasoning in wayfinding is based on following cognitive assumptions:
humans may divide a large road network hierarchically,
the amount of detail increases form top to the lowest level,
the path found with hierarchical reasoning is (close to) optimal (if hierarchical levels are formed according to expected travel speed), and
wayfinding occurs in small subnetworks.

Deducing general principles from this set of observations of a particular task is objective of this study in order to make them applicable generally.
Given a spatial algorithm to solve a spatial reasoning problem, the goal is to hierarchically subdivide the space and in consequence the data set the algorithm is operating on, such that the same result is achieved, but processing is more economical, i.e., it uses smaller subsets of data. For each method of hierarchical spatial reasoning the following three elements must be given:
a hierarchical structure, describing how the levels are composed and related,
rules how to use this structure and how reasoning progresses over the levels, and
comparisons of the results for correctness of the results of the hierarchical processing with the results achieved with a non-hierarchical algorithm, and also the performance improvement.
These are the general principles of hierarchical spatial reasoning.


The particular application, studied to gain further insight into the general problem, is wayfinding in large road networks. A conceptual model of hierarchically organized road networks for wayfinding the road network is a simple topological network containing only necessary nodes and connections among them to find the way by ignoring detailed information.
The example of finding the fastest path in a street network can be abstracted to the mathematical problem of finding the fastest path in a weighted graph, i.e., a graph where each edge is weighted with the expected travel time. Algorithms to find this path of least cost are well known for a regular (non-hierarchical) graph. On the other hand, this is a problem where sufficient evidence for hierarchical structure in human performance is available. The abstract, formal objective is to improve this method by introducing a hierarchical structure for the space and to deduce the general principles of this transformation.
Structuring knowledge hierarchically incurs a cost and thus a larger gain in performance must be achieved to make it worth. Performance must consider both computational operations and storage requirements for data. The hierarchical algorithm will increase performance by excluding some of the input data from consideration. It remains thus to demonstrate that the results are correct in the sense of the same as the 'flat' algorithm will produce when using the full data set. There are important cases, where a hierarchical algorithm is the only solution: if the full data set is not available, but all the data that the hierarchical algorithm needs can be provided. Wayfinding is such a case.
We propose an algorithm for determining the minimum-cost path from a node A to a node B in a hierarchically structured graph. It is based on a 'flat' algorithm enriched by heuristics about how to deal with a hierarchical structure. Given Ai and Bj , where i and j are the highest levels in which A and B are contained, the hierarchical algorithm can be applied to the network at the highest level in which A and B are both contained (min(i, j)). This network is smaller, thus the algorithm is faster (see Fig.1).
Figure 1: Hierarchical algorithm applied to determine the path between Ai and Bj.
Following we define the ontology for a nonhierarchical and hierarchical case. Ontology is an abstracted, idealized model of reality containing only those objects, relations among them, and rules that govern them, which are of interest in a particular reasoning system being designed [Davis, 1990 #136, pp.6].
Ontology for a nonhierarchical case contains places and road-segments. A place is a distinctive location where humans make decisions about the further process of wayfinding. A road segment connects two places. Attributes like travel time or length are assigned to it.
Ontology for the hierarchical case must contain the ontology of the nonhierarchical case (i.e., places and road segments), so that the algorithm for the flat case can be applied in each graph independently. Thus it contains places, road segments, meshes, and hierarchical levels. The hierarchical structure is built by selecting a set of connected edges in the graph, and have them form a connected subgraph representing the next higher level. The process can be repeatedly applied to form a multilevel hierarchy. The selection is based on the classification of the roads according to levels like interstate highway, freeway, or local road, etc. Levels are subdivided into subnetworks: each subnetwork, a mesh, is bounded by edges of the next higher level.
The use of hierarchy is actually a method of abstraction. From the driver's point of view, wayfinding occurs in small subnetworks, i.e., on hierarchical levels. When finding the fastest path (i.e., the minimum-cost path considering, for example, the travel time), a driver will mostly try to use the highest possible level of the entire network (e.g., an interstate highway). When planning a trip, he tries to find the nearest entry node to the next higher level from the start point, and the nearest exit node to the goal point. The entry and exit must be on the same higher level. The fastest path between them is then found considering only the nodes belonging to this subgraph, i.e., hierarchy level. The other exit/entry points "disappear" as well as the lower subnetworks nested within the meshes of the next higher level.
In a two level network the path determined with the algorithm is equally fast if traveling on the higher level is twice as fast then on the lower level. Ratios of 1.5 to 2 for the travel speed between levels are quite realistic, and translate to say 50km/h on local roads, 75km/h on regular roads, and 120km/h on highways.
Current state of the project and the forthcoming work

The formalization mechanism in this work uses algebraic specifications as a high-level formal language to derive a formal model from the conceptual model. The theory behind algebraic specifications has been developed and used in software design. There are only few applications to generic geometric problems. We have defined the object types relevant (e.g., places, road-segments, meshes, and levels) together with their properties and operations defined with the set of axioms. The method models the hierarchy of space (a large road network where wayfinding takes place), which is complementary to the methods of modeling a hierarchy of tasks. The computational model of the cognitive model of large road networks will be used for different experiments (simulations and case studies) in order to prove the validity of the model. This project is ongoing research and there are no final results yet. The ontology has been defined for both flat and hierarchical case. Hierarchical structure is imposed on space to allow efficient spatial reasoning. The formalization is partly done. We expect the applied methods and results to provide the theory to heuristics currently proposed, and, therefore, its applicability in cases where large data sets need to be processed: e.g., in Car Navigation Systems to achieve more effective wayfinding in very large road networks using hierarchical structure.
Another, more general case of hierarchical structurization of space to look closer at, is Christaller's space. A hierarchical structure, which is the same on each level, uses boundaries that do not exist in nature. Formalization of underlying, already existing Christaller's model according to the posited general principles of hierarchical spatial reasoning would be another suitable case study.


Powered by CMSimple