Partitioning algorithms for agent-based crowd simulation

Abstract

Simulating crowds is a challenging but important problem. There are various methodologies in the literature ranging from macroscopic numerical flow simulations to detailed, microscopic agent simulations. One key issue for all crowd simulations is scalability. Some methods address this issue through abstraction, describing global properties of homogeneous crowds. However, ideally a modeler should be able to simulate large heterogeneous crowds at fine levels of detail. We are attempting to achieve scalability through the application of distributed simulation techniques to agent-based crowd simulation. Generally, for an agent-based crowd simulation that aims to simulate a large number of agents under different scenarios, a proper partitioning algorithm is an essential factor to the performance of the system. However, selecting/developing an appropriate partitioning algorithm for a specific agent-based crowd simulation still remains an issue. One way is to implement distributed agent-based crowd simulations using multiple partitioning algorithms and to compare their performance. This requires multiple distributed simulation experiments, one for each partitioning algorithm. Considering the resources and the effort needed to perform multiple distributed simulation experiments, it is therefore preferred to predict the performance of partitioning algorithms instead. The research reported in this thesis focuses on investigating an effective and efficient approach to evaluate proposed partitioning algorithms for agent-based crowd simulations. A generic framework and an evaluation process are proposed to address the issue of selecting an appropriate partitioning algorithm by simulating the effect of a partitioning algorithm so as to predict its performance for the agent-based simulations. Our study also focuses on investigating and developing efficient and effective partitioning algorithms for crowd simulation. Generally, agents form into groups or follow flow patterns in crowd simulation.