A Markov Jump Approach to Modeling and Analysis of Pedestrian Dynamics

The key issue of establishing a pedestrian dynamics model is to select the direction and magnitude of the pedestrian velocity. In this paper, an improved Markov jump model based on the heuristic method is proposed to simulate the dynamic behavior of the pedestrians. According to the speed of the pedestrian, the pace is divided into four states, and the next step of the state is only determined by the current state and state transition matrix. According to the characteristics of decision-making in the pedestrian motion, a heuristic method is referenced, which is based on the pedestrian visual field, and the pedestrian will select the moving direction according to the proposed method. The validity of the model is verified by constantly modifying the parameters and components, which achieves the fundamental flow-density or velocity-density diagram and gets the reappearance of the self-organization phenomena, such as “arching and clogging” and “lane formation.” The simulation results show that the fundamental diagrams are qualitatively consistent with the field data in the cited works.

SECTION I. Introduction

The research of predicting the movement of pedestrians is meaningful in many case. The panic situation analysis is the one that has motivated the large majority of research activities in the field [10], [23]. However, it is a specific situation. Not only the scope of application is small, but also the behavior of the pedestrian may become non-rational which is a unique objective to save their own lives [34]. Capturing the behavior of pedestrians in normal situations is very important.

The presence of collective behavioral patterns from the interactions among a large number of individuals leads to the complexity of pedestrian behavior. In order to understand complex movement characteristics of pedestrians, the important work is to construct an appropriate model for capturing pedestrians’ behaviors. As with vehicular traffic, pedestrian traffic has been researched mainly from macroscopic and microscopic approaches. In macroscopic methods, the crowd is described with fluid-like properties, describing how density and velocity change over time by using partial differential equations, including Navier-Stokes or Boltzmann-like equations [16], [17]. This method observes at medium and high densities based on some analogies. Even though the macroscopic model can describe the overall trend of the crowd, interaction of the crowd and the detailed behavior of the individual will be ignored [51]. As a consequence, the key of current research takes the pedestrian as a set of individual paradigms. This is microscopic model, where collective phenomena appear from the complicated interactions between many pedestrians called self-organizing effects. The social forces model of Helbing is one example of such models, where an individual is subject to long-ranged forces and his dynamics conform to the equation of motion. It is similar to Newtonian mechanics [11], [12], [38], [50]. Although physics-inspired models are able to reappear some of the observations pretty well, it is becoming more and more difficult to obtain the complete range of crowd behaviors in one single model [29]. The cellular automaton (CA) model is another example [1], [14], [31], [37]. Under the condition of the local movement, the pedestrian are modeled with a matrix of preferences which includes the probabilities for a movement, related to the inclined walking direction and speed, toward the nearby direction. Schadschneider introduces the interesting idea of floor field to simulate the long-ranged forces. In this field, it is modified by pedestrians and in turn modifies the matrix of preferences, and has its own dynamic including diffusion and decay in this field [52]. Simulating interactions between individuals and the geometry of the system is simple. However, the settled regularity of a static discretization of the space and the homogeneity of the rules is not appropriate to simulate a more flexible situation in cellular automaton model. Except these two models, the micro models have lattice gas model [21], [28], [40], [42], network-based model [9], [19], [24], discrete choice model [8], [26] and so on. These models can reproduce typical pedestrian behaviors such as faster is slower [11], [12], lane formation [21], herding behavior [12], self-organization [13], [30], and capture microscopic and macroscopic characteristics of pedestrian traffic.

A completely different approach called Markov jump model [3], [4], [25], [33], [35], [36], [39], [45]–​[49], [54], which can be used to predict the occurrence of the accidents by the pedestrian moving track in vehicle pedestrian accidents, fully embodies the randomness in the process of pedestrian movement [43]. In this model, according to the speed of pedestrians, the pedestrian pace state is divided into four states including static, walking, jogging and running. Once a new state has been chosen, new target values for speed and direction are randomly picked up from two independent probability distribution. Although many scholars have made some i8mprovements to the Markov pedestrian model, they have not solved the inherent defects well [53]. For example, it can’t adapt to the changeable walking environment, and show the subjective characteristics of the pedestrian [20]. And these four states cannot reflect the movement of a dense crowd. 9 Motivated by those observation, we propose a new Markov jump model based method to establish and verify the pedestrian dynamics: According to the actual experience, pedestrians will react according to other objects and the environment within the field of their view, and the impact out of view on the pedestrian behavior is very small [2]. Pedestrians will make reasonable decisions based on the current environment. Considering the intelligence of the crowd behavior, vision scope, automatic deceleration and avoidance mechanism, Moussaid modified the desired velocity direction of a dense population in the moving process by introducing the optimal theory, and proposed a cognitive science approach based on behavioral heuristics [29], [30]. We can get the basic principle of the cognitive science approach [6], [7]. To meet our goals, we have made some changes to the heuristic method so that it can improve the defects of the Markov model.

