Simulating the Collision Avoidance Behavior of Pedestrians

 

1.       Introduction

For the design of public facilities, it is important to be able to estimate the behavior of the crowd, to be able to predict heavily used routes or peak flows:

Ø        For a more efficient and safer design of public facilities

Ø        To elaborate the emergency evacuation plan of a large building for example.

The models available to describe the behavior of the crowd usually deal with macroscopic variables like the average speed or the flow.

Our purpose is to design an individual-based model of the crowd, hoping that a more refined simulation might be obtained by considering each pedestrian’s behavior.

2.       Crowd Models

a.    Macroscopic approach

In this approach, the crowd is described with fluid-like properties. Usually some measures are made to get an expression of the speed according to the density (of course, the higher the density is, the more frequent the contacts are, and the lower the speed is). Individually, there are many variations according to one’s sex, age, physical shape, motivation… but this model only deals with averages.

テキスト ボックス: Macroscopic variables Ø Average walking speed U (in meter per minute) Ø Density of pedestrians d (in pedestrians per square meter) Ø Flow Q (in pedestrians per minute per meter width), with Q=U.d Linear relation between the speed U and the density d: U = A-B.d

Figure 2‑1 Speed-Density graph

 

 

 

テキスト ボックス: Factors defining the quality of the flow Ø Freedom to choose one’s desired speed and to overtake Ø Ability to cross a stream Ø Ability to walk in the direction opposing the major flow

Figure 2‑2 Levels of service

In simulations using the macroscopic approach:

Ø        The environment can be modeled by a graph, each edge being a transit place (sidewalk, passageway, stairway, escalator…) with its own capacity (estimated from surveys).

Ø        The pedestrian concentration is propagated across this graph.

These simulations are successfully used for large-scale estimations, such as the study of the effect of a modification in the design of a facility (adding a new entrance, a new exit…), or the estimation of the evacuation time of a building.

However, they do not take into consideration behavioral elements, and thus cannot be used at a more precise scale, to study how pedestrians really act.

b.    Microscopic approach

i.  Individual description

Yielding is the action to change one’s own trajectory to allow another pedestrian to pass. It is hard to measure exactly the distance at which one starts yielding. Observations made showed that the yielding distance decreases as the density increases, from 2.1 m at low density, to 1.5 m in congested situation.

Ø        When the density is low enough (unimpeded situation), people start detouring much earlier, at about 15~30 m from the obstacle.

Ø        At high density, when a simple detour is not possible, the “step-and-slide” movement occurs, starting at a distance of about 1.5 m. It consists in a slight angling of the body, the turning of the shoulders and a side step.

While the people coming ahead are usually briefly glanced at, and then discarded, when a collision is likely to happen, a kind of communication occurs, involving:

Ø        The emission of signs to allow the other to discover one’s purpose

Ø        An establishment point, when both parties acknowledge

Of course, misunderstanding is possible in this communication, both parties proposing to take the same option at the same time. They enter in what was called a “reciprocal dance”, which can require a couple of occurrences to break. 

ii.Boids

This famous model of group movements can simulate flocks of birds, herds of horses, schools of fish… Reynolds called these bird-like agents “boids” (for bird-oid).

The model is based on a very simple formulation of local rules that any agent in the group must enforce, resulting in a surprisingly harmonious result:

Ø        Separation: avoid collision with nearby flock mates

Ø        Alignment: match velocity with nearby flock mates

Ø        Cohesion: attempt to go towards the center of the flock

When avoiding collisions, a boid only considers the positions of its flock mates, and it chooses its speed relying only on its neighbors’ speed. Therefore, collision-free navigation appears as a side effect.

Boids are cooperative and all share the same goal and preoccupations. In a human crowd, everyone tries to avoid collisions, but the result is very different from a school of fish. This is probably because few pedestrians have the same objectives, and because everyone tends to act in a rather selfish way, not enforcing the rules of alignment and cohesion. The difference shall be evident at low densities, when every one is free to choose his speed.

iii.   Particle systems

