Hierarchical Graphs as Organisational Principle and Spatial Model Applied to Pedestrian Indoor Navigation

In this thesis, hierarchical graphs are investigated from two
different angles – as a general modelling principle for
(geo)spatial networks and as a practical means to enhance
navigation in buildings. The topics addressed are of interest from
a multi-disciplinary point of view, ranging from Computer Science
in general over Artificial Intelligence and Computational Geometry
in particular to other fields such as Geographic Information
Science. Some hierarchical graph models have been previously
proposed by the research community, e.g. to cope with the massive
size of road networks, or as a conceptual model for human
wayfinding. However, there has not yet been a comprehensive,
systematic approach for modelling spatial networks with
hierarchical graphs. One particular problem is the gap between
conceptual models and models which can be readily used in practice.
Geospatial data is commonly modelled - if at all - only as a flat
graph. Therefore, from a practical point of view, it is important
to address the automatic construction of a graph hierarchy based on
the predominant data models. The work presented deals with this
problem: an automated method for construction is introduced and
explained. A particular contribution of my thesis is the
proposition to use hierarchical graphs as the basis for an
extensible, flexible architecture for modelling various (geo)spatial
networks. The proposed approach complements classical graph models
very well in the sense that their expressiveness is extended:
various graphs originating from different sources can be integrated
into a comprehensive, multi-level model. This more sophisticated
kind of architecture allows for extending navigation services
beyond the borders of one single spatial network to a collection of
heterogeneous networks, thus establishing a meta-navigation
service. Another point of discussion is the impact of the hierarchy
and distribution on graph algorithms. They have to be adapted to
properly operate on multi-level hierarchies. By investigating
indoor navigation problems in particular, the guiding principles
are demonstrated for modelling networks at multiple levels of
detail. Complex environments like large public buildings are
ideally suited to demonstrate the versatile use of hierarchical
graphs and thus to highlight the benefits of the hierarchical
approach. Starting from a collection of floor plans, I have
developed a systematic method for constructing a multi-level graph
hierarchy. The nature of indoor environments, especially their
inherent diversity, poses an additional challenge: among others,
one must deal with complex, irregular, and/or three-dimensional
features. The proposed method is also motivated by practical
considerations, such as not only finding shortest/fastest paths
across rooms and floors, but also by providing descriptions for
these paths which are easily understood by people. Beyond this, two
novel aspects of using a hierarchy are discussed: one as an
informed heuristic exploiting the specific characteristics of indoor
environments in order to enhance classical, general-purpose graph
search techniques. At the same time, as a convenient by- product of
this method, clusters such as sections and wings can be detected.
The other reason is to better deal with irregular, complex-shaped
regions in a way that instructions can also be provided for these
spaces. Previous approaches have not considered this problem. In
summary, the main results of this work are: • hierarchical graphs
are introduced as a general spatial data infrastructure. In
particular, this architecture allows us to integrate different
spatial networks originating from different sources. A small but
useful set of operations is proposed for integrating these
networks. In order to work in a hierarchical model, classical graph
algorithms are generalised. This finding also has implications on
the possible integration of separate navigation services and
systems; • a novel set of core data structures and algorithms have
been devised for modelling indoor environments. They cater to the
unique characteristics of these environments and can be specifically
used to provide enhanced navigation in buildings. Tested on models
of several real buildings from our university, some preliminary but
promising results were gained from a prototypical implementation
and its application on the models.