Simulation and optimized scheduling of pedestrian traffic : from geometric modeling to pedestrian navigation

Abstract

Today, more and more simulation tasks with a traditionally non-geometric background need to be embedded into some geometric context, in order to provide spatial context to non-spatial data. This holds especially true for graph-based applications in some location-aware context. As an example, one might think of a theme park or a large commercial center, where the customers shall be provided with some navigation and scheduling information such as where to go and when - either a priori or even in real time via some mobile device. This can be done by analyzing the pedestrian traffic and waiting time situation by simulating the pedestrian movement and using the simulation data to optimally navigate and schedule the tasks that are to be executed by the customer. The main issues addressed in this thesis are as follows. Initially, a flexible simulation framework is built to simulate the pedestrian movement in a 3D scenario, for example, a commercial building. Since the pedestrians strongly interact with the environment surrounding them, the geometry is taken into account. Architectural data such as paths, type and capacity of the paths, destinations and its properties, etc., is extracted from the CAD-model and are organized in a graph structure. The movement of the pedestrians and the waiting queues at the destinations are modeled as queuing systems using the discrete event simulation technique. These queuing systems are then embedded into the geometry model. The necessary input modeling parameters are also defined. The resulting scenario, when simulated, gives an overview of congestions and waiting times across the scenario for different time stages. Apart from the simulation, the geometry data - or here the graph - is hierarchically organized in an octree structure. An octree-based model is chosen since octrees have the natural property of hierarchically storing 3D data. The octree data is used to identify the position of the pedestrian within the scenario. The potential destinations in the neighborhood that can be visited by the customer are also identified using neighbor search algorithms. Combining the simulation data with the octree modeling, the customer is navigated to the optimal destination. Furthermore, when visiting several destinations, combinatorial optimization methods are used to optimally schedule the set of tasks to be executed by the customer. The optimization methods take into account the congestion information obtained from the simulation data, and the octree structure for navigation. This approach results in an effective pedestrian navigation system.

Es besteht heute oftmals die Notwendigkeit, Simulationen ohne geometrischen Hintergrund in einen geometrischen Kontext zu integrieren, um einen Bezug zwischen räumlichen und nicht-räumlichen Daten herzustellen. Dies gilt insbesondere für graphenbasierte Anwendungen mit räumlichem Bezug. Wir betrachten hier ein System, das in einem großen Bürogebäude Kunden Informationen zur Navigation und Zeitplanung zur Verfügung stellt, d.h. wohin sie zu welchem Zeitpunkt gehen müssen. Diese Informationen können im Voraus oder in Echtzeit über ein mobiles Gerät zur Verfügung gestellt werden. Dazu wird zunächst das Fußgängerverhalten und die Wartezeit an Bedienstationen in einem dreidimensionalen Modell (Bürogebäude) analysiert, indem das beschriebene Szenario simuliert wird. Danach werden die verschiedenen möglichen Anwendungen unter Verwendung der Simulationsdaten untersucht. Ziel einer solchen Anwendung ist die Entwicklung eines intelligenten Fußgänger-Navigationssystems - betrachtet man z.B. einen Kunden, der das Bürogebäude besucht, um bestimmte Aufgaben durchzuführen, besteht das Problem aus der optimalen Planung, die sowohl Informationen über den Weg als auch die Bearbeitungsreihenfolge der Aufgaben enthält. Dabei werde das aktuelle (Fußgänger-)Verkehrsaufkommen sowie die Warteschlangensituation im Bürogebäude berücksichtigt. Die notwendigen Daten erhält man als Ergebnis der Fußgängersimulation.