Abstract
Several issues in transferring AI results in crowd modeling and simulation are due to the fact that control applications are aimed at achieving optimal solutions, whereas simulations have to deal with the notions of plausibility and validity. The latter requires empirical evidences that, for some specific phenomena, are still scarce and hard to acquire. To face this issue, the present work presents an investigation on the route choice decisions of pedestrians, by producing empirical evidences with an experiment executed in a controlled setting. The experiment involves human participants facing a relatively simple choice among different paths (i.e. choose one of two available gateways leading to the same target area) in which, however, they face a trade-off situation between length of the trajectory to be covered and estimated travel time, considering the level of congestion in the different paths. The data achieved with the experiment are used to design and evaluate a general simulation model for pedestrian route choice. The proposed model firstly considers the fact that other pedestrians are generally perceived as repulsive and that choice of route is generally aimed at avoiding congestion (as for proxemics theory). On the other hand, we also introduce an additional mechanism due to the conjecture that the decision of a pedestrian to reconsider the adopted path is a locally perceivable event that is able to trigger a similar reconsideration by nearby pedestrians, that can imitate the former one. The model is experimented and evaluated in the experiment scenario, for calibration and validation, as well as in a larger scale environment, for exploring the implications of the modeling choices in a more complex situation.
Introduction
The simulation of pedestrians and crowd movement in spatial structures is an established and already successful application of the domain of complex system simulation, widely dealt with the multi-agent paradigm [27]. Nonetheless, many open challenges are still present and new ones are emerging for researchers in different fields and disciplines: both the automated analysis and the synthesis of pedestrian and crowd behavior, as well as attempts to integrate these complementary activities [35], present issues and potential developments in a smart environment perspective [31]. Although the currently available commercial tools are used on a day-to-day basis by designers and planners, according to a report commissioned by the Cabinet Office [6] there is still room for innovations in models, to improve their effectiveness in modeling pedestrians and crowd phenomena, their expressiveness (i.e. simplifying the modeling activity or introducing the possibility of representing phenomena that were still not considered by existing approaches) and efficiency.
Even if we only consider choices and actions related to walking, modeling human decision making activities and actions is a complicated task: different types of decisions are taken at different levels of abstraction, from path planning to the regulation of distance from other pedestrians and obstacles present in the environment. Models producing interesting results in relatively small scale situations such as the crossing of corridors or bends, the evacuation from a room, might have difficulties in scaling to situations in which agents associated to pedestrians are not simply required to perform locomotion level activities, regulating their distance from obstacles and other pedestrian while pursuing a predefined destination. Choosing among different alternative routes, abstracting away from details of low level locomotion, implies considering cognitive level aspects such as the knowledge of the environment by the pedestrians, but also their preference with respect to the length of the covered trajectory, the possibility to maintain a certain walking speed or to avoid congestions. Moreover, the measure of success and validity of a model is definitely not the optimality with respect to some cost function, as (for instance) in robotics, but the plausibility, the adherence of the simulation results to data that can be acquired by means of observations or experiments.
The present research effort is aimed at producing insights on this aspect: an experiment involving pedestrians has been set up to investigate to which extent pedestrians facing a relatively simple choice (i.e. choose one of two available gateways leading to the same target area) in which, however, they can face a trade-off situation between length of the trajectory to be covered and estimated travel time. The closest gateway, in fact, is initially selected by most pedestrians but it is too narrow to allow a smooth passage of so many pedestrians, becoming increasingly congested. The other choice can therefore become much more reasonable, allowing a higher average walking speed and comparable travel time. Modeling this kind of choices with current approaches can be problematic.
The present work represents a step in the direction of both producing empirical evidences to fill this gap and producing a general model fitting the achieved ground truth. In particular, after a discussion of relevant related works, Section 3 will introduce an experiment in which pedestrians were forced to take a decision involving a trade-off between length of the trajectory to be covered and the estimated travel time, due to increasing congestion in one of the passages to be selected to reach the final target of the movement. Results of the experiment will be presented and discussed, and they represent the starting point for an analysis of different alternatives for modeling and simulating this kind of scenario, which will be illustrated in Section 4. Conclusions and future works will end the paper.
Related works
The inclusion in simulation models of decisions related to trade off scenarios, such as the one between overall trajectory length and presumed travel time (considering congestion in perceived alternative gateways), represent an issue in current modeling approaches.
Commercial instruments, for instance, mostly provide basic tools to the modelers, that are enabled and required to specify how the population of pedestrians will behave: this implies that the operator constructing the simulation model needs to specify how the pedestrians will generally choose their trajectory, by means of annotation of the actual spatial structure of the simulated environment through landmarks representing intermediate or final destinations (some relevant work [20] explored the possibility to automatically generate the intermediate destinations). The choice of paths does not necessarily have to follow the so called “least effort principle”, which suggests that pedestrians generally try to follow the (spatially) shortest path toward their destination. Space, in fact, represents just one of the relevant aspects in this kind of choice: since most pedestrians will generally try to follow these “best paths” congestion can arise and pedestrians can be pushed to make choices that would be sub–optimal, from the perspective of traveled distance.
Recent works in the area of pedestrian and crowd simulation began to investigate this aspect. In particular, Wagoum et al. [36] explored the implications of four different strategies for the management of route choice operations, through the combination of applying the shortest or quickest path, with a local (i.e., minimize time to vacate the room) or global (i.e., minimize overall travel time) strategies. Guo and Huang [13] proposed the modification of the floor-field Cellular Automata [4] approach for considering pedestrian choices not based on the shortest distance criterion but also considering the impact of congestion on travel time. This model is used to simulate a situation of evacuation. The dynamics in case of evacuation is different from a standard situation due to the faster-is-lower effect [28]: while the desired velocity of people increases, the delays generated by cloggings at bottlenecks becomes more significant and the evacuation times gets higher. Guo and Huang [12] proposed an extension of the floor field model [4] for the simulation of evacuation situation, introducing parameters to deal with pushing and bumping forces arising for the rush of people (another work by Henein and White [17] has analogous aims and methods). This model has been later extended in [14] to simulate route choice in case of evacuation and reproduce the observed data of an experiment. The work of Liu et al. [24] discusses the results of an experiment about the evacuation of a classroom with two exits, proposing a cellular automata model for its simulation and comparing the results. Tang et al. [33] further investigates the evacuation of two exits classroom, proposing a differentiation between rational behavior, mainly aimed to optimize the own travel time, and irrational one, attracted by the choices of other people and leading to higher evacuation times. Results of the above works are not conclusive: shortest path is not necessarily the adopted criterion for path planning, which can be reasonable in case of congestion, but pedestrians are generally not even making optimal choices, individually and globally (see, e.g., [9]).
Iterative approaches, borrowing models and even tools from vehicular transportation simulation, are aimed at the simulation of ordinary situation and propose to adopt a more coarse grained representation of the environment, i.e. a graph in which nodes are associated to intersections among road sections, but the process can be also adopted in buildings and pedestrian environments [8, 20]. In this kind of scenario, pedestrians can start by adopting shortest paths on a first round of simulation: as suggested before, the fact that all pedestrians take the best path generally leads to congestion and sub-optimal travel times. Some selected pedestrians, especially those whose actual travel time differs significantly from the planned one, will change their planned path and a new simulation round will take place. The iteration of this process will lead to an equilibrium or even to system optimum, according to the adopted travel cost function [21]. This iterative scheme has also been employed in multi-scale modeling approaches [9, 22]. It must be stressted that, unlike game theoretic studies like a recent work by Gatti et al. [11], this kind of work is not aimed at proving properties of the overall system, solution concepts, equilibria characterization, or overall learning dynamics, but rather at providing practical tools to study specific complex pedestrians and crowd management situations.
The above approach naturally leads to consider that this kind of problem has been paid considerable attention in the field of Artificial Intelligence, in particular by the planning community. Hierarchical planning [30] approaches, in particular, provide an elegant and effective framework in which high level abstract tasks can be decomposed into low level activities. Despite the fact that the formulation of the approach date to the seventies, it is still widely considered and employed in the close area of computer graphics [18], in which actions of virtual pedestrians are planned with the aim of being visually plausible and decided within real-time constraints. Within this framework, also issues related to the reconsideration of choices and plans were analyzed, mostly within the robotics area [23]. In the pedestrian simulation context, one could consider that microscopic decisions on the steps to be taken can follow a high-level definition of a sequence of intermediate destinations to be reached by the pedestrian. This kind of approach, which we experimentally investigated in [10], also allows exploiting already existing models dealing with low level aspects of pedestrian actions and perceptions [2]. The latter resembles an approach to trajectory planning devised in the area of robotics [19]: the environment in which robots are positioned and act is associated to a representation in which the presence of robots themselves and other relevant objects is associated to alterations in a field of forces. The overall rationale of the approach is to move the burden of computation from agents to the environment they are situated in [38]. In our approach, the environment is characterized by a set of discrete representations comprising both static information, such as the distance from each cell to relevant areas (creating a sort of gradient enabling agent navigation towards that region of interest), as well as dynamic information, for instance the currently perceived density of pedestrian in cells.
The main issues in transferring AI planning results within this context of application, and more generally producing applicable contributions to the field, are partly due to the above suggested fundamental difference between the measures of success between simulation and control applications. Whereas the latter are targeted at optimal solutions (see, e.g., [26]), the former have to deal with the notions of plausibility and validity. Moreover, we are specifically dealing with a complex system, in which different and conflicting mechanisms are active at the same time (e.g. proxemics [15] and imitative behaviors [16]). Finally, whereas recent extensive observations and analyses (see, e.g., [13]) produced extensive data that can be used to validate simulations within relatively simple scenarios (in which decisions are limited to basic choices on the regulation of mutual distances among other pedestrians while following largely common and predefined paths like corridors with unidirectional or bidirectional flows, corners, bottlenecks), we still lack comprehensive data on way-finding decisions, especially in relatively large scale settings (e.g. large train stations).
This lack of knowledge has been in some cases overcome by means of experiments, largely aimed at investigating evacuations situations in simple settings. The work of Guo et al. [14] presents an experiment of evacuation from a classroom with a single exit, analyzing the impact of absence of visibility. Liu et al. [24] proposed an experiment of evacuation from a classroom with two exits, with the aim to study the impact of congestion and density on the route choice of the students.
The experiment presented in the next Section is aimed at studying the effect of both congestion avoidance and following behaviors and it proposes a different scenario consisting in two rooms connected by up to 3 doors, where pedestrians are asked to pass through. The authors do not want to consider it as an evacuation experiment, since all participants have been explicitly asked to not rush or push others during their movement, thus it aims at investigating the route choice in standard situations.
An experiment to understand tactical decisions
The experiment has been performed at the University of Tokyo in November 2015. A group of 46 persons has participated, uniformly composed of male students aged around 20 years old. The setting has been configured with the intention to acquire empirical evidences on the influence of crowding conditions on route choice decisions. The setting is designed to describe an elementary choice: it is characterized by a rectangular environment of 7.2 × 12 m2 divided in two areas of equal size; the access is regulated by three gates positioned to create three paths of different lengths. A schematic representation of the scenario is illustrated in Fig. 1.
The entrance and exits of the environment are aligned on the x-axis, in order to generate a shortest path (Path a ) and to induce the decisions of the participants. Table 1 describes the average lengths of the three possible paths, calculated as the sum of distances between the central points of the crossed openings.
The difference between Path
a
and
Path
b
is relatively small (<1 m) while
Path
c
is significantly longer than the shortest path. These
differences will be reflected on the achieved results pointing out, as generally known, that
the main element influencing the route choice is the distance. The two starting areas in the
scenario have been used individually one after the other, in order to optimize the
procedural times, on one hand, and to test the potential influence of a mirror placement of
the gates, by reversing the flow direction in the environment. The openings related to
Path
b
and Path
c
were eventually
closed to configure different procedures. Each procedure has been repeated 4 times to
achieve a more consistent dataset. The procedures are described in the following: only
Path
a
allowed; Path
a
and
Path
b
allowed; Path
a
and
Path
c
allowed; all gates are open.
The procedure iterations have been performed with a randomized schedule, to possibly avoid bias provided by the learning of participants. Finally, to stimulate the will to minimize the traveling time towards the destination, the participants have been asked to reach quickly the opposite side of the setting.
Methodology for the analysis
The experiment has been performed under an arcade of the university buildings, due to weather conditions. The lack of safe points to attach any camera to the ceiling did not allow to have a zenithal perspective in the video recordings, which would be useful for an automatic tracking. Hence, four HD cameras positioned on tall tripods (5m circa) have been used to record the experiment. The videos have been synchronized by means of a global chronometer shown to the cameras at the beginning of the recording. Since the frame rate of the two cameras with the highest resolution was slightly variable (a small number of frames was skipped during the recording), some manual adjustment has been done to the video synchronization. This was possible by using visible events in the overlapping areas of multiple camera views and also by using the audio track of the videos. The software AviSynth has been employed to achieve the synchronization and merge the multiple video tracks. The results that will be presented in the following subsection has been achieved by means of manual counting and tracking.
Results and discussion
The video footages of the performed experiments did not allow us to perform a fine tracking of the exact trajectories followed by the different pedestrians, mainly due to the positioning of cameras. Nonetheless, different types of analysis will be carried out to acquire novel empirical evidences on pedestrian route choice in presence of crowding conditions.
So far, we focused on two relatively simple analysis that regarded: (i) the number of participants who passed through each gate depending on the experimental procedure, and therefore on the level of congestion; (ii) the time passed from the start signal of the staff until the last person leaves the observed area, which we denoted as completion time of the procedure. The principal aim of the analysis was to verify if the experimental results supported the conjecture that pedestrians, when the perceived level of congestion makes less appealing the shortest path, choose a longer trajectory to preserve their walking speed. Additional analyses will be carried out, within the limits posed by the vantage point, as a consequence of the results of this first round of integrated analysis and synthesis activities [35].
Table 2 shows the data achieved with the experiment. As briefly introduced, procedure 2 and 3 are characterized by a decision among two choices, the shortest path and a longer one; in procedure 2 the difference among the alternatives is quite small (i.e. less than a meter, less than 10% of the shortest trajectory, considering the middle point of the gates for the measurement), whereas in procedure 3 the longer trajectory is more significantly worse than the shortest path (i.e. over 20% longer). Finally, procedure 4 allows pedestrians to choose among all three alternatives. Nonetheless, intermediate gates are small (1 m) but the evidence shown that they still allow the passage of two pedestrians almost at the same time. Moreover, the passage between the starting area and the region before the gates is relatively wide (2.4 m) and here pedestrians are able to walk side by side; this implies that some of them are naturally closer to the best trajectory while for others the worst ones are not that longer.
Results are in line with the conjecture that pedestrians would distribute among the alternative passages in case of congestion. In fact, in procedure 2, almost half of the pedestrians chooses the slightly longest path to avoid the congestion in the Eastern door and to possibly preserve their desired speed: in average, the completion time of procedures in which two passages are present (i.e. procedure 2 and 3) are at least 5 s lower than for procedure 1, meaning that this decision allowed a higher flow throughout the environment. The fact that, in procedure 3, the longer alternative (Path c ) is more significantly worse than the shortest path, makes this choice appealing to a slightly lower number of pedestrians. On the other hand, this did not lead to a significant impact on the average completion time, which is similar to the one of procedure 2. Procedure 4, finally, shows that the Path a and Path b are perceived as almost equivalent, but a few pedestrians even choose Path c allowing to decrease the completion time of about half second on average: this also suggests that, considering this crowding level, two passages are sufficient to grant a smooth flow of pedestrians.
A few general qualitative considerations on all the analyzed procedures can be done: pedestrians choosing
longer paths (Path
b
and
Path
c
) generally enter the area
before the gates on the Western side; pedestrians choosing longer paths generally do so after some preceding ones have
perceivably chosen the best path, and therefore can be considered as potential
future competitors either for the occupation of the gate or for the path leading to
it; this is particularly apparent for procedure 3 and 4; sometimes, when choosing the longer path
(Path
c
) pedestrians seem to
follow someone before them that had chosen this trajectory before
and, at the same time, avoiding much closer pedestrians that have
perceivably chosen other shorter paths.
Figure 2 emphasizes these considerations by showing 4 screen captures of the footage of one iteration of the experiment. While these results are still quite aggregated, they suggest that pedestrians consider the expected travel time rather than just the length of the trajectory. Moreover, they also suggest that there might be a form of behavioral implicit interaction [5], to some extent reminding conflicting but simultaneously present behavioral components of cohesion and separation of the boids model [29]. In particular, the modeling approach that will be introduced in the following Section, will consider both the fact that other pedestrians are generally perceived as repulsive (as for proxemics theory) but also the fact that the decision of a pedestrian to detour (i.e. change a previous decision on the path to be followed) is a locally perceivable event that might trigger a similar reconsideration by nearby pedestrians.
A model to encompass the pedestrian movement and route choice
This Section will propose a multi-agent model designed for the simulation of pedestrian movement and route choice behavior. The model of agent is composed of two elements, respectively devoted to the low level reproduction of the movement towards a target (i.e. the operational level, considering a three level model described in [25]) and to the decision making activities related to the next destination to be pursued (i.e. the route choice at the tactical level). The component devoted to the operational level behavior of the agent is not extensively described since, for this purpose, the model described in [2] has been applied. For a proper understanding of the approaches and mechanisms that will be defined at the tactical level, on the other hand, a brief description on the representation of the environment, with different levels of abstractions, is firstly provided in this Section. More attention will then be devoted to the introduction and discussion of the model for the management of the route choice, which represents the main contribution of this paper.
The representation of the environment and the knowledge of agents
The adopted agent environment [38] is discrete and modeled with a rectangular grid of 40 cm sided square cells. The size is chosen considering the average area occupied by a pedestrian [37], and also respecting the maximum densities usually observed in real scenarios. The cells have a state that informs the agents about the possibilities for movement: each one can be vacant or occupied by obstacles or pedestrians (at most two, so as to be able to manage locally high density situations).
To allow the configuration of a pedestrian simulation scenario, several
markers are defined with different purposes. This set of objects has
been introduced to allow the movement at the operational level and the reasoning at the
tactical level, identifying intermediate and final targets: start areas
openings
regions
final
destinations
obstacles
, places were pedestrians are generated: they contain
information for pedestrian generation both related to the type of pedestrians and to
the frequency of generation;
, sets of cells that divide, together with the obstacles,
the environment into regions. These objects constitutes the decision elements for
the route choice;
, markers that describe the type of the region where they
are located: with them it is possible to design particular classes of regions (e.g.
stairs, ramps) and other areas that imply a particular behavior of
pedestrians;
, the ultimate targets of
pedestrians;
, non-walkable cells defining obstacles and non-accessible
areas.
An example of environment annotated with this set of markers is proposed in Fig. 3(b). This model uses the floor fields approach [4], using the agents’ environment as a container of information for the management of the interactions between entities. In this particular model, discrete potentials are spread from cells of obstacles and destinations, informing about distances to these objects. The two types of floor fields are denoted as path field, spread from openings and final destinations (one per destination object), and obstacle field, a unique field spread from all the cells marked as obstacle. In addition, a dynamic floor field that has been denoted as proxemic field is used to reproduce a proxemic behavior [15] in a repulsive sense, letting the agents to maintain distances with other agents. This approach generates a plausible navigation of the environment as well as an anthropologically founded means of regulating interpersonal distances among pedestrians.
This framework, on one hand, enables the agents to have a position in the discrete environment and to perform movement towards a user configured final destination. On the other hand, the presence of intermediate targets allows choices at the tactical level of the agent, with the computation of a graph-like, topological, representation of the walkable space, based on the concept of cognitive map [34]. The method for the computation of this environment abstraction has been defined in [7] and it uses the information of the scenario configuration, together with the floor fields associated to openings and final destinations. In this way a data structure for a complete knowledge of the environment is pre-computed. Recent approaches explores also the modeling of partial knowledge of the environment by agents (e.g. [1]), but this aspect goes beyond the scope of the current work. The cognitive map identifies regions (e.g. a room) as nodes of the labeled graph and openings as edges. An example of the data structure associated to the sample scenario is illustrated in Fig. 3(c). Overall the cognitive map allows the agents to identify their topological position in the environment and it constitutes a basis for the generation of an additional knowledge base, which will enable the reasoning for the route calculation.
This additional data structure has been called Paths Tree and it contains the information about plausible paths towards a final destination, starting from each region of the environment. The concept of plausibility of a path is encoded in the algorithm for the computation of the tree, which is discussed in [10] and only briefly described here. The procedure starts by defining the destination as the root of the tree and it recursively adds child nodes, each of them mapped to an intermediate destination reachable in the region. Nodes are added if the constraints describing the plausibility of a path are satisfied: in this way, trajectories that imply cycles or a not reasonable usage of the space (e.g. passing inside a room to reach the exit of a corridor, as illustrated in Fig. 3(a)) are simply avoided.
The results of the computation is a tree whose nodes are mapped to targets in the environment and each edge refers to a particular path between two targets. The root of the tree is mapped to a final destination, while the underlying nodes are only mapped to openings. Hence, each branch from the root to an arbitrary node describes a minimal (i.e. plausible) path towards the final destination associated to the tree. To complete the information, each node n is labeled with the free flow travel time 1 associated to the path starting from the center of the opening associated to n and passing through the center of all openings mapped by the parent nodes of n, until the final destination. In this way, the agents knows the possible paths through the environment and their respective estimated traveling times.
For the choice of their path, agents access the information of a Paths Tree generated from a final destination End with the function Paths (R, End). Given the region R of the agent, the function returns a set of couples {(P i , tt i )}. P i ={ Ω k , …, End } is the ordered set describing paths which start from Ω k , belonging to Openings (R), and lead to End. tt i is the associated free flow travel time.
The route choice model of agents
This aspect of the model is inspired by the behaviors observed in the experiment presented in Section 3. The objective is to propose an approach that would enable agents to choose their path considering distances as well as the evolution of the dynamics. At the same time, the model must provide a sufficient variability of the results (i.e. of the paths choices) and a calibration over possible empirical data.
To understand the mechanisms designed in the model, the discussion must start with an overview of the agent life-cycle, illustrating which activity is performed and in which order. The workflow of the agent, encompassing the activities at operational and tactical level of behavior at each time-step, is illustrated in Fig. 4.
First of all, the agent performs a perception of its situation considering its knowledge of the environment, aimed at understanding its position and the markers perceivable from its region (e.g. intermediate targets). At the very beginning of its life, the agent does not have any information about the location, thus the first assignment to execute is localization. This task analyses the values of floor fields in its physical position and infers the location in the Cognitive Map. Once the agent knows the region where it is situated, it loads the Paths Tree and evaluates possible paths towards its final destination.
The evaluation has been designed with the concept of path utility, assigned to each path to successively compute a probability to be chosen by the agent. The probabilistic choice of the path outputs a new intermediate target of the agent, used to update the reference to the floor field followed at the operational layer with the local movement.
The scheme points out that the evaluation of the plan is not only performed at the beginning of the simulation. The wayfinding component is in fact activated at the beginning of every step, yet the plan is reconsidered only in two cases: (i) the agent has just entered into a new region or (ii) the current way that the agent is following has been perceived as congested.
The first case means that the agent enters in a new region and it is able to perceive new information about its current path and the possible alternatives, thus it performs a new evaluation. In the second case, however, the evaluation is performed while reaching the intermediate target, if the path passing through this has been perceived congested. Basically this implies that until this congestion is perceived, the agents reconsider their decisions in favor of alternatives, thus assuming an uncertain behavior in case of having multiple congested ways. To improve the dynamics in this situations, an inertia mechanisms preserving the current decision is introduced. This is managed by means of two parameters, configuring two time intervals: a short one (τ short ), to use right after a new decision has been taken, and a longer one (τ long ), to be used if the evaluation led again to the current or previously chosen choice.
In particular, when an agent reconsiders the chosen plan due to congestion and then chooses again the original plan, then the choice will not be reconsidered before a longer period of time τ long . The rationale behind this modeling choice is that the agent has tried an alternative path, but eventually it turned out to be less convenient than initially expected. Therefore the agent will have some inertia and it will try to stand by the original plan at least for τ long , limiting erratic forth and back movements.
The utility-based approach fits well with the needs to easily calibrate the model and to achieve a sufficient variability of the results. The core functions of the wayfinding model are Evaluate Paths and Choose Paths, which will be now discussed.
The utility and choice of paths
The function that computes the probability of choosing a path is exponential with
respect to the utility value associated to it. This is completely analogous to the
choice of movement at the operational layer:
The usage of the exponential function for the computation of the probability of
choosing a path P is a good solution to emphasize the differences in
the perceived utility values of paths, limiting the choice of relatively bad solutions
(that in this case would lead the agent to employ relatively long paths).
U (P) comprises the three observed components
influencing the route choice decision, which are aggregated with a weighted sum:
where the first element evaluates the expected travel times; the second considers the queueing (crowding) conditions through the considered path and the last one introduces a positive influence of perceived choices of nearby agents to pursue the associated path P (i.e. imitation of emerging leaders). All the three functions provide values normalized within the range [0, 1], thus the value of U (P) is included in the range [- κ q , κ tt + κ f ].
In theory, there is no best way to define these three components: the usage of very simple functions as well as complicated ones might provide the same quality to the model. The only way to evaluate the reliability of this model, in fact, is with a validation procedure over some empirical knowledge. Hence, these three mechanisms have been designed with the main objective to allow the calibration over empirical datasets, preferring the usage of simple functions where possible.
Building a function for the evaluation of traveling times is a arduous task, despite
the mere usage of the traveling times information could be thought already as a good
solution. First of all, the information about the travel time
tt
i
of a path
P
i
is derived from the Paths Tree with
Paths (R, End) (where
End is the agent’s final destination, used to select the appropriate
Paths Tree, and R is the region in which the agent is situated and it
is used to select the relevant path P
i
in
the Paths Tree structure) and it is integrated with the free flow travel time to reach
the first opening Ω
k
described by each
path:
where PF Ω k (x, y) is the value of the path field associated to Ω k in the position (x, y) of the agent and Speed d is the desired velocity of the agent, that can be an arbitrary value (see [2] for more details of this aspect of the model).
Then, as just introduced, this travel time value could be used as-it-is to design the
cost of a path regarding this component of the utility function:
where N tt is the normalization factor, i.e., 1 over the sum of TravelTime (P) for all paths. Hence, the greatest the travel time, the closer the value of the function to -1 and the lower the utility for the choice of that path (assuming κ tt > 0). However, let us consider a simple case in which the agent can choose between two doors relatively side-by-side, separated by a small wall. The probability to choose each door should change according to the position of the agent and the target, making the choice of one door predominant in cells from which its choice would imply a shorter trajectory and producing a much less predictable behavior in the area in which the choice of the door to follow is less relevant (i.e. the alternative trajectories have similar length), from the point of view of the length of the trajectory. To represent and analyze this uncertainty in the route choice, the concept of entropy heat map has been introduced (see the Appendix for more detail) and it is tested with a simplification of the large scenario used for the experiment in the next Section: for the moment, it is sufficient to say that there are four starting areas connected to a large atrium by relatively large corridors, whereas the atrium has a variable number of exits, used to explore the entropy landscape in different situations.
Figure 5(a) illustrates the entropy over the space of the setting with two gates leading to the outside area, located in the upper part, achieved with calibration weights configured as κ tt = 100, κ q = 0, κ f = 0 (only this component of the utility influences the agents choice in this test). It is possible to see that the choice from each cell of the environment seems to respect the desired behavior: very low entropy in the surrounding of each door, high entropy in the space between them (the size of this area depends on κ tt ). Let us now introduce a gate in a relatively far position from the two considered so far, as shown in Fig. 5(b). Since the exit is this distant, it should not influence the decisions in the portion of space close to the previous two gates. As depicted in the entropy map, however, it does have a noticeable impact. With this configuration of Eval tt , the entropy values gets sensibly higher in the part of the environment where the choice, before the introduction of this additional path, was essentially deterministic. This is due to the normalization element N tt of the travel time values, which smooths the differences in the distance between the first two paths –related to the closer doors– with the introduction of the very long one. This means that this simple function is not effective to model this component.
This problem has been avoided by using the minimum value of the traveling times over
the possible paths in the function as follows:
In this way the range of Eval tt is changed to (0,1], being 1 for the path with minimum travel time and decreasing the higher the difference with this. As it is shown in Fig. 5(c) and (d), the introduction of an additional but locally irrelevant path does not affect anymore the probability distribution in the area surrounding the close doors. In addition, a comparison between Fig. 5(a) and (c) highlights that the new equation did not make a sensible difference in the values of the simple case with two gates, thus Eq. 5 is now suitable to model this utility component.
The behavior modeled in the agent in this model considers congestion as a negative element for the evaluation of the path. This does not completely reflect the reality, since there could be people who could be attracted by congested paths as well, showing a mere following behavior. On the other hand, by acting on the calibration of the parameter κ q it is possible to define different classes of agents with customized behaviors, also considering attraction to congested paths with the configuration of a negative value.
For the evaluation of this component of the route decision making activity associated to a path P, a function is first introduced for denoting agents a′ that precede the evaluating agent a in the route towards the opening Ω of a path P:
where Pos and Dest indicates respectively the position and current destination of the agent; the fact that PF Ω (Pos (a′)) < PF Ω (Pos (a)) assures that a′ is closer to Ω than a, due to the nature of floor fields. Each agent is therefore able to perceive the main direction of the others (its current destination). This kind of perception is plausible considering that only preceding agents are counted, but we want to restrict its application when agents are sufficiently close to the next passage (i.e. they perceive as important the choice of continuing to pursue that path or change it). To introduce a way to calibrate this perception, the following function and an additional parameter γ is introduced:
The function Eval q is finally defined with the normalization of PerceiveForward values for all the openings connecting the region of the agent:
where FirstEl returns the first opening to cross of a path, myself denotes the evaluating agent and width scales the evaluation over the width of the door (larger doors sustain higher flows).
This component of the decision making model aims at representing the effect of an additional stimulus perceived by the agents associated to sudden decision changes of other persons that might have an influence. An additional grid has been introduced to model this kind of event, whose functioning is similar to the one of a dynamic floor field. The grid, called ChoiceField, is used to spread a gradient from the positions of agents that, at a given time-step, change their plan due to the perception of congestion.
The functioning of this field is described by two parameters
ρ
c
and
τ
c
, which defines the diffusion radius
and the time needed by the values to decay. The diffusion of values
from an agent a, choosing a new target Ω′, is
performed in the cells c of the grid with
Dist (Pos (a) ,
c) ≤ ρ
c
with the
following function:
The diffused values persist in the ChoiceField grid for τ c simulation steps, then they are simply discarded. The index of the target Ω′ is stored together with the diffusion values, thus the grid contains in each cell a vector of couples {(Ω m , diff Ω m ) , …, (Ω n , diff Ω n )}, describing the values of influence associated to each opening of the region where the cell is situated. While multiple neighbor agents changes their choices towards the opening Ω′, the values of the diffusion are summed up in the respective diffΩ′. In addition, after having changed its decision, an agent spreads the gradient in the grid for a configurable amount of time steps represented by an additional parameter τ a . In this way it influences the choices of its neighbors for a certain amount of time.
The existence of values diff Ω k > 0 for some opening Ω k implies that the agent is influenced in the evaluation phase by one of these openings, but the probability for which this influence is effective is, after all, regulated by the utility weight κ f . In case of having multiple diff Ω k > 0 in the same cell, a individual influence is chosen with a simple probability function based on the normalized weights diff associated to the cell. Hence, for an evaluation performed by an agent a at time-step t, the utility component Eval f can be equal to 1 only for one path , between the paths having diff Ω k > 0 in the position of a.
The evaluation of the model is discussed with two simulation scenarios: (i) the simulation of the experiment performed at the Tokyo university and (ii) a simulation of a larger scenario, with the aim of verifying the behavior of the model in a real-world environment and to perform a qualitative comparison of the results with another wayfinding model from the literature.
All presented results have been achieved with the calibration weights of the utility function configured as Ω tt = 100, Ω q = 25 ; Ω f = 5, while the parameters related to the ChoiceField have been set to ρ c = 1.2m, τ c = 0.5s and τ d = 1s. The configuration of these parameters has been achieved after an exploratory work on the calibration of the model, in which various absolute values and proportions among the parameters have been experimented with the aim to fit the range of the empirical dataset. A more thorough sensitive analysis and discussion of the effects of each parameter on the simulation results is object of ongoing works.
In the first scenario a unique desired speed of agents of 1.6 m/s has been configured, since all participants to the experiment were young male students instructed to move quickly. For the large scenario, instead, this kind of homogeneity cannot be assumed (due to the large number of simulated pedestrians), therefore a normal distribution of desired speeds is generated, centered in 1.4 m/s and with standard deviation of 0.2 m/s, in accordance with the pedestrians speeds usually observed in the real world (e.g. [39]). The distribution is discretized in classes of velocity, starting from 1.0 m/s and with a maximum of 1.8 m/s, each 0.1 m/s wide (see the blue boxes in Fig. 8(c)). To allow a maximum speed of 1.8 m/s — considered plausible in this outflow scenario— the time-step duration is assumed to s.
Validation in the experiment scenario
Figure 6 shows some screenshots of a simulation run (with procedure 4, i.e. all paths available), where the scenario configuration is also displayed. A unique start area has been configured for all the runs: at this point, in fact, no mechanism has been introduced to induce decisions on one particular direction (e.g. left or right turn in case of conflict), thus the model is not reproducing any difference by inverting the direction of flow in this environment. To configure the three procedures of the experiment, center and right doors are eventually filled with obstacles.
A set of 50 iterations are run for each procedure, to exhaustively explore the variability of the results and achieve a reliable average. In order to understand the improvement achieved through the proposed approach in the simulation results, an additional set of 50 iterations is executed in the same scenario with a baseline version of the model, not employing the wayfinding functionality described in Section 4: this baseline is essentially a floor-field model in which pedestrians non-deterministically follow the least-effort principle, mitigated by proxemic considerations but only on the choice of the next cell to occupy. Within this set of experiments, a unique floor field is spread out from the cell of the final destination (the blue object in Fig. 6) and throughout all of the environment. In this way the agents try to avoid congestion only locally, and pedestrians can pass through a sub-optimal gate f only because, at a certain point of the simulation, the overall system dynamics brought it closer to f than to the initially optimal gate to choose.
A comparison between the simulation results and the empirical data achieved with the experimental procedures, regarding the counting of people passing through each door, is shown in Fig. 7(a), (b) and (c). By looking at the results achieved with the baseline model, there is a sensible error produced for the procedure 2, where agents passing through the central door have been about 15 on average while in the observations this path was used by around 23 persons. In addition, the baseline model provides higher variability of results for this procedure, which overall cannot be calibrated in a effective way. The error is particularly noticeable in the other two procedures where, due to the pure floor field approach that leads the agents to try to follow the shortest path, the west door has not been employed at all during all simulation runs.
Figure 7(d) shows a comparison of the completion times observed in the experiment and achieved with the simulation iterations. Despite the variability of results also provides data in a range of about 5 seconds, the average completion times achieved with the usage of the proposed model is close to the empirical one in all the simulated procedures. Overall the trend is also respected. Firstly, in procedure 3 it has been observed an average completion time slightly higher than in procedure 2 (see Table 2) and this is also reflected in the model, even though more significantly. In addition, simulations shown that procedure 4 provides a lightly lower average completion time than all the other procedures and this has also been observed in the experiment.
The proposed wayfinding model is instead more effective in reproducing the empirical dataset. The average values are very close to the observed ones and the range of variability is also contained. This emphasizes that this model can be successfully calibrated to fit this empirical data range achieved with the experiment runs, for all the tested procedures.
For a more qualitative analysis, the distribution of pedestrian choices over the space before the three doors is shown in the screenshots of Fig. 6, taken every 2 seconds from time 4s to 10s. The screenshots illustrate the current target of the agents by changing their color: brown for the top door, cyan for the central one and purple for the bottom. It is evident that the top rows of cells of the region –according to this visualization– are crossed for the most by agents headed towards the top gate, while the remaining part is characterized by a less decided behavior of agents near the entrance of the region, which gets more deterministic by getting closer to the two doors. Qualitatively, the distribution of decisions is in accordance with what has been observed in the videos of the experiment.
Large scale scenario
The aim of the second simulation scenario is to analyze the outputs of the model in presence of a larger and more realistic scenario. The simulation scenario describes the outflow from a portion of the Düsseldorf Arena, as described in [36]. The annotated environment used for the simulation with the discussed model is illustrated in Fig. 8(a): 4 starting areas (green in the figure) model the bleachers of the stadium and generates the agents in the simulation, whose aim is to reach the outside area indicated with the blue object (i.e. the Northern and Eastern borders of the scenario). Cyan objects are the intermediate targets describing the potential wayfinding decisions of agents. 250 agents are generated in random positions of the related start area at the beginning of the simulation, producing a total of 1000 pedestrians.
The heat map shown in Fig. 8(b) provides information about the usage of the space during the simulation, by describing the average local densities perceived by the agents (so-called cumulative mean density maps). The major congested areas are located in front of the exit doors, given their relatively small width of 1.2 m. An interesting point that comes out from this analysis (also visible in the screenshot in Fig. 8(a)) is that the present configuration of the environment implies that several exits receive an incoming flow from more sources (i.e. corridors), while there are 3 exits in the upper right corner of the environment which are not employed at all by the agents during the simulation. In addition, the usage of the exits is unbalanced, causing the level of density to be higher in some of them. An apparent effect of the mechanisms defined in the proposed wayfinding model is related to the visible traces of pedestrians that were moving together with other ones headed towards the most congested exits which actually changed their decision and moved towards less crowded ones.
The evaluation of this kind of result would require empirical data that could be used either to support the modeling choices or to confute the achieved results and therefore lead to a different calibration (e.g. adopting a lower weight for the consideration of travel time, that would lead to an increased usage of the farther exits).
The corridors connecting each bleacher to the atrium are affected as well by high densities (around 2.5–3 persons/m2) but their widths guarantee a sensibly higher flow, causing much lighter congestion —and so higher speeds—inside the starting regions.
Figure 8(c) shows a comparison between the distribution of the achieved average walking speeds (red bars) and initial desired speeds (blue bars) of agents during the simulation. The congestion arisen in the exit doors of the atrium sensibly affected the travel time of the agents. This caused that only a relatively small portion of the simulated population succeeded in maintaining its desired speed throughout the overall trajectory (the agents that have been generated in positions closer to the three exit corridors of the bleachers), while most of them experienced a significant delay during their way.
Conclusions
The present paper has described a research effort aimed at improving our understanding of decision making activities related to pedestrian route choices in presence of congestion, both by means of an experimental observation and by means of the definition of a general model for decision making activities related to pedestrian route choices. The model encompasses three aspects that has been observed to influence these choices: expected travel time, perceived level of congestion on the chosen path, and decisions of other preceding pedestrian to pursue a different path. The results achieved by means of an experimental observation describe the number of students choosing each path and the completion time for all the procedures: additional analyses we aim to carry out will focus on when and where the decision to follow a longer but supposedly faster trajectory is taken, considering a change in the trajectory (maybe following another pedestrian that already took such a decision). The defined model is an extension of previous works in this area, and it preserves desirable properties on the basic locomotion of pedestrians and aggregated effects in simple scenarios (e.g. corridors, bends and junctions): the experimental campaign described in this paper shows its adequacy in reproducing the empirical result achieved through the experimental observation. Moreover, the model has been applied to a larger scale scenario, in which it produced interesting results that would, however, require additional empirical evidences for a more thorough validation.
Ongoing works are aimed to achieve further analysis on the experiment, in order to acquire additional data for the validation of the model (especially aimed at fine tuning and validating the mechanism managing the change in the planned trajectory) and for possible improvements. Moreover, the effect of this kind of modeling approach in more complicated environmental structures (i.e. deeper trees for path planning) will also be investigated.
Footnotes
Appendix – The entropy heat map
The heat map used to evaluate and calibrate the model of this paper describes the concept
of entropy –conceived as in information theory [32]– calculated with the set of probabilities of choosing each path from all
points of the scenario. Generally speaking, given a set of events
(e1, e2, …,
e
n
) and p the function
to compute their probability, the entropy of the probability distribution is calculated
as:
where b indicates the measurement unit of the entropy and, as commonly used in this field, we assumed bits (b = 2). With this definition, H describes the content of information of the distribution, but by applying it to the probability distribution of the choices available to an agent a in a certain position during the simulation run, it can provide a description of its uncertainty in choosing the path, due to the current dynamics. In particular, let us consider a static setting without the influence of other agents and assume κ tt > 0. While the agent is in a position relatively close to a passage, the choice of paths employing that passage will get more probable in favor of the other possibilities, thus the value of H will get closer to 0. Conversely, if the agent is at a relatively same distance between alternative passages, H gets higher values, describing a relevant uncertainty of the agent.
The entropy heat map is then obtained by calculating the entropy of the probability distribution of the choices over possible paths for all the cell of the environment, at a certain step of the simulation.
The travel time that the agent can employ without encountering any congestion in the path, thus moving at its free flow speed.
Acknowledgments
This research has been partially founded by the Italian Association for Artificial Intelligence (AI*IA) with the “AI*IA OUTGOING MOBILITY GRANTS 2015”. The authors would like to thank Francesco Crippa for his support in the development and testing of the model.