1 Introduction

In 2021 the European Commission reported 7665 fatal traffic accidents in urban areas inside the European Union(EU) [18]. Analyzing which type of road user was involved in an accident, the study shows that 31% of all recorded fatalities happened due to fatally injured pedestrians who collided with motorized vehicles. This statistic underlines the immense vulnerability of pedestrians, especially those who interact with motorized vehicles. The varying risk aversion of pedestrians on street crossings further complicates finding effective countermeasures to prevent fatal accidents [20]. Because of these circumstances, pedestrians, among cyclists and motorcyclists, are often referred to as Vulnerable Road Users (VRU).

Driven by the incentives to identify traffic safety indicators and form a mathematical representation of the behaviour of pedestrians that can be used to improve Autonomous Vehicles (AVs), recent research has focused on modelling the behaviour of pedestrians who interact with cars in simulations [5, 7, 16, 21].

The behavioural models used by this field of research can be classified into three categories, i.e. macroscopic, mesoscopic and microscopic models [3]. Macroscopic models simulate groups of pedestrians by modelling, e.g. the density of a crowd with flow dynamics. Microscopic models represent the actions of each agent, creating crowd behaviours purely out of the microscopic dynamics within the simulation. Mesoscopic models represent a compromise between the two approaches [3].

For microscopic models, most notably cellular automata, social force [9] and rule-based models [2], are especially popular for modelling the trajectories of pedestrians. These models allow the simulation of individual agents crossing a road as well as large crowds crossing, for example, a crosswalk [5]. Microscopic models often rely on path-finding algorithms to generate an agent’s desired path while being influenced by its environment, i.e. obstacles or other agents. A common choice for the path-finding algorithm is the A* algorithm, which finds a path between a start and a goal that minimizes a given function while considering obstacles between both points [1].

Traditional approaches find it challenging to predict where the pedestrians will cross the road in a more complex layout, such as the layout shown in Fig. 3 [14]. Approaches to overcome this challenge within a microscopic simulation include the model by Lu et al. [13] who incorporate the gap acceptance model in combination with the social force model by Ren et al. [22] to simulate where a pedestrian crosses the street [1]. The gap acceptance model [25] is a decision model which predicts when and where a pedestrian will cross a street based on the size of gaps between the cars in front of the pedestrian. As such, it does not account for the risk associated with the different sections of a crossing and depends on simulating cars to simulate realistic crossing behaviours of pedestrians.

The approach presented in this paper does not add another decision model. Instead, it introduces a change to the underlying path-finding algorithm, improving the crossing behaviour of the simulated pedestrians without the need to simulate cars. The adapted A* algorithm allows the modeller to specify risk-areas inside the layout of the simulation. The approach is based on the assumption that the impact of other road users on the pedestrian’s chosen path is minimal in urban areas where the street can be crossed at any point. Instead, the pedestrian avoids certain risky areas, generally independent of the presence of other road users. The new approach results in more realistic crossing behaviour than the standard A* algorithm while not inhibiting the functionality of the overall microscopic simulation model. The methodology can be compared to Zhen et al. [27], which describes a modified A* algorithm for ships in which risk-values from a risk map were included into the cost function of the A* algorithm. However, in contrast to the approach outlined in reference [27], the A* algorithm presented in this work is applied to the more complex case of human behaviour and applies the risk-values to a different term in the cost function of the A* algorithm. To validate and illustrate the improvements introduced by the altered A* algorithm, the Intersection Drone Dataset (InD) [4] is used. A selection of pedestrians recorded within this dataset are simulated with and without the adapted A* algorithm, and the simulated trajectories are compared to the observed trajectories.

This paper is structured as follows: Section 2 describes the microscopic model used in this work. Section 3 presents the data set and the respective simulation results, and Section 4 discusses the presented results. Finally, in Section 5 the work is summarized and an outlook on future developments is provided.

2 Background: Simulation Model

