Formal definition of a user-adaptive and length-optimal routing graph for complex indoor environments

Car routing solutions are omnipresent and solutions for pedestrians also exist. Furthermore, public or commercial buildings are getting bigger and the complexity of their internal structure has increased. Consequently, the need for indoor routing solutions has emerged. Some prototypes are available, but they still lack semantically-enriched modelling (e.g., access constraints, labels, etc.) and are not suitable for providing user-adaptive length-optimal routing in complex buildings. Previous approaches consider simple rooms, concave rooms, and corridors, but important characteristics such as distinct areas in huge rooms and solid obstacles inside rooms are not considered at all, although such details can increase navigation accuracy. By formally defining a weighted indoor routing graph, it is possible to create a detailed and user-adaptive model for route computation. The defined graph also contains semantic information such as room labels, door accessibility constraints, etc. Furthermore, one-way paths inside buildings are considered, as well as three-dimensional building parts, e.g., elevators or stairways. A hierarchical structure is also possible with the presented graph model.


Introduction
With the technological improvement of mobile devices, today's navigation systems offer a variety of functionalities for nearly any kind of requirement, but they are mainly designed for outdoor environments and hardly offer any solutions for indoor routing. By comparing indoor and outdoor space, it is evident that there are objects such as rooms or distinct areas in huge halls which do not have a counterpart in the outdoor street network (e.g., corridors can be compared to streets etc.), resulting in a complicated path network construction process. Nevertheless, there is an increasing need for specialized indoor solutions. Public buildings such as airports or shopping malls have become bigger and their internal structures have become more complex, resulting in a very complicated overall structure so that even familiar persons are likely to get lost when searching for a particular room or place. If the person is unfamiliar with the inner building structure, there is an even stronger need for proper guidance. [1,2] The field of application for indoor routing is very broad and there are many diverse application scenarios, e.g., emergency routing or personal routing at the airport. [3] Routing a person through space can be generalized to finding the shortest path between two nodes in a network. Well proven algorithms such as Dijkstra, [4] A* [5] and various specialized algorithms and heuristics, can compute shortest routes, but the creation of a network model is required beforehand. Several efforts (cf. next chapter) have been made in creating indoor networks, but existing approaches lack details and can only provide coarse routes without considering complex interior structures. Furthermore, none of the existing approaches tries to formally define a graph model for indoor environments, although existing approaches utilize graphs.
The main contribution of this paper is the formal definition of an improved indoor routing graph that allows route computation in complex indoor environments. The presented graph allows length-optimal routing based on the (complex) geometry of indoor spaces, whereby computations can be user-adaptive. The graph elements are manually extracted from floor plans and additional semantic information is collected for different functions of the graph. By applying a shortest path algorithm on the graph, the shortest route between two distinct points can be obtained. Detailed routing information, e.g., travel distances, etc., can also be obtained from the graph segments.

