# A Mathematical Model of the Formation of Lanes in Crowds of Pedestrians Moving in Opposite Directions

Authors: Guillermo H. Goldsztein
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

In crowded environments, pedestrians moving in opposite directions
segregate into lanes of individuals moving in the same direction.
It is believed that this formation of lanes that facilitates the flow
results from the individuals acting on their behalf, responding to local
stimuli, without the intention of benefiting the crowd as a whole. We
give evidence that this is true by developing and analyzing a simple
mathematical model. Our results suggest that the simple behavior
of moving out of the way to avoid imminent collisions leads to the
formation of  lanes of individuals moving in the same direction.


---

## Body

## 1. Introduction

Self-organization refers to the pattern formation or emergence of order in systems composed of several units or individuals, where these units or individuals respond only to local stimuli, independently of the global state of the system.Primary research goals in the field of self-organization are to understand the local interactions among individuals and with the environment and how these local interactions lead to the global self-organization. A major objective is to discover common features of different self-organizing systems to establish general principles that apply to classes of systems. Some books and review articles on self-organization in biological systems include [1–3].Self-organization in human crowds is commonly observed in real life scenarios and is well documented in the literature. Examples include the occurrence of alternating flows through bottlenecks, as two groups of a large number of individuals cross the bottleneck in opposite directions [4], the formation of trails [5], and the different pattern formations when the crowd is a collection of several small groups (friends) [6]. These coordinated behaviors are not planned by the crowd as a whole or by any member or group of members within the crowd. Instead, they emerge as a consequence of the individuals acting in response to local stimuli and motivated by their own goals.Examples of why the understanding of the dynamics of crowds is of interest include the following: (1) It is a source of interesting examples of self-organization. (2) It can provide guidelines to increase the safety in very transited areas like some bridges [7] or in events attended by massive crowds, such as events in stadiums. (3) It can provide guidelines in the design of buildings, such as movie theaters and shopping malls, where optimal crowd flow is desired because of economical and safety reasons. Accordingly, the study of dynamics of crowds, both theoretically (early works include [8, 9]; see also [10] for a review) and experimentally [11–13], is a very active area of research.The existing mathematical models of crowd dynamics can be categorized according to the length scale modeled as microscopic, mesoscopic, and macroscopic.Microscopic models solve for the position of each individual. This class includes cellular automata models [14–16], lattice gas automata models [17, 18], algorithms [19], and large systems of odes, where the mass times acceleration of each individual is set equal to the sum ofgeneralizedorsocial forces the individual feels [20–24]. Thesesocial forces are not real forces between individuals but are introduced to model the responses of the individuals to stimuli they feel, which include the environment and the presence of the other individuals. In most models, the social forces are of four types: (1) repulsive force acting in a very short range, to avoid collisions with other individuals or walls or obstacles, (2) attractive force that acts in a longer range and attempts to model the desire of individuals to move in groups, (3) a force that would result in the desired speed and direction of motion of the individual in the absence of the other forces, and (4) a random force to account for differences in individuals. In some models, the speed of each individual remains constant, and only its direction changes in response to the social forces [25]. Some of these models are known as self-propelled particles models [26] and others as individual based models [25, 27].Mesoscopic, kinetic, or Boltzmann type models are integropartial differential equations that describe the evolution of probability densities of the position and velocities of the pedestrians [28, 29]. Macroscopic or continuum models are partial differential equations (conservation equations), where the dependent variables are the density andlocal average velocity of individuals [30–34]. Some works connect microscopic to macroscopic models [35–37]. Also, network models have been introduced [38] and optimal control theory has been used [39].Consider a crowded long corridor or street. Assume some of the pedestrians move in one direction and the others in the opposite direction. A self-organizing phenomenon familiar to all of us is that the individuals segregate into lanes, where each lane contains only individuals moving in one direction [40–42]. This formation of lanes facilitates the flow in both directions [43]. In this paper, we introduce and analyze a new model motivated by this phenomenon. This new model is very different to the ones that can be found in the literature. The results we obtain suggest that the simple behavior of moving out of the way to avoid collisions leads to the self-organization of the system.In Section2, we introduce our model, in which we assume that individuals move around a two-lane circular track with the same angular speed, half of them in one direction and the other half in the opposite direction. Each time two individuals moving in the opposite direction and in the same lane meet; one of them, randomly chosen with each having the same probability of 1/2 of being chosen, moves to the other lane so they both can continue their motion around the track. In Section 3, we prove that, with probability 1, the system willself-organize; that is, all the individuals moving in the counterclockwise direction end up in the same lane, and all other individuals, moving in the clockwise direction, end up in the other lane. More details on the dynamics and final state of our system are given in the subsequent sections. In Section 4, we provide the probability that, after the system is self-organized, the pedestrians in lane 1 move in the clockwise direction. In Section 5, we find the expected number of collisions required for the system to self-organize, and in Section 6 we compute numerically the expected time to self-organization. We finish the paper with a small discussion in Section 7.