This paper presents an adjustment of a simulation environment presented in Köpke et al. [11] and adapted in Meyer et al. [17] to predict pedestrian behaviour at mass events. The simulation uses the social force model [10] to represent the pedestrian’s movements, see Fig. 1. The social force model divides the path that is provided by the path-finding algorithm into a sequence of goals. The direction from the current position of the pedestrian to the next goal is called the desired direction of motion \(e_\alpha \), towards which the social force model accelerates the agent until he reaches a desired speed \(v^0_{\alpha }\). In addition to this fundamental attracting force, obstacles and other agents emit a repulsive force, which leads the agent to deviate from \(e_\alpha \) and \(v^0_{\alpha }\) [24].

Fig. 1
Fig. 1
Full size image

The agent is driven by the driving force into the desired direction of motion, which is determined by the A* path-finding algorithm. Obstacles such as walls are modelled as potential fields which emit a repulsive force onto an agent. Depending on the density of agents, the repulsive forces between the agents are modelled either as a repulsive force from the social force model or with the SPH model. The graphic was adapted from Laufer and Planner [12]

Together, these forces describe the acceleration of each agent at each timestep:

$$\begin{aligned} {\textbf {f}}_\alpha (t) = \frac{v^0_\alpha e_\alpha - {\textbf {v}}_\alpha }{\tau _\alpha } + \sum _{\beta \ne \alpha } {\textbf {f}}_{\alpha \beta }(t) + \sum _{i} {\textbf {f}}_{\alpha i}(t) \end{aligned}$$
(1)

with \({\textbf {v}}_\alpha \) denoting the velocity of pedestrian \(\alpha \) at time t [24]. The repulsive forces are based on a circular specification:

$$\begin{aligned} {\textbf {f}}_{\alpha \beta } = A_\alpha e^{-\frac{(r_\alpha + r_\beta -|| {\textbf {d}}_{\alpha \beta }||)}{B_\alpha }} \cdot \frac{{\textbf {d}}_{\alpha \beta }}{|| {\textbf {d}}_{\alpha \beta } ||} \end{aligned}$$
(2)

with \(r_\alpha \) and \(r_\beta \) denoting the radius of pedestrian \(\alpha \) and \(\beta \), \({\textbf {d}}_{\alpha \beta }\) the distance between \(\alpha \) and \(\beta \) and \(A_\alpha \) and \(B_\alpha \) the strength and the range of the repulsive force. For simplicity, the dependence on t is left out in equation 2. The repulsive forces of an obstacle i, \({\textbf {f}}_{\alpha i}\), can be defined equivalently [24], with the addition that the repulsive force from the obstacle is not equally distributed between the outer bound of the radius \(r_i\) and the obstacle, but diminishes exponentially. If the density of agents exceeds four agents per \(m^2\), the repulsive forces for agents from the social force model are replaced by the Smoothed Particle Hydrodynamics (SPH) model [19] in the simulation. Because such a high density does not occur in the simulated data used in this paper, the SPH model plays a minor role in this paper. Figure 1 depicts the different forces influencing an agent inside the social force model. Given that it gives the desired path for each agent, the A* path-finding algorithm plays a major role in simulating realistic trajectories.

The A* algorithm is an informed path-finding algorithm first developed by Hart et al. in 1968 [8]. To run the algorithm, the layout on which to generate a path is first discretized, generating a grid of cells. The size of these cells is defined by the stepsize s of the algorithm. Given a start cell \(n_{spawn}\) and target cell \(n_{target}\), A* iteratively chooses the next cell to advance to by choosing the cell with minimal cost f(n) out of the cells neighbouring the already explored cells. The algorithm does not consider cells labelled as obstacles; thus, the A* algorithm generates paths around obstacles. In its basic form f(n) can be expressed as follows:

$$\begin{aligned} f(n) = g(n-1) + s + \epsilon * h(n), \end{aligned}$$
(3)

