Computer-based simulation of pedestrian dynamics is a consolidated application of agent-based models but it still presents open challenges. The wayfinding of pedestrians is a fundamental aspect to allow the application of such models on complex environments. Several novel approaches have recently been proposed in the literature, yet the lack of empirical knowledge still limits the reliability of the heuristics used in the models. In this paper, a novel model for the simulation of pedestrian wayfinding is discussed and the aim is to provide general mechanisms that can be calibrated for the reproduction of empirical evidences. The model is, in fact, inspired by the behaviors observed in a experiment performed with human volunteers in November 2015, which were put into a trade off scenario, since different paths were available but the shortest one was quickly congested. We observed that several pedestrians choose longer trajectories to preserve high walking speed, and often do so following a first emerging leader. The proposed model encompasses both a proxemic tendency to avoid congestion, as well as an imitation mechanism: these conflicting tendencies can be calibrated according to empirical evidences. A demonstration of the simulated dynamics on a larger scenario will be illustrated in the paper.
The simulation of the movement of pedestrians and crowds in spatial structures is a consolidated research and application context that still presents challenges for researchers in different fields and disciplines: both the automated analysis and the synthesis of pedestrian and crowd behaviour, as well as attempts to integrate these complementary and activities [Vizzari and Bandini, 2013], present open issues and potential developments in a smart environment perspective [Sassi et al., 2015]. Although the currently available commercial tools are used on a day-to-day basis by designers and planners1, according to a report commissioned by the Cabinet Office [Challenger et al., 2009] 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. 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, and it quickly becomes congested. The other choice can therefore become much more reasonable, allowing a higher average walking speed and comparable (if not even lower) travel time. We observed that several pedestrians choose longer paths to preserve high walking speed, and often do so following a first emerging leader. Modeling this kind of choices with current approaches can be problematic.
The present work represents a step in the direction of producing a general model fitting this kind of evidences. The proposed model encompasses both a proxemic tendency to avoid congestion, as well as an imitation mechanism: these conflicting tendencies can be calibrated according to empirical evidences. After a discussion of relevant related works, an analysis of different alternatives for modeling and simulating 1See http://www.evacmod.net/?q=node/5 for a large list of pedestrian simulation tools). this kind of scenario will be illustrated in Section 3. Results of the application of the proposed model in a real world scenario, initially described in [Wagoum et al., 2012], will then be described, with reference to their plausibility. Conclusions and future works will end the paper. 2
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 route
Recent works in the area of pedestrian and crowd simulation started to investigate this aspect. In particular, [Guo and Huang, 2011] proposed the modification of the floor-field Cellular Automata [Burstedde et al., 2001] approach for considering pedestrian choices not based on the shortest distance criterion but considering the impact of congestion on travel time. [Wagoum et al., 2012] 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.
Iterative approaches, borrowing models and even tools from vehicular transportation simulation, 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 [Kretz et al., 2014]. 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 [La¨mmel et al., 2009]. This iterative scheme has also been employed in multi-scale modeling approaches [La¨mmel et al., 2014; Crociani et al., 2016].
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 [Sacerdoti, 1974] 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 [Kapadia et al., 2013], 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 [Levihn et al., 2013]. 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 [Crociani et al., 2015], also allows exploiting already existing models dealing with low level aspects of pedestrian actions and perceptions.
The main issues in transferring AI planning results within
this context of application, and more generally producing
generally 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,
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
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 dedicated to the low level reproduction of the
movement towards a target
The adopted agent environment [Weyns et al., 2007] 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 [Weidmann, 1993], 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 , places were pedestrians are generated: they contain information for pedestrian generation both related to the type of pedestrians (e.g. the distribution of their destinations), and to the frequency of generation; openings , sets of cells that divide, together with the obstacles, the environment into regions. These objects constitutes the decision elements, intermediate destinations, for the route choice activities; regions , 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; final destinations ans;
, the ultimate targets of pedestriobstacles , non-walkable cells defining obstacles and non-accessible areas.
An example of environment annotated with this set of markers is proposed in Fig. 1(b). This model uses the floor fields approach [Burstedde et al., 2001], 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 [Hall, 1966] 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 representation of the walkable space, based on the concept of cognitive map [Tolman, 1948]. The method for the computation of this environment abstraction has been defined in [Crociani et al., 2014] 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 precomputed. Recent approaches explores also the modeling of partial knowledge of the environment by agents (e.g. [Andresen et al., in press]), 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. 1(c). Overall the cognitive map allows the agents to identify their 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 [Crociani et al., 2015] 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, paths 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. 1(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 time2 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 P aths(R; End). Given the region R of the agent, the function returns a set of couples f(Pi; tti)g. Pi = f k; : : : ; Endg is the ordered set describing paths 2The travel time that the agent can employ without encountering any congestion in the path, thus moving at its free flow speed. (a) (b) (c) (d) which start from k, belonging to Openings(R), and lead to End. tti is the associated free flow travel time. 3.2
This aspect of the model is inspired by the behaviors observed in a experiment performed with human volunteers in November 2015 at the University of Tokyo, aiming at identifying basic behavior at the wayfinding level. The participants were put into a trade off scenario, since different paths were available but the shortest one was quickly congested. Empirical analysis related to this experiment are not presented in this paper for lack of space. Qualitatively, it has been observed that several persons preferred to employ a longer trajectories for achieving higher walking speed, but this kind of choice seemed to be taken more frequently and easily after a first emerging leader had performed it.
By considering these aspects, 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.
The discussion of the model must starts with an overview of the agent life-cycle, in order to understand 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 Figure 2.
First of all, the agent performs a perception of his situation considering his knowledge of the environment, aimed at understanding its position in the environment 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 its location, thus the first assignment to execute is the 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 the 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 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 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:
P rob(P ) = N eU(P ) (1)
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:
U (P ) = ttEvaltt(P ) qEvalq(P ) + f Evalf (P ) (2) where the first element evaluates the expected travel times; the second considers the queuing (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. (3) (4)
The evaluation of traveling times is a crucial element of the model. First of all, the information about the travel time tti of a path Pi is derived from the Paths Tree with P aths(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 Pi 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:
TravelTime(Pi) = tti +
P F k (x; y)
Speedd where P F k (x; y) is the value of the path field associated to k in the position (x; y) of the agent and Speedd is the desired velocity of the agent, that can be an arbitrary value (see [Bandini et al., in press] for more details of this aspect of the model). The value of the traveling time is then evaluated by means of the following function:
Eval tt(P ) = Ntt
min Pi2Paths(r)
TravelTime(P ) (TravelTime(Pi)) where Ntt is the normalization factor, i.e., 1 over the sum of TravelTime(P ) for all paths. By using the minimum value of the list of possible paths leading the agent towards its own destination from the current region, the range of the function is set to (0,1], being 1 for the path with minimum travel time and decreasing as the difference with the other paths increases. This modeling choice, makes this function describe the utility of the route in terms of travel times, instead of its cost.
This design is motivated by the stability of its values with the consideration of relatively long path, which might be represented in the simulation scenario. By using a cost function, in fact, the presence of very high values of TravelTime(P ) in the list would flatten the differences among cost values of other choices after the normalization: in particular, in situations in which most relevant paths have relatively similar costs, excluding a few outliers (even just one), the normalized cost function would provide very similar values for most sensible paths, and it would not have a sufficient discriminating power among them.
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 a0 that precede the evaluating agent a in the route towards the opening of a path P : The function Eval q is finally defined with the normalization of PerceiveForward values for all the openings connecting the region of the agent:
Eval q(P ) = N
PerceiveForward (FirstEl (P ); myself )
width(FirstEl (P )) where FirstEl returns the first opening 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 0, is performed in the cells c of the grid with Dist (Pos(a); c) c with the following function:
Di use(c; a) =
1 (1=Dist (Pos(a); c) if Pos(a) 6= c otherwise (8)
The diffused values persist in the ChoiceField grid for c simulation steps, then they are simply discarded. The index of the target 0 is stored together with the diffusion values, thus the grid contains in each cell a vector of couples f( m; di m ); : : : ; ( n; di n )g, describing the values of Forward ( ; a) = jfa0 2 Agnfag : Dest(a0) = ^ PF (Pos(a0)) < PF (Pos(a))gj (5) where P os and Dest indicates respectively the position and current destination of the agent; the fact that PF (Pos(a0)) < PF (Pos(a)) assures that a0 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:
PerceiveForward ( ; a) = (Forward ( ; a); if PF (Pos(a)) < 0; otherwise (6) (7) influence associated to each opening of the region where the cell is situated. While multiple neighbor agents changes their choices towards the opening 0, the values of the diffusion are summed up in the respective di 0 . 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 di 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 di k > 0 in the same cell, a individual influence is chosen with a simple probability function based on the normalized weights di associated to the cell. Hence, for an evaluation performed by an agent a at time-step t, the utility component Evalf can be equal to 1 only for one path P , between the paths having di k > 0 in the position of a. 4
The evaluation of the model is here discussed with a simulation of a large 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 the presented results have been achieved with the
calibration weights of the utility function configured as tt =
100; q = 27; f = 5, while the parameters related to the
ChoiceF ield are set to c = 1:2m, c = 2 time-steps =
0:44s and d = 4 time-steps = 1s. The desired speed of
agents have been configured with a normal distribution
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
The simulation scenario describes the outflow from a portion of the Du¨sseldorf Arena, as described in [Wagoum et al., 2012]. The annotated environment used for the simulation with the discussed model is illustrated in Fig. 3(a): 4 starting areas models 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. Cyan objects are the intermediate targets describing the wayfinding decisions of agents. 250 agents are generated at the beginning of the simulation from each start area, producing a total of 1000 pedestrians.
The heat map shown in Figure 3(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). 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 screen-shot in Fig. 3(a)) is that the present configuration of the environment implies (a) (b) (c) 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. The evaluation of this evidence would require empirical data that could be used either to support the modeling choices or to confute these results and 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 far 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 smoother congestion —and so higher speeds— inside the starting regions.
The red boxes of Fig. 3(c) shows the distribution of desired walking speeds compared to the achieved average walking speeds 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 a small portion of the simulated population succeeded in maintaining its desired speed (the agents generated in positions closer to the exit), while most of them experienced a significant delay during their way. 5
The present paper has introduced a general model for decision making activities related to pedestrian route choices. The model encompasses three aspects influencing these choices, as observed in an experimental observation: expected travel time, perceived level of congestion on the chosen path, and decisions of other preceding pedestrian to pursue a different path. Achieved results are both plausible and encouraging, though a proper validation of the model would require additional results but also the acquisition of empirical evidences on human wayfinding decisions in congested situations.