Graph-based approaches for simulating pedestrian dynamics in building models

Höcker, Mario; Berkhahn, Volker; Kneidl, Angelika; Borrmann, André; Klein, Wolfram · 2010 · Crossref

DOI: 10.1201/b10527-65

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the challenge of simulating pedestrian dynamics within complex building environments by developing efficient, graph-based path-finding algorithms. The primary motivation is to improve the realism and computational efficiency of pedestrian simulations, which are critical for identifying bottlenecks, determining evacuation times, and optimizing routes in buildings. The authors aim to overcome the calibration difficulties of force-based models by using a visibility graph derived directly from scenario topography to guide individual navigation. The methodology involves two main components: graph derivation and routing algorithms. First, the authors automatically generate a visibility graph from the building’s geometry, including obstacles like walls and desks. This process involves placing orientation points on the bisectors of convex obstacle corners, adjusting their positions to avoid artificial congestion, and pruning redundant points. Edges are established between visible nodes, and a sight criterion is applied to remove unnecessary edges, reducing the graph’s complexity by up to 75%. For routing, the authors compare two approaches using this graph. The first employs a conventional Dijkstra algorithm where edge weights represent dynamic travel times rather than static Euclidean distances. Travel times are calculated based on pedestrian density on each edge, utilizing a velocity-density relationship to adjust speeds in real-time. The second approach utilizes a heuristic A* algorithm to find optimal paths more efficiently. The results demonstrate that dynamic edge weights lead to more realistic pedestrian distributions compared to static weights. In simulations of an office building, the static Dijkstra algorithm caused all pedestrians to follow the same route, whereas the dynamic version allowed pedestrians to adjust their paths based on congestion, resulting in a better distribution of flow. Furthermore, the A* algorithm significantly outperformed the Dijkstra algorithm in terms of computational efficiency. By using the Euclidean air-line distance as a heuristic, the A* algorithm searched only a relevant subset of the graph nodes rather than inspecting the entire network. The authors found that for a heuristic factor of $a \le 1$, the A* algorithm identified the same optimal paths as Dijkstra but with substantially reduced runtime, particularly in complex geometries with many rooms. The significance of this work lies in providing a robust framework for microscopic pedestrian simulation that balances realism with computational performance. By integrating automatic graph generation with dynamic, density-aware routing, the approach offers a practical solution for simulating large-scale pedestrian flows in complex structures. The study concludes that while the current model is effective for single-level scenarios, future work must address multi-level navigation (e.g., stairs and escalators) and further optimize edge weight calculations to handle runtime variations and dynamic events like emergencies.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• pedestrian behavior perception