where \(g(n-1)\) is the length of the path to the last chosen cell \(n-1\) and h(n) is chosen as the Euclidean distance \(d(n_{target},n)\) from the considered cell n to \(n_{target}\). The weight of h(n), \(\epsilon \), is used to make the algorithm priorities more direct routes towards the goal. For the purpose of this paper, it is set to 2.5. Since each cell has the same size, the first two terms simply describe the path length to the considered cell n. Figure 2 illustrates the single terms of the cost function. While this cost function is very efficient in generating a path, it does not consider any information from its environment except obstacles. It thus can produce unrealistic paths under specific circumstances, as shown in chapter 3. risk-areas are introduced and integrated into the A* algorithm to remedy this shortcoming by assigning a risk-value to each cell in the layout grid. These values then enter the cost function as a weight \(r_n\) to the stepsize:

$$\begin{aligned} f(n) = g(n-1) + r_n * s + \epsilon * h(n), \end{aligned}$$
(4)
Fig. 2
Fig. 2
Full size image

Illustration of the A* algorithm in a grid with grid size s. Dark green depicts the start, dark red the goal, dark grey obstacles, light green the border of all already considered cells, light blue the considered cells and dark blue the cell which will be chosen next. The illustration was created with the tool provided by Xu [26]

The risk \(r_n\) introduces heterogeneity into the grid by amplifying the stepsize for risky cells, weighting more risky cells stronger and thus more costly for the A* algorithm. As a result, the algorithm chooses a path that minimizes the risk associated with that path. The modeller must define the risk-areas and should choose them with regard to the specific layout on which to simulate the agents, see chapter 3.2.

After a path is generated, specific nodes within the path are deleted to "smooth" the path. To do so, each node in the path is considered from start to finish. If a node b is within a distance of r stepsizes to the currently considered node a and no object lies between the two nodes, node b is deleted. This allows paths to cut corners within the radius of r stepsizes, making the path more realistic. A relatively small radius of three stepsizes was chosen not to erase the influence of the risk-areas on the final path.

3 Application

Having introduced the simulation environment, the following section describes the different analyses used to illustrate and validate the improvements introduced by the new A* algorithm.

First, the dataset, a subset of the InD, used to illustrate and validate the results, is introduced. Secondly, the chosen risk-areas and their corresponding values, as well as a single simulated A* path, are presented to show the effect of the risk-areas. Third, results for simulating every trajectory in location b of the InD with and without the use of risk-areas are shown. Finally, the improvements of the simulation introduced by the new A* algorithm are validated by comparing the densities of the simulated trajectories to the InD trajectories.

3.1 Data

In order to test and illustrate the improved A* algorithm, the InD [4] was used to compare simulation results with recorded trajectories of pedestrians. The InD holds 31 recordings of high-quality trajectories for pedestrians, cyclists, motorcycles, cars, and larger cars i.e. busses or trucks, which were recorded at four different intersections in Aachen, Germany with the means of a drone [4]. From the four available locations, location b from the InD, see Fig. 3, was chosen to be simulated. Location b is most suitable for the task at hand since it holds 68% (2099) of all pedestrians detected in the dataset and features a cross-section where pedestrians can cross any of the four streets at a freely chosen place. Since this paper focuses on the risk-averse behaviour of pedestrians rather than their interactions with other road users, such as cars and bicycles, this paper simulates only the pedestrians to clearly illustrate the effect of the new simulation approach..

Fig. 3
Fig. 3
Full size image

Crossing at the Frankenburg in Aachen, location b of the InD dataset. The colors of the bounding boxes correspond to the different road users in the data set: Red for cars, orange for trucks or busses, blue for bicycles and green for pedestrians [4]

3.2 Risk-Areas and A* Paths

To simulate the trajectories of the InD, each observed trajectory’s start and finish points were used as the start and finish for the A* algorithm. Since the A* simulation informs the social force model, the simulated trajectories have the same start and end points as the observed trajectories. The simplified layout of location b and the defined risk-areas with their respected risk-values used by the implemented A* algorithm can be seen in Fig. 4a. Figure 4b shows the InD trajectories for context.

Fig. 4
Fig. 4
Full size image

Layout of location b in (a), with the different risk-areas, their corresponding risk-values and obstacles indicated in the legend. The InD trajectories plotted over the layout in (b)

