# A Generalized Dynamic Potential Energy Model for Multiagent Path Planning

Authors: Liu He; Haoning Xi; Tangyi Guo; Kun Tang
Journal: Journal of Advanced Transportation
 (2020)

---

## Abstract

Path planning for the multiagent, which is generally based on the artificial potential energy field, reflects the decision-making process of pedestrian walking and has great importance on the field multiagent system. In this paper, after setting the spatial-temporal simulation environment with large cells and small time segments based on the disaggregation decision theory of the multiagent, we establish a generalized dynamic potential energy model (DPEM) for the multiagent through four steps: (1) construct the space energy field with the improved Dijkstra algorithm, and obtain the fitting functions to reflect the relationship between speed decline rate and space occupancy of the agent through empirical cross experiments. (2) Construct the delay potential energy field based on the judgement and psychological changes of the multiagent in the situations where the other pedestrians have occupied the bottleneck cell. (3) Construct the waiting potential energy field based on the characteristics of the multiagent, such as dissipation and enhancement. (4) Obtain the generalized dynamic potential energy field by superposing the space potential energy field, delay potential energy field, and waiting potential energy field all together. Moreover, a case study is conducted to verify the feasibility and effectiveness of the dynamic potential energy model. The results also indicate that each agent’s path planning decision such as forward, waiting, and detour in the multiagent system is related to their individual characters and environmental factors. Overall, this study could help improve the efficiency of pedestrian traffic, optimize the walking space, and improve the performance of pedestrians in the multiagent system.


---

## Body

## 1. Introduction

Multiagent system used in the simulation reflects the psychological and physical properties of pedestrians. Walking is a hot topic in traffic research in recent years [1]. Walking is a sustainable mode in transportation with little space, no resource consumption, and no environmental pollution [2]. A growing number of recent studies have focused on improving the sustainability of transportation systems by routinely converting motorized travel to walking [3]. With the general change of the concept from vehicle-oriented to people-oriented traffic, related studies on pedestrian traffic are gradually increasing. In order to identify effective strategies for improving the efficiency of pedestrians in a multiagent system, planners need to identify how the current personal characters affect walking in transportation. Literature studies [1–4] conducted quantitative analysis to optimize the walking space. Literature studies [5–7] analysed the importance and effectiveness of walking in transportation through empirical case studies and system simulations. Eady and Burtt investigated the role of walking and access to suburban shopping centres will affect people traveling around Melbourne [5]. Bangcheng et al. considered the stability of the walking system and the rationality of its structural design in the study of dynamics for a humanoid robot [6]. Yamazaki et al. proposed an evacuating agent walking model and the estimated distribution of the evacuation based on the real evacuation data [7].Existing quantitative research on pedestrian traffic mainly focuses on system simulation, which can be divided into discrete and continuous models. Cellular automaton (CA) [8] model is a type of discrete model, which divides pedestrian walking areas into cells. Social force model is a type of continuous model, which defines pedestrians in a continuous space and describes the pedestrians’ behaviours through various forces. Both models are easy to understand, but cannot reflect the difference among individual characteristics of pedestrians. Dynamic pedestrian planning is the core of pedestrian simulation, and the main method of path planning is to establish a potential energy field [9]. The robot moves in the gradient direction, in which the potential energy drops fastest to avoid obstacles. Deepak Subramani and Lermusiaux combined the decision theory with the essential stochastic time-optimal path planning to establish the uncertain, strong, and dynamic risk-optimal path planning scheme based on partial differential equations [10]. Antonio Sedeño-noda and Colebrook extended the Dijkstra algorithm to the two-objective shortest path problem [11]. Rui Song et al. established a smooth A ∗ model for path planning of unmanned vehicles (UVs) [12]. Prahlad et al. combined the genetic algorithm with the global search function and the artificial potential energy field to construct the EAPF (evolutionary artificial potential field) algorithm; this method is affected by the population number and algebra of the genetic algorithm. The operation efficiency is low [13]. Ulises Orozco-Rosas et al. constructed a membrane evolution potential energy field based on a multiprocessor, which improves the computational efficiency of robot path planning [14]. Deepak N. Subramani et al. addressed the optimal path planning problem in a stochastic dynamic environment by combinatorial decision-making and time optimization theory [10], ant colony algorithm [15], simulated annealing method [16], firefly algorithm [17], and Q-learning [18]. The studies mentioned above mainly focus on the optimal path planning in various dynamic scenes under certain perceptual conditions from the view of system control, and they are not suitable for pedestrian simulation with physiological, psychological, and social uncertainties.Pieces of research on pedestrian path planning in the multiagent system belong to the artificial intelligence field. Multiagent system is composed of multiple interacting elements, known as agents. They can decide how to satisfy their objectives and interact with other agents by engaging in analogues of the kind of social activity: cooperation, coordination, and negotiation [19]. Since Kinny et al. introduced the multiagent into the air traffic control system [20], the multiagent has been a research focus in the field of transportation. Compared with vehicles, pedestrians have the characteristics of blindness (blindness means when the crowd is highly concentrated, especially when the situation is unclear, the pedestrian tends to follow the crowd blindly due to the herd mentality), purpose (purpose means when pedestrians have a clear destination, they will care about facilities, guidance systems, etc., so as to arrive as soon as possible; otherwise, it is easier to be attracted by the surrounding environmental factors), randomness, commonality, and so on, Hence, it is very important to highlight the process of independent decision-making and group game in path planning in a multiagent system. These research studies proposed several prototype techniques for agent systems in transportation management, including methodologies for agent-oriented analysis and design, formal specification and verification methods for agent systems, and techniques for implementing agent specifications [21–23].Existing studies only analyze the speed characteristics of pedestrian flow in the multiagent system [24–27] or study the large-scale macrocollection and distribution capacity of pedestrians [28–30]. Few research studies focus on the mechanism of path planning for the multiagent at mesolevel and consider different factors such as gender and luggage. Moreover, the deadlock problem always arises in traditional cellular automata simulations. In order to fill in these research gaps, this paper constructed the generalized dynamic potential energy field with large cells and small time segments to improve the discrete artificial potential energy field.To the best of the author’s knowledge, few studies establish a dynamic simulation model at the mesolevel to reflect the personal characteristics of each individual in a multiagent system. Hence, based on the disaggregation characteristics of the multiagent system, we establish a generalized dynamic potential energy model (DPEM) efficiently and accurately at mesolevel to strengthen the disaggregation characteristic of the multiagent system and reflect the characteristics such as gender and carry-on luggage by considering the characteristics of each individual as key parameters. The results of the case study validate the effectiveness of the proposed dynamic potential energy model (DPEM) and indicate that each agent’s path planning decision such as forward, waiting, and detour in the multiagent system is related to their characters and environmental factors.The rest of the paper is organized as follows: Section2 presents the procedure of establishing a generalized dynamic penitential energy model (DPEM) through 4 steps. Section 3 conducts a case study to illustrate the feasibility and effectiveness of the proposed DPEM. Section 4 concludes with a summary of main findings in this research and suggestions for future study.


## 2. Methodology

### 2.1. Notations and Preliminaries

Table1 summarizes the parameters, variables, and abbreviations used in this paper to describe the mathematical models.Table 1
Parameters, variables, and abbreviations.
qThe ID of an agent(i,j)The location of the cellkTime step of simulationdirThe direction of the agent walking aheadtkTime ofkth time stepτijρq,μThe velocity decline of agentq with space occupation ρ walking through the cell with μρSpace occupation by the agentGdirThe distance to the adjacent cell by direction dirμSpace occupied by the obstacleαqThe waiting potential energy dissipation coefficient of agentqΔμChange rate ofμ during a time stepβqThe waiting potential energy enhancement coefficient of agentqvqThe expected speed of agentq.VijqSpace potential energy of agentq in cell (i,j)SOStationary obstacleTijq,tkDelay potential energy of agentq in cell (i,j) at tkMGMale groupWijq,tkWaiting potential energy of agentq in cell (i,j) at tkFGFemale groupUijq,tkGeneralized dynamic potential energy of agentq in cell (i,j) at tkA pedestrian in the simulation system can be regarded as a multiagent; HCM2010 defines a pedestrian as an ellipse of 0.46 m×0.61 m, with a contact area of 0.28 m2 and a noncontact area of 0.66 m2. In Figure 1, we measured the space occupancy of pedestrians of different genders in five states of luggage: none, carry a bag, carry a knapsack, suitcase (stationary), and suitcase (moving). To simplify the model, the pedestrians defined in this paper do not include the elderly and children.Figure 1
Pedestrians of different genders in five states of luggage.In CA models, the length of a cell is 0.1 m to 0.5 m. Whether the cell is occupied by a pedestrian or obstacles is denoted as a {0, 1} variable. In this paper, the length of the cell is set as 0.8 m, which is larger than the normal cell defined in CA models, and a cell can accommodate multiple pedestrians or obstacles according to its space occupancy. The pedestrian space of pedestrians is shown in Table2.Table 2
Space occupancy of different pedestrians.
GenderLuggageWidth (m)Distance (m)Area (m2)Space occupancy (ρ) (%)MaleNone0.550.40.1727Carry a bag0.60.450.2133Carry a knapsack0.550.50.2234Suitcase (stationary)0.80.50.3148Suitcase (moving)0.80.950.6094FemaleNone0.450.30.1117Carry a bag0.550.40.1727Carry a knapsack0.450.40.1422Suitcase (stationary)0.750.50.2945Suitcase (moving)0.750.950.5688In the discrete simulation models, an agent can only reach the cells in his neighbourhood; this paper chooses the Moore neighbourhood and assumes that pedestrians can only reach one of the eight adjacent directional cells.According to the relevant literature, the pedestrian walking speed is between 0.4 m/s and 1.4 m/s [31]. So, it took 0.6 s∼2 s for a cell to reach its adjacent vertical cell and 0.8 s∼2.8 s to the oblique adjacent cell. Therefore, the simulation time step of the model is set as the maximum common divisor: 0.2 s. The actual walking time between the cell is commonly determined by the speed of the pedestrian and the number of rows in the cell. In this paper, we focus on a new type of cell, whose length is set as 0.8 m and time step is set as 0.2 s, and is vividly defined as the “pancake cell.”