Pedestrian’s state can be divided into four discrete states according to the crowd speed, and use this rule to select the velocity of pedestrian. Moreover, we discretize the pedestrian’s vision and combine the heuristic method to select the moving direction of pedestrian. Based on these, the Markov random walk model can be constructed. And by simulation experiments and data collection, the validity of the model can be verified.

The remainder of this paper is organized as follows: In Section 2, an improved model of pedestrian behavior, based on a Markov chain including four-discrete states and behavioral heuristics is described. Section 3 displays the simulation and results of the proposed model. Finally, section 4 gives the conclusion of the work.

SECTION II. Model Description

The pedestrian model used to study pedestrian dynamics is described in this section. In our model, each pedestrian $i$ is characterized by its current position $\vec {X_{i}}=(x_{i},y_{i})$ and velocity $\vec {v_{i}}=(v_{i},\theta _{i})$ . For simplicity, the projection of the pedestrian’s body on the horizontal plane is represented by the circle of radius $r$ . Each pedestrian is additionally characterized by his comfortable walking speed $v_{des}$ and his or her destination point $D$ . Therefore, the most important for capturing pedestrians’ behaviors is to describe walking speed $v_{i}$ and direction $\theta _{i}$ . Next, we will describe the direction and magnitude of the pedestrian’s velocity in the model respectively.

A. The Direction of Velocity

According to the actual experience, pedestrians will react according to other objects and the environment within the field of their view, and the impact out of view on the pedestrian behavior is very small [5], [18]. Pedestrians will make reasonable decisions based on the current environment and select the destination and the optional path dynamically in the process of movement, bypass the obstacle ahead and avoid collision. Based on this characteristic, Moussaid et al proposed a heuristic mechanical method [29], [30]. However, there are still some problems such as higher computational complexity.

In our model, we make some improvements in this method, and use it as the selection rules for the direction of the velocity. Assume that the shape of the pedestrian is round, the length of pedestrian visual field is $l$ , and $H$ represents the direction of velocity at current moment, which devised the current vision domain. The vision field of pedestrian ranges to the left and the right all by $\varphi$ with respect to the line of sight $H$ . $\alpha$ represents the walking direction in which pedestrians will walk. Fig.1 is the schematic diagram of a pedestrian vision domain.

FIGURE 1.

The vision domain of the pedestrian.

Empirical evidence suggests that pedestrians seek a walking direction without block, but dislike deviating too much from the direct path to their destination [41]. In reality, pedestrians adapt their behavior to select the more fluent walking route to the destination. In order to solve the problem of this method, the vision of the pedestrian will be divided into discrete $N$ parts, and the longest distance which can be went free will be estimated in each direction. The pedestrian can choose the smallest part deviated from the destination as the walking direction that taking into account the presence of obstacles. The minimum value of $d(\alpha)$ under normal walking situations is given by formula (1) according to Ref [29]. $$\begin{equation*} {d}^{2}_{i}(\alpha)=D^{2}+{f}^{2}_{i}(\alpha)-2\cdot D\cdot f_{i}(\alpha)\cdot cos(\alpha -\alpha _{0})\tag{1}\end{equation*}$$

In this formula, $\alpha$ represents the angle between the middle line of the pedestrian in each region and the direction of the destination, $D$ represents the distance between the pedestrian and destination. $f_{i} (\alpha)$ represents the maximum length which pedestrian can walk in this area. By using trigonometric function formula, we can get the minimum value of $d_{i}(\alpha)$ . And at this point pedestrian $i$ will walk along the direction of $\alpha$ . If the distance between the pedestrian and the destination is less than $l$ , the distance between this pedestrian and the destination is regarded as the length of the pedestrian’s visual field.

