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
'levelindependent' 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 nonhierarchical 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 (nonhierarchical) 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 minimumcost 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 roadsegments. 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 minimumcost 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
highlevel 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, roadsegments, 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.
