Comparing different metrics quantifying pedestrian safety

In this paper, we propose a methodology for comparing different metrics that compute density, velocity, flow and pressure fields, without the need for fundamental diagrams or visual inspection of these fields. Furthermore, we refine existing metrics to include obstacles in these fields by replacing the Euclidean distance by the geodesic (walking) distance.

In our experimental analysis, we see a wide range of possible values while the flows are similar. This confirms the need for calibrating the Levels of Service for each individual metric and scenario.

On the Topology of Walkable Environments

Motivated by motion planning applications, we study 2-dimensional surfaces embedded in 3-dimensional space with the property that their vertical projection is an immersion. We provide bounds on the complexity of a triangulation of such a surface, given that the projection of the boundary is a polygon with m segments. We then show how these bounds lead to efficient algorithm to compute such a triangulation. Finally, we relate our result to concrete motion planning setting and review related open questions.

Annotating traversable gaps in walkable environments

Autonomous agents typically need a navigation mesh of a 3D virtual environment to allow efficient path planning. This mesh needs as input a continuous representation of the walkable areas. However, the walkable environment (WE), i.e. the parts of the 3D environment that an agent can walk on, may contain gaps. These may be due to the filtering steps performed to compute the WE, because of modelling errors in the 3D model, or simply be part of the geometry of the environment.

We provide an algorithm that identifies and fills these gaps. We detect gaps, up to a given distance, between pairs of boundary edges of the walkable environment, and fill them with polygons. We employ a heuristic for choosing which pairs of edges should be connected.

We compare our algorithm to Recast, a voxel-based method for navigation mesh generation. We find that our method gives more accurate results in many environments: it retains the exact representation of the walkable environment, semantically separates the gaps from the walkable areas, and requires no tweaking of parameters to obtain good results. However, our method is currently slower than Recast, and requires more memory.

A comparative study of k-nearest neighbour techniques in crowd simulation

When performing a crowd simulation, it is often important to know what pedestrians are close together. Many different methods and implementations for solving this question, known as the k-nearest neighbour problem, exist. But what method is the best? In this paper, we tried to answer this question.

Performing multicut on walkable environments

This paper explores the theoretical aspect of splitting a 3d walkable environment in a set of 2d layers. The reason we want to do this is that many navigation algorithms only work in 2d environments. Obtaining this 2d decomposition turned out to be an NP-Hard problem.

Separating a walkable environment into layers

Before we can perform a crowd simulation study of an environment, we first need to create a suitable representation. When the environment is representable in two dimensions, lots of these techniques already exist. In this paper, we explore how we can obtain a decomposition of a three-dimensional environment in multiple two-dimensional layers.