Investigation on lane-formation in pedestrian flow with a new cellular automaton model*

Yi-zhou TAO （陶亦舟）， Li-yun DONG （董力耘）

Shanghai Institute of Applied Mathematics and Mechanics， Shanghai University， Shanghai 200072， China，

E-mail: yizhoutao@163.com

Investigation on lane-formation in pedestrian flow with a new cellular automaton model*

Yi-zhou TAO （陶亦舟）， Li-yun DONG （董力耘）

Shanghai Institute of Applied Mathematics and Mechanics， Shanghai University， Shanghai 200072， China，

In this paper， we investigate pedestrian flows by using a newly-proposed cellular automaton （CA） model， which is based on the floor-field model. The interaction of pedestrians includes completion and cooperation， respectively reflected by a modified dynamic field and a position-changing behavior. Then we utilize this model to research lane formation phase in counter flow problem，involving the probability of lane formation phase， the average number of lanes and the microscopic behavior of pedestrians. It is found that the interaction between pedestrians and the different significant influences of average density of pedestrian flow on the features of lane formation phase.

cellular automaton （CA）， floor filed model， pedestrian flow， lane formation

Introduction

One effective approach to research pedestrian flow is numerical simulation. Current modeling approaches in this field include social force models［1］，continuum models［2］and cellular automaton （CA） models， etc.. In the CA model， a complete discrete model，space is divided into cells， in which pedestrians are considered particles. They can move one or more cells in a single time step and the program is updated in parallel or sequentially. Furthermore， the CA models can be classified as the biased random walker model［3，4］， floor field model［5-8］， local model［9，10］， realcoded cellular automaton （RCA） model［11］， multi-grid model［12］and force-based model［13，14］， etc.. In the floor field model， two media called dynamic and static fields have been proposed to describe the long-range interaction between pedestrians and their neighbors in pathfinding.

Counter flow problem is one of the most important cases in pedestrian flow research［15，16］. As two groups of pedestrians walking oppositely， lanes will be spontaneously formed in pedestrians in both directions respectively， which is one of the typical selforganization phenomena. Many works have focused on the criterion of lane formation［6］and jamming-transition［17，18］， however， the characteristics of lanes， such as the width and number of lanes， the conflict between pedestrians and forming conditions of lane segregation are seldom mentioned in previous research［9，19，20］.

In this paper we propose a new CA model， named as interaction CA model based on the floor-field model. The conflict between pedestrians of different groups isdescribed by the modified dynamic field. In addition，two pedestrians failed to move would change their positions according to a given precondition. This setting decreases the probability of abnormal congestion. Then， by using this model in simulation， we investigate the characteristics of lanes.

1. Model definition

In the CA model the typical size of cell is 0.4×0.4 m2and a pedestrian is allowed to move to any neighboring cells. Particularly， in our model， a pedestrian can move to neighboring Moore cells （see Fig.1（a）） and the diagonal movement is equivalent to its projection to the expected direction. As the maximum average speed of pedestrian's is about 1.2 m/s， it can be concluded that 0.3stΔ≈， which is close to the average reaction time of pedestrian.

Fig.1 Moving directions and the corresponding probabilities

The moving direction is determined by the probability matrix （pk，l） （see Fig.1（b））， which mainly depends on the static field （Sk，l） and the dynamic field（Dk，l）. Here Sk，ldenotes the spatial position of cell（k，l） and Dk，ldescribes the interaction among pedestrians. In our model， we set the static field as in Ref.［21］， which is known as the flow-filled algorithm. Furthermore， the dynamic field （Dk，l） has two attributes called decay and diffusion， which correspond to pedestrian's memory and visual deviation respectively.

Consider two groups of pedestrians called A and B， who have different origins and destinations， then the probabilityis determined by

where φ is the angle between the expected moving directions of two groups （see Fig.2）.

Fig.2 The intersection angle φ

In Eq.（2）， there exist two hypotheses （H1-H2）:

H1: There holds =0φ as =AB， which means there is only one group in field Ω. In this case， Eq.（1）reduces to the general form of floor-field model.