### 2.2. Problem Description

Walking is a dynamic process of pedestrian path-planning decisions and displacements. Ideally, pedestrians determine their forward direction based on the shortest distance or time while avoiding other pedestrians and obstacles. Figure2(a) shows an agent’s walking area, in which the yellow part is an isolation bar. There is a gap (11, 13) on the west side of the isolation bar, which is the bottleneck of the pedestrian flow [32]. An agent travels from the (2, 2) to the blue cell (24, 8). During walking, gap (10, 13) is temporarily occupied by other agents. According to the path planning principle , the agent falls into the local minimum point of the artificial potential field. At this point, the agent faces three options:(a)
Delay: if the delay time is much lower than the detour time, the agent will wait and increase the delay time in the obstacle cell(b)
Detour: if the delay time is larger than the detour time, the agent will change other routes(c)
Waiting: an agent will wait in place for a certain period before reselectionFigure 2
Static artificial potential energy field and walking trajectory.
(a)(b)(c)Therefore, the dynamic potential energy model (DPEM) for the local minimum problem should reflect three characteristics: (1) an agent will make choices among delay detour and waiting; (2) an agent will jump out once he falls into the local minimum; and (3) an agent will not return back after jumping out of the local minimum cell. The effect of delay and waiting cost should be considered besides the static space in the potential energy field.


### 2.3. Model Formulation

In order to reflect the actual behaviours of pedestrians such as delay, detour, and waiting, we obtain the generalized dynamic potential energy by superimposing the delay potential energy, waiting potential energy, and static space potential energy all together. Then, we investigate the functional relationship between individual attributes and potential energy of the multiagent to reflect pedestrians’ different decisions for path planning.


#### 2.3.1. Space Potential Energy

In the space potential energy fieldV, the spatial potential energy is determined by the distance from the current position to the destination. Since the space potential energy is only related to the Euclidean distance and is static, it is called the static space potential energy.Consider the path planning problem of the multiagent to multidestinations; if there arem agent origins from different cellsOi,i∈m, to the destination cell Dj, j∈n, the traditional path search algorithm will calculate m×n times in each time step. In order to improve the computational efficiency, we can start from the destination set D to search the cells in all possible directions and record the distance to any cell.In each step, when pedestrians update the current cell coordinates, at least one cell that is nearer to the destination can be found in the neighbourhood. Pedestrians will choose the nearest one as the forward direction and finally reach the nearest cell in the destination set. Since all of the points in this region are search targets, the number of searches is fixed, and the Dijkstra algorithm can be improved directly.Here is the procedure of the improved Dijkstra algorithm:(i)
Step 1: set all cells which meetμ>1−ρ to be −1, and the others have no potential energy.(ii)
Step 2: traverse all the cells to find the cellb satisfying the following conditions:Cellb has no potential energy; there is at least one cell with positive potential energy in the neighbourhood of the cell. The two cells are connectable. The cell is assigned a temporary valueV^b=Va+Gab, where Vais the potential energy of the adjacent cell and Gab is the distance between two adjacent cells, whose value is 1 or 1.414. If there is more than one cell in the neighbourhood which satisfies the above conditions, choose a smaller value, namely, V^b=minVai+Gaib,i=1,2,…,8; then, all the satisfied cells will create a set {B}.(iii)
Step 3: replace the potential energy value with the smallest temporary value inB, Vb=V^b.(iv)
Step 4: if all the cells have potential energy, end; otherwise, return to Step 2.The simulation process of the improved Dijkstra algorithm is shown in Figure3.Figure 3
Flowchart of the improved Dijkstra algorithm.Here, we consider a case where an agent will walk from the upper left corner to the lower right corner. Figure2(b) displays the distribution of the static potential energy field, where blue colour represents the lower potential energy value and red colour represents the higher value. Figure 2(c) displays the potential energy and walking trajectory of an agent.


#### 2.3.2. Delay Potential Energy

