key: cord-0694175-gtdnq2y9 authors: Derjany, Pierrot; Namilae, Sirish; Srinivasan, Ashok title: Parameter Space Exploration in Pedestrian Queue Design to Mitigate Infectious Disease Spread date: 2021-08-03 journal: J Indian Inst Sci DOI: 10.1007/s41745-021-00254-0 sha: 50e8169659917da7f1bd2d905366202d1ebfee57 doc_id: 694175 cord_uid: gtdnq2y9 Reducing the interactions between pedestrians in crowded environments can potentially curb the spread of infectious diseases including COVID-19. The mixing of susceptible and infectious individuals in many high-density man-made environments such as waiting queues involves pedestrian movement, which is generally not taken into account in modeling studies of disease dynamics. In this paper, a social force-based pedestrian-dynamics approach is used to evaluate the contacts among proximate pedestrians which are then integrated with a stochastic epidemiological model to estimate the infectious disease spread in a localized outbreak. Practical application of such multiscale models to real-life scenarios can be limited by the uncertainty in human behavior, lack of data during early stage epidemics, and inherent stochasticity in the problem. We parametrize the sources of uncertainty and explore the associated parameter space using a novel high-efficiency parameter sweep algorithm. We show the effectiveness of a low-discrepancy sequence (LDS) parameter sweep in reducing the number of simulations required for effective parameter space exploration in this multiscale problem. The algorithms are applied to a model problem of infectious disease spread in a pedestrian queue similar to that at an airport security check point. We find that utilizing the low-discrepancy sequence-based parameter sweep, even for one component of the multiscale model, reduces the computational requirement by an order of magnitude. J. Indian Inst. Sci. | VOL xxx:x | xxx-xxx 2021 | journal.iisc.ernet.in suggest that colocation and movement of people in a crowded location even over relatively short periods lead to the disease spread. Pedestrian movement modeling can provide possible trajectories of pedestrians that can be used to model contact heterogeneity in crowded locations mentioned above. Among the various pedestrian movement models, e.g., cellular automata 13 , fluid flow 14 , and queuing 15 , social force models 16, 17 are most suited for individual trajectory evolution, required for contact estimation. Social force models first proposed by Helbing and Molnar 16 extend the concepts of force balance from molecular dynamics to pedestrian movement. Here, the forces are a measure of the internal motivations of individual pedestrians to move toward their destination in the presence of obstructions like other pedestrians and objects. Social force models have been applied to crowd simulations situations in panic 18 , traffic dynamics 19 , evacuation 20 , and animal herding 21 . Algorithmic developments have included generation of force fields using visual analysis of crowd flows 22 , explicit collision prediction 23 , and collision avoidance 24 . Namilae et al. 3, 25, 26 have combined pedestrian dynamics and stochastic epidemic models to study the spread of infectious diseases in settings like airplanes and pedestrian queues. Airborne diseases including COVID-19 are spread when susceptible individuals inhale pathogens suspended in the air. These organic particles are secreted by the nasal tracts and throat of an infected individual and are dispersed to the environment through expiratory events including breathing, talking, sneezing, or coughing. As these viral particles are able to remain suspended in the air and navigate distances of several feet, there is a high risk of disease outbreak in a local area with high density of people. Several factors determine the extent of transmission that will take place between the infective and the susceptible population; these include (1) the infectivity of the contagion, (2) survival lifetime of the pathogen, (3) the environmental conditions like the temperature and airflow that determine the contagion spread, (4) the extent of mixing between susceptible and infectious individuals resulting in new contacts, and (5) the duration of the contacts. The parametric range associated with each of these factors and the diversity in the initial conditions and the locations of potential disease spread exacerbate the prediction problem. The uncertainty associated with the large parameter space can be addressed using parameter sweep algorithms and parallel computing. Parameter sweep is an important computational tool that employs parallel computing resources to execute multiple computations with different combinations of values of the same parameters. Large-scale parameter sweep runs have found extensive applications in many scientific and engineering fields 27 . For example, parameter sweeps have been used to model electromagnetic cascade showers 28 , high-energy physics applications 29 , etc. Chunduri et al. 30 used a Low Discrepancy Sequence-based scrambled Halton sequence to effectively reduce the parameter space for a pedestrian-dynamics-based contact estimation problem. Here, we extend this approach to address the parameter space in the multiscale pedestrian-dynamics infection spread problem. The objective of this research is to evaluate the effect of pedestrian movement in a winding queue configuration on the spread of infectious diseases. We utilize a social force-based pedestrian-dynamics model and integrate it with a stochastic infection dynamics model to analyze the spread of infectious disease in the pedestrian queue. There are several parameters with inherent uncertainties in both pedestrian dynamics and infection spread models. To comprehensively understand this problem, the infectious disease spread needs to be investigated for various combinations of the parameters. Here, we show that a parameter sweep algorithm based on low-discrepancy sequence can be extremely effective in reducing the parameter space for this multiscale problem. This computational model addresses the transmission and dispersion of fatal infectious pathogens in locations, where large groups of people gather at high densities, through a multiscale model that combines pedestrian dynamics with stochastic infection spread models. The pedestrian-dynamics model uses a molecular dynamics (MD)-based numerical approach called social force method. The MD algorithm captures the step-by-step evolution of the system of particles tracing their trajectories and can be used to estimate the contact frequency between passengers during air-travel. We incorporate this contact analysis into a discrete-time stochastic Susceptible-Infected (SI) model with infection probability and contact radius as primary inputs. This generic model is applicable to several directly transmitted diseases including COVID-19 by varying the input parameters, and can be used to assess the influence of pedestrian movement on Pedestrian dynamics models: computational models commonly used in civil engineering to model the movement of pedestrians in build environments. Examples include agent based models and social force models. An infection dynamics model with individuals changing from susceptible to infected state based on the contact with infected individuals Molecular dynamics: A computational method in chemistry and materials science wherein movement of atoms is modeled using Newton's laws and an interatomic potential. disease spread. This multiscale framework is used to analyze the infectious disease spread in a winding queue configuration under various transmission scenarios using a parameter sweep. In the context of modeling the pedestrian mixing patterns to analyze infection spread in crowded environments, numerical simulations are performed to mimic the movement behavior of pedestrians. Here, the pedestrians are considered to be particles whose motion is determined by a balance of repulsive and propelling forces. The resulting trajectories are used to estimate the number of contacts. The repulsive ( f ped i ) and attractive ( f int i ) forces are summated as in as in Namilae et al. 3, 25 . The tendency to avoid collision and impenetrability with other individuals in high-density crowds and immobile obstacles in the pedestrian's path are represented by the repulsive terms where ∈ and σ are repulsive force field parameters and r il is the distance between the ith and the lth nearest front pedestrian in the queue. On the other hand, pedestrian self-propulsion to their target destination (e.g., an exit) either individually or collectively results in another force. This intention force is obtained by the average rate of change of momentum Pedestrians move at the speed of the nearest person ahead in a queue. This is accounted for by the location-dependent desired velocity, in the direction of motion ⌢ e 1 , in the self-propulsion term as The proposed social force model allows evolution of the pedestrian in time domain. The number of contacts is then obtained from the generated trajectories. The contact data are utilized in an epidemiological model to map the infectious disease propagation in the population. The contact data are obtained from pedestrian trajectories by comparing the distance between pedestrians to the transmission threshold (x) dependent on the types of pathogen and mechanisms for its spread The contact data are then integrated with a stochastic epidemic individual-based model to estimate the distribution of the newly infected individuals. The probability that an infectious individual "i" in the crowd comes into contact with other individuals is m i /N, where m i is the number of contacts. Using Bayes' theorem of conditional probability, P(contact and infection) = P (infection|contact). P (contact) = P inf · m i N . Here, P inf is the infection probability. To account for the inherent stochasticity of the susceptible individuals, the number of newly infected by this infective "i" is estimated by a binomial distribution I i (t)∼ B(S i , p i ) with parameters S i , the number of susceptibles, and p i = P inf . m i N . We assume that there is one infected individual among the pedestrians, but the location of the infected individual is not known apriori. We account for all the possible combinations "C" of the infective in the pedestrian movement simulation by varying the position of infected individual. The total number of newly infected is estimated by combining all the resulting binomial distributions of new infections and averaging it based on the weight of repetition w i ( i ) of the mean i in these runs where S i and P inf represent the number of susceptible pedestrians and the transmittance probability, respectively. The transmittance probability depends on the day post-onset of symptoms denoted by c, of the d total incubation period. The infection probability, radius of infection, and pedestrian-dynamics model parameters are all considered to be parametric variables. By varying these parameters over the space of possible numerical values, one can analyze how mitigation measures related to pedestrian movement would impact the disease spread in a wide variety of conditions. However, given the extremely large parameter space, efficient algorithms are desired to cover the parameter space effectively. Parameter sweep algorithms are used to efficiently cover the parameter space and account for combination of the parameters that significantly affect the model outcome. A conventional parameter sweep approach is lattice-based method wherein the parameters are uniformly partitioned. For example, consider a two-dimensional parameter space; in the lattice parameter sweep, the points (or parameters values) in the horizontal and vertical directions are equally spaced, respectively. This scheme is inefficient in terms of domain coverage and for checking convergence 30 . For example, consider a situation where the model has d parameters resulting in a d-dimensional parameter space. If this is partitioned uniformly in these dimensions with R points (representing simulations) for each parameter, the total number of points obtained is N = R d . To check for convergence, if we refine the space domain by doubling the number of points. Then, the number of points This ratio between the two consecutive lattice sizes ( N = 2 d ) is very large and is imprecise for checking convergence. Also, running a simulation of N' grid points is computationally exhaustive and time-consuming. Instead, alternate non-uniform A conventional parameter algorithm in which the parameters are uniformly partitioned. parameter sweep techniques offer better convergence and faster outcomes. Non-uniform domain partition methods based on the pseudo-random and quasi-random sequences are promising algorithms for nodes sequence generation enabling faster convergence at lower number of nodes compared to the lattice method. These methods are commonly used in Monte Carlo and quasi-Monte Carlo algorithms to solve for numerical integration problems 31 . In a Monte Carlo simulation, the accuracy of the results depends on the generation of the pseudorandom sequence over a [0, 1] interval. Using a random sequence was found to be asymptotically slower than LDS, because sparse and clustered regions are observed in the space domain 30 . Quasi-random sequences are deterministic alternatives to pseudo-random sequences. They are infinite sequence of points, used in Quasi-Monte Carlo (QMC) simulations 32 Here, we use Scrambled Halton LDS for a parameter sweep as in Chunduri et al. 30 . However, we extend the application to the multiscale model by applying the algorithm interchangeably for the pedestrian and infection models. The results are then compared to lattice sweep to show the efficiency of LDS in terms of faster convergence and execution time. We study the problem of infection spread in a pedestrian winding queue using this approach. Low discrepancy sequences: sequence of numbers that are well distributed with low irregularity for which convergence to uniform distribution on [0, 1] occurs rapidly. Pedestrian winding queues are an unavoidable component of crowd management in places like airport security checks, and religious and entertainment venues. In Derjany et al. 26 , different queue configurations are evaluated in terms of contact generation and infection propagation among neighboring pedestrians. One pedestrian queue configuration from this study, as shown in Fig. 1 , is used in the current study. The modeling work-flow shown in Fig. 2 consists of applying the parameter sweep to the pedestrian parameters first. The resulting trajectories are input to the infection model (Eq. 5), incorporating a parameter sweep of infection variables. Table 1 lists the ranges of the pedestrian and infection parameters considered in the parameter sweep study. Both lattice and LDS parameter sweeps are used with these ranges to examine their efficiency in reducing the number of simulations needed to adequately cover the design space. For both Lattice and LDS sweeping algorithms, a coarse grid is first considered, and then refined until convergence is attained. At each grid size, a histogram with the targeted variable (the number of newly infected pedestrians) versus the frequency of occurrence is plotted. Four descriptive moments of the probability distribution, mean, standard deviation, skewness, and kurtosis are analyzed to determine convergence. Once the relative difference of the output between two grid sizes is lower than a predetermined tolerance, as shown in Eq. (6), further refinement of the parameter space is not required where V is a statistical moment and ε is a tolerance value. The selection of the tolerance order depends on the statistical moment. For instance, for the relative mean, ε is of the order of 10 -3 compared to 10 -1 for the root of standard deviation, skewness, and kurtosis. The abrupt drop of the relative kurtosis from a value greater than unity to a value of order 10 -1 indicates that the histogram distribution is invariant between the runs. When these conditions are met, convergence is attained. The workflow in Fig. 2 is applied with parametric variations in Table 1 as follows. First, a 5D lattice parameter sweep is performed by varying the three pedestrian-dynamics parameters, and two infection model parameters over an evenly spaced lattice grid. This baseline is compared with two other situations in which 2D lattice grid for infection model is combined with 3D LDS for pedestrian-dynamics parameters, and 3D Lattice grid for pedestrian dynamics is combined with 2D LDS parameter sweep for the infection model. The convergence and model implications in each case are discussed. The lattice-based parameter sweep is applied to the parameters of the two models separately. The trajectories are obtained from the pedestrian model by varying pedestrian maximum speed (v A + v B ) and allowable proximate pedestrianpedestrian distances ( δ 1 and δ 2 ). The resulting contact data ( m i ) for each simulation are used in the infection model by varying the contact radii (R) and transmission probability ( P inf ). Changing the increment sizes for these five parameters on a lattice grid results in six parameter sweeps with 6480, 11,664, 144,900, 2,125,000, 4,165,392, and 8,245,776 numbers of simulations. Each of these simulations generates an average number of infections. For example, consider a case where the infective has an infectious disease (e.g., which is at a stage where the transmission probability is 0.1 and the infection radius is 72 in. Consider that this infective passes through the pedestrian queue shown in Fig. 1 . If the pedestrians in the queue have an average unobstructed speed of 4 ft/s and maintain a distance of 3 ft between each other, this results in an average of 8 new infections. The average here implies that the position of the infective in the queue is not known apriori and this is varied and averaged to obtain the number of new infections. This result is one specific output for these specific input parameter values. Figure 3 shows this output as a function of frequency for the parameters varied on different lattice grids. There is uncertainty with respect to both pedestrian parameters like speed and distance between people, and also infection parameters like transmission probability and infection spread radius. By varying all of these parameters, we can get a comprehensive idea of how disease would spread. If these parameters are varied on a coarse grid like in Fig. 3a , some of the variations are not captured. As the parameter lattice is refined, more of these variations are captured. A similar parameter sweep with an intervention would show how for a 6480, b 11,664, c 144,900, d 2,125,000, e 4,165 ,392, and f 8,245,776 grid points using 5D Lattice method. the infection spread would change across the entire parameter space. Note that convergence can be visually ascertained when the shape of the histogram remains proportionally the same while increasing the number of simulations. In this case, convergence starts from Grid 4 in Fig. 3d . The convergence is also validated theoretically using statistical variables mentioned earlier. Sweep Here, LDS-based parameter sweep is applied to the pedestrian-dynamics component of the multiscale model, i.e., to the three pedestrian-dynamics parameters in Table 1 , while the two infection model parameters are varied on a lattice grid. Six parameter grids with successively finer spacing are considered. For Grids 1 and 2, the infection lattice parameter spacing corresponding to Grid 2 of the 5D lattice sweep shown in Fig. 3b is used. For Grids 3-6, a finer lattice spacing corresponding to Grid 4 of the 5D lattice sweep shown in Fig. 3d is used. The LDS algorithm is used to generate sequences for the 3D pedestrian-dynamics parameter space. This combination of parameters leads to six sequences with 4050, 11,250, 157,500, 525,000, and 787,500 simulations, respectively. Figure 4 shows the histograms of the combined lattice and LDS approach. With a low number of combinations for the speed and distance parameters and a coarse lattice grid for the infection parameters, the histograms corresponding to Grids 1 and 2 do not capture the distribution of the newly infected at high numbers. Grids 3-6 can capture the distribution of infections much more effectively, as shown in Fig. 4 . It can be noted that the convergence is reached by 157,500 simulations in this case compared to the 2,125,000 simulations needed with 5D lattice parameter sweep. A similar analysis is conducted with 2D LDS parameter sweep for the infection parameters, combined with a 3D lattice sweep for pedestriandynamics parameters. The variation of parameters again results in six simulation grid sizes with 108,000, 144,000, 288,000, 809,600, 1,012,000 and 1,214,400 simulation sequences. We find that the visual and numerical convergence in this case happens for Grid 4 with 809,600 simulations (see Fig. 5 ). Figure 6 shows the convergence metrics for the three parameter sweeps conducted in this work. The convergence is analyzed by comparing the four statistical measures mean, standard deviation, kurtosis, and skewness. In the case of the 5D lattice parameter sweep, convergence is attained at Grid 4 with 2,125,000 simulations. The relative difference of the mean, standard deviation, skewness, and kurtosis values are within tolerance when a finer lattice grid with more simulations is used. The values of the relative mean and standard deviation vary minimally as the number of simulations is increased, whereas the skewness and kurtosis increase with parameter refinement, which indicates the biasing of the histograms toward a high-frequency value of three newly infected pedestrians. The distribution of for a 4,050, b 11,250, c 52,500, d 157,500, e 525 ,000, and f 787,500 grid points using 3D pedestrian LDS combined with 2D lattice method. the histogram in bell shape (Fig. 4) around the peak accounts for the stochasticity of the model. The histogram's peak is attained at three newly infected members, which indicates that there is a highest probability of one infective generating three new infections for the pedestrian queue studied here. However, in preventive planning, one should account for the worst-case scenario. The plot extends to a worst-case scenario of 24 possible infection cases with a mean of about 7 new infections. In the case of 2D LDS-3D Lattice parameter sweep, the same mean of 6.98 with a close standard deviation is obtained at Grid 4 with only 809,600 simulations compared to 2,125,000 required for 5D Lattice sweep. The convergence is reached with the same increments used previously for the pedestrian model parameters and only 200 low-discrepancy sequences to cover the two-dimensional infection parameters space. The computational effort is less than 50% compared to that required for a 5D lattice. The plot in Fig. 7 showing the relative difference of the four statistical moments behaves in a similar manner as that of 5D lattice after convergence is reached. When LDS parameter sweep is applied for the three parameters in the pedestrian movement model, convergence is attained at 157,500 simulations with a similar mean of 7.04. Again, at Grid 4, the relative differences of the statistical moments converge toward a zero value, as shown in Fig. 6 . The parameters increments at convergence for the three parameter sweeps are shown in Table 2 . Low-discrepancy sequences have found various applications in various fields. For instance, multidimensional integrals are often evaluated using quasi-stochastic Monte Carlo method (Cools, 2002) . Parameter sweep for high-dimensional space is a closely related problem. A disadvantage with pseudo-random finite sequences is that they are not equidistributed over the domain of integration which can yield asymptotically worse convergence rate. The usage of increased equidistributed random sequences improves accuracy, but can be computationally expensive 36 . The lattice-based space repartition is a uniform distribution method that partitions the domain uniformly. This method has a much higher computational cost compared to the pseudo-random sequences. Low-discrepancy sequences using quasi-random numbers were originally introduced to improve convergence in comparison to Monte Carlo integration, but they can also address the high computation time problem for large parameter sweeps on parallel clusters. Lowdiscrepancy (quasi-random) sequences have an advantage of being more equidistributed than pseudo-random numbers and are more efficient both with respect to space coverage and convergence. Chunduri et al. 30 used the low-discrepancy sequence-based parameter sweep for analyzing pedestrian movement in an airplane boarding and showed that this approach significantly reduces the number of simulations needed to adequately cover the parameter space. Many engineering and public health problems are multidisciplinary and multiscale in nature. For example, consider the infectious disease spread in a pedestrian queue considered in this study. The contact analysis is based on pedestrian movement and mixing at one scale, while the infectious disease propagation is at another scale. The results of this study show that there is a significant reduction in computational requirements compared to lattice-based parameter sweep, when the LDS method is used in one of the sub-models. There is an order of magnitude improvement in the number of simulations needed to adequately cover the parameter space, as shown in Fig. 7 . Another significant advantage of LDS approach is that if further refinement of the parameter space is needed, the scrambled Halton sequence adds to the existing sequence, enabling reuse of the existing simulations. This facilitates the restart of parameter sweep problems. In this paper, we model the infectious disease spread in a pedestrian winding queue and analyze the parameter space using novel parameter sweep. A multiscale model is formulated combining social force-based pedestrian-dynamics model with an individual stochastic epidemiological model. The model is applicable to many directly transmitted diseases including COVID-19 based on the input parameters. A five-dimensional space consisting of three pedestrian-dynamics parameters (free speed, cut-off distances) and two epidemic model parameters (transmission probability and infection radius) is considered for the parameter sweeps. A uniform lattice-based parameter sweep is first used to analyze the five-dimensional parameter space. In each dimension, the increment is taken to be constant, generating a uniformly distributed vector of values within the range of definitions of each parameter. A coarse uniform partition of the parameters vectors may leave out some critical parameter combinations, which can lead to deficiencies in the results. This is undesirable for assessing preventive strategies that inhibit the disease outbreak. A fine uniform lattice is computationally expensive both for covering the parameter space and convergence checks. We find that 2,125,000 simulations are needed to obtain convergence using the lattice approach. An effective alternative to lattice parameter sweep is a Scrambled Halton Low Discrepancy Sequence approach. In the multidisciplinary model used here, we find that use of LDS in even one of the interconnected models is effective in reducing the required number of simulations. When LDS is used to generate sequence for threedimensional parameter space for the pedestrian model and the conventional lattice is used for the infection model, the convergence is achieved with 157 500 simulations, which is an order of magnitude improvement in computational efficiency. When LDS is used for the two-dimensional parameter space of the infection model, the parameter space can be covered using 809,600 simulations. A mean of seven newly infected individuals is obtained for the distribution of new infections over the entire parameter space. The number of infections may extend up to 24 cases with the highest probability obtained for 3 cases. Given the stochasticity and uncertainty in infection spread and human behavior; interventions to reduce infections need to be effective across many scenarios. The modeling and parameter sweep approach developed in this study can help identify such interventions. Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. Modeling infectious disease dynamics in the complex landscape of global health Spatiotemporal spread of the 2014 outbreak of Ebola virus disease in Liberia and the effectiveness of non-pharmaceutical interventions: a computational modelling analysis Self-propelled pedestrian dynamics model: application to passenger movement and infection propagation in airplanes Measuring contact patterns with wearable sensors: methods, data characteristics and applications to datadriven simulations of infectious diseases Models of epidemics: when contact repetition and clustering should be included The relative importance of frequency of contacts and duration of exposure for the spread of directly transmitted infections Indirect virus transmission in cluster of COVID-19 cases Coronavirus: 5 More Cases at Osaka Concert Venues Coronavirus toll mounts at Seattle-area nursing home Transmission potential of the novel coronavirus (COVID-19) onboard the diamond Princess Cruises Ship Why a South Korean Church Was the Perfect Petri Dish for Coronavirus Clinical findings in a group of patients infected with the 2019 novel coronavirus (SARS-Cov-2) outside of Wuhan, China: retrospective case series Simulation of pedestrian dynamics using a twodimensional cellular automaton The statistics of crowd fluids A study of simulation model for pedestrian movement with evacuation and queuing Social force model for pedestrian dynamics Simulating dynamical features of escape panic Phase diagram of traffic states in the presence of inhomogeneities Evacuation behaviors at exit in CA model with force essentials: a comparison with social force model Simulation of pedestrian crowds in normal and evacuation situations Friction based social force model for social foraging of sheep flock Abnormal crowd behavior detection using social force model Social force model with explicit collision prediction Getting out of the way: collision-avoiding pedestrian models compared to the realworld. Pedestrian and evacuation dynamics Multiscale model for pedestrian and infection dynamics during air travel Multiscale model for the optimal design of pedestrian queues to mitigate infectious disease spread Management of a parameter sweep for scientific applications on cluster environments SLAC-265). Stanford Linear Accelerator Center Harnessing the capacity of computational grids for high energy physics Parallel low discrepancy parameter sweep for public health policy Quasi-Monte Carlo methods for numerical integration: comparison of different low discrepancy sequences Quasi-random sequences and their discrepancies Monte Carlo and quasi-Monte Carlo methods in financial derivative pricing Algorithm 247: radical-inverse quasirandom point sequence Advances in multidimensional integration Quasi-versus pseudorandom generators: discrepancy, complexity and integration-error based comparison This research was supported in part by DOT Center for advanced transportation mobility, and NSF Grant # 2027518 and 1931483. The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. Derjany completed his PhD in Aerospace Engineering from Embry-Riddle Aeronautical University recently. His research interests are in the areas of particle dynamics, computational modeling, and aerospace structures.