key: cord-0505339-7ojtwe78 authors: Parisi, Daniel R.; Patterson, Germ'an A.; Pagni, Lucio; Osimani, Agustina; Bacigalupo, Tomas; Godfrid, Juan; Bergagna, Federico M.; Brizi, Manuel Rodriguez; Momesso, Pedro; Gomez, Fermin L.; Lozano, Jimena; Baader, Juan Martin; Ribas, Ignacio; Meyer, Facundo P. Astiz; Luca, Miguel Di; Barrera, Nicol'as E.; 'Alvarez, Ezequiel M. Keimel; Oyhanarte, Maite M. Herran; Pingarilho, Pedro R.; Zuberbuhler, Ximena; Gorostiaga, Felipe title: Social Distance Characterization by means of Pedestrian Simulation date: 2020-09-08 journal: nan DOI: nan sha: 325249707132934c7f174f2360d3dfdf75170372 doc_id: 505339 cord_uid: 7ojtwe78 In the present work, we study how the number of simulated clients (occupancy) affects the social distance in an ideal supermarket. For this, we account for realistic typical dimensions and process time (picking products and checkout). From the simulated trajectories, we measure events of social distance less than 2 m and its duration. Between other observables, we define a social distance coefficient that informs how many events (of a given duration) suffer each agent in the system. These kinds of outputs could be useful for building procedures and protocols in the context of a pandemic allowing to keep low health risks while setting a maximum operating capacity. Recent works [2, 3] propose to combine microscopic agent simulation with general disease-transmission mechanisms. However, because of the complexity and uncertainties in the actual knowledge for quantifying these transmission processes, we will not consider in this work any particular contagion mechanism, instead, we will focus on studying the distance between people in an everyday pedestrian facility as an isolated aspect to be integrated in the future by experts considering all mechanism for any particular disease propagation. An antecedent of this kind of analysis was recently reported considering field data from a train station [4] . One of the key questions we try to answer is how to describe the realized social distance for a given occupation of an establishment. For solving this problem, it is necessary to consider the pedestrian displacements and trajectories that they do while performing certain tasks, and thus, a natural tool is to use pedestrian simulation. The time evolution of positions from simulated agents can provide not only the relative distance between agents, but also the duration of events in which the recommended social distance is not kept. Many industries and shops were closed in different phases of the COVID-19 pandemic. However, grocery shops had to be kept open, in particular supermarkets. To avoid crowding and to keep some physical distance between clients, the authorities lowered the allowed capacity. Different countries regulation adopt social distance requirements between 1 and 2 m [4] . In the present study we will consider a distance of 2 m as the social distance threshold, because this distance is an upper bound for the saliva droplets from a human cough which cannot travel more than 2 m in space at approximately zero wind speed [5] . We propose to investigate how the value of the allowed capacity affects the social distance in an ideal supermarket of 448 m 2 . The results should not be directly extrapolated to other supermarkets or facilities, nevertheless, the methodology and indicators can be useful for applying them to other source of data, being from simulations or field data of other pedestrian systems. In order to simulate the complex environment and the agent's behavior, the proposed model involves three levels of complexity: operational, tactical, and strategic [6] . The more general level of the model is in charge of providing a master plan for the agent when it is created. In practical terms for the present system, it gives a list of n p products for agents to acquire (a shopping list). Each one of the n p items is randomly chosen between a total of m p products available. Also, they are identified with a unique target location (x pn ) in the supermarket. Once the agent is initialized with its shopping list, the strategic level shows the first item in the list to the agent. The agent will move toward it using the lower levels of the model. When the agent reaches the position of the product, it will spend a picking time (t p ) choosing and taking the product, after which the strategic level will provide to the agent the next item on the list. After the list of products is completed, the agent must proceed to the less busy supermarket checkout line. It will adopt a queuing behavior until it gets the checkout desk and spends a time t co processing its purchase. The function of the tactical level is to provide successive visible targets to the agent that will guide it to the location of the desired product (x pn ) or checkout line. As inputs, the tactical module takes the current agent position (x i (t)) and the position of the current product (x pn ) in the list. The output is a temporal target (x v (t)) visible from the current position of the agent. The definition of visibility is that if we take a virtual segment between (x i (t)) and (x v (t)), this segment does not intersect any of the walls or obstacles (shelves). The information delivered by the tactical module is obtained by implementing a squared network connecting all the accessible areas of the simulated layout (see Fig.2 ). Given any two points in the walkable domain, the corresponding nearest points on the network are found and then the shorter path between these points is computed by using the A* algorithm [7] . Once the path on the network is defined, the temporary target x v (t) is chosen as the farthest visible point on that path seen from the current agent position. Clearly, x v (t) will change with time, as the position of the agent changes. When the product target is visible from the agent, this is set as the visible target and the network path is no longer considered until a new product should be found. As the lower level describing the short-range movements of agents we propose an extended version of the "Contractile Particle Model" [8] . This extension will provide an efficient navigation allowing to avoid potential collisions with other agents and obstacles. The basic model is a first-order model in which particles have continuous variable radii, positions and velocities that change following certain rules. Specifically, the position is updated as where v i is the desired velocity and x i (t) the position at time t. The radius of the i th particle (r i ) is dynamically adjusted between r i min and r i max . When this radius has large values, it represents a personal distance necessary for taking steps, but when it has low values, it represents a hard incompressible nucleus which limits maximum densities. When particles are not in contact, the desired velocity v i points toward the visible target with a magnitude proportional to its radius, where the direction e i t and the magnitude v are defined by the following equations where v d is the desired speed. While the radius has not reached the maximum r max , it increases in each time step following being τ a characteristic time in which the agent reaches its desired speed as if it was free, and ∆t is the simulation time step of Eq. 1. When two particles enter into contact (d ij = |x i − x j | − (r i + r j ) < 0) both radius instantaneously collapse to the minimum values while an escape velocity appears moving the particles in the directions that will separate the overlap: The escape velocity has the magnitude of the free speed and, thus, it can be written as v i e = v d e ij . This velocity is only applied during one simulation step because, as the radii are simultaneously collapsing, the agents are no longer overlapping. Up to here, we described the basic CPM as it appears in Ref. [8] . This model satisfactorily described experimental data of specific flow rates and fundamental diagrams of pedestrian dynamics. However, particles do not anticipate any collisions, and this capacity is a fundamental requirement for simulating the ideal supermarket (displaying low and medium densities, and agents circulating in different directions). For this, we propose to extend the calculation of the agent velocity (Eq. 2) by considering a simple avoidance mechanism. The general idea is that the self-propelled particle will produce any action only through changing its desired velocity v i (t) as stated in Ref. [9] . In this case, the new mechanism will only change the direction of desired velocity v depending on the neighbor particles and obstacles. First, the collision vector (n c i ) is calculated where j indicates the nearest visible neighbor, k the nearest point of the nearest visible wall or obstacle, andη is a noise term for breaking possible symmetric situations. visibility field of agent "i" Then the avoidance direction is obtained from and finally the velocity of the particle to be used in Eq In Fig.1 the vectors associated with the original and modified model can be seen in detail. Because the agents must perform different tasks, more complex than just going from one point to another, it was necessary to define five behavioral states. This was achieved by setting different model parameters and movement patterns. More concisely, the five behavioral states of agents were: -Going: This is the normal walking behavior when going from one arbitrary point to another with the standard velocity and model parameters. Only in this state, the agent uses the modified CPM velocity (Eq. 9) for avoiding potential collisions. The rest of the behavioral states only use the basic CPM (Eq. 1 to 6). -Approximating: When the agent is closer than 2 m of the current product, it reduces its desired speed and, because of how parameters are set, it will not be forced to reach it if there is another agent buying a product in the same target x pn . -Picking: Once the agent reaches the product (closer than 0.1 m) a timer starts and it will remain in the same position (Eq. 1 does not update its position) until the picking time (t p ) is up. -Leaving: After spending the time t p , the agent leaves the current location going to the next product on the list. While abandoning this position, it could find other waiting agents (in Approximating behavioral state) and, thus, its parameters must be such that it can make its way through. Once the agent is farther than 2 m from the past product, it changes to the "going" behavioral state. -Queuing: Finally, when the agent completes the shopping list, it proceeds to the checkout desks by choosing the one with the smaller line. It waits at a distance of 1.5 m from the previous queuing agent, and when it reaches the checkout position, it remains there for a t co time. By considering these behavioral states in the agent model, the conflicts and deadlock situations are minimized. In this way, this model improvement allows us to simulate higher densities than with the basic operational models. Finally, as a closure for this general section (2) about the model, we point out that for the sake of comparison, we also implement other operational models: the "Social Force Model" [10, 11] , and the "Predictive Collision avoidance Model" (PCA) [12] . The results for all models will be compared in selected observables, while the more deep study is performed using the modified CPM described above. The plant of 448 m 2 of the ideal supermarket to be simulated is shown in Fig. 2 . The dimension of shelves (1 m x 10 m) and corridor width (2 m) are taken from typical real systems. Also, the different process time and other data considered were provided by a supermarket chain from Argentina. We define N as the allowed capacity or the occupation of the supermarket as the total number of agents buying simultaneously inside the system. This is the more important input to be varied in our study and it ranges from N = 2 to N = 92. The agent generator produces an inflow of 1 agent every 5 seconds until it reaches the N value for the simulation. From that moment on, the agent generator monitors the occupation, and it generates a new agent every time an existing agent completes its tasks and is removed from the simulation. By doing this, the value of N is maintained constant over the whole simulation. Every agent created by the generator is equipped with a shopping list of exactly n p = 15 items, which are chosen randomly from a total of 228 items available (shown in Fig.2 B) . The corresponding product locations (x pn ) are separated by one meter between adjacent locations. Agents visiting the products on its lists, spend a picking time with a uniform distribution (t p ∈ [60s, 90s]). After completing the lists, agents choose the shortest queue to one of the eight checkout points shown in Fig. (2 B) . The ideal supermarket has a maximum of four queues, and each of them leads to two checkout desks. The distance between the agents that form the queue is 1.5 m. The first positions on these queues are at a distance of 3 m (at y = 4 m, in Fig.2 ) from the checkout points. Once an agent reaches the cashier (at y = 1 m, in Fig.2) it spends a checkout time t co uniformly distribute between t co ∈ [120s, 240s]. For each value of N , we simulated two hours (7200 s) and recorded the state of the system every ∆t2 = 0.5 s, thus producing 14400 data files with positions, velocity, and behavioral state of agents. The rest of the model parameters depends on the behavioral state of the agent. For the case of "going", the parameters of the avoidance mechanism described in Eq. (7) We first show general results of the simulated supermarket by displaying typical trajectories (Fig. 3) and density fields (Fig. 4) . Figure 3 plots ten random chosen trajectories in the second hour of simulations for the selected N values. Qualitatively it can be seen more intricate trajectory patterns as the occupancy increases. However, in all cases, it can be observed that the available area is uniformly visited by simulated agents while visiting their product list. Complementary information is shown in Fig.4 , where the density is averaged over all the simulation time (2 hours). As expected, greater occupancy presents greater mean density values. Besides, these density fields present higher values at the spots that agents stay longer, revealing picking points of products and predefined places at queuing. Also, as a macroscopic observable of the system, we study the number of agents that could be processed (i. e. fulfill the shopping list and exit the supermarket between the two hours simulated) and the mean residence time for those agents. The results are presented in Fig. 5 . As can be observed, both quantities increase monotonically with the allowed occupancy for the studied range of values and the supermarket set up, considering eighth checkout desks. Also, it can be seen that different operational models display similar observables. The SFM [10, 11] and PCA [12, 10] models are force-based models which present more limitations in terms of the maximum density they can simulate before forces get balanced (generating dead-locks) for the complex scenarios and behavior considered. This is the reason why the maximum occupancy studied with these models is lower than that simulated with the CPM described in Sec.2. In this subsection, we characterize distance between agents during the simulations with the modified contractile particle model (CPM) for different allowed capacities. An interesting outcome is the distance to the first neighbor for each agent shown in Fig. 6 . The PDF of first-neighbor distances (d f n ) shows that for lower occupations of the simulated supermarket, the probability of having the first neighbors further away than d f n ∼ 5 m is greater. On the other hand, higher occupancy values display higher probabilities of having a distance shorter than 5 m. In particular, all distributions show a maximum probable value around d f n ∼ 4 m. Moreover, the height of these probability peaks decreases for lower occupancy values. Now we take the social distance threshold of 2 m, as discussed in Sec.1, and calculate related probabilities of agents below this critical social distance. The first observable we calculate is the probability of having the first neighbor closer than 2 m (P f n<2m ). In other words, this is the probability of having at least one neighboring agent within 2 m. It is determined by averaging over recorded data every ∆t2 = 0.5 s, from minute 20 to 120 as shown in Eq.(10) where n ti = 12000 = 14400 − 2400 is the data at recorded times after 20 minutes, N is the occupancy and n f n2m is the number of particles having a first neighbor at less than 2 m. Note that if two particles i and j are the only particles at less than 2 m, n f n2m = 2. Also, if j is the first neighbor of i, not necessarily, i will be the first neighbor of j. The above probability (P f n<2m ) only considers if the first neighbor is closer than 2 m, but it does not take into account if there are many occurrences of neighbors at less than 2 m. For this reason, we now take into account the number of pairs having distance less than 2 m, and the corresponding probability (P pair<2m ) where n p2m is the number of pairs of particles at distance closer than 2 m and [N (N − 1)]/2 is the total number of possible pairs, having N particles in the system. In this case, if only particles i and j are closer than 2 m, n p2m = 1 because one pair is counted. In Fig. 7 both probabilities ( P f n<2m and P pair<2m ) are displayed for the modified contractile particle model (CPM) and also by comparison with the social force model (SFM) and predictive collision avoidance model (PCA). It can be seen that the probability of having the nearest neighbor at less than 2 m increases monotonically with the allowed capacity. However, the pair probability quickly increases for low occupancy, and after N ∼ 15, it remains nearly constant indicating that the number of pairs n p2m scaled with N as the number of total possible pairs (∼ N 2 ). Furthermore, Fig. 7 indicates that different operational models display similar macroscopic behavior regarding social distances, at least for values bellow or above 2 m. In the above analysis, the occurrence of certain distances between simulated agents was studied, but the duration of these events was not considered explicitly. This will be done in the following subsection. Here we study the time that lasts the events when pairs of agents are found at less than 2 m (see Sec.1). The main sources of these events are when agents are picking products at neighbor product locations or when queuing for checking out from the supermarket. If two particles i and j encounter at a given time, then they separate for more than 2 m, and the same particles re-encounter at a future time, it is considered as two separate events. Considering that: (a) The parameter we choose to maintain constant during each simulation is the allowed capacity N , and this capacity is reached at the beginning of each simulation in a very short time comparing to other processes, and (b) All agents have the same number of items in their list, and thus the required time to complete it is similar in average. The first group of N agents will go to the checkout points at nearly the same time, producing the greater demand for checkout, which generates the longest queues. After that, the new agents will enter slowly as other agents exit the simulation, and thus the described behavior will relax. This dynamic lead to more queuing agents during the first hour of simulation and less during the second hour. Because of it, we analyze separately the duration of encounters occurred during the first and the second simulation hour in Fig. 8 . The different time scales and the number of cases in its both panels confirm that the first hour is dominated by particular long lines waiting for checkout, while in the second hour (Fig. 8 B) the duration of social distance events less than 2 m are dominated by the shorter process, i.e.: the picking time at products. Events in the queuing line are much long-lasting because of two reasons. First, the particular process at the checkout desk takes between 2 to 4 minutes (instead of 1 to 1.5 minutes in the picking process). Second, a line with n l agents will produce that the last agents will spend about n l times t co , which for a few agents, namely n l = 5, it could represent 20 minutes of waiting time at a distance of 1.5 m from another agent. This problem of high exposure time between pairs of agents at queuing lines could be avoided if a slower ramp of inflow of agents was adopted in the start of the process, let's say something above the maximum average outflow of the system (eight agents in three minutes, i.e. ∼ 1 agent every 23 s). We did not adopt this in the simulations because it would take too long for simulations to reach the desired occupation N . But it is clear that the problem noted above at the beginning could be solved in a real operation by allowing a low flow rate of agents at the opening (of about twice the capacity of the checkout). Also, this problem would be a transient behavior only at opening, being the most part of the day operation as described in our second simulation hour. Furthermore, Fig.8 shows that, as expected, fewer social distance events occur when the time thresholds increase. And in all cases, the number of events seems to grow quadratically with N . Now, looking for a criterion that determines which would be a reasonable allowed capacity in the ideal supermarket, we define the social distance coefficient (SD c (t e )), for the threshold distance of 2 m, as where t e is the minimum duration of a particular social distance event (r ij ≤ 2 m), N e (t e ) is the number of these events which last at least t e , and N p is the total number of agents processed by the system in the same period of time in which N e is computed. Factor 2 is needed for taking into account the number of agents in the numerator since 2 agents (i and j) participate in each event. This coefficient allows us to compare how many agents have participated in social distance events of duration greater than t e concerning the number of people who have passed by the system. Thus, a value of SD c (t e > 2min.) = 1 indicates that, on average, each agent has participated in one event of social distance less than 2 m that lasts at least 2 minutes. If SD c (t e > 2min.) < 1, it would indicate that only a fraction of the agents have participated in such events. Having established in Subsec. 4.3 that the event duration of the first simulation hour is dominated by checkout lines, we now concentrate on looking at the second hour of simulation when the impact of these lines is very low and stationary. This situation is representative of the daily operation of the supermarket, and it is shown in Fig.9 displaying the social distance coefficient as a function of the occupation for different event duration limits t e . First, we note in Fig. 9 A that the curve corresponding to t e > 1 min. grows steeply with N. This could be related to the fact that the picking time range between 1 minute and 1.5 minutes, and that the products are spaced by 1 m, so if two agents must go simultaneously to the same product or the first or second nearest product, they could generate a 2 m social event lasting at most 1.5 minutes, in particular many events lasting more than 1 minute would occur. Also, the social distance coefficient seems to follow a linear relation with N for this particular time limit t e . A change of regime can be observed for t e > 1.5 min. in which curves are more similar between themselves for the different t e presented, and they follow a quadratic relation with N . Because the maximum picking time is 1.5 minutes, this is the maximum possible overlapping time for two agents in neighbor (or the same) products. Greater time events will arise when more than two agents are waiting for the same or near products, as is in the cases of products near any of the short lines for checking out. Finally, we could use Fig. 9 B, as a guide for deciding on the allowed occupancy. If based on epidemiological knowledge or criteria, it was decided that it would be acceptable to allow that all agents participate once in a 2-m social event lasting at most 1 minute, then the allowed occupation would be very small, N ∼ 10. Alternatively, if events up to 1.5 minutes were accepted, then the allowed occupation would be N = 40. In the case of t e = 2 min., the capacity could rise to N = 70. Also, it could be established that even for N = 90 the events of the social distance of 2 m, lasting more than 3 minutes, would only affect the 40% of the processed agents. Of course, the same Fig. 9 B could be used for finding another allowed occupancy if the criterion would consider that, for example, only 25% of the agents can participate in the analyzed events. In this work, we investigate and characterize the social distance realization in an everyday pedestrian system by simulating the dynamics of an ideal supermarket. Many sources of complexity were successfully taken into account with a multi-level model, which allows us to simulate not only translation but also more complex behaviors like waiting times when picking for particular products and queuing for checkout points. The main process that keeps pedestrians near one to another is the queuing lines for checkout. Therefore, advice for the operation would be to keep these lines as small as possible either by increasing the number of checkout points or by decreasing the occupancy. Different operational models, display similar macroscopic observables regarding social distances at values greater than 2 m indicating that the results are robust with respect to microscopic collision avoidance resolution and also suggesting that the simulated paths of the particles are more influenced by the geometry, shopping list, and time-consuming process, than by the particular avoidance mechanism. However, first-order models as the CPM presented in [8] and Sec.2 seem more suitable for simulation of high populated scenarios with complex behavioral agents. Taking a social distance threshold of 2 m [5] , probabilities and duration of such events were studied. The social distance coefficient was defined as an indicator of the fraction of the population passing by the system that is involved in one or many of these events lasting at least a certain time threshold t e . The same analysis can be done for a different set of parameters and, of course, for other pedestrian facilities, being other specific supermarkets or any different systems (Transport, Entertainment, etc.). Of course, existing facilities can be monitored with measurement methods [4] providing high-quality trajectory data. This kind of data could also be interpreted in terms of the analysis performed in the present work. By setting a distance and a time threshold, and what fraction of the population would be tolerable to be exposed to these conditions, the maximum occupancy can be established in any particular system by performing simulations and using the observables defined in this work. Therefore, this analysis could be used for determining which is the ideal occupation of a pedestrian facility, keeping low contagion risk, and maximizing the number of users per unit of time. World Health Organization. Coronavirus disease (COVID-19) advice for the public A microscopic approach to study the onset of a highly infectious disease spreading Agent-based simulation of pedestrian dynamics for exposure time estimation in epidemic risk assessment Monitoring physical distancing for crowd management: real-time trajectory and group analysis On coughing and airborne droplet transmission to humans Pedestrian route-choice and activity scheduling theory and models Path planning for virtual human motion using improved a* star algorithm Continuous-space automaton model for pedestrian dynamics Pedestrian collision avoidance with a local dynamic goal Simulating dynamical features of escape panic Specification of the social force pedestrian model by evolutionary adjustment to video tracking data A predictive collision avoidance model for pedestrian simulation The authors acknowledge the information and data provided by the Argentinean Supermarket chain "La Anónima". This work was founded by project PID2015-003 (ANPCyT) Argentina.