(1) Obstacle Delay Function. The open space cell has no constraints on an agent’s walking path choice; an agent can enter from any direction in the open space cell and walk through with the desired speed, and thus, the initial space occupancy of an open space cell is zero. Moreover, the obstacles such as walls, foundation columns, isolation bars, and other pedestrians have impacts on an agent’s path choice. The agent will initiatively stay away from the walls, bypass the columns and facilities, and keep their distance from each other. From the perspective of the space occupation of the cell, the walking environment can be divided into four categories.In Table3, ρ and μ represent the space occupancy of an agent and obstacle, respectively. The cell with no obstacles does not occupy space and has no effects on path planning of the agent. The complete obstacle cell is repulsive to the agent from any direction. A channelized obstacle, such as an isolation bar, is considered to be at the edge of a specified direction of the cell to prevent an agent from walking toward in the specified direction, but there are no constraints on pedestrians in other directions.Table 3
Obstacle classification.
TypeSpace occupationμImpact on the cellExampleNo obstacleμ=0NoneOpen spaceComplete obstacleμ≥1−ρPrevents entry from any directionWallsCanalized obstacleμ=0Prevents entry from a particular directionIsolation barPartial obstacle0<μ<1−ρSlows down the walking speedDustbinThe delay potential energy reflects the time consumption of pedestrians while passing through the cell. In this paper, a continuous variableμ∈ [0, 1] is used to indicate whether the cell is occupied or not, instead of 0-1 variables in the traditional methods. When an agent with a body size of ρ walks through a cell occupying the space of μ, there will be delays due to lateral avoidance. Delays are affected by the following two factors: (1) the “body type” of an agent is determined by the gender and the number of carry-on luggage; (2) the space occupation of the cell.Then, a cross-observation experiment is carried out to explore the regulation of speed decline rate. 40 student participants from the author’s college were evenly divided into two groups by gender. Place cone buckets of different sizes or stand on other participant groups to change the occupancy of the cell every time. Each group of participants is required to carry different luggage through the cell in turn. Record the time consumed by each participant from entering to leaving the cell. Divide the time passed by empty hands by the time passed by this round to get the speed decline rate. If the participant cannot pass the cell, it is set as 0. Table4 shows the results of the experiment.Table 4
Relationship between speed decline rate and space occupation.
SexLuggageρ (%)Obstacle typeObstacle occupationμ0%10%20%30%40%50%60%70%80%90%100%MaleNone27Stationary obstacle (SO)100%98%95%84%76%61%40%10%1%0%0%Bag33100%93%90%78%67%52%21%3%1%0%0%Knapsack34100%95%91%80%71%57%33%7%1%0%0%Suitcase94100%61%24%11%3%2%0%0%0%0%0%FemaleNone17100%96%90%81%72%54%35%12%2%0%0%Bag27100%92%88%75%62%47%15%2%0%0%0%Knapsack22100%94%86%78%65%50%22%3%1%0%0%Suitcase88100%35%5%2%1%1%0%0%0%0%0%MaleNone27Male group (MG)100%95%88%75%63%49%33%10%3%1%0%Bag33100%90%80%69%54%38%15%5%2%0%0%Knapsack34100%91%82%71%58%42%20%6%2%0%0%Suitcase94100%40%12%5%2%1%1%0%0%0%0%FemaleNone17100%90%78%47%21%7%2%0%0%0%0%Bag27100%85%70%41%18%5%1%0%0%0%0%Knapsack22100%88%72%42%18%6%1%0%0%0%0%Suitcase88100%40%10%5%4%3%2%1%0%0%0%MaleNone27Female group (FG)100%95%87%69%47%30%8%0%0%0%0%Bag33100%92%82%60%38%15%5%0%0%0%0%Knapsack34100%92%83%65%41%15%2%0%0%0%0%Suitcase94100%33%8%5%3%0%0%0%0%0%0%FemaleNone17100%94%82%72%54%41%30%12%5%0%0%Bag27100%88%75%58%41%29%12%2%1%0%0%Knapsack22100%88%76%60%43%32%18%2%1%0%0%Suitcase88100%35%10%3%2%1%0%0%0%0%0%Through increasing the space occupation of the obstacles from 0% to 100%, the functional relationship between speed decline rate and space occupation for both males and females is fitted and shown in Figure4.Figure 4
Experimental curve of speed drop and space occupation.
(a)(b)(c)(d)(e)(f)The experimental results (Figure4) show that the speed decline rate decreases with the obstacle occupancy (μ) for the agent with different occupancy (ρ). If μ+ρ⟶1, the rate of speed decline rate will dramatically increase. Different types of obstacles have different impacts on the speed of the agent, among which the stationary obstacle has the least impact on obstacles. Through the experimental observation, a male agent has a higher spatial tolerance to obstacles and can adjust their posture and luggage position more flexibly to get through obstacles quickly. As a result, although the value of ρ for the male agent is larger than that for the female agent, the speed of a male agent is less affected by obstacles compared with that of the female agent. Moreover, since the space of the agent with a suitcase is more flexible, it is possible for the agent to walk through the cell when μ+ρ>1.Figure5 displays the curve ofτ for male and female agents, and the fitting formulas of the velocity decline rate τρ,μ for the male agent are given as(1)τρ,μ=1,μ=0,0,ρ+μ≥1,−1.452ρ+μ2+0.5893ρ+μ+1,type=SO,ρ+μ<1,−1.297ρ+μ2+0.343ρ+μ+1,type=MG,ρ+μ<1,−1.616ρ+μ2+0.4191ρ+μ+1,type=FG,ρ+μ<1.Figure 5
Fitting curve ofτ. (a) The relationship between speed decline rate (τ) and (b) space occupation μ+ρ) for male and female agents, respectively.
(a)(b)The fitting formulas of the velocity decline rateτρ,μ for the female agent are given as(2)τρ,μ=1,μ=0,0,ρ+μ≥1,−1.1947ρ+μ2+0.1656ρ+μ+1,type=SO,ρ+μ<1,−0.795lnρ+μ−0.0748,type=MG,ρ+μ<1,−0.6275ρ+μ2−0.3902ρ+μ+1,type=FG,ρ+μ<1.As shown in Figure5, all five curves had R2 fitting values greater than 0.9, except for the curve representing women crossing the male group (MG), and this may be because women are more repelled by the opposite gender. Therefore, the time that the agent reaches any adjacent cell can be expressed as(3)Tijq=Gdirvqτijρq,μ,where Gdir represents the distance to the adjacent cell and is related to the direction of the agent and vq denotes the expected speed of agent q.(2) Delay Potential Energy Function. The static potential energy value is determined by the spatial distance between the cell and the destination. The pedestrian chooses the cell with the lower potential energy value, which is closer to the destination. Assuming that the pedestrians will walk at the expected speed, the shortest path is considered both the shortest distance and time to unify the time and space.After considering the influence of obstacles, the actual speed of the agent is gradually lower than the expected speed, and the relationship between walking distance and time is nonlinear (Figure6). In this case, shortening the walking distance will increase the time, the agent needs to walk for more distance to save the time, and thus, the multipath problem will arise. Therefore, the microscopic path-planning problem can be transformed into a multiobjective optimization problem considering the influence of partial obstacles. There are two methods to solve the multiobjective problem: (1) to transform the multiobjective problem into a single objective problem by weighting; (2) to solve the problem based on the Pareto optimal solutions, such as data envelopment analysis (DEA) and heuristic algorithm. Since the two objectives of time and space distance can be converted through velocity, the first method is adopted in this paper.Figure 6
Relationship between time and walking distance.The agent often makes different choices on the time and space distance. From experience, the agent in a hurry will choose the most time-saving path, while others will choose a relatively short path. We explain this phenomenon as the “degree of laziness,” and the generalized potential energy of the agent is that spatial distance and time are weighted by “laziness coefficient.” The weighting factor of the distance is larger for the “lazier” agent, and the weighting factor of the time is larger for the diligent agent, so the spatial potential energy can be transformed into the generalized potential energy. In this way, the choice of path for the agent is more objective and diverse.Then, we explain the “laziness coefficient” from the view of opportunity cost, where the difference lies in the value of time (VOT) of the agent. Moreover, the opportunity cost of time is reflected by the maximum distance that the agent can walk during the delayed time period.Thus, waiting potential energyTijq can be expressed as(4)Tijq=Gdirτijρq,μvq−Gdirvqvq=1−τijρq,μτijρq,μGdir,where vq represents the expected speed of agent q and τijρq,μ represents the coefficient of the velocity decline rate for the partial obstacle in the cell i,j.


#### 2.3.3. Waiting Potential Energy

Since the agent will lose patience and choose other paths after waiting if other pedestrians have occupied the target cell, the waiting potential energy is introduced in this paper. The waiting potential energy is affected by the characteristics of the agent and changes with time and has two opposite characteristics of dissipation and enhancement.(1) Dissipation. If the pedestrian has left the cell i,j, the waiting potential energy W will dissipate over time. At first, the agent still remembers that he has passed through the cell i,j, and thus, the waiting potential energy can keep pedestrians from returning. When the waiting potential energy dissipates to 0, the agent will forget whether he has passed through the cell.When agentq leaves the cell i,j at t0, the waiting potential energy of the cell i,j can be expressed as Wijq,tkafter k simulation time steps:(5)Wijq,tk=αqWijq,tk−1=αq2Wijq,tk−2=αqkWq,t0,0<αq<1,where Wq,t0 is the basic waiting potential energy and αq is the waiting potential energy dissipation coefficient of agent q. The smaller αq is, the faster the waiting potential energy will dissipate.The waiting potential energyWq,tk is mainly affected by three variables: basic waiting potential energy Wq,t0, dissipation coefficient αq, and enhancement coefficient βq.If the agent waits for a time step, he will give up the movement during this time step at the expected speed, and this is also defined as the opportunity cost:(6)Wq,t0=0.2⋅vqtk.The dissipation coefficientαq reflects the perception of the agent. If αq⟶1, it will dissipate slowly, and it is impossible for the agent to return. If αq⟶0, the agent will return to the same local minimum cell and fall into a dead cycle. From this point of view, αq should be as large as possible. However, the local minimum of the cell may disappear after a short period; since the agent blocking at the door will leave, it will take a long time for the agent to return. Therefore, the dissipation coefficient also reflects how far the agent is willing to search after falling into a local minimum and successfully jumping out. According to observation experiments, the interval between pedestrian path-planning decisions is about 1 second, and it is related to the gender, age, and luggage of the agent. To simplify the model, let αq=0.9; after 1 second (5 time steps), the waiting potential energy can be reduced to the original 0.95=0.59 times, namely, it will dissipate at a rate of 60% per second.(2) Enhancement. If the agent stays in the cell i,j, the waiting potential energy W will increase over time, and the agent will wait before falling into a local minimum. The longer the waiting time is, the greater the waiting potential energy of the cell will be. When the superimposed potential energy of the cell is higher than that of other cells in the neighbourhood, the agent will successfully jump out of the local minimum. On the contrary, after jumping out of the local minimum, the waiting potential energy of the cell is large and dissipates slowly, so pedestrians will not return in a short time. When pedestrian q enters and stays in the cell i,j at t0, after k simulation time steps, the waiting potential energy of the cell i,j is expressed as(7)Wijq,tk=βqWijq,tk−1+Wijq,t0=1−βqk+11−βqWq,t0,βq>1,kWq,t0,βq=1,where βq is the waiting potential energy enhancement coefficient of agent q. The larger value of βq represents that the agent is reluctant to wait. When βq = 1, the waiting potential energy increases linearly with time; when βq > 1, the longer the pedestrians wait, the faster the waiting potential energy increases. When the total potential energy of the superimposed cell is greater than that of the neighbourhood cell, pedestrians successfully jump out of the local minimum. This can also reflect the process that pedestrians gradually lose patience and look for other paths after waiting for a period.The enhancement coefficientβq reflects the patience of the agent. The lower value of the coefficient means that the agent is more patient. The decisive factor of βq is the agent’s judgement on velocity decline rate of the occupation in the bottleneck cell, which is also related to the gender, age, and travel purpose of the agent. In order to simplify this model, it is assumed that βq is only related to the variation of occupation μ in the next time step.Impatient agent judges that the cell occupation of obstacles is constant and will leave at the next time step after jumping into the local minimum cell, and thus, whenΔμ=μtk+1−μtk=0, βq will reach the maximumβq=+∞. The patient agent thinks that the occupancy of the obstacle cell will be reduced to zero, and thus, when Δμ=μtk+1−μtk=μ, βqreaches the minimum value βq=1. Therefore, the logarithmic function can be established:(8)βq=lnμΔμ+1,μ≥Δμ.