The layout is divided into six categories of areas: Obstacles, sidewalks, the crosswalk, parking areas, the street and the street centre. Obstacles include bushes, a bench, a fountain, some sitting stones in the southeast area, and areas where bicycles can be parked. The other areas can be set to different risk-values, representing the risk-areas considered by the A* algorithm.

As the calibration of the various parameters of the simulation, including the risk-values, would exceed the scope of this paper, the modeller established the risk-values with two objectives in mind:

First, the risk-values should follow the inequality shown in Eq. 5, which reflects the danger for pedestrians in the areas relative to the other areas in the layout and equally represents the preferences of pedestrians on where to cross the road:

$$\begin{aligned} {\begin{matrix} r_{sidewalk} & \le r_{crosswalk}< r_{parking-area} \\ & < r_{street} < r_{street-centre} \end{matrix}} \end{aligned}$$
(5)

The street centre is set with the highest risk since the two potentially fast traffic flows intersect here and since crossing this area is always accompanied by a relatively long walk on the road [20]. Crossing the other areas of the street does not imply the same guaranteed prolonged stay on the road and does not feature intersecting traffic flows. However, cars drive with potentially high velocities on the street, which is why it is the second most risky area in the layout. The parking area typically features slower-moving vehicles, but the view of the drivers is often limited while parking, and thus, it is set to be less risky than the street but riskier than the crosswalk. Finally, since vehicles must stop for pedestrians on a crosswalk by law, the crosswalk features the lowest risk-value except for the sidewalk [20].

As a second condition, the risk term, i.e. \(s * r_n\), should be balanced with the other factors present in the cost function of the A* algorithm, Eq. 4, namely the \(g(n-1)\) and h(n), without negating the effect of \(\epsilon \). To meet these requirements, \(s * r_n\) was set with the following formula:

$$\begin{aligned} s * r_n = s + \hat{r}_n * (\hat{D}_{max} - s) \end{aligned}$$
(6)

where \(\hat{r}_n \in {0,1}\) and is set by the modeller and \(\hat{D}_{max}\) is the average Euclidean distance between the start and end points of all pedestrians observed in location b, giving an estimate for the maximum values of the terms \(g(n-1)\) and h(n) when \(\epsilon \) equals 1. The formula ensures that \(s * r_n\) does not exceed \(\hat{D}_{max}\). Table 1 shows the chosen values of \(\hat{r}_n\) and corresponding rounded values for \(r_n\) with \(\hat{D}_{max} = 38\). The values for \(\hat{r}_n\) were finetuned within the boundaries of Eq. 5 and 6 to improve the accuracy of the simulation.

Table 1 The chosen values of \(\hat{r}_n\) and corresponding values for \(r_n\) according to Eq. 6
Full size table

Figure 5a shows the simulated path of the pedestrian and all cells considered by the A* algorithm when no risk-areas are considered by the A* algorithm. As no other restrictions were implemented, the A* algorithm chooses the shortest path and thus only considers cells directly next to the shortest path. The resulting path is highly unrealistic, as it does not cross the crosswalk, disregards the parking area, and crosses the street without minimizing the time spent on the street, thus with no regard for risk concerns.

Fig. 5
Fig. 5
Full size image

A single path generated by the A* algorithm, with and without considering the risk-areas. Green dots indicate the steps checked by the A* algorithm, while blue dots indicate the chosen steps. The dark blue and purple dots indicate the start and end points. The Blue line indicates the finished path. The colouring of the areas of the layout indicates the risk-values, which correspond to the values and the areas shown in Fig. 4a

Figure 5b shows the path of a pedestrian when the use of risk-values is applied. It is more realistic, avoids the parking area and crosses the street using the crosswalk. In contrast to the simple A* Algorithm, the risk-minimizing version considered more cells. This is due to the algorithm avoiding risky areas and finding a way around them.

It should be noted that the path crosses the south street slightly unrealistically by crossing further to the south instead of crossing closer to the centre of the crossing. This showcases that the algorithm does minimize the time the agent spends in risky areas since the street gets wider towards the north.

3.3 Simulation of Crossing Behavior

