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:

right of way and
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.

Overview

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:

Utility

The utility of the simulator refers to the cost of simulation. In computers, no alogirthm is ever too fast or too efficient. Even in applications which don't explicitly have intentions to operate interactively would benefit from the cheapest possible algorithms. Fast algorithms means fast results. Fast results enables planners and architects to iterate through design choices more quickly. Furthermore, fast, lightweight algorithms are more suited to mobile devices. If the algorithm is efficient enough, crowd management experts could use crowd simulation techniques on mobile devices interactively to perform local predictions to assess local crowd conditions.

Utility is a function of two sub-properties: efficiency and stability.

Efficiency: the computational time cost of a single simulation step. How much work, per agent, must be performed to update the agent's simulation state. We measure this in seconds and smaller numbers are better.
Stability: the simulation model's ability to take large time steps and still produce meaningful results. We measure this simply as the size of the largest viable time step, in seconds.

We define utility, a unit-less numerical value, as stability / efficiency. Our goal is to maximize the utility value. This can be accomplished by reducing the cost of a single time step (efficiency), increasing the size of a valid time step (stability) or, ideally, both. Both the model and the integration method contribute to the utility. The model, and its concommitant required computations, defines the lower bound on efficiency and can constrain the stability. The numerical integrator will also influence both stability and efficiency. Simple integrators are more efficient but tend to lead to lesser stability. As we use more sophisticated integrators (such as higher-order explicit integration or even implicit integration) the stability increases, but the cost of evaluating that time step also increases. Ultimately, mzximizing utility comes from finding the best combination of model and numerical integrator.

Robustness

The ideal pedestrian model should capture those elements of human thought and behavior which spans the space of how humans interact with each other and their environments in a shared space. THe parameters should represent the pedestrian. As such, the simulation parameters should not depend on the enviornment or the conditions of the simulation. We should only change the parameters because we are modeling a different population (e.g. old vs. young, Americans vs. Chinese, etc.) A robust simulator should allow us to define a single space of values for modeling a single population and be equally appliable to arbitrary scenarios. The danger of changing simulation parameters from simulation to simulation (for, ostensibly, the same population) is that we're no longer evaluating the population, but we are evaluating our expectations for the population. When tuning simulation parameters, how do we know we have the "right" parameters? Because we determine the behavior to be reasonable. We are no longer determining what the population would do, we are merely determining if our simulation paradigm can conform to what we think the population should do.

Behavior

The final, and most vital property, is the simulator's behavior. Ultimately, the behaviors exhibited by the simulator's agents must be consistent with real humans. The credibility of the simulator is wholly dependent on this property. High utility and robustness avalis nothing, if the behavior is not credible. This property is particularly challenging for two reasons. First, the pedestrian dynamics community still does not know what behaviors must be reproduced to meaningfully produce reliable predictions. Second, it is unclear how to quanitfy those behaviors or, more particularly, how to quantify reproduction of such behaviors as known. This work falls in the domain of experimental researchers. As we expand our understanding of the dominant modes of human behavior and devise better ways of measuring the degree of such behaviors, our pedestrian models must evolve to conform to this new knowledge.

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).

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).


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.*

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.

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).


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.

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)