Multi-scale modelling is a powerful approach that has been successfully exploited in the context of simulation of traffic and transportation systems. While the paradigm allows the simulation of large cities in a already efficient fashion, the consideration of detailed environments for a precise simulation of pedestrian traffic can be still a demanding task, especially in iterative approaches for the search of optimal solutions. In this context, the paper proposes the application of a supervised machine learning algorithm to learn the observables of a microscopic model of pedestrian dynamics in the simulated environment. The aim is to generate a simpler model that (i) is able to describe the dynamic travel times of pedestrians in the scenario and (ii) can replace the microscopic model in the iterative search of optimal solutions. After a formal description of the approach, the paper provides preliminary results with its application in benchmark scenarios, aimed at analysing its reliability in controlled conditions.
Designers, planners employ tools for the simulation of pedestrians’ and crowd’s movement in the built environment on an everyday basis, especially in collective transportation facilities and in the urban context in general: decisions related to the construction or maintenance of specific facilities undergoing crowding situations call for results of the so-called what-if scenarios, indicating what plausibly happens within a given geometry subject to certain levels of demand. Even crowd managers, when already existing facilities must be used for hosting large numbers of pedestrians, growingly use these tools to evaluate the crowd management procedures before they are enacted. Results of research on pedestrian and crowd simulation has lead to technology transfer (off-the-shelf available commercial tools are daily used by designers and planners), but these products are sided by open challenges for researchers in different fields and disciplines, to improve model expressiveness (i.e. simplifying the modelling activity or introducing the possibility of representing phenomena that were still not considered) and efficiency of the simulators based on those approaches.
Despite the substantial effort and significant achieved
results, two aspects that are still object of investigation by the
research community are related to efficiency of the
developed simulators, on one hand, and to the requirements in
terms of modeler’s effort in tailoring a general model to
precisely represent a given scenario, with the related demand
and especially the so-called traffic assignment. A
particularly relevant effort, within this framework, is represented
by multi-scale approaches
Still, the need to carry out a substantial number of runs of micro-scale scenarios limits the practical applicability of the approach in case of very large scenarios and/or very limited time-frame for the elaboration of results. The approach proposed in this paper is based on the idea to substantially limit the number of the execution of micro-scale models but at the same time to employ the observable aggregated results to characterize the meso-scale model, preserving the accuracy in the management of aspects like interaction among pedestrians, but further reducing the computational costs. The basic idea is to actually learn the how observable aggregated results emerge from micro-scale simulations: the latter will therefore be run in plausible contextual conditions, but the attempt is to generalize the achieved results to actually define functions describing, for instance, the expected travel time of a pedestrian over an edge of the graph (i.e. a certain passage in the environment) given precise contextual conditions.
From this perspective, the proposed approach is somewhat
related to those employing computational intelligence
techniques for parameter estimation
The paper breaks down as follows: the following section more formally introduces the above mentioned multi-scale approach, whereas Sect. 3 more thoroughly presents the proposed learning model for micro-scale aggregated results. The experimental application of the proposed approach is then presented, discussing achieved results achieved in a uni and bidirectional corridor, and in a more complex paradigmatic benchmark scenario in which paradoxical effects can be observed. Conclusions and future developments end the paper. 2
The machine learning based approach proposed in this paper is applied to the multi-scale simulation system described in previous works by the authors [Crociani and La¨mmel, 2016; Crociani et al., 2016]. For completeness and to allow a clear understanding of the presented results in Sec. 4, fundamental mechanisms of the model will be now briefly described.
The simulation system is composed of two models with two different scales of detail: (i) a 2d discrete microscopic model for a detailed yet efficient reproduction of environments crossed by pedestrian flows; (ii) a queue model used to simulated a larger part of the transportation network, hosting heterogeneous forms of traffic. The integration between these two models composes a quite powerful approach, capable of performing analysis in metropolitan scenarios, by considering multiple modes of transportation and performing simulations in relatively short times.
Keeping the computational costs relatively low is very important for this model, since the multi-scale system applies an iterative approach to manage the agents’ strategic model, for which agents iteratively adapt their choice of route on the basis of a cost function applied to experienced travel times from the previous simulation. Overall this workflow makes the system converge either towards a Nash Equilibrium (NE) or to the system optimum (SO), depending on the chosen cost function. In this way the user of the simulation system is able to provide an estimation of the traffic in the scenario on a normal day (NE approach) or to have information about the minimum average travel time of the population of agents (SO). 2.1
The model is a 2-dimensional Cellular Automaton with a representation of the space as a grid of square cells. The 0:4 0:4 m2 size of the cells describes the average space occupation of a person [Weidmann, 1993] and reproduces a maximum pedestrian density of 6.25 persons/m2 which covers the values usually observable in the real world. Basically, a cell of the environment can be one of two types, walkable or obstacle, meaning that it will never be occupied by any pedestrian during the simulation.
Intermediate targets can also be introduced in the environment to mark the extremes of a particular region (e.g. rooms or corridors) which act as decision points for the routing choice of agents. Final goals of the discrete environment are its open edges, i.e., the entrances/exits of the discrete space that will be linked to roads. Since the concept of region is fuzzy and the space decomposition is a subjective task that can be tackled with different approaches, their configuration in the scenario is not automatic and is left to the user.
Employing the floor field approach [Burstedde et al., 2001] and spreading one field from each target –either intermediate or final– allows to build a network of the environment. In this graph, each node denotes one target and the edges identify the existence of a direct way between two targets (i.e. passing through only one region). To allow this, the floor field diffusion is limited by obstacles and cells of other targets. An example for an environment with the overlaid network is shown in Fig.1. The open borders of the microscopic environment are the nodes that will be plugged to the other network of the mesoscopic model.
To integrate the network with the one of the mesoscopic model and to allow the reasoning at the strategic level, each edge a of the graph is firstly labelled with its length la, describing the distance between two targets i; j in the discrete space. This value is computed using the floor fields as: la( 1; 2) = (FF 1 (Center ( 2)) + FF 2 (Center ( 1))) 2 (1) where FF (x; y) gives the value of the floor field associated to a destination in position (x; y); Center ( ) describes the coordinates of the central cell of . The average is computed to provide a unique distance value. Together with the average speed of pedestrians in the discrete space (explained below), la is used to calculate the free speed travel time of the link T free = slaa .
a
With a simple probabilistic choice, similar to the one proposed in [Burstedde et al., 2001], the pedestrian movement towards one target is reproduced with the floor fields values. This allows to avoid obstacles and other pedestrians in a very simple way, but it is not enough to generate plausible dynamics, i.e. by respecting the fundamental relation about local density and flow.
For the achievement of a realistic microscopic model, the idea of [Flo¨ttero¨d and La¨mmel, 2015] has been extended to 2-dimensional models. The model works on the basis of 3 simple rules that allow the calibration to fit the fundamental diagram of 1-directional and 2-directional flow. The movement rules are summarized as follows: (i) movement rule: a pedestrian cannot change his/her position before m seconds; (ii) jam rule: if a cell is occupied at time t by the pedestrian p, every pedestrian p 6= p cannot occupy that cell before time t + j ; (iii) counter-flow rule: if two pedestrian in two consecutive cells at time t are in a head-on conflict, then they will swap their position at time t + m + s.
The first rule describes the minimum time that a pedestrian needs to move forward one cell, thus m is the duration of the time-step. The second rule manages the dynamics in presence of jamming, implying additional time to move in case of congestion. In particular, this rule has been implemented by letting the agents produce a trace in their previous position, which will keep the cell occupied for j seconds. This mechanism is able to translate back the effects of congestion as observed, generating the so-called density waves. The third rule defines an agents position exchange mechanism for managing counter-flow situations. In case of two agents moving in opposite direction and deciding to swap positions, this action needs m + s seconds. In [Crociani and La¨mmel, 2016] it is shown how, by varying the value of m and s with the local density, it is possible to calibrate this model to precisely fit fundamental diagrams of 1-directional and 2-directional pedestrian flow.
In summary, these rules enable the model to produce feasible simulations of pedestrian motion in planar environments. Nonetheless, the simulation of a complex environment needs to consider particular elements, such as stairs and ramps, which implies at least a lower speed of the agents. To overcome this issue, the definition of the environment has been enriched by introducing the possibility to mark the borders of stairs, which will affect the agent’s speed by multiplying their m times a parameter slow , i.e. they will not move every time-step of the simulation while they are inside.
Finally, in order to respect the dynamics among the mesoscopic and microscopic models, the connection at the borders of the two models are managed with so-called transition areas. These ones temporarily host agents before entering in the actual environment, sharing their occupations in both models and, thus, allowing them to have a temporary double presence to spread the influence in both models [La¨mmel et al., 2014].
The presented model is validated against fundamental diagrams related to 1-directional and 2-directional flows in planar scenarios, using empirical data from laboratory experiments described in [Zhang et al., 2011; 2012] and for 1directional flow in staircases. For a thorough discussion of the properties and calibration of the model, it is referred to [Crociani and La¨mmel, 2016; Crociani et al., 2016]. 2.2
The overall system is implemented within the MATSim framework1. The standard simulation approach in MATSim is based on the queueing model discussed in [Simon et al., 1999]. Originally, the model was designed for the simulation of vehicular traffic only, but later it has been adapted for the additional consideration of pedestrians [La¨mmel et al., 2009]. The network is modelled as a graph with links describing urban streets and nodes describing their intersections. In the pedestrian context, “streets” also include sidewalks, ramps, etc. Links behave like FIFO queues controlled by the following parameters: (i) the length of the link l; (ii) the area of the link A; (iii) the free flow speed v^; (iv) the free speed travel time tmin, given by l/v^; (v) the flow capacity F C; (vi) the storage capacity SC.
Thus the dynamics follow the rules defined by these parameters. An agent is able to enter a link l until the number of agents inside l is below its storage capacity. Once the agent is inside, it travels at speed v^ and it cannot leave the link before tmin. The congestion is managed with the flow capacity parameter F C, which is used to lock the agents inside the link to not exceed it. 2.3
At the strategic level, agents plan their paths through the
environment. Normally, the aim of the strategic planning is to
emulate the real-world pedestrians’ behavior. A reasonable
assumption is that pedestrians try to minimize the walking
distance when planning their paths. In the simulation context,
the shortest path solution is straightforward to compute e.g.
by Dijkstra’s shortest path algorithm [Dijkstra, 1959].
However, it is well known that the shortest path solution neglects
congestion and thus the shortest path solution is not
necessarily the fastest one. In particular, commuters who repeatedly
walk between two locations (e.g. from a particular track in a
large train station to a bus stop outside the train station) often
try to iteratively find faster paths. If all commuters display
that same behavior, they might reach a state where it is no
longer possible to find any faster path. If this is the case, then
the system has reached a state of a NE [Nash, 1951] w.r.t.
individual travel times. This approach can be emulated by
applying an iterative best-response dynamic [Cascetta, 1989]
and it has been widely applied in the context of
vehicular transport simulations
NE is an interesting concept, but it is generally different from the SO, which does not minimize individual travel times but the overall system (or average) travel time. Like the NE, the SO can also be achieved by an iterative best response dynamic, but based on the marginal travel time instead of the individual travel time. The marginal travel time of an individual traveler corresponds to the sum of the travel time experienced by her/him (internal costs) and the delay that he/she impose to others (external costs). While it is straightforward to determine the internal costs (i.e. travel time), the external cost calculation is not so obvious. An approach for 1http://www.matsim.org (a) (b) the marginal travel time estimation and its application to a mesoscopic evacuation simulation is discussed in [La¨mmel and Flo¨ttero¨d, 2009]. Based on this, [Crociani and La¨mmel, 2016] propose an adaption of the approach to microscopic simulation models. In the present work, the external costs are estimated in the same way as proposed in [Crociani and La¨mmel, 2016]. The following gives a brief description of the approach. As discussed, both the mesoscopic and the microscopic model are mapped on the same global network of links and nodes. A link can either be in a congested or in an uncongested state. Initially, all links are considered as uncongested. A link switches from the uncongested state to the congested state once the observed travel time along the link is longer than the free speed travel time. Vice versa, a link in the congested state switches to the uncongested state as soon as the first pedestrian is able to walk along the link in free speed travel time. Every pedestrian that leaves a given link while it is in the congested state imposes external costs to the others. The amount of the external costs corresponds to the time span from the time when the pedestrian under consideration leaves the congested link till the time when the link switches to the uncongested state again.
In this work, the iterative search of equilibrium/optimum follows the logic of the iterative best response dynamic and is described by the following tasks: (1) Compute plans for all agents (2) Execute the multi-scale simulation (3) Evaluate executed plans of the agents (4) Select a portion of the agents population and re-compute their plans (5) Jump to step 2, if the stop criterion has not been reached
The stopping criterion is implemented as a predetermined number of iterations defined by the user, since the number of iterations needed for the system to reach a relaxed state depends on the complexity of the scenario and is not known a priori, but empirically one hundred iterations represents a good compromise between relaxation and run-time.
Initial plan computation is performed with a shortest path algorithm. In the subsequent iterations, the agents try to find better plans based on the experienced travel costs. Depending on the cost function, the agents learn more convenient paths either for them individually (relaxation towards a NE) or for the overall population (relaxation towards the SO). 3
The multi-scale model discussed above represents a valuable framework for the analysis of the heterogeneous traffic that circulates in metropolitan cities, by estimating the congestions and travel times that could affect the network in a normal day (with the NE approach) or with an optimal configuration of flows which brings useful information to optimize the network. The implementation in MATSim allows to simulate large road and transportation networks (considering buses, trains and other forms of mass transportation). On the other hand, the microscopic model is a rather efficient approach to simulate the detailed pedestrian dynamics inside transportation facilities or other pedestrian environments that are considered interesting from the users of the system.
However, it must be noted that even if the microscopic model is very efficient, the simulation of large scenarios composed of many detailed representations of pedestrian environments might result in long computation times. The iterative nature of the overall approach requires the run of a undetermined number of iterations and this makes the system still computationally demanding.
The idea behind this paper is to apply supervised machine learning algorithms for data regression, in order to construct a macroscopic model from some observables of the microscopic simulation at the first iterations. The learned model, that we denote as ETT, will be used in the successive iterations as substitute of the microscopic one in the search of NE/SO, allowing to save time and computations.
A first peculiarity of this approach is that a high degree of reliability (close to 100%) of ETT is not completely necessary since it will only help the convergence in iteration process, but on the other hand its precision will also affect its effectiveness in saving computational time.
The objective of ETT is to approximate the dynamics of the microscopic pedestrian model in a detailed environment in terms of travel times. The geometry and the congestion arising from the configured pedestrian flows, in fact, affect the time employed by pedestrians to carry out a given route. Moreover, as described in Sec. 2.3, the travel time is the information used by the routing algorithm in the iterative search of equilibrium.
Hence, ETT is defined to provide an estimation of the travel time tt needed by pedestrians to cross the portions of space between two destinations, depending on the congestion conditions. In the high-level representation of the environment (see Sec. 2.1), the space between two targets is represented by a directed edge l connecting the nodes respectively mapped to the destinations. We therefore define ETT as a set of functions tt i, each one calculating the travel time of the link li for an agent, given the current state of the network:
ETT = ftt 1; : : : ; tt ng (2)
We must now clarify the meaning of “current state” of the network, that is, what is the input of each tt function. The dynamics in this model is mainly affected by the static configuration of the geometry and composition of the environment (e.g. presence of staircases) and by the dynamic evolution of the pedestrian flows (possibly leading to the emergence of congestions). Hence we define tt i, associated to the link li, as a function taking as input a vector ~o(i;t) and returning a number 2 R describing the time needed to arrive at the next destination by entering at the current time-step (see Fig. 2(a)). ~o(i;t) is composed by numbers 2 N and provides an abstraction of the number of pedestrians currently (i.e. at time t) present in the area referred by the link and its direct surrounding. It must be noted, in fact, that a certain area of the environment can be crossed by agents following different paths (i.e. with their positions mapped in different links of the graph), so considering only the occupation of the link li will not lead to a good estimation of tti.
To overcome this issue we define the neighbourhood of a link l, denoted as nh(l), as the set of links starting from / leading to the destination node of li (an abstraction of the area forward to the agent). The logic is graphically exemplified in Figure 2(b). According to nh(l), the occupation vector ~o(i;t) considered as the domain of tt (l) is formally defined as: ~o(i;t) = occ(^l; t) jl 2 nh(li) [ flig ^ (3)
The problem of the computation of ETT can be now formally stated: given the travel times y(i;t) achieved with the microscopic model in the link li (for every link li of the network simulated in the detailed way) and with associated occupation vector ~o(i;t), find the function h such that: h(i;t)(~o(i;t)) y (4)
The additional consideration of the time-step of simulation t allows the framework to potentially learn also systematic variation of pedestrian speeds over a simulated time window of a full day (e.g. higher speed in time windows related to commuting). This feature, however, will not be analysed in this work because its aim is to study the feasibility and performances of the learning framework in simple benchmark scenarios. The machine learning algorithm applied to this problem and its configuration will be now described.
computation of ETT The problem of regression of a series of training data f(x1; y1) ; : : : ; (xm; ym)g X R, where X is the multidimensional domain of inputs, can be dealt with any algorithm that have been proposed in the supervised machine learning field. In this context we apply the Support Vector Regression (SVR). Despite SVR dates back to 1995 [Drucker et al., 1997] and it could be considered as an old approach in favour of the deep neural network architectures applied nowadays in numerous domains, the introduction of the Radial Basis Function (RBF) kernel have redefined its robustness and versatility in classification and regression tasks [Ferna´ndezDelgado et al., 2014]. Moreover, despite a neural network can theoretically lead to a higher precision in the regression task, the large amount of data needed to train such model would represent an issue for the problem in question.
As thoroughly discussed in [Smola and Scho¨lkopf, 2004], a kernelized SVR applied to a dataset with m inputs and using the kernel function k can be formulated using the Lagrangian: maximize
m 1 X ( i 8 > > > > < 2 i;j=1
m m >>> " X ( i + i ) + X yi ( i >: i=1 i=1 i ) j j k(xi; xj) i ) (5) m subject to X ( i i=1 i ) = 0 and i; i 2 [0; C]
Where i; i are the Lagrangian multipliers and C is the parameter controlling how much deviation from the input dataset is tolerated. We apply the RBF kernel function, also known as the Gaussian kernel, which is defined with parameter as: k(xi; xj ) = exp jjxi xj jj2 (6)
In our context, each input xi of the dataset is represented by an occupation vector ~o(i;t), while the yi is denoted as y(i;t) and represents the time needed by an agent to travel between the two destinations mapped by the link i, starting at time t. In the next section we will discuss the application of this approach in benchmark tests scenarios. 4
The SVR based approach to learn the ETT model is tested with two benchmark scenarios representing simple but paradigmatic settings. The aim is to evaluate the effectiveness and reliability of the model in learning and reproducing results of microscopic simulations in controlled situations.
For each simulation campaign we perform the following workflow, as also graphically depicted in Fig. 3: 1. run few iterations of the microscopic simulation and build the training/test dataset2; 2. train the ETT model with the dataset. Cross-validation with the test dataset is here performed, using Mean Squared Error (MSE) for the evaluation and calibration of parameters of the SVR for each link associated to some observation; 3. simulate the same scenario using the ETT model to predict the travel times of links for the agents.
The last point is performed to validate ETT over the dynamics previously generated with the microscopic model. In particular, we simulate the evolution of the occupation and travel time of links in the network by configuring the same 2The dataset is subdivided in the typical proportion 70/30 %. initial population of agents, the same routes and the same frequency of generation on the initial links (see Fig. 3-center). At each time-step of the simulation (Fig. 3-right), active agents asks the travel time t^ to the model tt l associated to the next link l of their plan, and update the occupation information in the link right after. They then remain un-active for t^ time-steps, and repeat the life-cycle until they reach the last link of their route. To guarantee some non-determinism in the system, a 5% random noise is added/subtracted to the output t^ of tt functions.
The two scenarios used for the evaluation are shown in Fig. 4 and they represent respectively: (i) a corridor of 24x4m2 crossed by uni and bi-directional flows; (ii) an implementation of the Daganzo paradox [Daganzo, 1998] for a pedestrian environment, crossed by a uni-directional flow from left to right and where the iterative re-routing of agents affects their travel time. For simplicity, we will refer to the results achieved with the microscopic model as observation, while we will call simulated data the results of ETT.
The corridor environment is configured with both unidirectional and bi-directional flows, to generate a training dataset of totally 10 simulation iterations: 2 iterations are generated with a unique flow of 600 pedestrians from one of the origin links (inW or inE in Fig. 4(a)) and 8 iterations are run with a balanced bi-directional flow of 300 pedestrians per side. In all cases the incoming rate is 4 ped/s per starting side.
To evaluate the effectiveness of the proposed approach we analyse the links occupation along the simulation time. This allows a direct comparison between results of the simulation using the ETT model and using the the microscopic one. For sake of space, a selection of results related to two links for the bi-directional scenario is proposed in Fig. 5 (sufficient to evaluate the performances since results for other links are similar). The diagrams show the comparison of two observations with a simulation using ETT. The learning framework was able to successfully identify the relations between the occupation of links and their travel times, leading the simulated data being in the range of observations for all cases. In particular, the trend of the datasets appear to be quite similar, despite the link 3 ! 2 provides a more variable and quite oscillating trend for the simulated data. On the other hand, the simulated data are inside the range provided by observations and the emptying times of links is also close. 4.2
The second scenario represents an implementation of the Daganzo paradox [Daganzo, 1998], where a long initial corridor is connected to a bifurcation where a short way is interested by a narrow bottleneck, while the other way is sensibly longer. At the first iteration, all agents are choosing the short route experiencing congestion and long travel times, but iterating the scenario leads the congestion to partially dissipate and the agents to choose the longer route. We computed the dataset with 20 iterations (with re-routing active) so that the ETT model is able to learn the travel times for all links in the scenario: at the first iteration links in the southern part of the environment are not used. We trained ETT with the full dataset and then we evaluate the results based on the routes of the first iteration (all agents configured with the shortest path) and the tenth (many agents takes the detour).
Results in Fig. 6(a) and (b) represents the occupation of links 7 ! 8 and 8 ! 9 at the first iteration, while (c) and (d) show the comparison achieved using the routes of agents of the tenth iteration. In all cases the simulated occupation respects quite well both trend and range of the observation data. In particular, two points must be highlighted: (i) the ETT model reproduced well the maximum occupation of the bottleneck link (8 ! 9) and the link before without having been trained on data about this; (ii) the congestion generated on the bottleneck spreads back to the link 7 ! 8 and also to the link describing the initial corridor, meaning that the model fitted the occupation-travel time data of links successfully. A preliminary evaluation of computation times is now presented. The analysis is performed using the second scenario, because it can host a higher number of agents simultaneously: a unique simulation is configured with 4000 agents crossing the environment and having to pass through the bottleneck, with the aim to produce a sensible congestion. The simulation has been performed on a laptop with CPU Intel i7-4712HQ 2.3 GHz and RAM 16 GB.
Times for the computation of single time-steps with the
ETT model, dependent on the number of agents
simultaneously present in the simulation, are shown in Fig. 7. The
speedup is calculated with the ratio cosmimpuultaatteidontitmime e , where
the simulated time for a single time-step of ETT is
configured as 0.1s in this implementation. These results highlight
the efficiency of the model: with 1000 simulated agents it
displays a speedup of about 30, while it is less than 5 with the
microscopic model
The paper has presented an approach for learning and exploiting micro-scale pedestrian simulation aggregated results to support effective and efficient meso-scale simulation, within a multi-scale simulation framework. The currently achieved results are encouraging, but the analysed scenario are so far too simpler (both in scale and structural complexity) than the real world situations it is targeted at. Next steps are related to facing situations closer to real world scenarios, evaluating both the effectiveness and efficiency of substituting the micro-scale model with ETT in the overall iterative process, in addition to reduce the initial cost provided by the training phase of the new model.