Related work
According to Pradhan [6] and Brummit & Shafer [7] indoor space models can be separated into two different classes. The so called topological/semantic class contains models relying on abstract descriptions of spatial relations (e.g., "Office X is near the Elevator"). In contrast, so called metrics models rely on concrete measurements of distances and angles (e.g., "The distance from Office X to Office Y is 12.3 meters"). Early examples for such topological models are presented by Raubal & Worboys [8] or Brummit & Shafer, [7] but they all lack geometric aspects, thus they are not usable for computing optimal routes and predicting distances.
In contrast, Gilliéron & Bertrand [9] invented an indoor space representation model based on CAD files. The files only contain metric information, i.e., manual enrichment with semantic data is required. In doing so, information about locations, shapes and topological relations of spatial entities (e.g., rooms, corri-dors, hallways, etc.) can be received. Afterwards all available data are used to derivate a so called link/node view of the building network. The authors decided to model each room as one node and corridors as a huge link with connection nodes. However, this procedure rather provides a very abstract view on the topology than a detailed perspective on the geometry. Important constraints and details such as the position of doors or obstacles inside rooms are not considered at all. A hybrid spatial model for indoor environments, which consists of hierarchically structured paths and optional semantic information, is presented by Lorenz et al. [10] They propose a direct mapping for small building instances (e.g., small rooms, corridors) to nodes in the graph. Furthermore, pathways between rooms are described as links. For gangways, they propose decomposing cells into several non-overlapping disjoint cells (cf. Fig. 1). This approach has been extended, so that also rooms with a concave shape can be modeled. [11] A three-dimensional navigable data model is described by Lee. [12] The network model is deviated via Poincaré duality combined with a graph-theoretic framework, a hierarchical representation schema and a straight-medial axis transformation. [13,14] The model contains two dual graphs, where one contains topologic information and the other one geometric aspects. Thereby, the separation into two different graphs is similar to the ISO standard 19107:2003 for describing the spatial characteristics of geographic features. [15] Other modelling frameworks following this standard are described by Becker et al. [16] and Becker et al. [17] Moreover, the latter one is also utilized for defining the format IndoorML, a LOD4 CityGML based format for exchanging interior models. [18] Also the models presented by Lee & Zlatanova [19] or Kolbe et al. [20] are based on. [12] A 3D-GIS based framework that supports BIM for topologic analysis-oriented indoor navigation is also proposed. [21] The BIM file covers geometric and semantic information and is utilized for creating the network model. They propose to separate floor elements according to their functional aspects, but they do not provide detailed information on their graph model. Yuan & Schneider proposed an indoor model that produces optimal non-circuitous routes. [22] They consider all building parts as cells and separate those into simple cells, complex cells, open cells, and connectors. Furthermore, their mapping, i.e., relationship between doors/rooms to nodes/edges, is different to other models. Doors are mapped to nodes and the rooms are mapped to edges. This approach is based on the assumption that doors, i.e., entrances of rooms, are the destination of the user and furthermore, this allows the construction of length-dependent routes. Additionally the authors describe how to connect two doors in a concave shaped room (cf. Fig. 2).
They define a direct path graph (DPG) G := (V,E) "which reflects all possible path constructions in a given indoor space scenario". [22] However, this is a coarse formal definition of a routing graph. Also, the computation of length-optimal routes comes at the Fig.2 Various directly connected access points in a concave room [22] cost of a negative impact on the runtime. The complexity of routing algorithms strongly depends on the amount of graph elements. By following their approach and trying to model a long office corridor, this results in n nodes (n is the amount of doors) and several links between all these nodes. The amount of required links (arl) can be calculated according to Eq.(1): For an exemplary corridor with 20 offices, this approach leads to 20 nodes and 190 edges. Extending this to a building with 7 levels, two elevators and one building entrance, such a graph would require 1.800 graph elements for a simple building structure, which is inacceptable for performance and storage and furthermore similar models get along with less graph elements (as will be described later).
In conclusion, it needs to be emphasized that all existing models do not discuss how to deal with obstacles or walls inside a room. The direct connection between two doors might not be navigable, due to physical constraints (cf. Fig. 3), but existing models are not able to capture this. Furthermore, existing models are not capable of considering different areas inside rooms (e.g., smoking area and check-in counter in an airport entrance hall), because rooms are modeled as single elements. Moreover, existing models assume that path segments do not have directions. This might be true for most buildings, but there are some scenarios (e.g., airport) where the consideration of one-way paths inside a building is required. Also, none of the existing approaches tries to formally define the utilized graphs. That is, existing approaches use a graph that has never been formally defined beforehand.

Fig.3 A convex shaped room with physical constraint inside 2 Relevant building components for indoor routing
Routing describes the process of leading users from a starting point to a destination point in an optimal manner (according to distinct requirements). Such routes are often obtained by applying a routing algorithm onto a graph. In this chapter, we discuss which inner building components are relevant for routing, and thus need to be integrated in an indoor routing model. Special constraints such as obstacles or one-way paths are also discussed. In general, small rooms (e.g., offices, kitchens, etc.) are modelled as described by Yuan & Schneider [22] (cf. Fig.4). We share the opinion that doors are the first targets of users, but nevertheless navigation inside rooms (as will be refined later) is also required. In contrast to previous approaches, modelling of corridors is also discussed.

