INDOOR SPACE ROUTING GRAPHS: VISIBILITY, ENCODING, ENCRYPTION AND ATTENUATION

Abstract. The conventional approach to path planning for indoor navigation is to infer routes from a subdivided floor map of the indoor space. The floor map describes the spatial geometry of the space. Contained in this floor map are logical units called subspaces. For the purpose of path planning the possible routes between the subspaces have to be modelled. Typical these models employing a graph structures, or skeletons, in which the interconnected subspaces (e.g., rooms, corridors, etc.) are represented as linked nodes, i.e. a graph.

This paper presents a novel method for creating generalised graphs of indoor spaces that doesn’t require the subdivision of indoor space. The method creates the generalised graph by gradually simplifying/in-setting the floor map until a graph is obtained, a process described here as chained deflation. The resulting generalised graph allows for more flexible and natural paths to be determined within the indoor environment. Importantly the method allows the indoor space to be encoded and encrypted and supplied to users in a way that emulates the use of physical keys in the real world. Another important novelty of the method is that the space described by the graph is adaptable. The space described by the graph can be deflated or inflated according to the needs of the path planning. Finally, the proposed method can be readily generalised to the third dimension.

The concept and logic of the method are explained. A full implementation of the method will be discussed in a future paper.