Pedestrian Velocity Obstacles: Pedestrian Simulation through Reasoning in Velocity Space

Sean Curtis       Dinesh Manocha
Stephen J. Guy     
University of North Carolina at Chapel Hill

Basim Zafar     
Hajj Research Institute, Umm al-Qura University, Makkah, Saudi Arabia

A brief summary of models and techniques used to create a viable pedestiran simulation using velocity-obstacle-based techniques including:

  1. right of way and
  2. adherence to the fundamental diagram.
Specifically, it is a pedestrian model which uses the Optimal Reciprocal Collision Avoidance (ORCA) algorithm to define local agent-agent and agent-obstacle interactions.


In designing shared spaces or planning for mass events, simulating the movement and behaviors of pedestrians can have inestimable value. In many cases it would be impractical to perform meaningful real-world experiments and, in some cases, it could be dangerous. Pdestrian simulation allows us to evaluate designs and plans in vitro. Architectural plans can be evaluated and design choices can be iterated easily in order to converge towards designs which improve pedestrian efficiency and safety.

We envisage an "ideal" pedestrian simulator with the following properties:

Pedestrian velocity obstacles are based on techniques which have arisen from robotics: velocity obstacles. The underlying model has proven to be both stable and efficient. However, the behaviors produced by the model are inconsistent with observed human behavior. Below, we define a model which apply the velocity obstacle model, in conjunction with psychological and physiological models, to produce a pedestrian simulator which preserves the stability and efficiency of velocity obstacles but faithfully reproduces credible human behavior.

Right of Way

Generally, as pedestrians move through a shared space, each pedestrian exerts effort to avoid collisions with others while still moving towards their goal. This can generally be modeled as symmetric responses to perceived collision threats. Howver, there are many meaningful scenarios in which symmetric responses are inappropriate.

On a subway platform, pedestrians enter the platform, find a location to await the train and then stop. In navigating the platform, moving pedestrians typically move around those already waiting. After they've stopped in their chosen position, those following behind, must move likewise around them. At that moment, the pedestrian shifts paradigms from an expectation of full responsibility for avoiding collisions, to the expectation that other moving pedestrians will assume the responsibility to avoid collision with them.

In the study of traffic, there is a concept that perfectly captures this phenomenon: right of way. Right of way is the set of rules which define when one entity must yield to another entity. When moving pedestrians walk around standing commuters on a train platform, the stationary people have right of way. When an aggressive person moves through a crowd and those around him part to let him through, it is because he implicitly has right of way.

Unlike with vehicles, where right of way has a very discrete, exclusionary interpretation (i.e. between two cars, right of way belongs entirely to one vehicle), between pedestrians it can be considered a continuous quantity. Right of way can be absolute, when one pedestrian completely yields to another or it can be shared such that each pedestrian partially yields, albeit to different degrees, to avoid collision.

We illustrate the need and efficacy of these principles in the simulation of the Tawaf. The Tawaf is a complex ritual performed in Makkah, Saudi Arabia in Al-Masjid al Haram, the holiest location to all of Islam. During the performance of performance of the ritual, tens of thousands of pilgrims all meet in the mosque to perform the Tawaf. The performance requires each pilgrim to walk seven circles around the Kaabah located at the center of the mosque. Ideally, each pedestrian would approach the eastern corner of the Kaabah to kiss the Black Stone. The pilgrims form an informal queue along the south-east face of the Kaabah. At the most extreme, observed density has reached as high as eight people per square meter. Often, crowds of people are likened to fluids. The individual desire becomes subsumed by the aggregate motion of the crowd. And yet, even in these high densities, pilgrims are able to form and maintain the queue despite the influence and effect of the circling pilgrims (See Figure 1).

Performance of the Tawaf
Figure 1: A time-elapsed photo of pilgrims performing the Tawaf. This image illustrates the discontinuities in flow. Pilgrims near the Kaabah (central black structure) are stationary while surrounded by circling pilgrims. Also, pilgrims on the right side of the image (vertically centered) have slowed down to perform Istilam.

The application of the right of way principle makes it possible for the simulator to reproduce this behavior (see Figures 2 and 3).

Failure to mantain queue Sustained queue
Figure 2: Simulation of the Tawaf without right of way. The queueing agents (in green) are unable to maintain the integrity of the queue because of the flow of other agents. Figure 3: Simulation of the Tawaf with right of way. The queueing agents (in green) are now able to maintain the integrity of the queue despite the flow of other agents.

First page of Tawaf 2011 paper

Sean Curtis, Stephen J. Guy, Basim Zafar, and Dinesh Manocha. Virtual Tawaf: A Case Study in Simulating the Behavior of Dense, Heterogeneous Crowds. 1st IEEE Workshop on Modeling, Simulation and Visual Analysis of Large Crowds, 2011

Paper (PDF, 0.7 MB)

Slides (PPTX, 3.2 MB)

Adherence to the Fundamental Diagram

There is a universally observed phenomenon in groups of pedestrians; as the density among the pedestrians increase, the pedestrian speed reduces (Figure 4). For historical reasons, this phenomenon bears the name "the fundamental diagram". Generally, this is a monotonically decreasing function of speed with respect to density. The exact shape of this function has been shown to vary depending on multiple factors: make-up of the pedestrian population, pedestrian flows, environment, etc. The small variations in the speed-density relationship notwithstanding, any pedestrian simulator must produce a similar aggregate behavior.

Fundamental Diagram
Figure 4: The fundamental diagram. Various examples of the fundamental diagram extracted from experiments (data available here).

Agents which use ORCA to control their responses to other agents do not adhere to the fundamental diagram. This is quite reasonable. Fundamentally, the underlying algorithm uses relative positions and velocities to predict collisions. This is the only planning criteria. If a set of ORCA agents have zero relative velocities, then, even if the agents are densely packed, they will remain content to move at full speed. In fact, they behave much like a train. Figure 5 illustrates this problem. The simulated ORCA agents showed no response to density at all.

ORCA does not adhere to the fundamental diagram
Figure 5: ORCA agents exhibit no density-dependent behavior. The variation in ORCA agent speed is due to a normal distribution of preferred speeds.

We propose a model, based on physiological and psychological empirical data, which introduces this behavior into the simulator. The model introduces two new parameters which can intuitively model such factors as agent height and sensitivty towards density. Using this model, we successfully reproduce behavior observed in pedestrian experiments (see Figure 6 and 7).

German Fundamental Diagram Indian Fundamental Diagaram
Figure 6: With the fundamental diagram model applied, the ORCA agents reproduce the same behavior as exhibited by German subjects. Figure 7: Simply by modifying the psychological buffer, the ORCA agents were able to model the same behavior as the Indian subjects.

First page of paper

Sean Curtis and Dinesh Manocha. Pedestrian Simulation using Geometric Reasoning in Velocity Space. In Proceedings of Pedestrian and Evacuation Dynamics. 2012.

Paper (PDF, 0.9 MB)

Slides (PPTX, 21 MB)