Pedestrians’ Route Choice Model for Shopping Behavior Bruno Rocha Werberich Carlos Oliva Pretto Helena Beatriz Bettella Cybis Department of Production Engineer Federal University of Rio Grande do Sul Porto Alegre, Brazil {bruno.rwe;cpretto}@gmail.com , helenabc@producao.ufrgs.br Abstract et al. 2002] composed by, at least, two layers: a tactical and an operational layer. This paper presents an agent-based model to address the pedestrian route choice problem in shopping malls. The tactical layer chooses a path regarding an origin- Route choice in shopping malls may be defined by a destination pair and a route choice criteria such as minimum number of causal factors. Shoppers may follow a pre- distance and/or travel times. The tactical model determines defined schedule, they may be influenced by other the desired pedestrian directions, which are used in the people walking, or may want to get a glimpse of a operational model [Pretto et al. 2011]. familiar shopping. The route choice process assumes that the cost of each route can be calculated as a function The operational model determines the low level microscopic of three factors: route length, impedance generated by movements of pedestrians. It is ruled by principles of other pedestrians and attraction for areas of interest on pedestrians’sense and avoidance of obstacles. Most models the environment. The impedance generated by the reported in literature can be regarded as using force-based friction between pedestrians is assumed to exist even approaches [Helbing et al. 1991; Helbing et al. 1995]. In before physical contact, due to the psychological force-based models, agents evaluate forces exerted by tendency to avoid passing close to individuals with high infrastructure and by other agents. Helbing and Molnar relative velocity. Pedestrians seek minimal route length (1995) presented a relevant work on force-based models in and minimal friction with other pedestrians. In order to which they use Newtonian mechanics and a continuous represent shopping areas environments, a new factor is space representation to model a long-range interaction. The being considered in the calculation of the route cost: the concept behind this approach suggests that the motion of a attraction for areas of interest on the environment. pedestrian can be described by combination of several Simulation results were compared to real data collected forces (including the repulsive forces from walls and other by video recording in a shopping mall. pedestrians). The social force model reproduces various emergent phenomena observed on pedestrian´dynamics. 1 Introduction Modelling of pedestrian’s behavior is a complex task and The tactical model is responsible for route choice. Realistic has been studied by different research areas. In order to route choice is a complex process because most route represent motion of pedestrians more realistically, models selection strategies are based on subconscious decisions. are required to simulate several processes, including sense Most models presented in the literature are concerned only and avoidance of obstacles, interaction with other with the quickest or shortest route, like Kirik et. al. (2009), pedestrians and route choice. Agent-based abstraction has Dressler et. al. (2010) and Lämmel et. al. (2014). However, been widely used for pedestrian modeling, mainly due to its other factors play an important role in route choice capacity to provide insights about system´s reactions from behavior, such as: peoples’ habits, number of crossings, changes on entities proprieties, capturing information over pollution and noise levels, safety, shelter from poor weather space and time at a detailed level [Klügl and Bazzan 2012; conditions and other environment stimulations Macal et al. 2006; Rossetti R. et. al. 2002]. Agent-based [Papadimitriou E., 2012]. Most relevant route choice models models represent agents’ decision-making ability based on are concerned with pedestrians' evacuation. In Kretz et. al. their profile and perception over the environment. (2011), for instance, pedestrians routes are chosen based on the minimal remaining travel time to destination. Kretz et. Agent-based pedestrians models require the aggregation of al. (2014) introduce a generic method for dynamic different levels of abstraction, that are modeled on different assignment used with microsimulation of pedestrian layers. The majority of pedestrian models present a multi- dynamics. In the paper, the routes mark the most relevant layer simulation approach [Gaud et al. 2008; Hoogendoorn routing alternatives in any given walking geometry, reducing the infinitely many trajectories by which a pedestrian can move from origin to destination to a small set This paper presents an agent-based route choice model to of routes. Crociani and Lämmel (2016) present a work with represents pedestrians’ in a shopping mall environment. The two major topics. In the first topic, a novel cellular pedestrian model allows the representation of shopping automaton (CA) model is proposed, which describes the users capable to perform either planned and unplanned pedestrian movement by a set of simple rules, and the behaviour, depending on the agent´s profile. Simulation second topic describes how the CA can be integrated into an results were compared to real data collected by video iterative learning cycle where the individual pedestrian can recording in a shopping mall. adapt travel plans based on experiences from previous iterations. Patil et. al. (2010) propose an interactive 2 The Model algorithm to direct and control crowd simulation. The model presented by Treuille et. al., (2006) unifies route planning An agent-based model is proposed to address pedestrian and local collision avoidance by using a set of dynamic route choice problem. Agent-based models represent agents’ potential and velocity. Teknomo (2008) and Teknomo et al., decision-making ability based on agents’ characteristics (2008) described a self-organization route choice approach profile and perception over the environment. In the to model the dynamics of agents, such as pedestrians and proposed model, pedestrians are agents able to choose and cars on a simple network graph. The agents decide, when recalculate routes. Pedestrians are not assigned to reaching a vertex, which edge to enter next. This decision is predetermined routes. based on a set of rules regarding the agent’s observation of the local environment. In order to represent complex In this model, a route is a set of coordinates followed by a networks, such as shopping areas and urban scenarios, pedestrian from origin to destination. Route choice process agents need to represent more complex caracteristics and comprises three factors for calculation: (i) distance, (ii) capabilities. interaction with other pedestrians (avoiding jams) and (iii) attraction for areas of interest on the environment (in this The literature presents several agent-based applications to specific case: shop windows). simulate different pedestrians’ behaviors and environments. The pedestrians’ simulation in a commercial environment, The framework adopted to describe pedestrian behavior in such as shopping malls, is particularly complex since this model (Figure 1) presents a three-layer structure, each pedestrians are exposed to different stimulus and attractions layer representing: [Wang, W. et. al. 2014]. Agent-based simulation is (i) Demand for travel - set of origin and destination. particularly valuable for these cases because environment Each origin-destination pair is associated to a stimulus exert distinct influences depending on the person number of trips and a pedestrian generation rate. profile. Dijkstra et al., (2013) provide a model for pedestrian Origins and destinations are associated with nodes activity simulations in shopping environments. This on the environment layer. framework provides an activity agenda for pedestrian (ii) Simulation environment structure -.The agents, guiding their shopping behavior in terms of environment is described as a continuous space and destination and time spent in shopping areas. Pedestrian is composed by geometric entities, such as rooms, agents need to successively visit a set of stores and move doors, and other obstacles. The environment over the network. The authors assumed that pedestrian entities are linked by a graph-based structure agents’ behavior is driven by a series of decision heuristics. providing a route to all entities. In this model, Agents need to decide which stores to choose, in what order nodes are defined by a set of coordinates (x, y). and which route to take, subject to time and environment Nodes also contain properties defining local constraints. features of the environment. (iii) Pedestrians movement, sense and avoidance of Route choice in shopping malls may be defined by a number obstacles: set of equations and agents behavior of causal factors. Shoppers may follow a pre-defined rules. The social force model (1) describes schedule, they may be influenced by other people walking, pedestrian walking behavior regarding agents’ low- or may want to get a glimpse of a familiar shopping. level motion, collision avoidance and velocity adaptation. Pedestrians freely walk on the Shopping agents, as described in the literature [Borgers, A., modeling environment seeking the next graph node of the designated route. Pedestrians’ movements and Timmermans, H., 1986; Ali, W. and Moulin, B., 2006] are ruled by the sense and avoidance model and are usually decide (i) in which stores to stop, (ii) in what order not restricted to a strict set of links. and (iii) which route to take. In practice, however, shopping mall users´ behaviour is a combination of planned and unplanned decisions. Planned decisions can defined by a set of origin-destination pairs. Unplanned decisions may be resultant from eventual impulses or the attraction exerted by shopping windows. Figure 2 presents the elements involved in the route choice process. The cost estimation for a Pedestrian α to walk from node u to n involves three factors: (i) the distance between nodes ( r! − r! ), (ii) the impedance perceived by the pedestrian α exerted by other pedestrians (I! ) and (iii) the environment attraction perceived by pedestrian α for the node n (A!! ). Impedance exerted by the pedestrians in the simulation is calculated by simple vectors operations. Subtracting the desired velocity of pedestrian α from the velocity of pedestrians closer to node n ( pedestrians 𝛽) it is possible to estimate I! (equation 1). Figure 1 - Layers !! !!! I! = ! 𝑣! − !! !!! ∗ 𝑣!! (1) 2.1 The Route Choice Process The presented route choice process is derivate from model where: established by Werberich et. al. (2014). Werberich et. al. v! = Pedestrian’s β current velocity; propose that the cost of each route can be calculated as a r! = Node’s n vector position; function of two factors: route length and the impedance r! = Node’s u vector position ; generated by other pedestrians. The impedance generated by 𝑣!! = Pedestrian’s α desired speed. the friction between pedestrians is assumed to exist even before physical contact, due to the psychological tendency to avoid passing close to individuals with high relative The calculation of I! considers a neighborhood area around velocity [Helbing D. et al., 2000]. Pedestrians seek minimal the node n, defined by the radius R ! . All pedestrians inside route length and minimal friction with other pedestrians. In the neighborhood area, at the instant of the route choice, are this model, a new factor is being considered in route cost nominated pedestrians β. I! is the sum of the friction forces calculation: attraction for areas of interest on the exerted by each pedestrian β over the desired velocity of the environment. pedestrian α. The total route cost is the sum of all link costs. Dijkistra As mentioned above, the graph nodes contain properties that algorithm [Dijkstra E., 1959] is adopted to generate valid classify local features of the environment. Node properties routes for any origin/destination pair. Figure 2 describes the define the environment characteristics. For example, cost calculation for a link. properties can be defined as female clothes store, male clothes store, electronics store, shoe store, etc. Nodes are defined by a set of values for all simulated properties. Higher properties values mean the node is closer of the related feature. Properties can assume values in the range [0 – 1]. The attraction exerted by these nodes properties on pedestrians vary dependeing on pedestrians profiles. Pedestrians' profiles also present a set of values for all simulated environment properties, that represent their attraction for these features. For example, male pedestrians probably have higher values for a property relating to a male clothes store. These properties also assume values in the range [0 – 1]. The attraction of node n, perceived by pedestrian α (A!! ), is calculated as a weighted average (Equation 2): ! ! ! !!! !! ∗!! 𝐴!! = ! !! (2) !!! ! Figure 2 – Pedestrian’s profile and node attraction where: p = total number of properties; speed vector (𝑣!! ) and the forces exerted by the hotspot P!! = pedestrian α property i value; walls, keep the pedestrian standing in the neighborhood N!! = node n property i value. area. During this period, the interaction between pedestrians is maintained, allowing a realistic representation of The total estimated cost for pedestrian α to walk from node pedestrians behavior at window shops. When a pedestrian u to n (W!!,! ), is a balance between distance, impedance and stopping time has expired, a new route is recalculated to the attractiveness, as described in Equation 3: final the destination. W!!,! = r! − r! . (1 + I! /I!"# + (1 - A!! )) (3) The time a pedestrian stops at a hotspot may has variable assumptions. In this formulation, pedestrians stopping time where: is assumed to be fixed, equal to 20 seconds. Assumptions I!"# = settable parameter that adjusts the balance between about stopping times can be discussed in more detail. An distance and impedance. Further description of this important work regarding time spent at store windows was parameter can be obtained in Werberich et al. (2014). developed by Dijkstra J. et. al. (2014). In this paper, authors describe the time spent in a store based on pedestrians Elected routes minimize the total cost W! . Equation 3 profile and store segment. ensures pedestrians are attracted to areas of interest considering their profile. Pedestrians also avoid congested Figure 3 presents a flowchart of the agent’s internal process. areas and passing close to other pedestrians with high relative velocity. 2.2 Pedestrian Stopping Behavior It is expected that pedestrians walking on shopping environment, when attracted by an environmental stimulus, may stop for a while. For example, pedestrians attracted by a shop window frequently stop walking when they get closer to this interest point. This model simulates pedestrians route choice process subjected to attraction by interest areas, tipical of shopping environments. To simulate pedestrians’ stopping behavior the model introduces the concept of hotspots. Hotspots are defined by a location on the environment (𝑥 and 𝑦 coordinates) and a neighborhood area (radius 𝑅). Hotspots have the same environment properties as graph nodes. When a pedestrian reaches the neighborhood area of a hotspot, he decides whether to stop or not. This decision process considers the pedestrian profile and the hotspot properties. Pedestrian profile includes a value denoting the tendency to stop on a hotspot (T! ). Higher values of T! means the pedestrian have Figure 3 - Agent’s internal process higher tendency to stop on hotspots. T! values also respect the range [0–1]. Equation 4 defines the probability of a As presented in this flowchart, a pedestrian only performs a ! pedestrian α stopping on a hotspot q (S! ). route recalculation procedure after stopping at a hotspot. A Social Force-based route choice process considers the ! ! ! interaction with other pedestrians, which provides a !!!(!! ∗!! ) 𝑆!! = ! ! ! ∗ 𝑇! (4) dynamic behavior. However, if necessary, when simulating !!! ! complex scenarios, the model structure allows the where: introduction of route recalculation areas. When simulating p = total number of properties; small scenarios, where the decision at the beginning of the P!! = pedestrian α property i value; trip was based on a good assessment of the way forward for H!! = hotspot q property i value; all simulation timeframe, route recalculation may not be T! = pedestrian α tendency to stop on a hotspot. necessary. If a pedestrian decides to stop on a hotspot neighborhood, the hotspot coordinates become his new destination for the stopping period. The balance between the pedestrian desired 3 Collected Data Data analysis allows the identification of three stores with higher pedestrian attraction . Table 1 shows the number of Video data were collected in a shopping mall of Porto pedestrians, men (M) and women (W), that were attracted Alegre, Brazil. The camera collected images from a hall that and stopped closer to these areas. connects the two main corridors of the first floor. Figure 4 presents an image of the studied area and the collected pedestrian routes. Table 1 – Stopped pedestrians The software Tracker was used to collect pedestrians’ data in a semi-automatic process. The collected data is composed by a set of coordenates (x and y) over 1 minute of video for each pedestrian. In order to simplify the data analysis, the enviroment was segmented in cells. A color map representing the cumulative occupation of each cell is shown at figure 5, segmented by gender. 4 Simulation The proposed model has the potential to represent several properties regarding agents’ profile and environment characteristics. In order to simplify the simulation, only two properties were considered in this experiment: Male Store Attraction (MSA) and Female Store Attraction (FSA). These two properties were applied to: i. Scenario elements: hotspots and graph nodes (MSAs and FSAs); ii. Agents (MSAa and FSAa). The experiment was developed to identify the influence of MSAa and FSAa in the number of pedestrians that are attracted to hotspots. The MSAa and FSAa were calibrated based on collected data. The model was implemented using c# programming language (simulation engine) and Windows Presentation Foundation for the graphical interface. Figure 4 – The Mall 4.1 Simulation Scenario Figure 6 shows the simulation scenario built to represent the observed environment. Green areas (h1, h2, h3) are the hotspots. The hotspots correspond to stores where mall users used to stop on the real site. Dots are the graph nodes. Rectangles represent mall kiosks. Figure 6 – Simulation scenario Figure 5 –Collected data Table 2 shows the values for MSAs and FSAs considered for the hotspots and its surronding yellow graph nodes. Blue graph nodes (Figure 6) exert no attraction over the agent, the value for both MSAs and FSAs are zero. The MSAs and FSAs values were assumed to be constants. The MSAs and FSAs definition can be enhanced by considering effects of various design and management attributes. An example of the evaluation of consumers attraction can be found in Oppewal, H., and Timmermans, H. (1999). The authors estimated a stated preference model from responses to descriptions of an hypothetical shopping centers considering attributes such as: area for pedestrians, window displays, Figure 7 – Simulation screenshot street layout, and street activities. Figure 8 shows a color map of the results for all simulation groups (s1, s2, s3, s4), and the average number of agents stopping at each hotspot (h1, h2, h3) over 50 simulation Table 2 – Hotspots configuration runs. 4.2 Calibration The calibration process aimed to calibrate the agents’ profile (MSAa and FSAa) in order to reproduce the number of stopped pedestrians at each hotspot. For this purpose, four groups of simulations were run (s1, s2, s3, s4). For each simulation group, 50 simulations were performed. Two agents classes were implemented: male agents (MA) and female agents (FA). By definition, male agents have FSAa = 0 and female agents have MSAa = 0. Table 3 shows the configuration profiles defined for each simulation group. Table 3 – Agents profile configuration simulation group MA FA s1 MSAa = 0.1 FSAa = 0.1 s2 MSAa = 0.5 FSAa = 0.5 s3 MSAa = 0.7 FSAa = 0.7 Figure 8 – Simulations results s4 MSAa = 0.9 FSAa = 0.9 4.2 Simularion Analysis The only variables in simulations were MSAa and FSAa. Simulation group s3 presented the best ajustment to the The scenario configuration was kept constant. Agents’ observed data. Higher values of MSA and FSA lead to tendency to stop (𝑇! ) was set to 0.7. According to observed higher attraction to hotspots. However, it is important to data, each simulation run comprised 80 agents, 40% MA highlight that even though a pedestrian chooses a route to and 60% FA. Pedestrians are generated with a fixed rate get closer to a shop window, he needs to reach a hotspot to over time, with 40% of change to be male and 60% of stop. If the hotspot area is too crowded, he may not reach change to be female. Figure 7 shows a simulation the hotspot, due to the social force effect, and do not stop. screenshot, MA are green circles and FA are red circles. A Thus, the attraction effect has a tendency to be balanced. simulation video is availiable at: Figure 9 show the s3 color map and the color map generated https://youtu.be/10OUgNMaoNA. from real data. The s3 color map is one of 50 simulations. It is possible to observe differences in color patterns between simulation and real data. This difference is due the noise of pedestrians’ tracking process and camera perspective. It is References important to highlight stopping pattern at hotspots is similar. [Klügl, F., & Bazzan, A. L., 2012] Agent-based modeling and simulation. AI Magazine, 33(3), 29. [Macal, C. M., & North, M. J., 2006] Introduction to agent- based modeling and simulation. In MCS LANS Informal Seminar. [Rossetti, R. J., Bordini, R. H., Bazzan, A. L., Bampi, S., Liu, R., & Van Vliet, D., 2002] Using BDI agents to improve driver modelling in a commuter scenario. Transportation Research Part C: Emerging Technologies, 10(5), 373-398. [Gaud N, Galland S, Gechter F, et al., 2008] Holonic multilevel simulation of complex systems: application to real-time pedestrians simulation in virtual urban environment. Simul Model Pract Theory 2008; 16: 1659–1676. [Hoogendoorn S, Bovy P and Daamen W., 2002] Microscopic pedestrian wayfinding and dynamics Figure 9 – Real data versus simulation data modelling. In: Schreckenberg M and Sharma S (eds) Pedestrian and evacuation dynamics. Berlin: Springer, 5 Conclusions 2002, pp.123–155. The modeling approach presented in this paper provides a [Pretto CO, Jacobsen AC and Cybis H B B. 2011] A multi- sound representation of pedestrian route choice dynamics layer simulation model for vehicle and pedestrian. In: considering the attraction to shop windows. Route choice is Proceedings of the 90th Annual Meeting of the based on a combination of distance, impedance generated by Transportation Research Board, Vol. 1, Washington, other pedestrians and shop window attraction. The model 2011, pp.1–15. differs from other pedestrians’ route choice approaches [Helbing D., 1991] A mathematical model for the behavior because it seamlessly incorporates pedestrians social force of pedestrians. Behav Sci. 1991; 36: 298–310. into the route choice decision process. [Helbing D and Molnar P., 1995] Social force model for pedestrian dynamics. Phys Rev E Stat Phys Plasmas In this model, we have created an association between the Fluids Relat Interdisciplin Top 1995; 51: 42–82. pedestrian’s profile and store segment. When a pedestrian defines a route, due to its attraction to a store, he draws his [Kirik ES, Yurgel’yan TB and Krouglov DV., 2009] The chance to stop at a hotspot. The formulation of stopping shortest time and/or the shortest path strategies in a chances can be enhanced through a more complex agent pedestrian dynamics model. J Siberian Fed Univ Math abstraction. However, it is well known that increasing Phys 2009; 2: 271–278. model complexity usually leads to an increase in the [Dressler D, Groß M, Kappmeier J, et al. 2010] On the use calibration process effort. of network flow techniques for assigning evacuees to exits. Procedia Eng 2010; 3: 205–215. The analysis from simulations indicates that the agents’ emerging behavior provides a promising approach for real [Lämmel G and Plaue M., 2014] Getting out of the way: case applications. This model formulation is capable of collision avoiding pedestrian models compared to the supporting more complex agents’ profiles and aplications to real world. In: Weidmann U, Kirsch U and different enviroments, such as variable shopping premisses, Schreckenberg M (eds) Pedestrian and evacuation expositions sites and passengers terminals. dynamics 2012. Berlin: Springer, 2014. [Papadimitriou E., 2012] Theory and models of pedestrian Acknowledgments crossing behaviour along urban trips. Transp Res Part F Traffic Psychol Behav 2012; 15: 75–94. The authors wants to thank the financial supported by the National Council for the Improvement of Higher Education [Kretz T, Große A, Hengst S, et al., 2011] Quickest paths in (CAPES) and National Council for Scientific and simulations of pedestrians. Adv Complex Syst 2011; 14: Technological Development (CNPq), both of Brazil. 733–759. [Kretz, T., Lehmann, K., Hofsäß, I., & Leonhardt, A., 2014] Dynamic assignment in microsimulations of pedestrians. arXiv preprint arXiv:1401.1308 [Crociani, L., & Lämmel, G., 2016] Multidestination Pedestrian Flows in Equilibrium: A Cellular Automaton- Based Approach. Computer Aided Civil and Infrastructure Engineering, 31(6), 432-448. [Patil S, Van Den Berg J, Curtis S, Lin MC and Manocha D., 2010] Directing crowd simulations using navigation fields, IEEE Trans Visualization Comput Graphics 2010; 17(2): 244–254. [Treuille A, Cooper S and Popovic Z., 2006] Continuum crowds. ACM Trans Graphics 2006; 25(3):1160–1168. [Teknomo K. 2008., 2008] Modeling mobile traffic agents on network simulation. In: Proceedings of the 16th annual conference of the Transportation Science Society of the Philippines (TSSP), Manila, 2008. [Teknomo K, Bauer D and Matyus T., 2008] Pedestrian route choice self-organization. In: Proceedings of the 3rd international symposium of simulation in transportation, Gold Coast, Australia, 2008. [Wang, W. L., Lo, S. M., Liu, S. B., & Kuang, H. 2014] Microscopic modeling of pedestrian movement behavior: Interacting with visual attractors in the environment. Transportation Research Part C: Emerging Technologies, 44, 21-33. [Dijkstra, J., Timmermans, H. J., & de Vries, B., 2013]. Activation of shopping pedestrian agents—Empirical estimation results. Applied Spatial Analysis and Policy, 6(4), 255-266. [Borgers, A., & Timmermans, H., 1986]. A Model of Pedestrian Route Choice and Demand for Retail Facilities within InnerCity Shopping Areas. Geographical analysis, 18(2), 115-128. [Ali, W., & Moulin, B., 2006]. How artificial intelligent agents do shopping in a virtual mall: A ‘believable’and ‘usable’multiagent-based simulation of customers’ shopping behavior in a mall. In Advances in Artificial Intelligence(pp. 73-85). Springer Berlin Heidelberg. [Werberich, B. R., Pretto, C. O., & Cybis, H. B. B., 2014] Pedestrian route choice model based on friction forces. Simulation, 0037549714547295. [Helbing D, Farkas I and Vicsek T., 2000] Simulating dynamical features of escape panic. Nature 2000; 407: 487–490. [Dijkstra E., 1959] A note on two problems in connection with graphs. Numer Math 1959; 1: 269–271. [Dijkstra, J., Timmermans, H., Jessurun, J., & de Vries, B., 2014]. Modeling Time Duration of Planned and Unplanned Store Visits in a Multi-Agent Simulation of Pedestrian Activity in City Centers. In Pedestrian and Evacuation Dynamics 2012 (pp. 815-823). Springer International Publishing. [Oppewal, H., & Timmermans, H., 1999] Modeling consumer perception of public space in shopping centers. Environment and Behavior, 31(1), 45-65.