“Differentiable Hybrid Traffic Simulation” by Son, Qiao, Sewall and Lin
Conference:
Type(s):
Title:
- Differentiable Hybrid Traffic Simulation
Session/Category Title: Solids and Fluids
Presenter(s)/Author(s):
Abstract:
We introduce a novel differentiable hybrid traffic simulator, which simulates traffic using a hybrid model of both macroscopic and microscopic models and can be directly integrated into a neural network for traffic control and flow optimization. This is the first differentiable traffic simulator for macroscopic and hybrid models that can compute gradients for traffic states across time steps and inhomogeneous lanes. To compute the gradient flow between two types of traffic models in a hybrid framework, we present a novel intermediate conversion component that bridges the lanes in a differentiable manner as well. We also show that we can use analytical gradients to accelerate the overall process and enhance scalability. Thanks to these gradients, our simulator can provide more efficient and scalable solutions for complex learning and control problems posed in traffic engineering than other existing algorithms. Refer to https://sites.google.com/umd.edu/diff-hybrid-traffic-sim for our project.
References:
1. Shivam Akhauri, Laura Y Zheng, and Ming C Lin. 2020. Enhanced transfer learning for autonomous driving with systematic accident simulation. In 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 5986–5993.
2. Philipp Andelfinger. 2021. Differentiable Agent-Based Simulation for Gradient-Guided Simulation-Based Optimization. In Proceedings of the 2021 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation. 27–38.
3. AATM Aw and Michel Rascle. 2000. Resurrection of” second order” models of traffic flow. SIAM journal on applied mathematics 60, 3 (2000), 916–938.
4. Masako Bando, Katsuya Hasebe, Akihiro Nakayama, Akihiro Shibata, and Yuki Sugiyama. 1995. Dynamical model of traffic congestion and numerical simulation. Physical review E 51, 2 (1995), 1035.
5. Emmanuel Bourrel and Jean-Baptiste Lesort. 2003. Mixing microscopic and macroscopic representations of traffic flow: Hybrid model based on Lighthill-Whitham-Richards theory. Transportation Research Record 1852, 1 (2003), 193–200.
6. Michael S Branicky, Vivek S Borkar, and Sanjoy K Mitter. 1998. A unified framework for hybrid control: Model and optimal control theory. IEEE transactions on automatic control 43, 1 (1998), 31–45.
7. Dan Cascaval, Mira Shalah, Phillip Quinn, Rastislav Bodik, Maneesh Agrawala, and Adriana Schulz. 2021. Differentiable 3D CAD Programs for Bidirectional Editing. arXiv preprint arXiv:2110.01182 (2021).
8. Michael J Cassidy and John R Windover. 1995. vÍethodology for Assessing Dynamics of Freeway Traffic Flow. (1995).
9. Adèle Colas, Wouter van Toll, Katja Zibrek, Ludovic Hoyet, Anne-Hélène Olivier, and Julien Pettré. 2022. Interaction Fields: Intuitive Sketch-based Steering Behaviors for Crowd Simulation. In Computer Graphics Forum.
10. Carlos F Daganzo. 1995. Requiem for second-order fluid approximations of traffic flow. Transportation Research Part B: Methodological 29, 4 (1995), 277–286.
11. Filipe de Avila Belbute-Peres, Kevin Smith, Kelsey Allen, Josh Tenenbaum, and J Zico Kolter. 2018. End-to-end differentiable physics for learning and control. Advances in neural information processing systems 31 (2018), 7178–7189.
12. Alexey Dosovitskiy, German Ros, Felipe Codevilla, Antonio Lopez, and Vladlen Koltun. 2017. CARLA: An Open Urban Driving Simulator. In Proceedings of the 1st Annual Conference on Robot Learning. 1–16.
13. Tao Du, Kui Wu, Pingchuan Ma, Sebastien Wah, Andrew Spielberg, Daniela Rus, and Wojciech Matusik. 2021. DiffPD: Differentiable Projective Dynamics with Contact. arXiv:2101.05917 (2021).
14. Tao Du, Kui Wu, Andrew Spielberg, Wojciech Matusik, Bo Zhu, and Eftychios Sifakis. 2020. Functional Optimization of Fluidic Devices with Differentiable Stokes Flow. ACM Trans. Graph. (2020).
15. Myungeun Eom and Byung-In Kim. 2020. The traffic signal control problem for intersections: a review. European transport research review 12, 1 (2020), 1–20.
16. Rafael Fierro, Aveek K Das, Vijay Kumar, and James P Ostrowski. 2001. Hybrid control of formations of robots. In Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No. 01CH37164), Vol. 1. IEEE, 157–162.
17. Denos C Gazis, Robert Herman, and Renfrey B Potts. 1959. Car-following theory of steady-state traffic flow. Operations research 7, 4 (1959), 499–505.
18. Denos C Gazis, Robert Herman, and Richard W Rothery. 1961. Nonlinear follow-the-leader models of traffic flow. Operations research 9, 4 (1961), 545–567.
19. Moritz Geilinger, David Hahn, Jonas Zehnder, Moritz Bächer, Bernhard Thomaszewski, and Stelian Coros. 2020. ADD: Analytically differentiable dynamics for multi-body systems with frictional contact. ACM Transactions on Graphics (TOG) 39, 6 (2020).
20. Peter G Gipps. 1981. A behavioural car-following model for computer simulation. Transportation Research Part B: Methodological 15, 2 (1981), 105–111.
21. Abhinav Golas, Rahul Narain, Jason Sewall, Pavel Krajcevski, Pradeep Dubey, and Ming Lin. 2012. Large-scale fluid simulation using velocity-vorticity domain decomposition. ACM Transactions on Graphics (TOG) 31, 6 (2012), 1–9.
22. Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. 2018. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on machine learning. PMLR, 1861–1870.
23. Torsten Hädrich, Daniel T Banuti, Wojtek Pałubicki, Sören Pirk, and Dominik L Michels. 2021. Fire in paradise: mesoscale simulation of wildfires. ACM Transactions on Graphics (TOG) 40, 4 (2021), 1–15.
24. Nikolaus Hansen. 2006. The CMA evolution strategy: a comparing review. Towards a new evolutionary computation (2006), 75–102.
25. Feixiang He, Yuanhang Xiang, Xi Zhao, and He Wang. 2020. Informative scene decomposition for crowd analysis, comparison and simulation guidance. ACM Transactions on Graphics (TOG) 39, 4 (2020), 50–1.
26. Eric Heiden, Miles Macklin, Yashraj S Narang, Dieter Fox, Animesh Garg, and Fabio Ramos. 2021. DiSECt: A Differentiable Simulation Engine for Autonomous Robotic Cutting. In Proceedings of Robotics: Science and Systems. Virtual.
27. Philipp Holl, Vladlen Koltun, Kiwon Um, and Nils Thuerey. 2020. phiflow: A differentiable pde solving framework for deep learning via physical simulations. In NeurIPS Workshop.
28. Yuanming Hu, Luke Anderson, Tzu-Mao Li, Qi Sun, Nathan Carr, Jonathan Ragan-Kelley, and Frédo Durand. 2020. DiffTaichi: Differentiable Programming for Physical Simulation. In ICLR.
29. Yuko Ishiwaka, Xiao S Zeng, Michael Lee Eastman, Sho Kakazu, Sarah Gross, Ryosuke Mizutani, and Masaki Nakada. 2021. Foids: bio-inspired fish simulation for generating synthetic datasets. ACM Transactions on Graphics (TOG) 40, 6 (2021), 1–15.
30. Rui Jiang, Qingsong Wu, and Zuojin Zhu. 2001. Full velocity difference model for a car-following theory. Physical Review E 64, 1 (2001), 017101.
31. Arne Kesting, Martin Treiber, and Dirk Helbing. 2007. General lane-changing model MOBIL for car-following models. Transportation Research Record 1999, 1 (2007), 86–94.
32. Dieter Kraft et al. 1988. A software package for sequential quadratic programming. (1988).
33. Randall J LeVeque et al. 2002. Finite volume methods for hyperbolic problems. Vol. 31. Cambridge university press.
34. Tzu-Mao Li, Miika Aittala, Frédo Durand, and Jaakko Lehtinen. 2018. Differentiable Monte Carlo ray tracing through edge sampling. ACM Trans. Graph. 37, 6 (2018).
35. Yifei Li, Tao Du, Kui Wu, Jie Xu, and Wojciech Matusik. 2022. DiffCloth: Differentiable Cloth Simulation with Dry Frictional Contact. ACM Trans. Graph. (2022).
36. Edward Lieberman and Ajay K Rathi. 1997. Traffic simulation. Traffic flow theory (1997).
37. Michael James Lighthill and Gerald Beresford Whitham. 1955. On kinematic waves II. A theory of traffic flow on long crowded roads. Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences 229, 1178 (1955), 317–345.
38. Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. 2015. Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.02971 (2015).
39. Pablo Alvarez Lopez, Michael Behrisch, Laura Bieker-Walz, Jakob Erdmann, Yun-Pang Flötteröd, Robert Hilbrich, Leonhard Lücken, Johannes Rummel, Peter Wagner, and Evamarie Wießner. 2018. Microscopic traffic simulation using sumo. In 2018 21st International Conference on Intelligent Transportation Systems (ITSC). IEEE, 2575–2582.
40. Pingchuan Ma, Tao Du, John Z Zhang, Kui Wu, Andrew Spielberg, Robert K Katzschmann, and Wojciech Matusik. 2021. Diffaqua: A differentiable computational design pipeline for soft underwater swimmers with shape interpolation. ACM Transactionson Graphics (TOG) 40, 4 (2021), 1–14.
41. Laurent Magne, Sylvestre Rabut, and Jean-François Gabard. 2000. Towards an hybrid macro-micro traffic flow simulation model. In INFORMS spring 2000 meeting.
42. Salim Mammar, Saïd Mammar, and Jean-Patrick Lebacque. 2006. Highway traffic hybrid macro-micro simulation model. IFAC Proceedings Volumes 39, 12 (2006), 627–632.
43. Khaled M Mohamed and AA Mohamad. 2010. A review of the development of hybrid atomistic-continuum methods for dense fluids. Microfluidics and Nanofluidics 8, 3 (2010), 283–302.
44. Miguel Angel Zamora Mora, Momchil P Peychev, Sehoon Ha, Martin Vechev, and Stelian Coros. 2021. PODS: Policy Optimization via Differentiable Simulation. In International Conference on Machine Learning. PMLR, 7805–7817.
45. Rahul Narain, Abhinav Golas, Sean Curtis, and Ming C Lin. 2009. Aggregate dynamics for dense crowd simulation. In ACM SIGGRAPH Asia 2009 papers. 1–8.
46. Rahul Narain, Abhinav Golas, and Ming C Lin. 2010. Free-flowing granular materials with two-way solid coupling. In ACM SIGGRAPH Asia 2010 papers. 1–10.
47. John A Nelder and Roger Mead. 1965. A simplex method for function minimization. The computer journal 7, 4 (1965), 308–313.
48. Gordon Frank Newell. 1961. Nonlinear effects in the dynamics of car following. Operations research 9, 2 (1961), 209–229.
49. Merlin Nimier-David, Delio Vicini, Tizian Zeltner, and Wenzel Jakob. 2019. Mitsuba 2: A retargetable forward and inverse renderer. ACM Transactions on Graphics (TOG) 38, 6 (2019).
50. Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems 32 (2019), 8026–8037.
51. Harold J Payne. 1971. Model of freeway traffic and control. Mathematical Model of Public System (1971), 51–61.
52. Yi-Ling Qiao, Junbang Liang, Vladlen Koltun, and Ming C. Lin. 2020. Scalable Differentiable Physics for Learning and Control. In ICML.
53. Yi-Ling Qiao, Junbang Liang, Vladlen Koltun, and Ming C. Lin. 2021a. Differentiable Simulation of Soft Multi-body Systems. In Conference on Neural Information Processing Systems (NeurIPS).
54. Yi-Ling Qiao, Junbang Liang, Vladlen Koltun, and Ming C. Lin. 2021b. Efficient Differentiable Simulation of Articulated Bodies. In ICML.
55. Paul I Richards. 1956. Shock waves on the highway. Operations research 4, 1 (1956), 42–51.
56. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 (2017).
57. Jason Sewall, David Wilkie, and Ming C Lin. 2011. Interactive hybrid simulation of large-scale traffic. In Proceedings of the 2011 SIGGRAPH Asia Conference. 1–12.
58. Jason Sewall, David Wilkie, Paul Merrell, and Ming C Lin. 2010. Continuum traffic simulation. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 439–448.
59. Jason Douglas Sewall. 2011. Efficient, scalable traffic and compressible fluid simulations using hyperbolic models. Ph.D. Dissertation. The University of North Carolina at Chapel Hill.
60. Siyuan Shen, Yang Yin, Tianjia Shao, He Wang, Chenfanfu Jiang, Lei Lan, and Kun Zhou. 2021. High-order differentiable autoencoder for nonlinear model reduction. arXiv preprint arXiv:2102.11026 (2021).
61. Tetsuya Takahashi, Junbang Liang, Yi-Ling Qiao, and Ming C Lin. 2021. Differentiable Fluids with Solid Coupling for Learning and Control. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 6138–6146.
62. Martin Treiber, Ansgar Hennecke, and Dirk Helbing. 2000. Congested traffic states in empirical observations and microscopic simulations. Physical review E 62, 2 (2000), 1805.
63. Adrien Treuille, Seth Cooper, and Zoran Popović. 2006. Continuum crowds. ACM Transactions on Graphics (TOG) 25, 3 (2006), 1160–1168.
64. Hua Wei, Guanjie Zheng, Huaxiu Yao, and Zhenhui Li. 2018. Intellilight: A reinforcement learning approach for intelligent traffic light control. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2496–2505.
65. Gerald Beresford Whitham. 2011. Linear and nonlinear waves. Vol. 42. John Wiley & Sons.
66. Huan Yu and Miroslav Krstic. 2019. Traffic congestion control for Aw-Rascle-Zhang model. Automatica 100 (2019), 38–51.
67. H Michael Zhang. 2002. A non-equilibrium traffic model devoid of gas-like behavior. Transportation Research Part B: Methodological 36, 3 (2002), 275–290.
68. Yuanshi Zheng, Jingying Ma, and Long Wang. 2017. Consensus of hybrid multi-agent systems. IEEE transactions on neural networks and learning systems 29, 4 (2017), 1359–1365.