Corridors
From a geometric point of view, corridors are a special type of rectangular rooms in which two opposing sides are short (i.e., just a few meters) and the other two sides are way much longer (i.e., 0 < long_side/short_side 1 ). Big corridors (i.e., all sides are several meters long), need to be rather considered as a hall than a corridor. In addition, from a semantic point of view, a corridor is often not a destination node, but just a connector node. There are two basic possibilities for modelling a corridor: [23] just one node per corridor (not applicable) or by utilizing an adjusting line in the centre of the corridor. In contrast, Yuan & Schneider [22] proposed to model a corridor in the same manner as a room (cf. Fig.4). So practically there are two different methodologies for corridors, but which one is more appropriate with respect to computation performance and accuracy. When considering a corridor with 14 doors (quite common) this results in 105 graph elements for any kind of corridor layout, when modelling a corridor in the same way as a room. In contrast for the centreline approach, the total amount of required nodes depends on the corridor layout (i.e., the exact location of doors) and the amount of required edges is always #edges = #nodes -1. One possible corridor layout is that all doors are located at one side of the corridor (cf. Fig.5 (a)) leading to #nodes = 2·|n| for n doors and to 55 graph elements for exemplary 14 doors. Another possible layout is that two doors are at every short side and the rest of the doors are at one single side (cf. Fig.5 (b)). In general this leads to #nodes = 2·|n| -2 and for the example to a total of 51 graph elements. A third possible corridor layout (depicted in Fig.5 (c)) is that the half amount of doors is on one long side and the others on the opposed side with the constraint that there is no pair of opposed doors, resulting in #nodes = 2·|n|, thus in 28 nodes for the exemplary floor. Another layout is illustrated in Fig.5 (d), whereby opposed doors are allowed. For the exemplary corridor, the route graph has 21 nodes. Generally, such a layout requires #nodes = 3/2·|n|. A last possible layout (Fig.5 (e)) has the characteristics that there is one door on every small corridor side and the remaining ones are equally distributed on both long sides, whereby pairs of opposed doors are allowed, leading to #nodes = 3/2·|n| -1 (39 graph elements for the example).
Of course there are other corridor layouts possible, but the described ones represent special cases. Layout a (cf. Fig.5 (a)) and layout e (cf. Fig.5 (e)) represent the upper and lower borders for the complexity and the amount of required graph elements (arge) can be approximated as follows: Additionally, Table 1 provides an overview for different door amounts. It depicts, that the centreline approach might need less elements for more than four doors per corridor, but it definitely is advantageous for more than six doors in the corridor (which can be found very often in public or commercial buildings). Trying to reduce the complexity of the route graph, the centreline approach is preferable. By adding geometric information to the model (as will be described later), it is possible to analyze travel distances and provide nearly length-optimal routes. However, distance calculations also depend on the model itself, i.e., investigations on the overhead (additional travel distance) are required. A 50 m long and 2 m wide floor with 4 doors (depicted in Fig.6 (a)) serves as an example. The iNav approach [22] proposes an edge between every possible pair of nodes ( Fig.6  (b)) and the centreline approach adds additional nodes in the middle of the corridor (Fig.6 (c)). Table 2 shows the different travel distances and compares the two approaches. Thereby it becomes obvious that, the more distant two doors are, the lesser is the overhead of travel distance. Therefore, e.g., for d 3 → d 4 the overhead is 25.7%, whereas it is 2.0% for d 1 → d 3 . Furthermore, there is no additional overhead for opposed doors (Table 2). In general, the resulting overhead can be approximated by Ω (0) ≤ overhead ≤ Ο(b) whereby the parameter b is the width of the corridor. Concluding this discussion, it becomes apparent that the centreline approach is advantageous because it reduces the amount of graph elements, and thus is likely to increase performance. The additional travel distance is rather fractional and has no serious impact on the route. Furthermore, the centreline model is more realistic because a user is likely to take a step in the middle of the corridor and then walk along it, rather than directly walking next to the wall.

Different areas and obstacles in halls and big rooms
Previous indoor model approaches do not present any work on big rooms (i.e., halls) with complex inner shapes (e.g., solid walls in the inner room). The main problem of such rooms is that the intended route through a room cannot be taken due to this physical constraint or the next target point cannot be seen (cf. Fig.3), i.e., additional instructions are required for proper guidance. By manually adding additional nodes, it is possible to securely bypass such obstacles and computed routes will be more length-optimal (cf. Fig.7).

Fig.7 Routing graph for bypassing obstacles inside rooms
How many and where nodes need to be added, is a question of the accuracy of navigation and not related to the routing itself. The procedure is not limited to fixed, solid obstacles, and can also be applied to other obstacles affecting the route (e.g., consideration of desks or plants for navigating visually impaired). In the future it is likely that this procedure can be achieved (semi)-automatically, by utilizing intelligent space-partitioning methodologies.
Another factor not considered in previous research approaches is the consideration of special areas inside rooms. All the previous models abstract a room as a single graph element, not permitting a detailed separation of a room into different areas. For example the entrance hall of an airport is a huge room (hall) with different areas such as check-in counters or smoking areas etc., and existing solutions do not model that kind of information (i.e., routing a user from the entrance to the check-in counter is not possible). Another example is a huge exhibition hall with many different booths inside, where the previous approaches model this hall as one single graph element.

