Improved Deadlock Detection and Detours

Abstract

Crowd simulation is an important area of study since it is a broadly used subject: from the simulation of crowds in games to increase immersion, to simulations to improve the flow of people during an evacuation. As technology advances it is possible to simulate more and more agents in real time. This also increases interest in the simulation of high-density crowds. Even though there are many methods that are able to simulate high-density crowds there are still some unsolved problems. Examples are the forming of deadlocks for a variety of reasons such as the lack of lane forming or underutilization of available space.

The aim of this thesis is to create a method that solves some of these known issues to create more time-efficient paths for agents. For this purpose, this thesis introduces the Improved Deadlock Detection and Detours (ID3) algorithm as an extension of the MIRAN algorithm used for navigation. ID3 improves on MIRAN in two ways: by introducing deadlock detection and by planning detours using a density-based method based on the detours planned by the MIRANDA algorithm. The deadlock detection is vision-based and accounts for the flow of surrounding agents. The detours are improved by determining the detour goal by sampling density values and detecting what type of detour is planned. For global detours, paths are repaired using gates and memory is added to prevent continuous switching between different paths.

The experiments show, in most cases, that there was an improvement regarding the time it takes for an agent to reach their goal. In cases where there was no improvement on the time, there was often an improvement on either the realism or length of the path.