There are two special cases, causing unintentional movements that are not determined by the above heuristic method:

1. In case of the destination is not in the scope of the pedestrian’s view, the pedestrian will not be able to perceive its location. And he will select a nearest position to the target point in the field of view as a temporary target point.

2. In case of overcrowding, physical interactions between bodies may occur. Indeed, at extreme densities, it is necessary to distinguish between the intentional avoidance behavior of pedestrians adapting their motion according to perceived visual cues and unintentional movements resulting from interaction forces caused by collision with other bodies. Under these circumstances, the pedestrian will move along the angle bisector of the pedestrian-to-target line and reverse extension line which along the two pedestrians centers. As shown in Fig.2, two solid lines with arrows represents the direction in which pedestrian $i$ and pedestrian $j$ will walk respectively when they contacted each other physically. And pedestrian $j$ is the nearest to pedestrian $i$ . The angle relationship as shown in formula (2). $$\begin{equation*} \alpha _{1}=\alpha _{2}\tag{2}\end{equation*}$$

FIGURE 2.

The changes of pedestrians’ direction in physical collision.

B. The Magnitude of Velocity

In addition to the direction of the velocity, another important factor in walking process of the pedestrian is the magnitude of the velocity. The four state in Ref [43] are not suitable for describing pedestrian movement in crowd. In the model built in this paper, we will combine it and real pedestrian’s behavior to select the walking speed $v_{i}$ .

Based on the empirical observation of the crowd, pedestrian pace state $S_{i}$ is divided into four discrete states including $S_{1}$ , $S_{2}$ , $S_{3}$ and $S_{4}$ , representing static, walking, jogging and running states. For each pace, there is a set of possible speeds and changes of direction. The pedestrian will continue for a period of time called step time $\tau$ in each state. According to the current state and the state transition matrix, the pedestrian will decide the state of the next moment, and its basic idea is that the action of the pedestrian is only related to its recent behavior.

In the process of pedestrian movement, the change of the pace state can be expressed in Fig.3. The arrow indicates that the pedestrian can be changed from one state to another state directly, and two states which have no arrow connection between them cannot be converted directly, but the transition can be accomplished through the intermediate state. For example, $S_{1}$ cannot be converted to $S_{3}$ and $S_{4}$ directly, it needs $S_{2}$ as an intermediate state. Under normal circumstances, $S_{1}$ and $S_{2}$ can be converted to each other, $S_{2}$ and $S_{3}$ can be converted to each other, $S_{3}$ and $S_{4}$ can be also converted to each other. However, in some larger population density and the environment more complex cases, there are some transitions between states will be limited.

FIGURE 3.

Pedestrian state transition diagram.

Each state corresponds to a velocity interval. Through the observation of the crowd movement, and compare with the experience data, we can describe the speed distribution in Tab 1. In formula (3), $P$ is the transition probability matrix, and physical meaning of $P_{ij}$ represents the transition probabilities from state $i$ to state $j$ . The sum of the probability accumulation in each line is 1. If the current state of the pedestrian is the same with the previous state, we will keep the speed value of the previous state. Once the state changed, a speed value randomly in the corresponding interval of the speed range combing with the truncated Gauss function after determining the state will be selected [22]. The truncated Gaussian function is shown in formula (4), the truncated place said the value range of the speed corresponding to each state, the pedestrian will randomly select a speed value according to the probability density within the scope of this value range after selecting state. Where $\eta$ is a compensation constant, which makes the value of CDF (Cumulative Distribution Function) be 1 in the point that the speed is maximize. $v_{avg}$ is the average value of the speed range corresponding to each state. $\sigma$ is the standard deviation of Gaussian function. $$\begin{align*} P=&\left [{ \begin{array}{cccc} P_{11} & P_{12} & P_{13} & P_{14} \\ P_{21} & P_{22} & P_{23} & P_{24} \\ P_{31} & P_{32} & P_{33} & P_{34} \\ P_{41} & P_{42} & P_{43} & P_{44} \\ \end{array} }\right] \tag{3}\\ f(v)=&\eta \cdot \frac {1}{\sqrt {2\pi }\cdot \sigma }\cdot e^{-\frac {(v-v_{avg})^{2}}{2\cdot \sigma ^{2}}}\tag{4}\end{align*}$$

