Learning Obervables of a Multi-scale Simulation System of Urban Traffic Luca Crociani1 , Gregor Lämmel2 , Giuseppe Vizzari1 and Stefania Bandini1,3 1 Complex Systems and Artificial Intelligence research center University of Milano-Bicocca, Viale Sarca, 336 - U14, 20126, Milan, Italy {name.surname}@disco.unimib.it 2 Institute of Transportation Systems, German Aerospace Center (DLR) (on leave) gregor.laemmel@gmail.com 3 RCAST, The University of Tokyo, Tokyo, Japan Abstract troducing the possibility of representing phenomena that were still not considered) and efficiency of the simulators based on Multi-scale modelling is a powerful approach that those approaches. has been successfully exploited in the context of simulation of traffic and transportation systems. Despite the substantial effort and significant achieved re- While the paradigm allows the simulation of large sults, two aspects that are still object of investigation by the cities in a already efficient fashion, the considera- research community are related to efficiency of the devel- tion of detailed environments for a precise simu- oped simulators, on one hand, and to the requirements in lation of pedestrian traffic can be still a demand- terms of modeler’s effort in tailoring a general model to pre- ing task, especially in iterative approaches for the cisely represent a given scenario, with the related demand search of optimal solutions. In this context, the pa- and especially the so-called traffic assignment. A particu- per proposes the application of a supervised ma- larly relevant effort, within this framework, is represented chine learning algorithm to learn the observables by multi-scale approaches (see, e.g., [Crociani et al., 2016; of a microscopic model of pedestrian dynamics in 2017]) coupling micro-simulation models (often adopting an the simulated environment. The aim is to gener- agent-based approach) with more coarse grained ones (e.g. ate a simpler model that (i) is able to describe the in which the environment is a graph whose vertices are as- dynamic travel times of pedestrians in the scenario sociated to intersections and edges are associated to paths and (ii) can replace the microscopic model in the connecting them), to couple high precision in the spatial rep- iterative search of optimal solutions. After a formal resentation and management of interactions among pedestri- description of the approach, the paper provides pre- ans in some specific parts of the simulated environment with liminary results with its application in benchmark an overall computational efficiency and adequacy to manage scenarios, aimed at analysing its reliability in con- large scale scenarios. trolled conditions. 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 lim- 1 Introduction & Related Works ited time-frame for the elaboration of results. The approach Designers, planners employ tools for the simulation of pedes- proposed in this paper is based on the idea to substantially trians’ and crowd’s movement in the built environment on an limit the number of the execution of micro-scale models but everyday basis, especially in collective transportation facili- at the same time to employ the observable aggregated results ties and in the urban context in general: decisions related to to characterize the meso-scale model, preserving the accuracy the construction or maintenance of specific facilities undergo- in the management of aspects like interaction among pedes- ing crowding situations call for results of the so-called what-if trians, but further reducing the computational costs. The ba- scenarios, indicating what plausibly happens within a given sic idea is to actually learn the how observable aggregated geometry subject to certain levels of demand. Even crowd results emerge from micro-scale simulations: the latter will managers, when already existing facilities must be used for therefore be run in plausible contextual conditions, but the at- hosting large numbers of pedestrians, growingly use these tempt is to generalize the achieved results to actually define tools to evaluate the crowd management procedures before functions describing, for instance, the expected travel time of they are enacted. Results of research on pedestrian and crowd a pedestrian over an edge of the graph (i.e. a certain passage simulation has lead to technology transfer (off-the-shelf avail- in the environment) given precise contextual conditions. able commercial tools are daily used by designers and plan- From this perspective, the proposed approach is somewhat ners), but these products are sided by open challenges for re- related to those employing computational intelligence tech- searchers in different fields and disciplines, to improve model niques for parameter estimation (such as, for instance, Par- expressiveness (i.e. simplifying the modelling activity or in- ticle Swarm Optimization [Spolaor et al., 2017]), since the learned function is surely an important element of the meso- scale model, but actually something more complicated than a value (or interval of values) for a parameter. On the other hand, this approach is surely less demanding than previous works that are actually aimed at learning pedestrian behav- ior at the micro-scale (such as [Junges and Klügl, 2012] and, more recently, [Martinez-Gil et al., 2017]). The latter, as of this moment, although presenting interesting and encourag- ing results, still present limitations that hinder their practical applicability in the short term. The proposed approach, al- Figure 1: Sample scenario with its network representation. Cyan though it still needs improvements and especially a validation cells describe intermediate targets, while external arrows connect on large scale scenarios it is actually targeted at, is a less am- the outside network, simulated with the mesoscopic model. bitious attempt that already produced encouraging results in benchmark scenarios. The paper breaks down as follows: the following section m2 size of the cells describes the average space occupation more formally introduces the above mentioned multi-scale of a person [Weidmann, 1993] and reproduces a maximum approach, whereas Sect. 3 more thoroughly presents the pro- pedestrian density of 6.25 persons/m2 which covers the val- posed learning model for micro-scale aggregated results. The ues usually observable in the real world. Basically, a cell of experimental application of the proposed approach is then the environment can be one of two types, walkable or obsta- presented, discussing achieved results achieved in a uni and cle, meaning that it will never be occupied by any pedestrian bidirectional corridor, and in a more complex paradigmatic during the simulation. benchmark scenario in which paradoxical effects can be ob- Intermediate targets can also be introduced in the environ- served. Conclusions and future developments end the paper. ment to mark the extremes of a particular region (e.g. rooms or corridors) which act as decision points for the routing 2 A Multi-Scale Simulation System for Urban choice of agents. Final goals of the discrete environment are Traffic its open edges, i.e., the entrances/exits of the discrete space that will be linked to roads. Since the concept of region is The machine learning based approach proposed in this paper fuzzy and the space decomposition is a subjective task that is applied to the multi-scale simulation system described in can be tackled with different approaches, their configuration previous works by the authors [Crociani and Lämmel, 2016; in the scenario is not automatic and is left to the user. Crociani et al., 2016]. For completeness and to allow a clear Employing the floor field approach [Burstedde et al., 2001] understanding of the presented results in Sec. 4, fundamental and spreading one field from each target –either intermediate mechanisms of the model will be now briefly described. or final– allows to build a network of the environment. In this The simulation system is composed of two models with graph, each node denotes one target and the edges identify two different scales of detail: (i) a 2d discrete microscopic the existence of a direct way between two targets (i.e. passing model for a detailed yet efficient reproduction of environ- through only one region). To allow this, the floor field diffu- ments crossed by pedestrian flows; (ii) a queue model used sion is limited by obstacles and cells of other targets. An ex- to simulated a larger part of the transportation network, host- ample for an environment with the overlaid network is shown ing heterogeneous forms of traffic. The integration between in Fig.1. The open borders of the microscopic environment these two models composes a quite powerful approach, ca- are the nodes that will be plugged to the other network of the pable of performing analysis in metropolitan scenarios, by mesoscopic model. considering multiple modes of transportation and performing To integrate the network with the one of the mesoscopic simulations in relatively short times. model and to allow the reasoning at the strategic level, each Keeping the computational costs relatively low is very im- edge a of the graph is firstly labelled with its length la , de- portant for this model, since the multi-scale system applies scribing the distance between two targets δi , δj in the discrete an iterative approach to manage the agents’ strategic model, space. This value is computed using the floor fields as: for which agents iteratively adapt their choice of route on the basis of a cost function applied to experienced travel times (FF δ1 (Center (δ2 )) + FF δ2 (Center (δ1 ))) from the previous simulation. Overall this workflow makes la (δ1 , δ2 ) = (1) the system converge either towards a Nash Equilibrium (NE) 2 or to the system optimum (SO), depending on the chosen cost where FF δ (x, y) gives the value of the floor field associ- function. In this way the user of the simulation system is able ated to a destination δ in position (x, y); Center (δ) describes to provide an estimation of the traffic in the scenario on a nor- the coordinates of the central cell of δ. The average is com- mal day (NE approach) or to have information about the min- puted to provide a unique distance value. Together with the imum average travel time of the population of agents (SO). average speed of pedestrians in the discrete space (explained below), la is used to calculate the free speed travel time of the 2.1 The Discrete Microscopic Model link Taf ree = slaa . The model is a 2-dimensional Cellular Automaton with a rep- With a simple probabilistic choice, similar to the one pro- resentation of the space as a grid of square cells. The 0.4×0.4 posed in [Burstedde et al., 2001], the pedestrian movement towards one target is reproduced with the floor fields values. 2.2 The mesoscopic model This allows to avoid obstacles and other pedestrians in a very The overall system is implemented within the MATSim simple way, but it is not enough to generate plausible dynam- framework1 . The standard simulation approach in MATSim ics, i.e. by respecting the fundamental relation about local is based on the queueing model discussed in [Simon et al., density and flow. 1999]. Originally, the model was designed for the simulation For the achievement of a realistic microscopic model, the of vehicular traffic only, but later it has been adapted for the idea of [Flötteröd and Lämmel, 2015] has been extended to additional consideration of pedestrians [Lämmel et al., 2009]. 2-dimensional models. The model works on the basis of 3 The network is modelled as a graph with links describing ur- simple rules that allow the calibration to fit the fundamental ban streets and nodes describing their intersections. In the diagram of 1-directional and 2-directional flow. The move- pedestrian context, “streets” also include sidewalks, ramps, ment rules are summarized as follows: (i) movement rule: a etc. Links behave like FIFO queues controlled by the follow- pedestrian cannot change his/her position before τm seconds; ing parameters: (i) the length of the link l; (ii) the area of the (ii) jam rule: if a cell is occupied at time t by the pedestrian link A; (iii) the free flow speed v̂; (iv) the free speed travel p, every pedestrian p 6= p cannot occupy that cell before time time tmin , given by l/v̂; (v) the flow capacity F C; (vi) the t + τj ; (iii) counter-flow rule: if two pedestrian in two con- storage capacity SC. secutive cells at time t are in a head-on conflict, then they will Thus the dynamics follow the rules defined by these pa- swap their position at time t + τm + τs . rameters. An agent is able to enter a link l until the number The first rule describes the minimum time that a pedestrian of agents inside l is below its storage capacity. Once the agent needs to move forward one cell, thus τm is the duration of the is inside, it travels at speed v̂ and it cannot leave the link be- time-step. The second rule manages the dynamics in pres- fore tmin . The congestion is managed with the flow capacity ence of jamming, implying additional time to move in case parameter F C, which is used to lock the agents inside the of congestion. In particular, this rule has been implemented link to not exceed it. by letting the agents produce a trace in their previous posi- tion, which will keep the cell occupied for τj seconds. This 2.3 Strategic model mechanism is able to translate back the effects of congestion At the strategic level, agents plan their paths through the en- as observed, generating the so-called density waves. The third vironment. Normally, the aim of the strategic planning is to rule defines an agents position exchange mechanism for man- emulate the real-world pedestrians’ behavior. A reasonable aging counter-flow situations. In case of two agents moving assumption is that pedestrians try to minimize the walking in opposite direction and deciding to swap positions, this ac- distance when planning their paths. In the simulation context, tion needs τm + τs seconds. In [Crociani and Lämmel, 2016] the shortest path solution is straightforward to compute e.g. it is shown how, by varying the value of τm and τs with the by Dijkstra’s shortest path algorithm [Dijkstra, 1959]. How- local density, it is possible to calibrate this model to precisely ever, it is well known that the shortest path solution neglects fit fundamental diagrams of 1-directional and 2-directional congestion and thus the shortest path solution is not necessar- pedestrian flow. ily the fastest one. In particular, commuters who repeatedly In summary, these rules enable the model to produce feasi- walk between two locations (e.g. from a particular track in a ble simulations of pedestrian motion in planar environments. large train station to a bus stop outside the train station) often Nonetheless, the simulation of a complex environment needs try to iteratively find faster paths. If all commuters display to consider particular elements, such as stairs and ramps, that same behavior, they might reach a state where it is no which implies at least a lower speed of the agents. To over- longer possible to find any faster path. If this is the case, then come this issue, the definition of the environment has been the system has reached a state of a NE [Nash, 1951] w.r.t. enriched by introducing the possibility to mark the borders individual travel times. This approach can be emulated by of stairs, which will affect the agent’s speed by multiplying applying an iterative best-response dynamic [Cascetta, 1989] their τm times a parameter κslow , i.e. they will not move and it has been widely applied in the context of vehicu- every time-step of the simulation while they are inside. lar transport simulations (see, e.g, [Raney and Nagel, 2004; Krajzewicz et al., 2012]), but in the pedestrian context it is Finally, in order to respect the dynamics among the meso- rather recent. scopic and microscopic models, the connection at the borders NE is an interesting concept, but it is generally different of the two models are managed with so-called transition ar- from the SO, which does not minimize individual travel times eas. These ones temporarily host agents before entering in the but the overall system (or average) travel time. Like the NE, actual environment, sharing their occupations in both models the SO can also be achieved by an iterative best response dy- and, thus, allowing them to have a temporary double presence namic, but based on the marginal travel time instead of the to spread the influence in both models [Lämmel et al., 2014]. individual travel time. The marginal travel time of an in- The presented model is validated against fundamental dia- dividual traveler corresponds to the sum of the travel time grams related to 1-directional and 2-directional flows in pla- experienced by her/him (internal costs) and the delay that nar scenarios, using empirical data from laboratory experi- he/she impose to others (external costs). While it is straight- ments described in [Zhang et al., 2011; 2012] and for 1- forward to determine the internal costs (i.e. travel time), the directional flow in staircases. For a thorough discussion of the external cost calculation is not so obvious. An approach for properties and calibration of the model, it is referred to [Cro- 1 ciani and Lämmel, 2016; Crociani et al., 2016]. http://www.matsim.org (a) (b) Figure 2: (a) The logic of the machine learning approach: the model learned for one link provides the travel time for entering agents at the current time-step and it can be used in substitution of the microscopic model in the iterative process. (b) Set of links (grey) considered as neighbours of the link li . the marginal travel time estimation and its application to a either for them individually (relaxation towards a NE) or for mesoscopic evacuation simulation is discussed in [Lämmel the overall population (relaxation towards the SO). and Flötteröd, 2009]. Based on this, [Crociani and Lämmel, 2016] propose an adaption of the approach to microscopic 3 Learning Observables of a Microscopic simulation models. In the present work, the external costs are estimated in the same way as proposed in [Crociani and Model Lämmel, 2016]. The following gives a brief description of The multi-scale model discussed above represents a valuable the approach. As discussed, both the mesoscopic and the mi- framework for the analysis of the heterogeneous traffic that croscopic model are mapped on the same global network of circulates in metropolitan cities, by estimating the conges- links and nodes. A link can either be in a congested or in tions and travel times that could affect the network in a nor- an uncongested state. Initially, all links are considered as un- mal day (with the NE approach) or with an optimal configura- congested. A link switches from the uncongested state to the tion of flows which brings useful information to optimize the congested state once the observed travel time along the link is network. The implementation in MATSim allows to simulate longer than the free speed travel time. Vice versa, a link in the large road and transportation networks (considering buses, congested state switches to the uncongested state as soon as trains and other forms of mass transportation). On the other the first pedestrian is able to walk along the link in free speed hand, the microscopic model is a rather efficient approach to travel time. Every pedestrian that leaves a given link while it simulate the detailed pedestrian dynamics inside transporta- is in the congested state imposes external costs to the others. tion facilities or other pedestrian environments that are con- The amount of the external costs corresponds to the time span sidered interesting from the users of the system. from the time when the pedestrian under consideration leaves However, it must be noted that even if the microscopic the congested link till the time when the link switches to the model is very efficient, the simulation of large scenarios com- uncongested state again. posed of many detailed representations of pedestrian environ- In this work, the iterative search of equilibrium/optimum ments might result in long computation times. The iterative follows the logic of the iterative best response dynamic and is nature of the overall approach requires the run of a undeter- described by the following tasks: mined number of iterations and this makes the system still (1) Compute plans for all agents computationally demanding. (2) Execute the multi-scale simulation The idea behind this paper is to apply supervised machine (3) Evaluate executed plans of the agents learning algorithms for data regression, in order to construct (4) Select a portion of the agents population and re-compute a macroscopic model from some observables of the micro- their plans scopic simulation at the first iterations. The learned model, (5) Jump to step 2, if the stop criterion has not been reached that we denote as ETT, will be used in the successive iter- The stopping criterion is implemented as a predetermined ations as substitute of the microscopic one in the search of number of iterations defined by the user, since the number NE/SO, allowing to save time and computations. of iterations needed for the system to reach a relaxed state A first peculiarity of this approach is that a high degree of depends on the complexity of the scenario and is not known reliability (close to 100%) of ETT is not completely neces- a priori, but empirically one hundred iterations represents a sary since it will only help the convergence in iteration pro- good compromise between relaxation and run-time. cess, but on the other hand its precision will also affect its Initial plan computation is performed with a shortest path effectiveness in saving computational time. algorithm. In the subsequent iterations, the agents try to find The objective of ETT is to approximate the dynamics of better plans based on the experienced travel costs. Depending the microscopic pedestrian model in a detailed environment on the cost function, the agents learn more convenient paths in terms of travel times. The geometry and the congestion Figure 3: Workflow of the simulation using the ETT model. arising from the configured pedestrian flows, in fact, affect microscopic model in the link li (for every link li of the net- the time employed by pedestrians to carry out a given route. work simulated in the detailed way) and with associated oc- Moreover, as described in Sec. 2.3, the travel time is the in- cupation vector ~o(i,t) , find the function h such that: formation used by the routing algorithm in the iterative search of equilibrium. h(i,t) (~o(i,t) ) ≈ y (4) Hence, ETT is defined to provide an estimation of the The additional consideration of the time-step of simulation travel time tt needed by pedestrians to cross the portions of t allows the framework to potentially learn also systematic space between two destinations, depending on the congestion variation of pedestrian speeds over a simulated time window conditions. In the high-level representation of the environ- of a full day (e.g. higher speed in time windows related to ment (see Sec. 2.1), the space between two targets is repre- commuting). This feature, however, will not be analysed in sented by a directed edge l connecting the nodes respectively this work because its aim is to study the feasibility and per- mapped to the destinations. We therefore define ETT as a formances of the learning framework in simple benchmark set of functions tt i , each one calculating the travel time of scenarios. The machine learning algorithm applied to this the link li for an agent, given the current state of the network: problem and its configuration will be now described. ETT = {tt 1 , . . . , tt n } (2) 3.1 Support Vector Regression for the We must now clarify the meaning of “current state” of the computation of ETT network, that is, what is the input of each tt function. The The problem of regression of a series of training data dynamics in this model is mainly affected by the static con- {(x1 , y1 ) , . . . , (xm , ym )} ⊂ X × R, where X is the multi- figuration of the geometry and composition of the environ- dimensional domain of inputs, can be dealt with any algo- ment (e.g. presence of staircases) and by the dynamic evo- rithm that have been proposed in the supervised machine lution of the pedestrian flows (possibly leading to the emer- learning field. In this context we apply the Support Vector gence of congestions). Hence we define tt i , associated to the Regression (SVR). Despite SVR dates back to 1995 [Drucker link li , as a function taking as input a vector ~o(i,t) and re- et al., 1997] and it could be considered as an old approach in turning a number ∈ R describing the time needed to arrive at favour of the deep neural network architectures applied nowa- the next destination by entering at the current time-step (see days in numerous domains, the introduction of the Radial Ba- Fig. 2(a)). ~o(i,t) is composed by numbers ∈ N and provides sis Function (RBF) kernel have redefined its robustness and an abstraction of the number of pedestrians currently (i.e. at versatility in classification and regression tasks [Fernández- time t) present in the area referred by the link and its direct Delgado et al., 2014]. Moreover, despite a neural network can surrounding. It must be noted, in fact, that a certain area of theoretically lead to a higher precision in the regression task, the environment can be crossed by agents following different the large amount of data needed to train such model would paths (i.e. with their positions mapped in different links of the represent an issue for the problem in question. graph), so considering only the occupation of the link li will As thoroughly discussed in [Smola and Schölkopf, 2004], not lead to a good estimation of tti . a kernelized SVR applied to a dataset with m inputs and using To overcome this issue we define the neighbourhood of the kernel function k can be formulated using the Lagrangian: 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  m 1 X (αi − αi∗ ) αj − αj∗ k(xi , xj )   forward to the agent). The logic is graphically exemplified in − 2    Figure 2(b). According to nh(l), the occupation vector ~o(i,t) maximize m i,j=1 m (5) considered as the domain of tt(l) is formally defined as:   −ε X (αi + α ∗ ) + X yi (αi − αi∗ ) i      i=1 i=1 ~o(i,t) = occ(ˆl, t) |ˆl ∈ nh(li ) ∪ {li } (3) m The problem of the computation of ETT can be now for- X subject to (αi − αi∗ ) = 0 and αi , αi∗ ∈ [0, C] mally stated: given the travel times y(i,t) achieved with the i=1 (a) (b) Figure 5: Comparison of observation (blue and cyan) and simulation Figure 4: The two test environments and their superimposed net- (red) results regarding the links 0 → 2 (left) and 3 → 2 (right) from work. Names of origin links are emphasized in red, while other the simulation of the corridor scenario. links are named with ids of linked nodes (e.g. 0 → 1). initial population of agents, the same routes and the same fre- Where αi , αi∗ are the Lagrangian multipliers and C is the quency of generation on the initial links (see Fig. 3-center). parameter controlling how much deviation from the input At each time-step of the simulation (Fig. 3-right), active dataset is tolerated. We apply the RBF kernel function, also agents asks the travel time t̂ to the model tt l∗ associated to known as the Gaussian kernel, which is defined with param- the next link l∗ of their plan, and update the occupation in- eter γ as: formation in the link right after. They then remain un-active for t̂ time-steps, and repeat the life-cycle until they reach the −||xi − xj ||2   last link of their route. To guarantee some non-determinism k(xi , xj ) = exp (6) in the system, a 5% random noise is added/subtracted to the γ output t̂ of tt functions. In our context, each input xi of the dataset is represented The two scenarios used for the evaluation are shown in by an occupation vector ~o(i,t) , while the yi is denoted as y(i,t) Fig. 4 and they represent respectively: (i) a corridor of and represents the time needed by an agent to travel between 24x4m2 crossed by uni and bi-directional flows; (ii) an im- the two destinations mapped by the link i, starting at time plementation of the Daganzo paradox [Daganzo, 1998] for t. In the next section we will discuss the application of this a pedestrian environment, crossed by a uni-directional flow approach in benchmark tests scenarios. from left to right and where the iterative re-routing of agents affects their travel time. For simplicity, we will refer to the 4 Application and Analysis of the Approach results achieved with the microscopic model as observation, The SVR based approach to learn the ETT model is while we will call simulated data the results of ETT. tested with two benchmark scenarios representing simple but paradigmatic settings. The aim is to evaluate the effective- 4.1 Uni- and Bi-directional flow in a Corridor ness and reliability of the model in learning and reproducing The corridor environment is configured with both uni- results of microscopic simulations in controlled situations. directional and bi-directional flows, to generate a training For each simulation campaign we perform the following dataset of totally 10 simulation iterations: 2 iterations are workflow, as also graphically depicted in Fig. 3: generated with a unique flow of 600 pedestrians from one of 1. run few iterations of the microscopic simulation and the origin links (inW or inE in Fig. 4(a)) and 8 iterations are build the training/test dataset2 ; 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. 2. train the ETT model with the dataset. Cross-validation To evaluate the effectiveness of the proposed approach we with the test dataset is here performed, using Mean analyse the links occupation along the simulation time. This Squared Error (MSE) for the evaluation and calibration allows a direct comparison between results of the simulation of parameters of the SVR for each link associated to using the ETT model and using the the microscopic one. some observation; For sake of space, a selection of results related to two links 3. simulate the same scenario using the ETT model to pre- for the bi-directional scenario is proposed in Fig. 5 (sufficient dict the travel times of links for the agents. to evaluate the performances since results for other links are The last point is performed to validate ETT over the dy- similar). The diagrams show the comparison of two observa- namics previously generated with the microscopic model. In tions with a simulation using ETT. The learning framework particular, we simulate the evolution of the occupation and was able to successfully identify the relations between the oc- travel time of links in the network by configuring the same cupation of links and their travel times, leading the simulated data being in the range of observations for all cases. In par- 2 The dataset is subdivided in the typical proportion 70/30 %. ticular, the trend of the datasets appear to be quite similar, (a) (b) Figure 7: Computation times (left) and speedup (right) related to the simulation of a single time-step of the bottleneck scenario using ETT. 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. 4.3 Computation Times (c) (d) A preliminary evaluation of computation times is now pre- sented. The analysis is performed using the second scenario, Figure 6: Comparison of observation (blue) and simulation (red) because it can host a higher number of agents simultaneously: results of links 7 → 8 ((a) for first and (c) for tenth it.) and 8 → 9 a unique simulation is configured with 4000 agents crossing ((b) first and (d) tenth) from the simulation of the second scenario. 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 despite the link 3 → 2 provides a more variable and quite os- 2.3 GHz and RAM 16 GB. cillating trend for the simulated data. On the other hand, the Times for the computation of single time-steps with the simulated data are inside the range provided by observations ETT model, dependent on the number of agents simulta- and the emptying times of links is also close. neously present in the simulation, are shown in Fig. 7. The simulated time speedup is calculated with the ratio computation time , where 4.2 An Environment with a Bottleneck the simulated time for a single time-step of ETT is config- The second scenario represents an implementation of the Da- ured as 0.1s in this implementation. These results highlight ganzo paradox [Daganzo, 1998], where a long initial corri- the efficiency of the model: with 1000 simulated agents it dis- dor is connected to a bifurcation where a short way is inter- plays a speedup of about 30, while it is less than 5 with the ested by a narrow bottleneck, while the other way is sensibly microscopic model (see [Crociani and Lämmel, 2016]). De- longer. At the first iteration, all agents are choosing the short spite this very encouraging result for this approach, it must route experiencing congestion and long travel times, but iter- be noted that the training of the SVR for all links of this sce- ating the scenario leads the congestion to partially dissipate nario still represents a bottleneck, having required a dataset and the agents to choose the longer route. We computed the composed of travel times of 20 simulation iterations with the dataset with 20 iterations (with re-routing active) so that the microscopic model and needing about 6 minutes for the train- ETT model is able to learn the travel times for all links in ing phase with cross validation. We are already working to the scenario: at the first iteration links in the southern part of reduce the burden of this initial cost, by means of: (i) pre- the environment are not used. We trained ETT with the full processing of data to reduce the variability of travel times dataset and then we evaluate the results based on the routes of provided by the discrete microscopic model; (ii) reducing the the first iteration (all agents configured with the shortest path) set of parameters used for the training with cross validation of and the tenth (many agents takes the detour). the SVR, searching for a smaller combination of values that generally work with a high number of scenarios. 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 5 Conclusions and Future Works of the tenth iteration. In all cases the simulated occupation The paper has presented an approach for learning and exploit- respects quite well both trend and range of the observation ing micro-scale pedestrian simulation aggregated results to support effective and efficient meso-scale simulation, within portation research part B: methodological, 71(C):194– a multi-scale simulation framework. The currently achieved 212, 2015. results are encouraging, but the analysed scenario are so far [Gawron, 1998] C. Gawron. An iterative algorithm to de- too simpler (both in scale and structural complexity) than the termine the dynamic user equilibrium in a traffic simula- real world situations it is targeted at. Next steps are related tion model. International Journal of Modern Physics C, to facing situations closer to real world scenarios, evaluat- 9(3):393–407, 1998. ing both the effectiveness and efficiency of substituting the micro-scale model with ETT in the overall iterative process, [Junges and Klügl, 2012] Robert Junges and Franziska in addition to reduce the initial cost provided by the training Klügl. Programming agent behavior by learning is phase of the new model. simulation models. Applied Artificial Intelligence, 26(4):349–375, 2012. References [Krajzewicz et al., 2012] Daniel Krajzewicz, Jakob Erd- mann, Michael Behrisch, and Laura Bieker. Recent devel- [Burstedde et al., 2001] C Burstedde, K Klauck, A Schad- opment and applications of SUMO - Simulation of Urban schneider, and J Zittartz. Simulation of pedestrian dy- MObility. International Journal On Advances in Systems namics using a two-dimensional cellular automaton. Phys- and Measurements, 5(3&4):128–138, December 2012. ica A: Statistical Mechanics and its Applications, 295(3 - 4):507–525, 2001. [Lämmel and Flötteröd, 2009] G. Lämmel and G. Flötteröd. Towards system optimum: Finding optimal routing strate- [Cascetta, 1989] E. Cascetta. A stochastic process approach gies in time-tependent networks for large-scale evacuation to the analysis of temporal dynamics in transportation net- problems. In KI 2009: Advances in Artificial Intelligence, works. Transportation Research B, 23B(1):1–17, 1989. volume 5803 of LNCS (LNAI), pages 532–539. Springer, [Crociani and Lämmel, 2016] Luca Crociani and Gregor Berlin Heidelberg, 2009. Lämmel. Multidestination pedestrian flows in equilib- [Lämmel et al., 2009] G. Lämmel, H. Klüpfel, and K. Nagel. rium: A cellular automaton-based approach. Computer- The MATSim network flow model for traffic simulation Aided Civil and Infrastructure Engineering, 31(6):432– adapted to large-scale emergency egress and an application 448, 2016. to the evacuation of the Indonesian city of Padang in case [Crociani et al., 2016] Luca Crociani, Gregor Lämmel, and of a tsunami warning. In Pedestrian Behavior, chapter 11, Giuseppe Vizzari. Simulation-aided crowd management: pages 245–265. Emerald Group Publishing Limited, 2009. A multi-scale model for an urban case study. In Agent [Lämmel et al., 2014] G. Lämmel, A. Seyfried, and B. Stef- Based Modelling of Urban Systems - First International fen. Large-scale and microscopic: a fast simulation ap- Workshop, ABMUS 2016, volume 10051 of Lecture Notes proach for urban areas. Annual Meeting Preprint 14-3890, in Computer Science, pages 151–171. Springer, 2016. Transportation Research Board, Washington, D.C., 2014. [Crociani et al., 2017] Luca Crociani, Gregor Lämmel, [Martinez-Gil et al., 2017] Francisco Martinez-Gil, Miguel H. Joon Park, and Giuseppe Vizzari. Cellular automaton Lozano, and Fernando Fernández. Emergent behaviors based simulation of large pedestrian facilities - a case and scalability for multi-agent reinforcement learning- study on the staten island ferry terminals. In Proceed- based pedestrian models. Simulation Modelling Practice ings of the 96th Transportation Research Board annual and Theory, 74:117 – 133, 2017. meeting, Washington, 2017. [Nash, 1951] J. Nash. Non-cooperative games. The Annals [Daganzo, 1998] CF Daganzo. Queue spillovers in trans- of Mathematics, 54(2):286–295, 1951. portation networks with a route choice. Transportation [Raney and Nagel, 2004] B. Raney and K. Nagel. Itera- Science, 32(1):3–11, 1998. tive route planning for large-scale modular transporta- [Dijkstra, 1959] E. Dijkstra. A note on two problems in con- tion simulations. Future Generation Computer Systems, nexion with graphs. Numerische Mathematik, 1:269–271, 20(7):1101–1118, 2004. 1959. [Simon et al., 1999] P.M. Simon, J. Esser, and K. Nagel. [Drucker et al., 1997] Harris Drucker, Chris J C Burges, Simple queueing model applied to the city of Portland. Linda Kaufman, Alex Smola, and Vladimir Vapnik. Sup- International Journal of Modern Physics, 10(5):941–960, port vector regression machines. Advances in Neural In- 1999. formation Processing Dystems, 1:155–161, 1997. [Smola and Schölkopf, 2004] Alex J. Smola and Bernhard [Fernández-Delgado et al., 2014] Manuel Fernández- Schölkopf. A tutorial on support vector regression, 2004. Delgado, Eva Cernadas, Senén Barro, Dinani Amorim, [Spolaor et al., 2017] Simone Spolaor, Andrea Tangherloni, and Dinani Amorim Fernández-Delgado. Do we Need Leonardo Rundo, Marco S. Nobile, and Paolo Cazzaniga. Hundreds of Classifiers to Solve Real World Classification Reboot strategies in particle swarm optimization and their Problems? Journal of Machine Learning Research, impact on parameter estimation of biochemical systems. 15:3133–3181, 2014. In 2017 IEEE Conference on Computational Intelligence [Flötteröd and Lämmel, 2015] G Flötteröd and G Lämmel. in Bioinformatics and Computational Biology (CIBCB), Bidirectional pedestrian fundamental diagram. Trans- pages 1–8, 2017. [Weidmann, 1993] Ulrich Weidmann. Transporttechnik der Fussgänger - Transporttechnische Eigenschaftendes Fussgängerverkehrs (Literaturstudie). Literature Re- search 90, Institut füer Verkehrsplanung, Transporttech- nik, Strassen- und Eisenbahnbau IVT an der ETH Zürich, 1993. [Zhang et al., 2011] Jun Zhang, Wolfram Klingsch, Andreas Schadschneider, and Armin Seyfried. Transitions in pedes- trian fundamental diagrams of straight corridors and t- junctions. Journal of Statistical Mechanics: Theory and Experiment, 2011(06):P06004, 2011. [Zhang et al., 2012] Jun Zhang, Wolfram Klingsch, Andreas Schadschneider, and Armin Seyfried. Ordering in bidirec- tional pedestrian flows and its influence on the fundamen- tal diagram. Journal of Statistical Mechanics: Theory and Experiment, (02):9, 2012.