#### 2.3.4. Generalized Dynamic Potential Energy

The generalized dynamic potential energyUijq,tkcan be obtained by superposing the space potential energyVijq, delay potential energy Tijq,tk, and waiting potential energy Wijq,tk. Moreover, three types of potential energy are unified by distance:(9)Uijq,tk=Vijq+Tijq,tk+Wijq,tk.The simulation process of the multiagent is shown in Table5 and Figure 7.Table 5
Simulation process of multiagent path planning.
StepDescription1Model initialization. Set the generation rate of the agent asαo and the number of agents as k.2Obtain the static spatial potential energy fieldV for destination set through the improved Dijkstra algorithm.3Generalize the delayed potential energy fieldT for all agents; set the potential energy field W = 0 and simulation time t=1.4Wait for the dissipation of potential energyW.5Set the agent number ask = 1.6Select thekth agent and jump to Step 13 if the agent has not departed or left the simulation area. Otherwise, move to Step 7.7If the agent is not waiting and the remaining time of the cell is greater than 0, then the remaining time will be −1, and jump to Step 13. Otherwise, move on to Step 8.8If the agent reaches the destination, set the agent waiting, subtract the space occupation of the agent from the space occupation of the cell; if the waiting potential energy fieldW becomes 0, then jump to Step 13; otherwise, move on to Step 9.9If the current time equals the initial entry time of the agent, strengthen the space occupation in the origin cell. Otherwise, if the direction of the agent is 1, the waiting potential energy will be strengthened.10Strengthen the basic waiting potential energy, and update 3 types of potential energy in all directions to obtain the generalized potential energyU by superposition.11Determine the target cell according to the cell probability selection model.12If the cell is a target cell, the agent will choose to stay, and set the agent waiting. Otherwise, update the direction and remaining time.13Ifk=K, move on to the next step. Otherwise,k=k+1, and return to Step 6.14Ift=tmax, end. Otherwise, t = t + 1, and return to Step 4.Figure 7
Flowchart of multiagent path planning.


## 2.1. Notations and Preliminaries

Table1 summarizes the parameters, variables, and abbreviations used in this paper to describe the mathematical models.Table 1
Parameters, variables, and abbreviations.
qThe ID of an agent(i,j)The location of the cellkTime step of simulationdirThe direction of the agent walking aheadtkTime ofkth time stepτijρq,μThe velocity decline of agentq with space occupation ρ walking through the cell with μρSpace occupation by the agentGdirThe distance to the adjacent cell by direction dirμSpace occupied by the obstacleαqThe waiting potential energy dissipation coefficient of agentqΔμChange rate ofμ during a time stepβqThe waiting potential energy enhancement coefficient of agentqvqThe expected speed of agentq.VijqSpace potential energy of agentq in cell (i,j)SOStationary obstacleTijq,tkDelay potential energy of agentq in cell (i,j) at tkMGMale groupWijq,tkWaiting potential energy of agentq in cell (i,j) at tkFGFemale groupUijq,tkGeneralized dynamic potential energy of agentq in cell (i,j) at tkA pedestrian in the simulation system can be regarded as a multiagent; HCM2010 defines a pedestrian as an ellipse of 0.46 m×0.61 m, with a contact area of 0.28 m2 and a noncontact area of 0.66 m2. In Figure 1, we measured the space occupancy of pedestrians of different genders in five states of luggage: none, carry a bag, carry a knapsack, suitcase (stationary), and suitcase (moving). To simplify the model, the pedestrians defined in this paper do not include the elderly and children.Figure 1
Pedestrians of different genders in five states of luggage.In CA models, the length of a cell is 0.1 m to 0.5 m. Whether the cell is occupied by a pedestrian or obstacles is denoted as a {0, 1} variable. In this paper, the length of the cell is set as 0.8 m, which is larger than the normal cell defined in CA models, and a cell can accommodate multiple pedestrians or obstacles according to its space occupancy. The pedestrian space of pedestrians is shown in Table2.Table 2
Space occupancy of different pedestrians.
GenderLuggageWidth (m)Distance (m)Area (m2)Space occupancy (ρ) (%)MaleNone0.550.40.1727Carry a bag0.60.450.2133Carry a knapsack0.550.50.2234Suitcase (stationary)0.80.50.3148Suitcase (moving)0.80.950.6094FemaleNone0.450.30.1117Carry a bag0.550.40.1727Carry a knapsack0.450.40.1422Suitcase (stationary)0.750.50.2945Suitcase (moving)0.750.950.5688In the discrete simulation models, an agent can only reach the cells in his neighbourhood; this paper chooses the Moore neighbourhood and assumes that pedestrians can only reach one of the eight adjacent directional cells.According to the relevant literature, the pedestrian walking speed is between 0.4 m/s and 1.4 m/s [31]. So, it took 0.6 s∼2 s for a cell to reach its adjacent vertical cell and 0.8 s∼2.8 s to the oblique adjacent cell. Therefore, the simulation time step of the model is set as the maximum common divisor: 0.2 s. The actual walking time between the cell is commonly determined by the speed of the pedestrian and the number of rows in the cell. In this paper, we focus on a new type of cell, whose length is set as 0.8 m and time step is set as 0.2 s, and is vividly defined as the “pancake cell.”


## 2.2. Problem Description

Walking is a dynamic process of pedestrian path-planning decisions and displacements. Ideally, pedestrians determine their forward direction based on the shortest distance or time while avoiding other pedestrians and obstacles. Figure2(a) shows an agent’s walking area, in which the yellow part is an isolation bar. There is a gap (11, 13) on the west side of the isolation bar, which is the bottleneck of the pedestrian flow [32]. An agent travels from the (2, 2) to the blue cell (24, 8). During walking, gap (10, 13) is temporarily occupied by other agents. According to the path planning principle , the agent falls into the local minimum point of the artificial potential field. At this point, the agent faces three options:(a)
Delay: if the delay time is much lower than the detour time, the agent will wait and increase the delay time in the obstacle cell(b)
Detour: if the delay time is larger than the detour time, the agent will change other routes(c)
Waiting: an agent will wait in place for a certain period before reselectionFigure 2
Static artificial potential energy field and walking trajectory.
(a)(b)(c)Therefore, the dynamic potential energy model (DPEM) for the local minimum problem should reflect three characteristics: (1) an agent will make choices among delay detour and waiting; (2) an agent will jump out once he falls into the local minimum; and (3) an agent will not return back after jumping out of the local minimum cell. The effect of delay and waiting cost should be considered besides the static space in the potential energy field.


## 2.3. Model Formulation

In order to reflect the actual behaviours of pedestrians such as delay, detour, and waiting, we obtain the generalized dynamic potential energy by superimposing the delay potential energy, waiting potential energy, and static space potential energy all together. Then, we investigate the functional relationship between individual attributes and potential energy of the multiagent to reflect pedestrians’ different decisions for path planning.


### 2.3.1. Space Potential Energy

In the space potential energy fieldV, the spatial potential energy is determined by the distance from the current position to the destination. Since the space potential energy is only related to the Euclidean distance and is static, it is called the static space potential energy.Consider the path planning problem of the multiagent to multidestinations; if there arem agent origins from different cellsOi,i∈m, to the destination cell Dj, j∈n, the traditional path search algorithm will calculate m×n times in each time step. In order to improve the computational efficiency, we can start from the destination set D to search the cells in all possible directions and record the distance to any cell.In each step, when pedestrians update the current cell coordinates, at least one cell that is nearer to the destination can be found in the neighbourhood. Pedestrians will choose the nearest one as the forward direction and finally reach the nearest cell in the destination set. Since all of the points in this region are search targets, the number of searches is fixed, and the Dijkstra algorithm can be improved directly.Here is the procedure of the improved Dijkstra algorithm:(i)
Step 1: set all cells which meetμ>1−ρ to be −1, and the others have no potential energy.(ii)
Step 2: traverse all the cells to find the cellb satisfying the following conditions:Cellb has no potential energy; there is at least one cell with positive potential energy in the neighbourhood of the cell. The two cells are connectable. The cell is assigned a temporary valueV^b=Va+Gab, where Vais the potential energy of the adjacent cell and Gab is the distance between two adjacent cells, whose value is 1 or 1.414. If there is more than one cell in the neighbourhood which satisfies the above conditions, choose a smaller value, namely, V^b=minVai+Gaib,i=1,2,…,8; then, all the satisfied cells will create a set {B}.(iii)
Step 3: replace the potential energy value with the smallest temporary value inB, Vb=V^b.(iv)
Step 4: if all the cells have potential energy, end; otherwise, return to Step 2.The simulation process of the improved Dijkstra algorithm is shown in Figure3.Figure 3
Flowchart of the improved Dijkstra algorithm.Here, we consider a case where an agent will walk from the upper left corner to the lower right corner. Figure2(b) displays the distribution of the static potential energy field, where blue colour represents the lower potential energy value and red colour represents the higher value. Figure 2(c) displays the potential energy and walking trajectory of an agent.