When simulating the pedestrians recorded at location b, i.e. calculating the position at each timestep of each agent following its A* path, it becomes apparent that the introduced risk-areas and changes to the cost function of the A* algorithm improve the simulation.

Fig. 6
Fig. 6
Full size image

The simulated trajectories in red and the trajectories of the InD of recording 24 in blue, plotted over the layout of location b. (a) shows the simulation that does not consider risk-areas, and (b) shows the simulation that does consider risk-areas

Figure 6 shows each simulated path in location b in red and the actual path the pedestrian chose in blue when risk-areas were not considered and when they were, respectively. 2088 of the 2099 trajectories recorded in location b of the InD could be simulated. Trajectories which could not be simulated were excluded from the analysis.

Most notably, not considering risk-areas leads to many pedestrians crossing the street through the middle of the cross-section, risking a fatal collision with cars or other road users. However, the risk-averse A* algorithm leads to a path very similar to the real trajectories, as visible by the overlapping red and blue trajectories in Fig. 6b. The improved A* algorithm suggests paths that prefer the crosswalk and cross the street in similar areas as the observed pedestrians.

Furthermore, Figure 6b also shows that even trajectories which end in the middle of the street and thus in an area with very high risk can be simulated. This shows that no functionality of the simulation is limited by the introduced risk-areas.

Table 2 The percental difference between the error terms when considering risk-areas and when not considering risk-areas in the simulation in three different areas of the layout
Full size table

It is also visible in Fig. 6b that the tendency of the A* algorithm to cross the south street further to the south than the observed trajectories carries over to the simulated paths. While the general tendency of the observed paths to cross the street perpendicular to the street is replicated by the simulation, the south area of Fig. 6b shows a divergence of the simulated trajectories from the observed ones.

3.4 Quantitative Analysis

To quantify the improvements introduced by the risk-areas an error term describing the difference between the simulated and the observed trajectories was constructed. For that purpose, a Gaussian kernel \(\phi _{H}\) was used to create a two-dimensional density distribution of the trajectories over a grid of 100 cells. Linear interpolation ensured that each simulated trajectory held the same data points as the observed trajectory. Since Scott’s method was used to calculate the bandwidth of the kernel estimation [23], the bandwidth used for each estimation was the same, i.e. 0.09. The densities were then used to calculate an error term e in the following way:

$$\begin{aligned} e(\hat{\chi }) = \sum _{x = 0}^{100}{\sum _{y = 0}^{100}{|\phi _{H}(\chi _{x,y}) - \hat{\phi }_{H}(\hat{\chi }_{x,y})|}} \end{aligned}$$
(7)

where \(\chi _{x,y}\) represents the data of the trajectories in the cells at coordinates x and y, \(\phi _{H}(\chi _{x,y})\) stands for the density of the observed data and \(\hat{\phi }_{H}(\hat{\chi }_{x,y})\) stands for the density of simulated data.

When using the metric described in Equation 7 to calculate the errors in different areas of the layout, the improvement of the simulation caused by the risk-areas becomes apparent. Table 2 shows the percental difference between the error terms when considering risk-areas \(e(\hat{\chi }_{no-risk})\) and when not considering risk-areas in the simulation \(e(\hat{\chi }_{risk-areas})\) in three different areas of the layout:

Since introducing the risk-areas was done to improve the crossing behaviour of the agents, the improvements have been most dominant in the street and especially in the street centre.

4 Discussion of Results

While the results clearly show that the introduced adjustment of the A* algorithm does make the simulation more realistic, certain aspects of the simulation could be improved.

Firstly, as shown in Fig. 5b, introducing the risk-areas increases the number of cells considered by the A* algorithm and consequently increases the computational time. Without considering risk-areas, the A* algorithm generates the 2091 paths of the pedestrians recorded in location b in 56.856 seconds. Considering risk-areas increases the computational time by 11.7 % to 63.519 seconds.

Fig. 7
Fig. 7
Full size image

