Generating sparse navigation graphs for microscopic pedestrian simulation models

The paper describes the extension of a microscopic pedestrian simulation for implementing hybrid navigation strategies. This is realized by introducing a navigation graph layer on top of the microscopic model. This navigation graph is intended to reflect possible route choices to the greatest extent possible, while at the same time avoiding spatially redundant edges in order to ensure a high efficiency of the applied routing algorithms. Accordingly, a new method is introduced for the automatic generation of such a graph (a reduced visibility graph) from a given topography. The generated graph subsequently forms the basis for implementing different navigational behavior of pedestrians - ranging from classic shortest path algorithms for modeling individuals with precise knowledge of the overall scenario to an A∗-based path selection for modeling the heuristic choices of individuals with vague and incomplete knowledge of their environment. The paper is concluded with a comparison of simulation results with and without the graph layer extension.