### 2.3.2. Delay Potential Energy

(1) Obstacle Delay Function. The open space cell has no constraints on an agent’s walking path choice; an agent can enter from any direction in the open space cell and walk through with the desired speed, and thus, the initial space occupancy of an open space cell is zero. Moreover, the obstacles such as walls, foundation columns, isolation bars, and other pedestrians have impacts on an agent’s path choice. The agent will initiatively stay away from the walls, bypass the columns and facilities, and keep their distance from each other. From the perspective of the space occupation of the cell, the walking environment can be divided into four categories.In Table3, ρ and μ represent the space occupancy of an agent and obstacle, respectively. The cell with no obstacles does not occupy space and has no effects on path planning of the agent. The complete obstacle cell is repulsive to the agent from any direction. A channelized obstacle, such as an isolation bar, is considered to be at the edge of a specified direction of the cell to prevent an agent from walking toward in the specified direction, but there are no constraints on pedestrians in other directions.Table 3
Obstacle classification.
TypeSpace occupationμImpact on the cellExampleNo obstacleμ=0NoneOpen spaceComplete obstacleμ≥1−ρPrevents entry from any directionWallsCanalized obstacleμ=0Prevents entry from a particular directionIsolation barPartial obstacle0<μ<1−ρSlows down the walking speedDustbinThe delay potential energy reflects the time consumption of pedestrians while passing through the cell. In this paper, a continuous variableμ∈ [0, 1] is used to indicate whether the cell is occupied or not, instead of 0-1 variables in the traditional methods. When an agent with a body size of ρ walks through a cell occupying the space of μ, there will be delays due to lateral avoidance. Delays are affected by the following two factors: (1) the “body type” of an agent is determined by the gender and the number of carry-on luggage; (2) the space occupation of the cell.Then, a cross-observation experiment is carried out to explore the regulation of speed decline rate. 40 student participants from the author’s college were evenly divided into two groups by gender. Place cone buckets of different sizes or stand on other participant groups to change the occupancy of the cell every time. Each group of participants is required to carry different luggage through the cell in turn. Record the time consumed by each participant from entering to leaving the cell. Divide the time passed by empty hands by the time passed by this round to get the speed decline rate. If the participant cannot pass the cell, it is set as 0. Table4 shows the results of the experiment.Table 4
Relationship between speed decline rate and space occupation.
SexLuggageρ (%)Obstacle typeObstacle occupationμ0%10%20%30%40%50%60%70%80%90%100%MaleNone27Stationary obstacle (SO)100%98%95%84%76%61%40%10%1%0%0%Bag33100%93%90%78%67%52%21%3%1%0%0%Knapsack34100%95%91%80%71%57%33%7%1%0%0%Suitcase94100%61%24%11%3%2%0%0%0%0%0%FemaleNone17100%96%90%81%72%54%35%12%2%0%0%Bag27100%92%88%75%62%47%15%2%0%0%0%Knapsack22100%94%86%78%65%50%22%3%1%0%0%Suitcase88100%35%5%2%1%1%0%0%0%0%0%MaleNone27Male group (MG)100%95%88%75%63%49%33%10%3%1%0%Bag33100%90%80%69%54%38%15%5%2%0%0%Knapsack34100%91%82%71%58%42%20%6%2%0%0%Suitcase94100%40%12%5%2%1%1%0%0%0%0%FemaleNone17100%90%78%47%21%7%2%0%0%0%0%Bag27100%85%70%41%18%5%1%0%0%0%0%Knapsack22100%88%72%42%18%6%1%0%0%0%0%Suitcase88100%40%10%5%4%3%2%1%0%0%0%MaleNone27Female group (FG)100%95%87%69%47%30%8%0%0%0%0%Bag33100%92%82%60%38%15%5%0%0%0%0%Knapsack34100%92%83%65%41%15%2%0%0%0%0%Suitcase94100%33%8%5%3%0%0%0%0%0%0%FemaleNone17100%94%82%72%54%41%30%12%5%0%0%Bag27100%88%75%58%41%29%12%2%1%0%0%Knapsack22100%88%76%60%43%32%18%2%1%0%0%Suitcase88100%35%10%3%2%1%0%0%0%0%0%Through increasing the space occupation of the obstacles from 0% to 100%, the functional relationship between speed decline rate and space occupation for both males and females is fitted and shown in Figure4.Figure 4
Experimental curve of speed drop and space occupation.
(a)(b)(c)(d)(e)(f)The experimental results (Figure4) show that the speed decline rate decreases with the obstacle occupancy (μ) for the agent with different occupancy (ρ). If μ+ρ⟶1, the rate of speed decline rate will dramatically increase. Different types of obstacles have different impacts on the speed of the agent, among which the stationary obstacle has the least impact on obstacles. Through the experimental observation, a male agent has a higher spatial tolerance to obstacles and can adjust their posture and luggage position more flexibly to get through obstacles quickly. As a result, although the value of ρ for the male agent is larger than that for the female agent, the speed of a male agent is less affected by obstacles compared with that of the female agent. Moreover, since the space of the agent with a suitcase is more flexible, it is possible for the agent to walk through the cell when μ+ρ>1.Figure5 displays the curve ofτ for male and female agents, and the fitting formulas of the velocity decline rate τρ,μ for the male agent are given as(1)τρ,μ=1,μ=0,0,ρ+μ≥1,−1.452ρ+μ2+0.5893ρ+μ+1,type=SO,ρ+μ<1,−1.297ρ+μ2+0.343ρ+μ+1,type=MG,ρ+μ<1,−1.616ρ+μ2+0.4191ρ+μ+1,type=FG,ρ+μ<1.Figure 5
Fitting curve ofτ. (a) The relationship between speed decline rate (τ) and (b) space occupation μ+ρ) for male and female agents, respectively.
(a)(b)The fitting formulas of the velocity decline rateτρ,μ for the female agent are given as(2)τρ,μ=1,μ=0,0,ρ+μ≥1,−1.1947ρ+μ2+0.1656ρ+μ+1,type=SO,ρ+μ<1,−0.795lnρ+μ−0.0748,type=MG,ρ+μ<1,−0.6275ρ+μ2−0.3902ρ+μ+1,type=FG,ρ+μ<1.As shown in Figure5, all five curves had R2 fitting values greater than 0.9, except for the curve representing women crossing the male group (MG), and this may be because women are more repelled by the opposite gender. Therefore, the time that the agent reaches any adjacent cell can be expressed as(3)Tijq=Gdirvqτijρq,μ,where Gdir represents the distance to the adjacent cell and is related to the direction of the agent and vq denotes the expected speed of agent q.(2) Delay Potential Energy Function. The static potential energy value is determined by the spatial distance between the cell and the destination. The pedestrian chooses the cell with the lower potential energy value, which is closer to the destination. Assuming that the pedestrians will walk at the expected speed, the shortest path is considered both the shortest distance and time to unify the time and space.After considering the influence of obstacles, the actual speed of the agent is gradually lower than the expected speed, and the relationship between walking distance and time is nonlinear (Figure6). In this case, shortening the walking distance will increase the time, the agent needs to walk for more distance to save the time, and thus, the multipath problem will arise. Therefore, the microscopic path-planning problem can be transformed into a multiobjective optimization problem considering the influence of partial obstacles. There are two methods to solve the multiobjective problem: (1) to transform the multiobjective problem into a single objective problem by weighting; (2) to solve the problem based on the Pareto optimal solutions, such as data envelopment analysis (DEA) and heuristic algorithm. Since the two objectives of time and space distance can be converted through velocity, the first method is adopted in this paper.Figure 6
Relationship between time and walking distance.The agent often makes different choices on the time and space distance. From experience, the agent in a hurry will choose the most time-saving path, while others will choose a relatively short path. We explain this phenomenon as the “degree of laziness,” and the generalized potential energy of the agent is that spatial distance and time are weighted by “laziness coefficient.” The weighting factor of the distance is larger for the “lazier” agent, and the weighting factor of the time is larger for the diligent agent, so the spatial potential energy can be transformed into the generalized potential energy. In this way, the choice of path for the agent is more objective and diverse.Then, we explain the “laziness coefficient” from the view of opportunity cost, where the difference lies in the value of time (VOT) of the agent. Moreover, the opportunity cost of time is reflected by the maximum distance that the agent can walk during the delayed time period.Thus, waiting potential energyTijq can be expressed as(4)Tijq=Gdirτijρq,μvq−Gdirvqvq=1−τijρq,μτijρq,μGdir,where vq represents the expected speed of agent q and τijρq,μ represents the coefficient of the velocity decline rate for the partial obstacle in the cell i,j.


