Abstract
Recently proposed gradient estimators enable gradient descent over stochastic programs with discrete jumps in the response surface, which are not covered by automatic differentiation (AD) alone. Although these estimators’ capability to guide a swift local search has been shown for certain problems, their applicability to models relevant to real-world applications remains largely unexplored. As the gradients governing the choice in candidate solutions are calculated from sampled simulation trajectories, the optimization procedure bears similarities to metaheuristics such as particle swarm optimization, which puts the focus on the different methods’ calibration progress per function evaluation. Here, we consider the calibration of force-based crowd evacuation models based on the popular Social Force model augmented by discrete decision making. After studying the ability of an AD-based estimator for branching programs to capture the simulation’s rugged response surface, calibration problems are tackled using gradient descent and two metaheuristics. As our main insights, we find 1) that the estimation’s fidelity benefits from disregarding large jumps inherent to the Social Force model, and 2) that the common problem of inferring a parameter’s posterior distribution given some data obviates the need for AD across the Social Force calculations, allowing gradient descent to excel.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Andelfinger, P.: Towards differentiable agent-based simulation. ACM Trans. Model. Comput. Simul. 32(4), 1–26 (2023)
Arya, G., Schauer, M., Schäfer, F., Rackauckas, C.: Automatic differentiation of programs with discrete randomness. In: Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., Oh, A. (eds.) Advances in Neural Information Processing Systems, vol. 35, pp. 10435–10447. Curran Associates, Inc. (2022)
Bengio, Y., Léonard, N., Courville, A.: Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXiv:1308.3432 (2013)
Bode, N.: Parameter calibration in crowd simulation models using approximate bayesian computation. arXiv preprint arXiv:2001.10330 (2020)
Chaudhuri, S., Solar-Lezama, A.: Smooth interpretation. ACM SIGPLAN Not. 45(6), 279–291 (2010)
Chen, X., Zhan, F.B.: Agent-based modelling and simulation of urban evacuation: relative effectiveness of simultaneous and staged evacuation strategies. J. Oper. Res. Soc. 59(1), 25–33 (2008)
Chopra, A., et al.: DeepABM: scalable and efficient agent-based simulations via geometric learning frameworks - a case study for COVID-19 spread and interventions. In: Winter Simulation Conference, pp. 1–12. IEEE (2021)
Christodoulou, S., Naumann, U.: Differentiable programming: efficient smoothing of control-flow-induced discontinuities. arXiv preprint arXiv:2305.06692 (2023)
Cranmer, K., Brehmer, J., Louppe, G.: The frontier of simulation-based inference. Proc. Natl. Acad. Sci. 117(48), 30055–30062 (2020)
Fu, M.C.: Chapter 19: gradient estimation. In: Henderson, S.G., Nelson, B.L. (eds.) Simulation, Handbooks in Operations Research and Management Science, vol. 13, pp. 575–616. Elsevier (2006)
Gödel, M., Bode, N., Köster, G., Bungartz, H.J.: Bayesian inference methods to calibrate crowd dynamics models for safety applications. Saf. Sci. 147, 105586 (2022)
Gong, W.B., Ho, Y.C.: Smoothed (conditional) perturbation analysis of discrete event dynamical systems. IEEE Trans. Autom. Control 32(10), 858–866 (1987)
González-Méndez, M., Olaya, C., Fasolino, I., Grimaldi, M., Obregón, N.: Agent-based modeling for urban development planning based on human needs. Conceptual basis and model formulation. Land Use Policy 101, 105110 (2021)
Griewank, A., Walther, A.: Evaluating derivatives: principles and techniques of algorithmic differentiation. SIAM (2008)
Hackl, J., Dubernet, T.: Epidemic spreading in urban areas using agent-based transportation models. Future Internet 11(4), 92 (2019)
Helbing, D., Molnar, P.: Social force model for pedestrian dynamics. Phys. Rev. E 51(5), 4282 (1995)
Ho, Y.C., Cassandras, C.: A new approach to the analysis of discrete event dynamic systems. Automatica 19(2), 149–167 (1983)
Kasereka, S., Kasoro, N., Kyamakya, K., Goufo, E.F.D., Chokki, A.P., Yengo, M.V.: Agent-based modelling and simulation for evacuation of people from a building in case of fire. Procedia Comput. Sci. 130, 10–17 (2018)
Kreikemeyer, J.N., Andelfinger, P.: Smoothing methods for automatic differentiation across conditional branches. IEEE Access 11, 143190–143211 (2023)
Kreiss, S.: Deep social force. arXiv preprint arXiv:2109.12081 (2021)
Margossian, C.C.: A review of automatic differentiation and its efficient implementation. Wiley Interdisc. Rev. Data Min. Knowl. Discov. 9(4), e1305 (2019)
Miranda, L.J.: PySwarms: a research toolkit for particle swarm optimization in Python. J. Open Source Softw. 3(21), 433 (2018)
Motieyan, H., Mesgari, M.S.: An agent-based modeling approach for sustainable urban planning from land use and public transit perspectives. Cities 81, 91–100 (2018)
Nesterov, Y., Spokoiny, V.: Random gradient-free minimization of convex functions. Found. Comput. Math. 17, 527–566 (2017)
Pietzsch, B., et al.: Metamodels for evaluating, calibrating and applying agent-based models: a review. J. Acad. Soc. Sci. Stud. 23(2) (2020)
Polyak, B.: Introduction to Optimization. Optimization Software, New York (1987)
Scheinberg, K.: Finite difference gradient approximation: to randomize or not? INFORMS J. Comput. 34(5), 2384–2388 (2022)
Seyer, R.: Differentiable Monte Carlo Samplers with piecewise deterministic markov processes. Master’s thesis, Chalmers University of Technology (2023)
Son, S., Qiao, Y.L., Sewall, J., Lin, M.C.: Differentiable hybrid traffic simulation. ACM Trans. Graph. (TOG) 41(6), 1–10 (2022)
Voloshin, D., Rybokonenko, D., Karbovskii, V.: Optimization-based calibration for micro-level agent-based simulation of pedestrian behavior in public spaces. Procedia Comput. Sci. 66, 372–381 (2015)
Wang, X., Mohcine, C., Chen, J., Li, R., Ma, J.: Modeling boundedly rational route choice in crowd evacuation processes. Saf. Sci. 147, 105590 (2022)
Williams, R.J.: Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach. Learn. 8, 229–256 (1992)
Wolinski, D., Guy, S.J., Olivier, A.H., Lin, M., Manocha, D., Pettré, J.: Parameter estimation and comparative evaluation of crowd simulations. Comput. Graph. Forum 33(2), 303–312 (2014)
Yin, W., Murray-Tuite, P., Ukkusuri, S.V., Gladwin, H.: An agent-based modeling system for travel demand simulation for hurricane evacuation. Transp. Res. Part C: Emerg. Technol. 42, 44–59 (2014)
Acknowledgments
Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation), grant no. 497901036 (PA) and 320435134 (JK).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Ethics declarations
Disclosure of Interests
The authors have no competing interests to declare that are relevant to the content of this article.
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Andelfinger, P., Kreikemeyer, J.N. (2024). Automatic Gradient Estimation for Calibrating Crowd Models with Discrete Decision Making. In: Franco, L., de Mulatier, C., Paszynski, M., Krzhizhanovskaya, V.V., Dongarra, J.J., Sloot, P.M.A. (eds) Computational Science – ICCS 2024. ICCS 2024. Lecture Notes in Computer Science, vol 14836. Springer, Cham. https://doi.org/10.1007/978-3-031-63775-9_16
Download citation
DOI: https://doi.org/10.1007/978-3-031-63775-9_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-63774-2
Online ISBN: 978-3-031-63775-9
eBook Packages: Computer ScienceComputer Science (R0)