Particle systems are usually used in computer animation for the modeling and the visualization of clouds, water, gases, fires… They consist in some clouds of elementary primitives (particles) with physical attributes (which obey physical laws). One can make the analogy with actual particles in electro-magnetic fields.

This method was used for simulation of crowd movement involving up to 50,000 persons, especially to test emergency evacuation plans. The model is robust enough to allow such large-scale simulations, and can be used to study the apparition of congestion points or the spreading of panic phenomena.

On the other hand individual behaviors are relatively simple (the agents do not plan their actions).

3.       An Algorithm for Collision Avoidance

a.    Outline

We adopted the following specifications for our model:

Ø        Each agent is able to plan a safe trajectory from the current position, using information on the position and speed of the obstacles to forecast their trajectories.

Ø        Both detouring and speed variations are possible in the avoidance scheme.

Ø        (x,y,t) space is used to represent the collision avoidance problem.

b.    (x,y,t) space

The future position of all visible obstacles is predicted and represented in a three-dimensional (x,y,t) space. In such a space, all objects are static, and the problem becomes one of path planning.

テキスト ボックス: When avoiding a collision point in (x,y,t) space : Ø Passing under it means passing earlier, thus accelerating Ø Passing above it means passing later, thus decelerating

Figure 3‑1 Collision avoidance in (x,y,t) space

c.     Avoiding collisions

 

テキスト ボックス: Admissible displacements The main constraint on the trajectory is that time is not reversible. Since z=VZ.t, where VZ is an arbitrarily fixed constant, all admissible displacement vector for the time intervalΔt must have VZ.Δt for third coordinates. Hence, the points that can be reached afterΔt are on a disk VZ.Δt above the current position, which radius is VM.Δt, VM being the maximum speed for the pedestrian.

Figure 3‑2 Admissible displacements

We would like to select a good point in the disk for the next movement. “good” meaning collision-free and optimal in relation to speed variation and detouring

To characterize a point P in the disk, we consider the trajectory TP obtained by adopting the speed corresponding to P (therefore TP is a straight line).

 

テキスト ボックス: Result 1: if the trajectory to avoid is a line in (x,y,t) space, then the set of points that would lead to a collision is a segment AZ in the disk of admissible displacements

Figure 3‑3 Representation of a trajectory in the disk

Then, taking a point P not on AZ, we calculated the minimal horizontal distance dmin between TP and the line to avoid.

テキスト ボックス: Result 2: points on a same line from Z correspond to a same dmin. Intuitively, it means that the closer P is to Z, the further the collision point is, and the less deviation is required.

Figure 3‑4 Forbidden area around a segment

If the pedestrian discards all movements that correspond to a dmin inferior to a fixed limit, it creates a triangular shaped forbidden area having Z for vertex.

d.    Finding the best movement

To choose among the points outside the forbidden area, we defined a cost function. In the following figure, the forbidden zone created by three obstacles is represented. Points V represent the pedestrian’s current speed, and the point leading to the goal at his favorite speed is G.

テキスト ボックス: The cost of a point P is defined as: K parameters are constants, with the following signification: Ø K1: cost of moving away from the goal Ø K2: cost of changing direction Ø K3: cost of acceleration Ø K4: cost of deceleration

Figure 3‑5 Definition of the cost of P

 

 

 

 

e.     Planning and following the trajectory

By iterating n times the process we described, a n-step trajectory can be planned from the current position.

Figure 3‑6 Navigation algorithm

 

4.       Implementation

テキスト ボックス: Physical characteristics Ø Speed limited by VMax=2m/s Ø Unlimited acceleration Ø Unlimited rate of rotation Ø Obstacles outside the field of vision are not considered

Figure 4‑1 Characteristics of an agent

Figure 4‑2 Screenshot of the graphical version of the simulation

5.       Evaluation

a.    Real data

Experimental data was obtained by filming outdoor scenes with a video camera, but we faced two problems:

Ø        The coordinates of the pedestrians must be extracted manually. It would have been interesting to make the whole process automatic, however, interesting scenes involve many pedestrians. In such cases, it is difficult to apply object tracking methods since the environment is complex and many occlusions occur.