## 2. The Mathematical Model

Assume thatN individuals or pedestrians move around a two-lane circular track, half of them in one direction and the other half in the opposite direction. Each time two individuals moving in opposite directions and in the same lane meet; one of them, randomly chosen, with each having the same probability of 1/2 of being chosen, moves to the other lane so they both can continue their motion around the track. More precisely, our model is defined as follows.Rules. The following set of rules define the dynamics of our model.(1)
Nindividuals move around a circular track with two lanes. The inner lane is referred to as lane 1 and the outer lane as lane 2. Each individual is labeled with an integer between 1 and N. We assume N is even.(2)
N/2 individuals move in the counterclockwise direction and the other N/2 in the clockwise direction.(3)
All individuals move with the same constant angular speedω.(4)
The position of the individuali at time t is described by an angle θi(t) and by li(t), the number of the lane the individual i is in at time t. Note that the angle θi(t) is not uniquely determined by the position of the individual i. Changing θi(t) by adding to it an integer multiple of 2π does not change the position of the individual i.(5)
We take all the angles to satisfy0≤θi(t)<2π for all t. The angle θi(t) is assumed to increase counterclockwise. Thus, if the individual i moves in the counterclockwise direction, we have θi(t)=θi(0)+ωt-2πMi(t), where Mi(t) is only the integer (that depends on t) that makes θi(t) satisfy the constraint 0≤θi(t)<2π. Analogously, if the individual i moves in the clockwise direction, then θi(t)=θi(0)-ωt+2πMi(t) for an integer value function Mi(t). With this rule, θi(t) is uniquely determined.(6)
We assume that initially all the angles are different; that is,θi(0)≠θj(0) for all i≠j.(7)
Two individuals,i and j, collide at time t if they reach the same location at that time; that is, θi(t)=θj(t) and li(t)=lj(t) (they have the same angle and are in the same lane).(8)
If two individuals,i and j, collide at time t, exactly one of them changes lanes at that time. The probability that the individual i changes lanes is 1/2 and, thus, 1/2 is also the probability that j changes lanes. The lane change is instantaneous; that is, it does not slow down the angular speed of the individual changing lanes.(9)
An individual can only change lanes when it collides with another individual.Observation 1.
Note that the assumptions that all the initial angles are different and that the angular speed of all individuals is the same imply that two individuals moving in the same direction will never have the same angle. Thus, if two individuals have the same angle at some timet, they must be moving in opposite directions. These facts imply that when two individuals collide, there is no other individual next to them in the other lane, and, thus, our rule that one of them changes lanes can be followed with no problems and no exceptions.Our model is very simple and is based on local responses only. The selection of the individual that changes lanes is independent of the location of all the other individuals. In other words, the individuals do not makesmart decisions attempting to minimize the number of lane changes they will have to make.Figure1 shows the results of a numerical simulation with N=80 individuals. The individuals move at one revolution per unit time. Figure 1 shows the positions of the individuals at three different times: t=0, t=1.2, and t=15.3. The number of collisions that occurred by those times is also indicated in Figure 1. The initial angle of the individuals, θi(0), was randomly chosen with uniform probability distribution around the track. The lane where each pedestrian started, li(0), was also randomly selected, with each lane having 1/2 as the probability of being chosen.Figure 1
Positions of the pedestrians at different times. The circles are the pedestrians moving clockwise. The stars are the pedestrians moving counterclockwise.
(a)
(b)
(c)Note that att=15.3, after 2688 collisions, all the pedestrians moving in the counterclockwise direction are in the outer lane, and all those moving in the clockwise direction are in the inner lane. No more collisions occur after this time. We say that the system has self-organized. We have run several simulations with different randomly generated initial conditions (not shown here), and in all those simulations the system self-organized.Our numerical simulations suggest that the system always self-organizes. Next, we prove that this is the case with probability 1.


