Simulating the Collision Avoidance Behavior of Pedestrians
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.
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.
Figure 2‑1 Speed-Density graph
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.
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.
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.
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).
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.
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.
Figure 3‑1 Collision avoidance in (x,y,t) space
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).
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.
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.
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.
Figure 3‑5 Definition of the cost of P
By iterating n times the process we described, a n-step trajectory can be planned from the current position.
Figure 3‑6 Navigation algorithm
Figure 4‑1 Characteristics of an agent
Figure 4‑2 Screenshot of the graphical version of the simulation
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.
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
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
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
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).
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.
Ø 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.
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.