Ø        The behavior of the pedestrians is difficult to analyze. We were able to obtain trajectories and velocity profiles; and we observed some variation according to the age (elder people walk more slowly) and the motivation (people in a hurry often rush when crossing the street). From these observations, we found that an average value for vfav can be 1.5 m/s.

b.    Test situations

i.  Frontal avoidance

In this situation, the two agents walk from opposite directions and must deviate to avoid a collision. The amount of deviations depends on the value of dmin, and the value of the K parameters does not influence the movement (the points on the limit of the forbidden area have the lowest cost). The trajectories of the pedestrians for different values of dmin are represented in the following figure.

Figure 5‑1 Frontal avoidance behaviors

ii.Lateral avoidance

In this situation, the pedestrians come from orthogonal direction. Collision avoidance is possible both by changing speed and by detouring. This choice depends on the values of the K parameters.

Ø        In the first case, the cost of deceleration is lower than the cost of acceleration for the pedestrian 0

Ø        In the second case, the cost of acceleration is higher

Ø        In the third case, the attraction to the goal is stronger, so that he does not yield and force pedestrian 1 to make a detour.

In the following figure, the (x,y,t) trajectories of the two pedestrian are represented (in green for P0 and in orange for P1).

Figure 5‑2 Lateral avoidance behaviors

 

iii.   Following behavior

In this situation, P0 is placed 2 meters behind P1. According to his “favorite speed”, he will either stay behind or overtake. In the first case, both have the save value for Vfav (1.5 m/s). In the second case, Vfav is set to 1.9 m/s for P0 and 1.3 m/s for P1. In the third case, the values are the same as for the second one, except that the value of dmin is 1.25 m instead of 0.85 m, so that P0 makes a greater detour to overtake.

Figure 5‑3 Following behavior

 

iv.                 Twelve pedestrians with converging trajectories

In this situation, 12 pedestrians arrive from different directions and converge to a same central point. We used this experiment to see the effect of dmin and n of the general aspect of the trajectories (an energy value was used as a measure of the smoothness of the trajectories).

テキスト ボックス: Influence of dmin Too small (dmin<0.8m): the resulting trajectories are no longer collision-free. Too large: unnecessary detours are made. テキスト ボックス: Influence of n Too small (n<4): the agents constantly re-plan their trajectory, so that it becomes difficult to accurately forecast their behavior, resulting in instable situations. Too large: the last part of the planned trajectory corresponds to unrealistic forecasting.

 

 

 

 

 

 

 

Figure 5‑4 Influence of n and dmin

From this experiment, we set the standard values to 20 for n (the trajectory is planned for the next 2 s, that is for a distance of about 3 m) and to 0.85 m for dmin.

c.     Limitations

Ø        The disk might be saturated when many pedestrians are to be avoided at the same time. A solution is to define a priority level (related to the actual distance or the distance in (x,y,t) space between the current position and the obstacle) and to consider only the pedestrians with the highest priority.

Ø        Oscillatory situations can appear when two pedestrians enter in a loop pattern. Of course, this pattern is observed in reality (“reciprocal dance”, see part 2), but it is usually prevented by the continuous perception of the environment that people have: the probability to take similar actions at the very same moment is much lower. Moreover, even in this case, the loop is broken after a few occurrences, because people can detect it and react to it. This kind of higher lever supervising mechanism should also be implemented in the simulation.

 

6.       Conclusion and future enhancements

We presented an efficient collision avoidance algorithm that was used in a simulation of crowd behavior, involving up to 12 pedestrians with conflicting goals.

Our model is based on a representation of the situation in a (x,y,t) space, which makes it possible to consider both detouring and speed modifications in the avoidance patterns.

Among the enhancements that are to be implemented before our model can realistically describe crowd behavior:

Ø        In the description of the environment: implement sources and sinks of pedestrians (doorways in reality) to generate large numbers of agents

Ø        In the description of the agents: improve the mechanical model (limited acceleration and rate of turn), implement specific behaviors (step-and-slide movement, group behavior), and improve the method used to forecast the trajectories to be avoided.