## 3. The System Self-Organizes with Probability 1

We denote byti the time when the ith collision occurs. For convenience, we also define t0=0. We denote by ti+ the time right after the ith collision, that is, right once one of the individuals that collided changed lanes, and set t0+=0. We define(1)Ai=numberofindividualsinlane1movingcounterclockwiseattimeti+-numberofindividualsinlane1movingclockwiseinthesametime.Observation 2.
The following observations about the sequenceAi will be used in our analysis.(1)
Since there are a total ofN/2 individuals moving counterclockwise and N/2 moving clockwise, we have that |Ai|≤N/2 for all i.(2)
Ai=N/2 implies that, at time ti+, all individuals moving in the counterclockwise direction are in lane 1 and all those moving clockwise are in lane 2. Analogously, Ai=-N/2 implies that, at time ti+, all those moving clockwise are in lane 1 and all those moving counterclockwise are in lane 2. Thus, if |Ai|=N/2, there will not be any more collisions at later times, that is, for t>ti. The system has self-organized.(3)
If|Ai|<N/2, there will be at least one more collision at some time larger than ti.Given the above observations, proving that the system self-organizes is equivalent to proving that|Ai|=N/2 for some i.In what follows, we use the standard notations ofP(B) to denote the probability that the event B occurs and P(C∣D) to denote the conditional probability that the event C occurs given that the event D has occurred.Because all the individuals move with the same angular speed, any collision is between two individuals moving in opposite directions. Assume that theith collision occurs in lane 1. If the individual changing lanes to lane 2 is the one moving in the counterclockwise direction, we have Ai=Ai-1-1; otherwise, Ai=Ai-1+1. Since each of the two individuals colliding has a probability of 1/2 to change lanes, we have that (2)PAi=Ai-1-1∣ithcollisionwasinlane1=12,PAi=Ai-1+1∣ithcollisionwasinlane1=12.Similar arguments show that(3)PAi=Ai-1-1∣ithcollisionwasinlane2=12,PAi=Ai-1+1∣ithcollisionwasinlane2=12.As a consequence, we have(4)PAi=Ai-1-1=PAi=Ai-1+1=12.Thus, we can identifyAi with a random walk in Z, the set of integers. The walker starts at A0. When the ith collision occurs, the walker moves to the right if Ai=Ai-1+1 or moves to the left otherwise. Thus, each time a collision occurs, the walker moves to the right with probability 1/2 or to the left also with probability 1/2, and the position of the walker right after the ith collision is Ai.We can now use the theory of random walks [44] to obtain conclusions about our model. Let(5)K=min⁡i:Ai=N2.Note that K is the total number of collisions. After the Kth collision, the system is self-organized and no more collisions occur. It is well known that [44, page 14](6)PK<∞=1.Since the time between consecutive collisions is bounded (by half the time an individual takes to go around the track once), the last equation proves that the system self-organizes with probability one in finite time.Observation 3.
Note that we have proved that the system self-organizes with probability 1 regardless of the initial condition, that is, the initial anglesθi(0) and the initial lane position li(0) of the individuals.In Figure2, we show the evolution of Ai, corresponding to the same simulation as in Figure 1, as a function of i and also as a function of time t. In this case, A2688=-N/2=-40. After this last collision, all the pedestrians in lane 1 (the inner lane) are those moving clockwise, and all the pedestrians in lane 2 are those moving counterclockwise.Figure 2
Evolution of the number of pedestrians moving counterclockwise minus the number of pedestrians moving clockwise in lane 1, the inner lane. In (a), we use the timet, but, in (b), we use the number of collisions as the independent variable.
(a)
(b)