The densities residuals defined as \(\hat{\phi }_{H}(\hat{\chi }_{x,y}) - \phi _{H}(\chi _{x,y})\) corresponding to Eq. 7 i.e. the density of trajectories simulated with risk-areas minus the density of trajectories observed in location b. Blue areas indicate a higher density of observed trajectories relative to simulated trajectories. Red areas indicate a higher density of simulated trajectories relative to observed trajectories

Secondly, as shown in Figs. 5b and 7, the newly introduced cost function of the A* path-finding algorithm does lead to slightly unrealistic paths. Visualizing the difference calculated in \(e(\hat{\chi }_{risk-areas})\) shows that these slight deviations cause major differences in density in specific areas and thus influence the metric \(e(\hat{\chi }_{risk-areas})\) heavily when considering the full layout. The residual densities used for \(e(\hat{\chi }_{risk-areas})\) are visualized in Fig. 7. Darker blue areas in Fig. 7 indicate that the observed trajectories show a higher density in that specific area than the simulated trajectories and vice versa for the red areas. Moderate differences in densities, such as on the north side of the layout, are to be expected since the simulation aims to approximate the crossing behaviour of pedestrians and not their specific behaviour on the sidewalks. However, the simulated trajectories in the southern area often cross the southern street slightly further to the south than observed in the InD. As shown in Fig. 5b, the simulated path crossing the south street aligns with the intended effect of the risk-areas, which leads the A* algorithm to minimize the time the created path spends in risky areas. Since the introduced metric only considers differences in density, the minor but prevalent diversions from the observed path introduced by the risk-areas have a major influence on the calculated metric.

Both problems, the higher computational time and the divergence from realistic routes, could be improved by calibrating the many parameters inherent to the simulation, i.e. the parameters of the social force model and the A* algorithm. However, a tradeoff between fidelity and computational costs must be considered. Calibrating an undifferentiable simulation with such a high-dimensional parameter space is challenging since the likelihood of such models is typically intractable [6]. Therefore, the loss function for such models must be defined by hand. One example of such a loss function can be found in the error term used for validating the improvements of the simulation in Chapter 3.4. As described above, even in the case of this paper, this error term shows clear limitations in quantifying apparent improvements. These limitations become more important when using such a metric as a loss function for calibrating the simulation, as the metric would then be used iteratively to quantify improvements. In theory, a simulation-based inference approach to calibrating the simulation would take the mentioned difficulties into account [6]. However, applying such a calibration method to the simulation presented in this paper would go beyond the scope of this paper and could be the focus of future research.

After this paper has shown how the risk-averse behaviour of pedestrians can efficiently be simulated with the adapted A* algorithm without the need to simulate cars, the simulation could now be further developed by also simulating cars and, in addition to the underlying risk-averse A* algorithm presented in this paper, incorporate the gap acceptance model into the agents’ decision-making model. This is possible since the risk-averse A* algorithm does not interfere with the decision models but only informs them. Finally, risk-values could be set for each agent individually to model different risk profiles of pedestrians [20]. When relaxing the assumption of static risk-values and potentially including risk-values that change while searching for an optimal path, the computational task becomes much more complex and using conventional path planning algorithms is no longer feasible. Then alternative solutions, as discussed in Maidana et al. [15], should be considered.

5 Conclusion

When walking inside an urban area, pedestrians are at a very high risk of being fatally injured in a traffic accident. Modelling pedestrian behaviour in agent-based simulations can help prevent such accidents. To this end, this paper suggests a way to efficiently simulate pedestrians’ risk-averse nature. Risk-areas were implemented as a weight to the cost function of the A* path-finding algorithm, which informs the overlaying agent-based simulation with a preferred path for each agent. The changes to the A* algorithm and thus to the agent-based simulation were tested by simulating trajectories observed in the InD at the Frankenburg crossing in Aachen, Germany using risk-areas and without them. The improvement of the simulation using the adapted A* algorithm was validated by comparing the density of trajectories from the two simulations with the observed density from the InD.

Further research could focus on calibrating the different parameters of the simulation, thus decreasing the computational time and increasing its validity. Furthermore, the simulation could be further developed to better predict where and when pedestrians cross the road by including cars in the simulation and incorporating the gap acceptance model into the decision model of the agents.