H2: The function η reflects the conflict intensity between the two groups， which is strongest when two groups walk in opposite directions （=φπ， =1η-）. The case for φ＜π are more common. It means the superposition of two groups' paths: pedestrians have to compromise on conflicts. Additionally， N is the normalization factor， given asWith Eqs.（1）-（3） given， the computing procedure of interaction model is organized as following:

Step 1: At =0T， set the initial-boundary conditions and static field）. In addition， let the initial dynamic field，（）CklD be 0 everywhere.

where the parameter α represents the decay speed.

It is assumed that pedestrians follow others by tracking the information left behind.

Step 4: Pedestrian moves to one neighboring cell（k，l） according to the probability）. If≤（i.e.， cell （，）kl is farther than cell （，）ij， only the static fieldis considered in pk，l

Fig.3 The position-changing behavior

Step 5: If two adjacent pedestrians a（∈A） and b（∈B） failed to move， then we assume them to change position （See Fig.3）. Pedestrian a having the initiative， the precondition is

Step 6: If cell （，）kl is passed by a pedestrian of group C， the dynamic fieldis added by 1:

and =+tttΔ. If tT＜， the procedure goes to Step 2，otherwise the program exits.

Fig.4 Four typical phases

2. Probability of lane formation

Figure 4 illustrates four typical phases found in simulation with densityρ=2.5peds/m2. Free moving phase （Fig.4（a）） usually appears when kD=0. There is no interactions between pedestrians except for the anti-collision regulation， the movement of pedestrian's is unrestrained. Therefore it is uncommon in daily life.

Congestion phase （Fig.4（b）） usually occurs when kD=4. With the strength of dynamic field increasing， the congestion phase is more likely to appear. The reason for congestion is the compact queues of pedestrians in the same group， leading to the difficulty of lane segregation.

Metastable lane formation phase （Fig.4（c）） frequently appears when kD=2.5. In spite of lane formation in local area， congestion coexists in the domain. Finally， the phase will transform into another stable phase， e.g.， congestion phase when flux is high.

Lane formation phase （Fig.4（d）） shows up when kD=1.0. To minimize the conflict between pedestrians in different groups， crowd is divided into several queues. Lane formation， one typical self-organization phenomenon， is always found in many-particle system，and the efficiency of system will be improved. In the boundary lays of queues occurs the conflict， which can be measured with the position-changing behavior in Step 5.

Fig.5 Probability of lane formation with varying densityρ and kD

Figure 5 shows the probability distribution of lane formation. The horizontal axis shows the average density ρ and the vertical axis shows the strength of dynamic field kD. Each point sample（ρ，kD） is computed for 20 times， in which the program runs 5 000 time steps.Nc， the newly designed variable， is introduced to reflect the strength of conflict

wherecN is the number of position-changing in every time step. Being the average value over N pedestrians andNT time steps， the first term of Eq.（9） describes the conflict which is weak in lane formation phase. ω is a parameter to guarantee≥0 and there is ω= 12 in our simulation. We identify the features of lane formation among the results by one of the following criteria （C1-C2）:

C1: There exists distinct segregation of different groups and the lane pattern is stable after long time simulation.

In the low-density region2（［1.87，2.08］peds/m）in Fig.5， the probability P of lane formation is 1. Since the space occupancy of Ω is low， two queues of different groups are interference-free and the lane formation phase is stable once it forms. However， in the high-density region2（［2.08，3.12］peds/m）， the probability P decreases with increasingDk for any given. Since space is limited， stronger interaction always means harder lane segregation especially when two groups encounter for the first time and they have to wedge into each other.

On the other hand， for any givenDk， the probability P is non-increasing whenis increasing. The reason is that the increasing space occupancy always leads to the increasing probability of encounter， which is also adverse to lane formation.

3. Number of lanes

The number of lanes is an important index of lane formation phase. As is already know， the relative velocity， the strength of interaction between pedestrians， the space occupancy and the numerical viscosity in macroscopic model have the impact on it［19］. In order to do quantification research， we introduce another variable

Table 1　withand kD（（α，β）=（0.4，0.8））

Table 1　withand kD（（α，β）=（0.4，0.8））