Motivated by such examples, it is advisable to have additional nodes for every point of interest and to
connect them with existing nodes. Therefore, e.g., in Fig.8 (a) the route graph for an airport entrance hall is modelled and in Fig.8 (b) the route graph of an exhibition hall is depicted. The decomposition of rooms into different areas can be further refined in a hierarchical manner (cf. Hierarchical outdoor wayfinding [24] ). In doing so, route instructions such as "From the check-in counter go to departure A and then to gate 22" can be realized.

Considering the possibility of one-way paths inside a building
In the street network, one-way roads are very common and therefore routing models are often realized as directed graphs. In contrast, most "ways" or doors in indoor-environments do not have a distinct direction (e.g., people can walk through a corridor in both directions). Existing approaches for indoor routing utilize non-directed graphs. However, they do not consider the possibility of one-way paths at all. There are few scenarios, e.g., escalators or passport checks at the airport, which require the consideration of one-way paths or doors. Since one-way paths in buildings are rare, it is proposed to realize an undi-rected graph with additional semantic information, reducing the amount of graph elements significantly.

Vertical building parts
Most buildings have several levels that are connected via stairways, elevators, etc., and it needs to be discussed how such vertical connections should be treated. Modeling an elevator is quite intuitive: all elevator doors are already included in the network model, because they are integrated when individual floors are modeled. Furthermore, there are only edges required for directly adjacent doors, i.e., door1 is connected with door2, door2 is connected with door3 etc., but there is no edge between door1 and door3. That is, an elevator connecting n levels can be modeled with n nodes and (n-1) edges (cf. Fig.9 (a)). Modeling staircases is achieved in a similar way, however it might be possible that edges are not congruent (from a bird-perspective). This is the case when stairway exits are on opposite sides of the stairway (cf. Fig.9 (b)). However, the modeling procedure is the same.
Modeling escalators is also intuitive: the start and the end of an escalator are modeled as a node inside rooms, and furthermore these nodes are connected with an edge. Since escalators cannot be strictly vertical, the edge is also not strictly vertical, but strictly horizontal edges (cf. moving walkway) are possible. Escalators are one-way and therefore additional information on the direction is required.

Formal definition of the weighted indoor routing graph
The most efficient way to find routes in a graph is applying a shortest path algorithm to the graph. Therefore, a graph for supporting shortest path algorithms has been developed.
Definition 1: A weighted indoor routing graph is a labelled graph that describes all possible path constructions in an indoor environment and furthermore contains semantic information about the different parts of the indoor environment. The WIRG is defined via the 7-tupel WIRG := (N, E, f, g, h, i, j), where N (nodes) is a set of relevant points, i.e., access points or doors or distinct areas in the indoor space, and E (edges) is a set of edges, i.e., connections between relevant points in the indoor space. Additionally, f, g, h, i and j are mathematical functions which are responsible for labelling, weight distribution, one-way definition, localization, access restrictions, and other semantic information. For providing the above mentioned functions and for making the graph adaptable to different user requirements, the sets L, TC, R, ID and SI are defined below. The set SI (semantic information) is a set of additionally available semantic information, whereby |SI|>1.
After defining different sets which are required for the model, the functions f, g, h, i and j are defined. The function f is responsible for labelling different edges in the route graph.

Definition 3:
The mathematic function f is defined as f: N → L describing a monadic, surjective and non-injective function from the set of all nodes N to the set of all labels L. That is, for each l ∈ L there is a corresponding n ∈ N, but f(n 1 )=f(n 2 ) does not automatically imply n 1 = n 2 . This function assigns a label, e.g., a room name or door name, to a node, thus adds semantic information to the model.
Next the function g, which is responsible for the weight distribution, is defined as follows.
Definition 4: The mathematic function g is defined as g: E × TC × R → ℝ + describing a non-surjective and non-injective function from the Cartesian product of the sets E, TC and R to the set ℝ + . This function assigns a non-negative weight to an edge e ∈ E and thereby considers different travelling conditions and different requirements.
The necessity of such a modular weight function can be illustrated by the following example, where e describes an edge between two stairway nodes: g(e,'healty','shortest_route')=5.2 and g(e,'elderly', 'shortest_route') = 19.9. Since stairways are easy to use for a healthy person, but are exhausting for an elderly person, the weight function g calculates different weights for this distinct edge e. That is, the function g is user-adaptive to individual user requirements and therefore also the WIRG is user-adaptive.
Furthermore, the function h is defined for considering one-way paths in indoor environments.
That is, the function h can be utilized for considering one-way ways inside a building while computing a route.
Also the function i is defined for retrieving the exact coordinates of a node. Definition 6: The mathematic function i is defined as describing a monadic, non-surjective and non-injective function from the set N to a triple of elements ℝ. The function i returns the three-dimensional coordinates (according to a distinct coordinate system) of a node. Additionally the function j is defined for adding additional semantic information, e.g., accessibility constraints, to the model. Definition 7: The mathematic function j is defined as j: N × ID → SI describing a binary non-surjective and non-injective function from the Cartesian product of the sets N and ID to the set SI. This function adds additional information from a distinct information domain i ∈ ID to a distinct n ∈ N.
For the possibility of a hierarchical structure inside the building, i.e., transition points and transition parts (e.g., corridors) are described as nodes and important parts are modelled in a more detailed perspective, it is furthermore possible to replace a single node with an additional graph, so that there are one or more WIRGs included in a WIRG. In doing so, it is possible to efficiently compute routes from room A to an area in room B.

