Fast Marching Method on Triangular Meshes for Pedestrian Flow Simulations

Abstract

This thesis addresses the limitations of common Cartesian grid implementations of the Fast Marching Method (FMM) by extending the algorithm to unstructured triangular meshes. The applications of this extend include pedestrian flow simulation during evacuation scenarios. The Eikonal equation, which describes the propagation of wavefronts through a domain, provides a mathematical foundation for optimal path planning in complex environments. While the FMM on Cartesian grids offers computational efficiency, it exhibits limitations in describing complex geometries, especially in the presence of complex or curved boundaries and obstacles. The FMM implementation on acute triangular meshes substantially improves the Cartesian version in terms of accuracy. It exhibits more balanced error distributions and superior performance in the L2 norm, while maintaining the expected computational complexity. Furthermore, the theoretical underpinnings for extending the FMM to meshes containing obtuse triangles are provided in detail, paving the way for a forthcoming implementation. This will ensure the applicability to arbitrary unstructured domains. Finally, the integration of the triangular FMM implementation into a simulation framework for emergency management demonstrates its practical utility in evacuation simulations. A benchmark test inspired by a possible real-world evacuation scenario of an university campus demonstrates the approach's application to enforce counter-measures in the evidence of contaminant dispersion. The flexibility offered by triangular meshes allows for the computation of navigation fields directly on the same mesh as used for other classes of simulations, thereby eliminating interpolation errors between different meshes and enhancing the overall accuracy of the simulation. The findings enhance the approach as a valuable tool for emergency planning and response in complex urban environments.