### 2.3.3. Waiting Potential Energy

Since the agent will lose patience and choose other paths after waiting if other pedestrians have occupied the target cell, the waiting potential energy is introduced in this paper. The waiting potential energy is affected by the characteristics of the agent and changes with time and has two opposite characteristics of dissipation and enhancement.(1) Dissipation. If the pedestrian has left the cell i,j, the waiting potential energy W will dissipate over time. At first, the agent still remembers that he has passed through the cell i,j, and thus, the waiting potential energy can keep pedestrians from returning. When the waiting potential energy dissipates to 0, the agent will forget whether he has passed through the cell.When agentq leaves the cell i,j at t0, the waiting potential energy of the cell i,j can be expressed as Wijq,tkafter k simulation time steps:(5)Wijq,tk=αqWijq,tk−1=αq2Wijq,tk−2=αqkWq,t0,0<αq<1,where Wq,t0 is the basic waiting potential energy and αq is the waiting potential energy dissipation coefficient of agent q. The smaller αq is, the faster the waiting potential energy will dissipate.The waiting potential energyWq,tk is mainly affected by three variables: basic waiting potential energy Wq,t0, dissipation coefficient αq, and enhancement coefficient βq.If the agent waits for a time step, he will give up the movement during this time step at the expected speed, and this is also defined as the opportunity cost:(6)Wq,t0=0.2⋅vqtk.The dissipation coefficientαq reflects the perception of the agent. If αq⟶1, it will dissipate slowly, and it is impossible for the agent to return. If αq⟶0, the agent will return to the same local minimum cell and fall into a dead cycle. From this point of view, αq should be as large as possible. However, the local minimum of the cell may disappear after a short period; since the agent blocking at the door will leave, it will take a long time for the agent to return. Therefore, the dissipation coefficient also reflects how far the agent is willing to search after falling into a local minimum and successfully jumping out. According to observation experiments, the interval between pedestrian path-planning decisions is about 1 second, and it is related to the gender, age, and luggage of the agent. To simplify the model, let αq=0.9; after 1 second (5 time steps), the waiting potential energy can be reduced to the original 0.95=0.59 times, namely, it will dissipate at a rate of 60% per second.(2) Enhancement. If the agent stays in the cell i,j, the waiting potential energy W will increase over time, and the agent will wait before falling into a local minimum. The longer the waiting time is, the greater the waiting potential energy of the cell will be. When the superimposed potential energy of the cell is higher than that of other cells in the neighbourhood, the agent will successfully jump out of the local minimum. On the contrary, after jumping out of the local minimum, the waiting potential energy of the cell is large and dissipates slowly, so pedestrians will not return in a short time. When pedestrian q enters and stays in the cell i,j at t0, after k simulation time steps, the waiting potential energy of the cell i,j is expressed as(7)Wijq,tk=βqWijq,tk−1+Wijq,t0=1−βqk+11−βqWq,t0,βq>1,kWq,t0,βq=1,where βq is the waiting potential energy enhancement coefficient of agent q. The larger value of βq represents that the agent is reluctant to wait. When βq = 1, the waiting potential energy increases linearly with time; when βq > 1, the longer the pedestrians wait, the faster the waiting potential energy increases. When the total potential energy of the superimposed cell is greater than that of the neighbourhood cell, pedestrians successfully jump out of the local minimum. This can also reflect the process that pedestrians gradually lose patience and look for other paths after waiting for a period.The enhancement coefficientβq reflects the patience of the agent. The lower value of the coefficient means that the agent is more patient. The decisive factor of βq is the agent’s judgement on velocity decline rate of the occupation in the bottleneck cell, which is also related to the gender, age, and travel purpose of the agent. In order to simplify this model, it is assumed that βq is only related to the variation of occupation μ in the next time step.Impatient agent judges that the cell occupation of obstacles is constant and will leave at the next time step after jumping into the local minimum cell, and thus, whenΔμ=μtk+1−μtk=0, βq will reach the maximumβq=+∞. The patient agent thinks that the occupancy of the obstacle cell will be reduced to zero, and thus, when Δμ=μtk+1−μtk=μ, βqreaches the minimum value βq=1. Therefore, the logarithmic function can be established:(8)βq=lnμΔμ+1,μ≥Δμ.


### 2.3.4. Generalized Dynamic Potential Energy

The generalized dynamic potential energyUijq,tkcan be obtained by superposing the space potential energyVijq, delay potential energy Tijq,tk, and waiting potential energy Wijq,tk. Moreover, three types of potential energy are unified by distance:(9)Uijq,tk=Vijq+Tijq,tk+Wijq,tk.The simulation process of the multiagent is shown in Table5 and Figure 7.Table 5
Simulation process of multiagent path planning.
StepDescription1Model initialization. Set the generation rate of the agent asαo and the number of agents as k.2Obtain the static spatial potential energy fieldV for destination set through the improved Dijkstra algorithm.3Generalize the delayed potential energy fieldT for all agents; set the potential energy field W = 0 and simulation time t=1.4Wait for the dissipation of potential energyW.5Set the agent number ask = 1.6Select thekth agent and jump to Step 13 if the agent has not departed or left the simulation area. Otherwise, move to Step 7.7If the agent is not waiting and the remaining time of the cell is greater than 0, then the remaining time will be −1, and jump to Step 13. Otherwise, move on to Step 8.8If the agent reaches the destination, set the agent waiting, subtract the space occupation of the agent from the space occupation of the cell; if the waiting potential energy fieldW becomes 0, then jump to Step 13; otherwise, move on to Step 9.9If the current time equals the initial entry time of the agent, strengthen the space occupation in the origin cell. Otherwise, if the direction of the agent is 1, the waiting potential energy will be strengthened.10Strengthen the basic waiting potential energy, and update 3 types of potential energy in all directions to obtain the generalized potential energyU by superposition.11Determine the target cell according to the cell probability selection model.12If the cell is a target cell, the agent will choose to stay, and set the agent waiting. Otherwise, update the direction and remaining time.13Ifk=K, move on to the next step. Otherwise,k=k+1, and return to Step 6.14Ift=tmax, end. Otherwise, t = t + 1, and return to Step 4.Figure 7
Flowchart of multiagent path planning.


## 2.3.1. Space Potential Energy

In the space potential energy fieldV, the spatial potential energy is determined by the distance from the current position to the destination. Since the space potential energy is only related to the Euclidean distance and is static, it is called the static space potential energy.Consider the path planning problem of the multiagent to multidestinations; if there arem agent origins from different cellsOi,i∈m, to the destination cell Dj, j∈n, the traditional path search algorithm will calculate m×n times in each time step. In order to improve the computational efficiency, we can start from the destination set D to search the cells in all possible directions and record the distance to any cell.In each step, when pedestrians update the current cell coordinates, at least one cell that is nearer to the destination can be found in the neighbourhood. Pedestrians will choose the nearest one as the forward direction and finally reach the nearest cell in the destination set. Since all of the points in this region are search targets, the number of searches is fixed, and the Dijkstra algorithm can be improved directly.Here is the procedure of the improved Dijkstra algorithm:(i)
Step 1: set all cells which meetμ>1−ρ to be −1, and the others have no potential energy.(ii)
Step 2: traverse all the cells to find the cellb satisfying the following conditions:Cellb has no potential energy; there is at least one cell with positive potential energy in the neighbourhood of the cell. The two cells are connectable. The cell is assigned a temporary valueV^b=Va+Gab, where Vais the potential energy of the adjacent cell and Gab is the distance between two adjacent cells, whose value is 1 or 1.414. If there is more than one cell in the neighbourhood which satisfies the above conditions, choose a smaller value, namely, V^b=minVai+Gaib,i=1,2,…,8; then, all the satisfied cells will create a set {B}.(iii)
Step 3: replace the potential energy value with the smallest temporary value inB, Vb=V^b.(iv)
Step 4: if all the cells have potential energy, end; otherwise, return to Step 2.The simulation process of the improved Dijkstra algorithm is shown in Figure3.Figure 3
Flowchart of the improved Dijkstra algorithm.Here, we consider a case where an agent will walk from the upper left corner to the lower right corner. Figure2(b) displays the distribution of the static potential energy field, where blue colour represents the lower potential energy value and red colour represents the higher value. Figure 2(c) displays the potential energy and walking trajectory of an agent.