Obtaining and navigating the WIRG
In chapter three, the building components relevant for the routing network were discussed, and in chapter four the WIRG was formally defined. Obviously, the combination of all relevant nodes equals the set N and the combination of all relevant edges between these nodes equals the set E. These sets can be (manually) obtained from 3D building models. For the functions f, g, h, i and j, the sets L, TC, R, ID and SI also need to be defined. The items of set L describe labels of distinct nodes inside the building (e.g. 'room 103') and such information can be gathered from diverse data source (e.g., 3D building models, facility management systems etc.). The items of the set TC vary from graph to graph and therefore need to be individually figured out. One example for sounding items of TC is {healthy, elderly, blind, wheelchair, crutches}. In most cases, the items of the set R are always the same, because R describes the different requirements for the route computation. That is, R can be defined as R = {shortest route, quickest route, most interesting, …}. The items of the set ID vary from graph to graph and therefore need to be individually decided upon. When creating the graph, it has to be decided what additional information is available and from which distinct information domain it comes from. Therefore, e.g., ID can be defined as ID = {accessibility, flowcapacity, …}. The items of the set SI are closely related to the different information domains described beforehand. Each element of SI represents a piece of information belonging to a distinct information domain, whereby these elements can be gathered from various data sources. Exemplary values for items belonging to SI are '08:00 am -04:00 pm' (accessibility) or '20' (flowcapacity). With these sets, the functions f, g, h, i and j can be defined, whereby a manual assignment of parameters and values needs to be performed (e.g., it has to be defined that g(e,'healty','shortest_route') = 5.2).
By combining all these sets and functions, a WIRG is constructed which can be utilized for shortest path algorithms. Furthermore, the functions f, g, h, i and j allow qualitative assertions and add additional topologic and semantic information. Such a WIRG has the characteristic that each edge between two nodes represents the most direct and most realistic path between any two connected nodes. Also, any two edges directly connected with each other share the characteristic that they are visible from each other, meaning that a user can directly reach the other node without encountering an obstacle inside the room. The length (i.e., travelling distance) of each edge can be calculated by using the Euclidean distance for three-dimensional spaces: where the triples (x 1 , y 1 , z 1 ) and (x 2 , y 2 , z 2 ) can be obtained from the function i. Thereby, the value of length is not necessarily equal to the value calculated by the function g, because the length of the edge is always the same but the weights can vary for different users (e.g., healthy vs. elderly). Route computation is performed by applying a shortest path algorithm on the WIRG. The corresponding weights of the different edges can be either calculated beforehand or on-demand. Normally a user is not interested in navigating to a distinct door, but to a distinct room or area. That is, if the room has several doors, the shortest path algorithm is performed for each potential target node (door) and the door with the smallest overall weight, i.e., the weight from the starting point to the potential target point, is determined as (implicit) target node.

Conclusion and future work
In this paper an advanced model which represents indoor environments with topologic, semantic, and metric information that allows nearly length-optimal routing in complex building structures has been presented. A description of the relevant parts of a complex indoor environment which are needed for route network construction and a discussion on how to model corridors and vertical building parts has been given. The importance of considering solid obstacles inside rooms by bypassing them has been described. Additionally, it has been discussed how to consider special areas inside rooms and how to integrate those areas into the routing graph. Based on these assumptions, a weighted indoor routing graph has been formally defined and constructed. This WIRG can then be used to calculate length-optimal routes between two points in a complex building structure. Since the WIRG offers semantic information, it is also possible to calculate different routes for different requirements (e.g., disabled persons, elderly persons), thus the proposed model is adaptable to different users and circumstances.
For future research, it is intended to improve the model. By developing a prototype for a huge complex multi-level building, the usability of the model can be demonstrated and performance tests can be conducted. Conciliated with this goal, it is necessary and planned to analyze how the semantic information provided by WIRG can be utilized for a clear and understandable description of the routes through the building.