TABLE 1 Correspondence Between State and Velocity

In order to avoid contact and collision, the pedestrian will slow down and maintain a certain distance when he faced with the nearest obstacle in the current direction [41]. The change in walking step size $v_{i}$ under normal walking situations is given by formula (5). $$\begin{equation*} v_{i}=min\left({v_{m},v_{eds},\frac {d}{\tau }}\right)\tag{5}\end{equation*}$$ where $v_{m}$ represents the speed value selected by the pedestrian state and the truncated Gaussian function and $v_{eds}$ is the desired speed. $d$ represents the longest distance which the pedestrian can walk in current direction, and $\tau$ is the step time. We choose the minimum of these three speeds to ensure that pedestrians do not collide with other pedestrians or obstacles during movement.

C. Movement Steps

Under these rules, the steps of the pedestrian walk path are follows.

1. The initial state $S$ and the initial position $\vec {X_{i}}=(x_{i},y_{i})$ of the pedestrian are selected;

2. Every step time $\tau$ , based on current state and the state transition matrix, pedestrian state will have a transition. Then according to the truncated Gaussian function and the collision avoidance rules, the pedestrian will choose the speed of movement $v_{i}$ . According to the rules of heuristic method, the pedestrian will select its movement direction $\theta _{i}$ and continue to move;

3. Repeat step (2) until the pedestrian reaches the destination.

SECTION III. Simulation and Results

Microscopic behavior can lead to macroscopic phenomena. Complex collective dynamics of pedestrian movement often derive from the combination of simple actions. The Markov pedestrian model which this paper built can predict pedestrian walking path and then discover the crowd’s characteristics and collective phenomena in different scenes. But before that, it is necessary to verify the validity of the proposed model. We can conduct some computer simulations to measure pedestrian velocity and find velocity change in different situations, and collect experimental data to validate our model. As a commonly used strategy, the computer simulations is to compare with the famous collective phenomena or adjust the parameters and components of the models until a similar trend between the simulation results and the fundamental diagrams are satisfied [15]. In the following, we will introduce the simulation results of typical cases. And the simulation results are presented as the collective patterns of pedestrian motion and fundamental diagram. In the simulations, the length of the pedestrian field is 5 m, and the field view angle $2\varphi$ is 180 degrees, that is, the pedestrian field is a semicircle. Given that the average step rate is 2 steps/s at walking pace [32], the step time is set to half a second. The desired speed is set to 1.8m/s according to Weidmann [44].

A. Validation of the Model

In order to improve the accuracy of the model, we test it in the context of simple interaction situations involving two pedestrians avoiding each other and compare the walking trajectory with the experiment data from Ref [30]. In Ref [30], the experiment corridor was 7.88 m long and 1.75 m wide to record the trajectories of this subjects. We made the simulation under the same conditions. One person is stationary in the middle of the corridor and the other moves from the left side to the right side and has to evade the standing person. In the process of obstacle avoidance, the walking path of the pedestrian is observed when $N$ takes different values (The direction which the pedestrian can walk in his vision). We can also obtain that the predicted path (black line) by our model lies within the standard deviation (blue dashed lines) of the real human paths [30] when the value of $N$ is from 3 to 20. Some of these results are shown in Fig.4(a)–(c). By comparison, when the value of $N$ is 17, the movement trajectory is most accurate to allow pedestrians to avoid other pedestrian or obstacle. Therefore, in the following simulation experiments, this value is chosen as the division value of pedestrian visual field.

FIGURE 4.

The effect of N on the pedestrian path. (a) N = 16. (b) N = 17. (c) N = 18.