## 2.3.2. Delay Potential Energy

(1) Obstacle Delay Function. The open space cell has no constraints on an agent’s walking path choice; an agent can enter from any direction in the open space cell and walk through with the desired speed, and thus, the initial space occupancy of an open space cell is zero. Moreover, the obstacles such as walls, foundation columns, isolation bars, and other pedestrians have impacts on an agent’s path choice. The agent will initiatively stay away from the walls, bypass the columns and facilities, and keep their distance from each other. From the perspective of the space occupation of the cell, the walking environment can be divided into four categories.In Table3, ρ and μ represent the space occupancy of an agent and obstacle, respectively. The cell with no obstacles does not occupy space and has no effects on path planning of the agent. The complete obstacle cell is repulsive to the agent from any direction. A channelized obstacle, such as an isolation bar, is considered to be at the edge of a specified direction of the cell to prevent an agent from walking toward in the specified direction, but there are no constraints on pedestrians in other directions.Table 3
Obstacle classification.
TypeSpace occupationμImpact on the cellExampleNo obstacleμ=0NoneOpen spaceComplete obstacleμ≥1−ρPrevents entry from any directionWallsCanalized obstacleμ=0Prevents entry from a particular directionIsolation barPartial obstacle0<μ<1−ρSlows down the walking speedDustbinThe delay potential energy reflects the time consumption of pedestrians while passing through the cell. In this paper, a continuous variableμ∈ [0, 1] is used to indicate whether the cell is occupied or not, instead of 0-1 variables in the traditional methods. When an agent with a body size of ρ walks through a cell occupying the space of μ, there will be delays due to lateral avoidance. Delays are affected by the following two factors: (1) the “body type” of an agent is determined by the gender and the number of carry-on luggage; (2) the space occupation of the cell.Then, a cross-observation experiment is carried out to explore the regulation of speed decline rate. 40 student participants from the author’s college were evenly divided into two groups by gender. Place cone buckets of different sizes or stand on other participant groups to change the occupancy of the cell every time. Each group of participants is required to carry different luggage through the cell in turn. Record the time consumed by each participant from entering to leaving the cell. Divide the time passed by empty hands by the time passed by this round to get the speed decline rate. If the participant cannot pass the cell, it is set as 0. Table4 shows the results of the experiment.Table 4
Relationship between speed decline rate and space occupation.
SexLuggageρ (%)Obstacle typeObstacle occupationμ0%10%20%30%40%50%60%70%80%90%100%MaleNone27Stationary obstacle (SO)100%98%95%84%76%61%40%10%1%0%0%Bag33100%93%90%78%67%52%21%3%1%0%0%Knapsack34100%95%91%80%71%57%33%7%1%0%0%Suitcase94100%61%24%11%3%2%0%0%0%0%0%FemaleNone17100%96%90%81%72%54%35%12%2%0%0%Bag27100%92%88%75%62%47%15%2%0%0%0%Knapsack22100%94%86%78%65%50%22%3%1%0%0%Suitcase88100%35%5%2%1%1%0%0%0%0%0%MaleNone27Male group (MG)100%95%88%75%63%49%33%10%3%1%0%Bag33100%90%80%69%54%38%15%5%2%0%0%Knapsack34100%91%82%71%58%42%20%6%2%0%0%Suitcase94100%40%12%5%2%1%1%0%0%0%0%FemaleNone17100%90%78%47%21%7%2%0%0%0%0%Bag27100%85%70%41%18%5%1%0%0%0%0%Knapsack22100%88%72%42%18%6%1%0%0%0%0%Suitcase88100%40%10%5%4%3%2%1%0%0%0%MaleNone27Female group (FG)100%95%87%69%47%30%8%0%0%0%0%Bag33100%92%82%60%38%15%5%0%0%0%0%Knapsack34100%92%83%65%41%15%2%0%0%0%0%Suitcase94100%33%8%5%3%0%0%0%0%0%0%FemaleNone17100%94%82%72%54%41%30%12%5%0%0%Bag27100%88%75%58%41%29%12%2%1%0%0%Knapsack22100%88%76%60%43%32%18%2%1%0%0%Suitcase88100%35%10%3%2%1%0%0%0%0%0%Through increasing the space occupation of the obstacles from 0% to 100%, the functional relationship between speed decline rate and space occupation for both males and females is fitted and shown in Figure4.Figure 4
Experimental curve of speed drop and space occupation.
(a)(b)(c)(d)(e)(f)The experimental results (Figure4) show that the speed decline rate decreases with the obstacle occupancy (μ) for the agent with different occupancy (ρ). If μ+ρ⟶1, the rate of speed decline rate will dramatically increase. Different types of obstacles have different impacts on the speed of the agent, among which the stationary obstacle has the least impact on obstacles. Through the experimental observation, a male agent has a higher spatial tolerance to obstacles and can adjust their posture and luggage position more flexibly to get through obstacles quickly. As a result, although the value of ρ for the male agent is larger than that for the female agent, the speed of a male agent is less affected by obstacles compared with that of the female agent. Moreover, since the space of the agent with a suitcase is more flexible, it is possible for the agent to walk through the cell when μ+ρ>1.Figure5 displays the curve ofτ for male and female agents, and the fitting formulas of the velocity decline rate τρ,μ for the male agent are given as(1)τρ,μ=1,μ=0,0,ρ+μ≥1,−1.452ρ+μ2+0.5893ρ+μ+1,type=SO,ρ+μ<1,−1.297ρ+μ2+0.343ρ+μ+1,type=MG,ρ+μ<1,−1.616ρ+μ2+0.4191ρ+μ+1,type=FG,ρ+μ<1.Figure 5
Fitting curve ofτ. (a) The relationship between speed decline rate (τ) and (b) space occupation μ+ρ) for male and female agents, respectively.
(a)(b)The fitting formulas of the velocity decline rateτρ,μ for the female agent are given as(2)τρ,μ=1,μ=0,0,ρ+μ≥1,−1.1947ρ+μ2+0.1656ρ+μ+1,type=SO,ρ+μ<1,−0.795lnρ+μ−0.0748,type=MG,ρ+μ<1,−0.6275ρ+μ2−0.3902ρ+μ+1,type=FG,ρ+μ<1.As shown in Figure5, all five curves had R2 fitting values greater than 0.9, except for the curve representing women crossing the male group (MG), and this may be because women are more repelled by the opposite gender. Therefore, the time that the agent reaches any adjacent cell can be expressed as(3)Tijq=Gdirvqτijρq,μ,where Gdir represents the distance to the adjacent cell and is related to the direction of the agent and vq denotes the expected speed of agent q.(2) Delay Potential Energy Function. The static potential energy value is determined by the spatial distance between the cell and the destination. The pedestrian chooses the cell with the lower potential energy value, which is closer to the destination. Assuming that the pedestrians will walk at the expected speed, the shortest path is considered both the shortest distance and time to unify the time and space.After considering the influence of obstacles, the actual speed of the agent is gradually lower than the expected speed, and the relationship between walking distance and time is nonlinear (Figure6). In this case, shortening the walking distance will increase the time, the agent needs to walk for more distance to save the time, and thus, the multipath problem will arise. Therefore, the microscopic path-planning problem can be transformed into a multiobjective optimization problem considering the influence of partial obstacles. There are two methods to solve the multiobjective problem: (1) to transform the multiobjective problem into a single objective problem by weighting; (2) to solve the problem based on the Pareto optimal solutions, such as data envelopment analysis (DEA) and heuristic algorithm. Since the two objectives of time and space distance can be converted through velocity, the first method is adopted in this paper.Figure 6
Relationship between time and walking distance.The agent often makes different choices on the time and space distance. From experience, the agent in a hurry will choose the most time-saving path, while others will choose a relatively short path. We explain this phenomenon as the “degree of laziness,” and the generalized potential energy of the agent is that spatial distance and time are weighted by “laziness coefficient.” The weighting factor of the distance is larger for the “lazier” agent, and the weighting factor of the time is larger for the diligent agent, so the spatial potential energy can be transformed into the generalized potential energy. In this way, the choice of path for the agent is more objective and diverse.Then, we explain the “laziness coefficient” from the view of opportunity cost, where the difference lies in the value of time (VOT) of the agent. Moreover, the opportunity cost of time is reflected by the maximum distance that the agent can walk during the delayed time period.Thus, waiting potential energyTijq can be expressed as(4)Tijq=Gdirτijρq,μvq−Gdirvqvq=1−τijρq,μτijρq,μGdir,where vq represents the expected speed of agent q and τijρq,μ represents the coefficient of the velocity decline rate for the partial obstacle in the cell i,j.


## 2.3.3. Waiting Potential Energy

