Computational Modelling of Agent Based Path Planning and the Representation of Human Wayfinding Behaviour within Egress Models

Anand Veeraswamy

2011

Abstract

The focus of this thesis is on wayfinding within buildings from an evacuation/circulation modelling perspective. Majority of the existing evacuation models simplify the process of wayfinding by assigning the shortest path to all agents. This is not a realistic representation of the actual route choices made by people in circulation/evacuation conditions. Wayfinding is a dynamic process and cannot be modelled as a static process by assigning pre-determined routes to the agents. Wayfinding is thus a very important aspect to be modelled accurately within evacuation/circulation models to simulate more realistic human behaviour.

The main goal of this thesis is to develop an agent based wayfinding model for the buildingEXODUS evacuation/circulation model. There were four major problems to be solved: spatial representation of the environment, implementation of graph search algorithms to generate choice set of routes for the agents to choose from, determination of factors that influence people’s wayfinding behaviour and the development/integration of the agent based wayfinding model within the buildingEXODUS evacuation/circulation model.

The existing spatial representation technique in buildingEXODUS was modified to best suit the requirement of the wayfinding model. Various graph search algorithms such as A*, Dijkstra and Yen’s algorithm were studied. Alternate algorithms were developed to quickly generate routes and were compared with the performance of the Yen’s algorithm. Two surveys were then developed and published on line. A total of 1200 participants from various countries took the survey. The survey results were statistically analysed and was utilised to model the decision making behaviour of the agents in the wayfinding model. An agent based wayfinding model was then developed incorporating features such as: spatial representation in terms of a graph, application of route choice set generating algorithms, agents with their individual attributes using multi criteria decision analysis methods to choose routes and changing routes dynamically on encountering congestion or gaining new exit knowledge.

This wayfinding model was then integrated within the buildingEXODUS model. The buildingEXODUS model passes spatial information and agent location to the wayfinding model at the start of the simulation. The wayfinding model applies the graph search algorithms to generate routes and assigns routes (a set of target locations) to the agents. The buildingEXODUS model generates events under certain circumstances: when agents reach a target location, encounter congestion or learn the location of a new exit. The wayfinding model listens to these events and assigns a new route to the agents if an alternate route is more favourable than the initially chosen one. Therefore, there is constant communication between the fine node buildingEXODUS and the coarse node wayfinding models, with the latter being responsible for assigning routes to the agents and the former being responsible for navigating the agents from one target location to the next. Thus, a sophisticated wayfinding model incorporating data from surveys has been developed using C++ and has been integrated into the buildingEXODUS evacuation model.

The introduction of the wayfinding model brought about significant changes to the evacuation statistics produced by the buildingEXODUS model. The difference was more significant in buildings where there was more than one path to an exit. The default option of the existing evacuation models is to assign the shortest path to all the agents in the simulation whereas with the wayfinding model, agents choose alternative paths based on other wayfinding criteria as well such as time, number of turns, etc.