A $4\,\,\text {m} \times 20$ m hallway scenario, see Fig. 5, is designed to measure the speed-density and flow-density relationship of unidirectional pedestrian flow. Pedestrians enter the corridor at the ends of left side at random positions with the flow of randomly generated 2 to 5 persons per second. A measurement section of $4\,\,\text {m} \times 4$ m representing with green solid box is set in the center of the hallway. The global density of the hallway is controlled by adjusting the state transition matrix, and the number of pedestrians in hallway is varied from 20 to 135. A fixed number of pedestrians with random directions and velocities are scattered in the hallway without overlapping each other. We use the measurement methods presented in the references. The average velocity $v$ and the density $\rho$ of pedestrian $n$ are obtained at a time interval. Through constant adjustment of the state transition matrix, the flow-density or velocity-density diagram obtained in the experiment is consistent with the experiment data. After analyzing the experimental data, the relationship of speed-density expressed by bright red stars are shown in Fig.6. And the measured results for the fundamental diagram of density against specific flow (bright red stars) are shown in Fig.7. We can also observe that the basic diagrams given by Weidmann [44], Helbing et al. [10], and Mri and Tsukaguchi [27] who all use the empirical measurements to describe the movement of pedestrians. From the two figures we can find that when the density is less than 1, pedestrians can move at a free speed because of the enough space and minor effects of other pedestrians and obstacles. Thus, the crowd almost kept stationary state when population density exceeds the critical range.

FIGURE 5.

Snapshots of unidirectional flow.

FIGURE 6.

Measured speed-density relationship contrasting with experimental results.

FIGURE 7.

Measured speed-flow relationship contrasting with experimental results.

The state transition matrix can also be obtained through constantly adjusting the parameters. In our model, the state of pedestrians is restricted by the environment, so three different state transition matrices are applied, and according to the real-time environment, pedestrian will decide which state transfer matrix to be used according to the population density within the scope of vision domain. When the population density is less than $1~p/m^{2}$ (people per square meter), the state transition matrix shown in formula (6) is used. When the density is greater than or equal to $1~p/m^{2}$ and less than 3.5 $p/m^{2}$ , the state transition matrix shown in formula (7) is used. When the population density is greater than or equal to 3.5 $p/m^{2}$ , we use the state transition matrix shown in formula (8). $$\begin{align*} P_{1}=&\left [{ \begin{array}{cccc} 0.1 & 0.9 & 0 & 0 \\ 0.1 & 0.3 & 0.6 & 0 \\ 0 & 0.1 & 0.8 & 0.1 \\ 0 & 0.05 & 0.15 & 0.8 \\ \end{array} }\right] \tag{6}\\ P=&\left [{ \begin{array}{cccc} 0.1 & 0.9 & 0 & 0 \\ 0.1 & 0.8 & 0.1 & 0 \\ 0 & 0.15 & 0.8 & 0.05 \\ 0 & 0.35 & 0.6 & 0.05 \\ \end{array} }\right] \tag{7}\\ P=&\left [{ \begin{array}{cccc} 0.8 & 0.2 & 0 & 0 \\ 0.15 & 0.8 & 0.05 & 0 \\ 0 & 0.9 & 0.05 & 0.05 \\ 0 & 0.9 & 0.05 & 0.05 \\ \end{array} }\right]\tag{8}\end{align*}$$

B. Simulations of Pedestrian Evacuation

In the past few decades, more and more attention has been paid to the personal safety of the people at the time of emergency evacuation. Pedestrian evacuation has become an meaningful and important societal issue. In this study, we use the established Markov pedestrian model to predict the pedestrian evacuation process, and observe the phenomenon in the process of evacuation. Data of the pedestrian flow can also be analyzed and obtained. The scenario is a square room of size $15\,\,\text {m} \times 15$ m with an exit which wide is 1 m. This standard is the same with the adoption by Helbing et al. [12]. The exit is located at the middle position of the east wall. Pedestrians are assumed to be scattered in a random positions without overlap between each other. The initial state of the pedestrian is randomly selected from four states and the pedestrian target direction for export.