Since the agent will lose patience and choose other paths after waiting if other pedestrians have occupied the target cell, the waiting potential energy is introduced in this paper. The waiting potential energy is affected by the characteristics of the agent and changes with time and has two opposite characteristics of dissipation and enhancement.(1) Dissipation. If the pedestrian has left the cell i,j, the waiting potential energy W will dissipate over time. At first, the agent still remembers that he has passed through the cell i,j, and thus, the waiting potential energy can keep pedestrians from returning. When the waiting potential energy dissipates to 0, the agent will forget whether he has passed through the cell.When agentq leaves the cell i,j at t0, the waiting potential energy of the cell i,j can be expressed as Wijq,tkafter k simulation time steps:(5)Wijq,tk=αqWijq,tk−1=αq2Wijq,tk−2=αqkWq,t0,0<αq<1,where Wq,t0 is the basic waiting potential energy and αq is the waiting potential energy dissipation coefficient of agent q. The smaller αq is, the faster the waiting potential energy will dissipate.The waiting potential energyWq,tk is mainly affected by three variables: basic waiting potential energy Wq,t0, dissipation coefficient αq, and enhancement coefficient βq.If the agent waits for a time step, he will give up the movement during this time step at the expected speed, and this is also defined as the opportunity cost:(6)Wq,t0=0.2⋅vqtk.The dissipation coefficientαq reflects the perception of the agent. If αq⟶1, it will dissipate slowly, and it is impossible for the agent to return. If αq⟶0, the agent will return to the same local minimum cell and fall into a dead cycle. From this point of view, αq should be as large as possible. However, the local minimum of the cell may disappear after a short period; since the agent blocking at the door will leave, it will take a long time for the agent to return. Therefore, the dissipation coefficient also reflects how far the agent is willing to search after falling into a local minimum and successfully jumping out. According to observation experiments, the interval between pedestrian path-planning decisions is about 1 second, and it is related to the gender, age, and luggage of the agent. To simplify the model, let αq=0.9; after 1 second (5 time steps), the waiting potential energy can be reduced to the original 0.95=0.59 times, namely, it will dissipate at a rate of 60% per second.(2) Enhancement. If the agent stays in the cell i,j, the waiting potential energy W will increase over time, and the agent will wait before falling into a local minimum. The longer the waiting time is, the greater the waiting potential energy of the cell will be. When the superimposed potential energy of the cell is higher than that of other cells in the neighbourhood, the agent will successfully jump out of the local minimum. On the contrary, after jumping out of the local minimum, the waiting potential energy of the cell is large and dissipates slowly, so pedestrians will not return in a short time. When pedestrian q enters and stays in the cell i,j at t0, after k simulation time steps, the waiting potential energy of the cell i,j is expressed as(7)Wijq,tk=βqWijq,tk−1+Wijq,t0=1−βqk+11−βqWq,t0,βq>1,kWq,t0,βq=1,where βq is the waiting potential energy enhancement coefficient of agent q. The larger value of βq represents that the agent is reluctant to wait. When βq = 1, the waiting potential energy increases linearly with time; when βq > 1, the longer the pedestrians wait, the faster the waiting potential energy increases. When the total potential energy of the superimposed cell is greater than that of the neighbourhood cell, pedestrians successfully jump out of the local minimum. This can also reflect the process that pedestrians gradually lose patience and look for other paths after waiting for a period.The enhancement coefficientβq reflects the patience of the agent. The lower value of the coefficient means that the agent is more patient. The decisive factor of βq is the agent’s judgement on velocity decline rate of the occupation in the bottleneck cell, which is also related to the gender, age, and travel purpose of the agent. In order to simplify this model, it is assumed that βq is only related to the variation of occupation μ in the next time step.Impatient agent judges that the cell occupation of obstacles is constant and will leave at the next time step after jumping into the local minimum cell, and thus, whenΔμ=μtk+1−μtk=0, βq will reach the maximumβq=+∞. The patient agent thinks that the occupancy of the obstacle cell will be reduced to zero, and thus, when Δμ=μtk+1−μtk=μ, βqreaches the minimum value βq=1. Therefore, the logarithmic function can be established:(8)βq=lnμΔμ+1,μ≥Δμ.


## 2.3.4. Generalized Dynamic Potential Energy

The generalized dynamic potential energyUijq,tkcan be obtained by superposing the space potential energyVijq, delay potential energy Tijq,tk, and waiting potential energy Wijq,tk. Moreover, three types of potential energy are unified by distance:(9)Uijq,tk=Vijq+Tijq,tk+Wijq,tk.The simulation process of the multiagent is shown in Table5 and Figure 7.Table 5
Simulation process of multiagent path planning.
StepDescription1Model initialization. Set the generation rate of the agent asαo and the number of agents as k.2Obtain the static spatial potential energy fieldV for destination set through the improved Dijkstra algorithm.3Generalize the delayed potential energy fieldT for all agents; set the potential energy field W = 0 and simulation time t=1.4Wait for the dissipation of potential energyW.5Set the agent number ask = 1.6Select thekth agent and jump to Step 13 if the agent has not departed or left the simulation area. Otherwise, move to Step 7.7If the agent is not waiting and the remaining time of the cell is greater than 0, then the remaining time will be −1, and jump to Step 13. Otherwise, move on to Step 8.8If the agent reaches the destination, set the agent waiting, subtract the space occupation of the agent from the space occupation of the cell; if the waiting potential energy fieldW becomes 0, then jump to Step 13; otherwise, move on to Step 9.9If the current time equals the initial entry time of the agent, strengthen the space occupation in the origin cell. Otherwise, if the direction of the agent is 1, the waiting potential energy will be strengthened.10Strengthen the basic waiting potential energy, and update 3 types of potential energy in all directions to obtain the generalized potential energyU by superposition.11Determine the target cell according to the cell probability selection model.12If the cell is a target cell, the agent will choose to stay, and set the agent waiting. Otherwise, update the direction and remaining time.13Ifk=K, move on to the next step. Otherwise,k=k+1, and return to Step 6.14Ift=tmax, end. Otherwise, t = t + 1, and return to Step 4.Figure 7
Flowchart of multiagent path planning.


## 3. Case Study

After superposing the delay potential energy fieldT and waiting potential energy field W, consider the path planning problem of a male agent without luggage (ρ=0.27） under different space occupation of obstacles (μ). The results obtained from the DPEM state that the agent will make different choices while facing the local minimum cell with different values of μ.Ifμ = 0.2, the agent will choose to go through the cell; if μ = 0.9, the agent will choose to detour affected by conflicts between the potential energy and the inertia potential energy of static obstacles.In Figure8(a), the agent falls into the local minimum cell (10, 13) at the 75th time step. After delaying 4 time steps, the agent will jump out at the 83rd time step and delay passing through the cell (11, 13), where the obstacle is located, and reach the destination at the 158th time step.Figure 8
Testing the local minimum detour (a) and (b) walking trajectories of the agent, whereμ=0.2 and μ=0.9, respectively.
(a)(b)In Figure8(b), the agent falls into the local minimum cell (10, 13) at the 75th time step. After waiting for 5 time steps, the agent jumps out at the 80th time step and choose to detour, reaching the destination at the 214th time step.


## 4. Conclusions

This paper first proposes a dynamic potential energy model (DPEM) under the spatial-temporal simulation environment with large cells and small time segments, where the deadlock problem arisen in traditional cellular automata simulations can be avoided. Secondly, this paper concludes that the agent’s selection such as forward, waiting, and detour while facing the obstacles is a dynamic decision-making process. Each agent will decide on opportunity cost with the objective of utility maximization and is affected by their personal characters and other environmental factors. Thirdly, through the empirical experiments, it is showed that the sum of the agent and obstacles’ space occupation (ρ+μ) is the main factor affecting the velocity decline rate in the multiagent system. The velocity decline rate is also related to the obstacle types, such as the stationary objective (SO), male group (MG), and female group (FG). Moreover, it is showed that the trajectory of each agent in the multiagent system has two characteristics: dissipation and enforcement. The dissipation characteristic can guarantee the condition in which each agent will not return, and the enforcement characteristic can guarantee the condition in which each agent will first wait and then make detours while facing the obstacles. Then, the relationship between each agent’s patience while waiting and the space occupation change rate of obstacles is showed to be logarithmic. Finally, we conduct a case study to verify the effectiveness of the proposed DPEM. The research results of this paper will be helpful for the construction of a mesoscopic pedestrian traffic simulation model accurately and efficiently and reflect different characters of each agent, such as the gender and carry-on baggage. In the future research, we will introduce more parameters and traffic control measures, such as travel companion, traffic signals, pedestrians’ selection between stairs and escalators to describe the environmental factors, and group characters of the multiagent based on the technology of data mining and decision-making game theory.



---

*Source: 1360491-2020-07-24.xml*