kD ρpeds·m-2/ 1.25 1.45 1.67 1.87 2.08 2.29 2.50 2.71 2.92 3.12 0.5 3.65 3.75 3.65 3.6 3.55 3.65 3.35 3.55 3.25 3.08 1.0 3.80 3.75 3.55 3.7 3.70 3.65 3.65 3.20 3.10 3.00 1.5 3.85 4.00 3.50 3.6 3.55 3.45 3.40 3.07 2.67 -2.0 3.75 3.85 3.60 3.4 3.50 3.60 2.88 2.00 2.00 -2.5 3.50 3.80 3.85 3.9 3.40 3.35 2.50 - - -3.0 3.45 3.75 3.60 3.4 3.30 3.08 - - - -

Table 2Nl　with five pairs of （α，β） （kD=1.5）

where Nl（i） is the number of lanes in the ith lane formation phase. By averaging Nl（i） over S samples， we deriveNl， the average number of lanes in lane formation phase.

Table 1 demonstrates the influence ofρ and kDon Nlwhile （α，β） is fixed to （0.4，0.8）. In our CA model， by moving to a nearby empty cell or repulsion produced by the dynamic field， pedestrians prefer to avoid a face-to-face conflict with another group. However， in the high-density region （［2.29，3.12］peds/m2）， space is rather limited and the dynamic field is the major factor that affects the lane segregation. The table shows thatNldecreases with increasing kD（except for few points）， because relatively compact crowd and stronger repulsion lead to fewer lanes when two groups encounter. Conversely，due to extra space existing in Ω， there is no rule of kD-Nlto be found in the low-density region （［1.25，2.08］peds/m2）: the influence ofon lane segregation is insignificant. Similarly， the relationship betweenρ andNlis ambiguous in this region for a given kD. Not exceeding threshold value of space occupancy， pedestrians have no need to wedge themselves into the other group， thus Nlis more or less stochastic. But in the high-density region aforementioned， pedestrians have to find their path by intruding themselves into the other group: as increasing space occupancy leads to difficulty in this action，Nldecreases with the increasing density ρ.

Another topic is how the decay and diffusion of dynamic field affect Nl. To elucidate the issue， we choose five pairs of （α，β） as shown in Table 2. Compared with （0.4，0.8）， the decay speed α of （0.5，0.8）and （0.6，0.8） is increased to 0.5 and 0.6 respectively when kD=1.5. With the decay of dynamic field being accelerated， the stability of lanes is getting to decrease. This would lead to larger probability of the occurrence of tributaries， thusNlof （0.5，0.8） is larger than（0.4，0.8）. That （0.4，0.9） and （0.4，1.0） weaken the diffusion of dynamic field also reduces the width of queues， and therefore，Nlincreases accordingly. The exception appears in pair （0.6，0.8）， which corresponds to the weakest strength of interaction among five pairs. Especially when we choose the average densi2ty which is far less than jam density （i.e.， 6.25 peds/m），the behavior of pedestrians is mainly controlled by the static field. As a result，Nlwith （0.6，0.8） seems to berelevant to the initial distribution of pedestrians in Ω and irregular.

4. Behavior of pedestrians

To disclose pedestrians' behavior in lane formation phase， we investigate the ρ-v relation and the average number of position-changingNcin this section. Fig.6（a） shows ρ-v relation with varying kD. This pattern shows that the average velocity of pedestriansv decreases with increasing densityρ， which is also a general conclusion in pedestrian flow research. Moreover， smaller kDcorresponds to larger velocityv. This conclusion also agrees with most of floor-field models， because the dynamic field always plays the role of noise in pedestrian movement. In fact，the main influential factor on velocity is the space between pedestrians in queues， which concerns the density in Ω and following behavior of pedestrian （i.e.，dynamic field）.

Fig.6（a） Relation of ρ-v with varying kDin lane formation phase

Furthermore， the slope of ρ-v curve is about 0.25 when kDequals 1 and 0.5. When kD=3.0， the slope is nearly 0.16. It is clear that the influence of average densityρ on average velocityv is more significant when the strength of dynamic field is relatively weak. However， some non-smooth points appear when kD=1.5， 2.0 and 2.5. One reasonable explanation for this phenomenon is that both dynamic field and space occupancy alternately affect the behavior of pedestrians.