## 4. Direction of the Pedestrians in Each Lane after Self-Organization

Known facts about random walks provide us with more information about the dynamics of our system. In particular, we have that [44, page 15](7)PAK=N2=A0+N/2N;that is, the probability that after the last collision all individuals in lane 1 move in the counterclockwise direction is the above a linear function of A0. Note that this is an increasing function of A0, which is expected since A0 is the difference between the initial number of individuals in lane 1 moving counterclockwise and the initial number of individuals in lane 1 moving clockwise.


## 5. Number of Collisions Required for Self-Organization

Given some initial conditions and, thus, the value ofA0, the expected number of collisions needed to reach self-organization, E[K∣A0], follows also from known facts about random walks [44, page 30]:(8)EK∣A0=N2-A0A0+N2(see (5) for a reminder of the definition of K).Note that the value of (8) depends on the initial conditions through A0. However, if we assume that each lane has a probability of 1/2 to be the initial lane of each individual, as we did in all our numerical calculations, it can be shown that the law of large numbers implies that the expected number of collisions needed to reach self-organization, E[K], is(9)EK=N24-ON,where O(N) means a quantity of order N, that is, bounded by some constant times N.


## 6. Time Required for Self-Organization

A final question we seek to answer is, What is the expected time required for the system to self-organize?We have performed numerical simulations and obtained the results displayed in Figure3. Each data point in that figure is the average value of 10,000 realizations. The initial positions of the individuals were randomly chosen with uniform probability distribution around the track. The lane where each pedestrian started was also randomly selected, with each lane having 1/2 as the probability of being chosen. A least square fit of our data into a straight line gave us the straight line E[Torg]=0.1013N+0.1193, where N is the number of pedestrians and E[Torg] is the expected time to self-organization. Our simulations suggest that E[Torg] is asymptotically a linear function of N, the number of pedestrians, in the parameter regime of large N (see Figure 3).Figure 3
Expected time required for self-organization as a function of the number of pedestrians. The circles are the results of our simulations and the solid line is the straight line obtained with least squares fit.


## 7. Summary

We have introduced a very simple model to study the formation of lanes in crowds of individuals moving in opposite directions. The intent of our model is to isolate the effect of pedestrians avoiding collisions by simply moving out of the way only when the collision is imminent. Our model has proved simple enough to be amenable to analytical analysis. In fact, we were able to borrow many results from the theory of random walks in one dimension. Our results suggest that, in fact, this single behavior of moving out of the way only to avoid imminent collisions leads to the formation of lanes.The model studied in this paper belongs to the class of microscopic models. However, it is truly different in nature from the existing models that can be found in the literature. This model is the simplest model we could think of that isolates the effect of pedestrians avoiding collisions in a very simple way. This model that could be considered a toy model has the usual advantage of simple models: (1) The results obtained are clear, concrete, and easy to interpret. (2) Its simplicity makes it amenable to analytical analysis.There is a tradeoff, and with simplicity we sometimes lose generality. Most models in the literature do not lend themselves to the simple analytical analysis presented in this paper. Instead, they have to be solved numerically. However, they are more general in the sense that different phenomena can be studied by simply changing boundary or initial conditions. We believe that both strategies, the study of simple toy models, as in this paper, and the study of comprehensive more complex models, as most of the studies found in the literature, are very valuable and complement each other.We believe that this paper is a step forward towards the understanding of self-organization in biological systems, and we hope the modeling style of this paper will be adopted by other researchers to study this and other self-organization phenomena in biological systems.



---

*Source: 872807-2015-06-17.xml*