From the observation, the whole evacuation process can be divided into three stages. Fig.8(a)–(c) display the snapshots of the crowd evacuation initially with 60 pedestrians at time step 10, 40 and 160 respectively. In the first stage of the evacuation, the pedestrians move from the initial position to the target point, the density of the crowd in the room is lower, and the pedestrian state is mostly in state $S_{3}$ and state $S_{4}$ . At this two states, pedestrians have a greater speed than other states. By the middle stage of the evacuation, most of the people gather at the door with the arching and clogging of crowd occurs, and only a few pedestrians who approach the exit have enough space through the export. At this time, the pedestrian is mainly in state $S_{1}$ and state $S_{2}$ . The speed of the pedestrians is very low. By the last stage of the evacuation, most pedestrians have passed through the bottleneck, leaving only a few pedestrians remaining in the room. Compared with the middle stage of the evacuation, the density becomes smaller, most pedestrians are in state $S_{2}$ and state $S_{3}$ . Fig.9 shows that the variation of the number of people in the room with the evacuation time. We can find that in the early stage of the evacuation, the evacuation rate is relatively fast. When it got to the middle stage, a large number of pedestrians gathered together at the doorway, so the evacuation rate slowed down. But at the later stage, with the decrease of the number of pedestrians in the room, evacuation rate increases again.

FIGURE 8.

Snapshots of crowd evacuation.

FIGURE 9.

The number of people in the room over time.

After observing the pedestrian flow phenomenon which is obtained by the evacuation experiments of the Markov pedestrian model, and analyzing the data as well as comparing with empirical data, we can find that the Markov pedestrian model can reproduce the evacuation path of the real pedestrian very well.

C. Simulation of Bidirectional Pedestrian Flow

As a most common traffic-organization form, the bidirectional pedestrian flow is more complex than unidirectional pedestrian flow because of its complicated interactions and head-on conflicts between counter pedestrians. Understanding the characteristics of bidirectional pedestrian flow is very important to improve the efficiency of emergency evacuation and transport infrastructure.

A simulation of bidirectional pedestrian flow is presented in Fig.10(a)–(c), which shows the results of a simulation with a corridor which wide is 4 m and long is 20 m. Pedestrians enter the corridor at the ends of each side in random positions with the flow of randomly generated 1 to 3 persons per second. Those intending to walk from the left side to the right side are represented by red hollow circle, whereas pedestrians intending to move into the opposite direction are represented by blue solid circle. The model uses periodic boundary conditions, that is, if pedestrians cross the hallway from left to right, and reenter the hallway from left-hand boundary once they exited from the right-hand boundary. Pedestrians who are walking to the left are treated in the same way. In our model, the pedestrian will choose the proper route to avoid collision with others at a suitable by selecting different states.

FIGURE 10.

Snapshot of bidirectional flow.

As shown in Fig.10(a)–(c), three simulation results are obtained. Fig.10(a) is the early stage of the simulation, it can be seen that there is a clear lane formation phenomenon, which is a typical characteristic feature of complex, self-organizing pedestrian system. Fig.10(b) is the middle stage of the simulation, the right line of the people are mainly distributed in two ends of the corridor, while the left pedestrian is mainly distributed in the middle of the corridor. As the simulation continuing, Fig.10(c) is the latest stage of the simulation, pedestrians in different directions are moved to both sides of the corridor. After several tests, we found that in the later stage of the experiment, the probability of one-way pedestrians moving to the upper or lower side of the channel is equal, so this is also consistent with the stratification of pedestrians in real scene flow.

Remark 1:

The most advantage of Markovian jump approach method is to speed up the simulation, which is very important problem in analysis and simulation of pedestrian dynamics.

SECTION IV. Conclusion

In this paper, by describing the selection mechanism of the pedestrian’s speed and direction, and combining vision domain of the pedestrian, a micro-Markov pedestrian model based on heuristic method is built. Through simulation experiments, a series of self-organization phenomena of pedestrian flow are obtained, including the arching and clogging phenomenon and the lane formation phenomenon. According to the analysis of the data which are obtained in the simulation process, we get the fundamental flow-density and velocity-density diagram. The correctness of the model is verified by comparing the simulation data with the experiment data.

Compared with some existing pedestrian models, Markov random walk model has its own advantages. First of all, the model is continuous in space, the speed and the direction of pedestrians are selected by different methods, which makes the walking path of pedestrians more realistic. Secondly, pedestrian walking behavior is divided into four different states, and pedestrian will use the state transition matrix and a collision avoidance rules to choose the speed of walking. This fully reflects the randomness of pedestrians in the process of movement. Thirdly, the pedestrian can make full use of the perceptual information obtained in the field of view and make the best choice, which can intelligently detour the obstacle appearing in the visual field. Finally, the model is discrete in time, so it is computationally efficient in the simulation process.