Figure 6（b） describes the influence of decay and diffusion on average velocityv. Compared with（0.4，0.8）， the decay speed α of （0.5，0.8） and （0.6，0.8） is increased to 0.5 and 0.6 when kD=1.5. With the noise in pedestrians' movement decreasing， the average velocityv is higher than that in pair （0.4，0.8）. For the same reason，v of pairs （0.4，0.9） and（0.4，1.0） is larger than that of pair （0.4，0.8）. The fact that velocity of （0.5，0.8） and （0.6，0.8） are relatively higher than （0.4，0.9） and （0.4，1.0） for any given ρ specifies that decay affects the dynamic field more significant than diffusion does.

Fig.6（b） Relation of ρ-v with varying （α，β） in lane formation phase

During lane formation， conflict between pedestrians of different groups mainly exists in the boundary lays of queues. The relation between density ρ and average number of position-changing Ncis illustrated in Fig.7. With space occupancy increasing， the gaps between queues decrease. As a result， the probability of encounter is getting larger. Thus for any given parameter pair （α，β），Ncincreases with increasing densityρ. On the other hand， the queue is looser when dynamic field is weaker. For this reason the probability of encounter （then Nc） increases when we weaken the dynamic field in Fig.7. BecauseNc≈7 is the critical point between areas in which probability of lane formation phase is 1 and less than 1 （See the dashed line in Fig.7）， we can find the critical density increases with the enhanced dynamic field. It implies that dynamic field is helpful to form lanes in counter flow.

Fig.7-with varying （α，β） in lane formation phase，kD=1.5

5. Conclusions

We have investigated lane-formation in pedestrian flow with a newly designed CA model， which is built based on the floor-field. The interaction of pedestrians， completion and cooperation， is included in this model. In addition， the position-changing behavior of pedestrians is also considered. By using this model， we have focused on characters of lanes in counter flow problem.

In the numerical simulation， we have found four typical phases such as free moving， congestion， metastable and stable lane formation. With varying density ρ and the sensitivity of the dynamic fieldDk， the probability of lane formation is illustrated. In low density region， the dynamic field is helpful to form the lanes. Conversely， in high density region， too strong a dynamic filed leads to the difficulty in lane segregation， which corresponds to the decreasing probability.

On the number of lanes， we have discussed the influence of density and the dynamic field. Because of relatively compact crowd and stronger repulsion， stronger dynamic field implies fewer lanes in high density region. However， when there exists extra space in facility， pedestrians could easily make a detour to avoid the conflict. Thus the influence ofDk is insignificant. Furthermore， the decay and diffusion of dynamic field（，）αβ are relevant to the stability and width of queues respectively.

At last， we have also investigated pedestrians' microscopic behaviors， which are pedestrians' average velocity and the frequency of position-changing behavior. The numerical results reveal the increasing dynamic field would lead to the decreasing efficiency of pedestrians' moving and the less frequency of position-changing.

References

［1］HELBING D.， MOLNAR P. Social force model for pedestrian dynamics［J］. Physical Review E， 1995， 51（5）: 4282-4286.

［2］HUANG L.， WONG S. C. and ZHANG M. et al. Revisiting Hughes' dynamic continuum model for pedestrian flow and the development of an efficient solution algorithm［J］. Transportation Research Part B： Methodological， 2009， 43（1）: 127-141.

［3］MURAMATSU M.， IRIE T. and NAGATANI T. Jamming transition in pedestrian counter flow［J］. Physica A：Statistical Mechanics and its Applications， 1999， 267（3）: 487-498.

［4］JIANG R.， WU Q. S. Pedestrian behaviors in a lattice gas model with large maximum velocity［J］. Physica A： Statistical Mechanics and its Applications， 2007， 373（36）: 683-693.

［5］GUO W.， WANG X. and LIU M. et al. Modification of the dynamic floor field model by the heterogeneous bosons［J］. Physica A： Statistical Mechanics and its Applications， 2015， 417（2）: 358-366.

［6］NOWAK S.， SCHADSCHNEIDER A. Quantitative analysis of pedestrian counterflow in a cellular automaton model［J］. Physical Review E， 2012， 85（6）: 066128.

［7］LI Xiang， DONG Li-yun. Modeling and simulation of pedestrian counter flow on a crosswalk［J］. Chinese Physics Letters， 2012， 29（9）: 098902.

［8］DONG Li-yun， LAN Dong-kai and LI Xiang. Self-organized phenomena of pedestrian counterflow through a wide bottleneck in a channel［J］. Chinese Physics B， 2016，25（9）: 098901.

［9］NARIMATSU K.， SHIRAISHI T. and MORISHITA S. Acquisition of local neighbor rules in the simulation of pedestrian flow by cellular automata［C］. 6th International Conference on Cellular Automata. Amsterdam， The Netherlands， 2004， 211-219.

［10］ YU Y. F.， SONG W. G. Cellular automaton simulation of pedestrian counter flow considering the surrounding envi- ronment［J］. Physical Review E， 2007， 75（4）: 046112.

［11］YAMAMOTO K.， KOKUBO S. and NISHINARI K. New approach for pedestrian dynamics by real-coded cellular automata （RCA）［C］. 7th International Conference on Cellular Automata. Perpignan， France， 2006， 728-731.

［12］ CAO S.， SONG W. and LV W. et al. A multi-grid model for pedestrian evacuation in a room without visibility［J］. Physica A： Statistical Mechanics and its Applications， 2015， 436: 45-61.

［13］JIAN X. X.， WONG S. C. and ZHANG P. et al. Perceived cost potential field cellular automata model with an aggregated force field for pedestrian dynamics［J］. Transportation Research Part C： Emerging Technologies， 2014，42（2）: 200-210.

［14］ QU Y.， GAO Z. and ORENSTEIN P. et al. An effective algorithm to simulate pedestrian flow using the heuristic force-based model［J］. Transportmetrica B： Transport Dynamics， 2015， 3（1）: 1-26.

［15］LIU X.， SONG W. G. and LV W. Empirical data for pedestrian counterflow through bottlenecks in the channel［J］. Transportation Research Procedia， 2014， 2（12）: 34-42.

［16］ ZHANG J.， SEYFRIED A. Comparison of intersecting pedestrian flows based on experiments［J］. Physica A：Statistical Mechanics and its Applications， 2014， 405: 316-325.

［17］ KUANG H.， LI X. and SONG T. et al. Analysis of pedestrian dynamics in counter flow via an extended lattice gas model［J］. Physical Review E， 2008， 78（6）: 066117.

［18］ NAGATANI T. Freezing transition in bi-directional CA model for facing pedestrian traffic［J］. Physics Letters A，2009， 373（33）: 2917-2921.

［19］ XIONG Tao， ZHANG Peng and WONG S. C. et al. A macroscopic approach to the lane formation phenomenon in pedestrian counterflow［J］. Chinese Physics Letters，2011， 28（10）: 108901.

［20］ GUO W.， WANG X. and ZHENG X. Lane formation in pedestrian counterflows driven by a potential field considering following and avoidance behaviours［J］. Physica A：Statistical Mechanics and its Applications， 2015， 432: 87-101.

［21］ VARAS A.， CORNEJO M. D. and MAINEMER D. et al. Cellular automaton model for evacuation process with obstacles［J］. Physica A： Statistical Mechanics and its Applications， 2007， 382（2）: 631-642.

E-mail: yizhoutao@163.com

（May 12， 2015， Revised May 20， 2016）

Pedestrian flow research has much attention in recent years due to its importance in social issues. The study offers evacuation strategy for the existing walking facilities and reference in facility designing. Unfortunately， disasters originated in the congestion of pedestrian flow have increased recently. For instance， the stampede which happened on the Bund of Shanghai， brought heavy casualties on New Year's Eve， December 31， 2014. This kind of accidents testifies to the significance of pedestrian flow research.

* Project supported by the National Natural Science Foundation of China （Grant No.11172164）， the National Basic Research Development Program of China （973 Program， Grant No.2012CB725404）.

Biography： Yi-zhou TAO （1982-）， Male， Ph. D.

Li-yun DONG，

E-mail: dongly@yeah.net