On sequential data assimilation for scalar macroscopic traffic flow models. (English) Zbl 1247.90087
Summary: We consider the problem of sequential data assimilation for transportation networks using optimal filtering with a scalar macroscopic traffic flow model. Properties of the distribution of the uncertainty on the true state related to the specific nonlinearity and non-differentiability inherent to macroscopic traffic flow models are investigated, derived analytically and analyzed. We show that nonlinear dynamics, by creating discontinuities in the traffic state, affect the performances of classical filters and in particular that the distribution of the uncertainty on the traffic state at shock waves is a mixture distribution. The non-differentiability of traffic dynamics around stationary shock waves is also proved and the resulting optimality loss of the estimates is quantified numerically. The properties of the estimates are explicitly studied for the Godunov scheme (and thus the Cell-Transmission Model), leading to specific conclusions about their use in the context of filtering, which is a significant contribution of this article. Analytical proofs and numerical tests are introduced to support the results presented. A Java implementation of the classical filters used in this work is available on-line at http://traffic.berkeley.edu for facilitating further efforts on this topic and fostering reproducible research.
MSC:
| 90B20 | Traffic problems in operations research |
| 91B69 | Heterogeneous agent models |
| 35L67 | Shocks and singularities for hyperbolic equations |
Keywords:
traffic flow; macroscopic modeling; sequential estimation; data assimilation; conservation law; Riemann problemSoftware:
EnKFReferences:
| [1] | (Hey, T.; Tansley, S.; Tolle, K., The Fourth Paradigm: Data-Intensive Scientific Discovery (2009), Microsoft Research: Microsoft Research Redmond, WA) |
| [2] | Kaipio, J.; Somersalo, E., Statistical and Computational Inverse Problems (2005), Springer: Springer New-York, NY · Zbl 1068.65022 |
| [3] | F. Bouttier, P. Courtier, Data assimilation concepts and methods, Training course notes of the European Centre for Medium-Range Weather Forecasts, 1999, Reading, UK.; F. Bouttier, P. Courtier, Data assimilation concepts and methods, Training course notes of the European Centre for Medium-Range Weather Forecasts, 1999, Reading, UK. |
| [4] | Le Dimet, F.-X.; Talagrand, O., Variational algorithms for analysis and assimilation of meteorological observations: theoretical aspects, Tellus A, 38, 2, 97-110 (1986) |
| [5] | Kalman, R., A new approach to linear filtering and prediction problems, J. Basic Eng., 82, 1, 35-45 (1960) |
| [6] | N. Wiener, Extrapolation, interpolation, and smoothing of stationary time series with engineering applications, The Technology Press of The Massachusetts Institute of Technology, Boston, MA, 1949.; N. Wiener, Extrapolation, interpolation, and smoothing of stationary time series with engineering applications, The Technology Press of The Massachusetts Institute of Technology, Boston, MA, 1949. · Zbl 0036.09705 |
| [7] | Bar-Shalom, Y.; Li, X.; Kirubarajan, T.; Wiley, J., Estimation with Applications to Tracking and Navigation (2001), John Wiley and Sons: John Wiley and Sons New York, NY |
| [8] | Schmidt, S., Kalman filter: Its recognition and development for aerospace applications, J. Guid. Control, 4, 1, 4-7 (1981) |
| [9] | Courtier, P.; Andersson, E.; Heckley, W.; Vasiljevic, D.; Hamrud, M.; Hollingsworth, A.; Rabier, F.; Fisher, M.; Pailleux, J., The ECMWF implementation of three-dimensional variational assimilation (3D-Var). I: Formulation, Q. J. R. Meteorol. Soc., 124, 550, 1783-1807 (1998) |
| [10] | Courtier, P.; Thepaut, J.; Hollingsworth, A., A strategy for operational implementation of 4D-Var, using an incremental approach, Q. J. R. Meteorol. Soc., 120, 519, 1367-1387 (1994) |
| [11] | Anderson, B.; Moore, J., Optimal Filtering (1979), Prentice Hall: Prentice Hall Upper Saddle River, NJ · Zbl 0688.93058 |
| [12] | S. Julier, J. Uhlmann, A new extension of the Kalman filter to nonlinear systems, in: Proceedings of AeroSense: SPIE 11th Annual International Symposium on Aerospace/Defense Sensing, Simulation and Controls, Orlando, FL, 1997.; S. Julier, J. Uhlmann, A new extension of the Kalman filter to nonlinear systems, in: Proceedings of AeroSense: SPIE 11th Annual International Symposium on Aerospace/Defense Sensing, Simulation and Controls, Orlando, FL, 1997. |
| [13] | Evensen, G., The ensemble Kalman filter: Theoretical formulation and practical implementation, Ocean Dynam., 53, 4, 343-367 (2003) |
| [14] | Liu, J.; Chen, R., Sequential Monte Carlo methods for dynamic systems, J. Amer. Statist. Assoc., 93, 443, 1032-1044 (1998) · Zbl 1064.65500 |
| [15] | Chen, R.; Liu, J., Mixture Kalman filters, J. R. Stat. Soc. Ser. B (Stat. Methodol.), 62, 3, 493-508 (2000) · Zbl 0953.62100 |
| [16] | Gazis, D.; Knapp, C., On-line estimation of traffic densities from time-series of flow and speed data, Transp. Sci., 5, 3, 283-301 (1971) |
| [17] | Szeto, M.; Gazis, D., Application of Kalman filtering to the surveillance and control of traffic systems, Transp. Sci., 6, 4, 419-439 (1972) |
| [18] | Wang, Y.; Papageorgiou, M., Real-time freeway traffic state estimation based on extended Kalman filter: a general approach, Transp. Res., 39, 2, 141-167 (2005) |
| [19] | Wang, Y.; Papageorgiou, M.; Messmer, A., Real-time freeway traffic state estimation based on extended Kalman filter: A case study, Transp. Sci., 41, 2, 167 (2007) |
| [20] | Papageorgiou, M.; Blosseville, J.-M.; Hadj-Salem, H., Modelling and real-time control of traffic flow on the southern part of Boulevard Peripherique in Paris: Part I: Modelling, Transp. Res., 24, 5, 345-359 (1990) |
| [21] | T. Schreiter, C. van Hinsbergen, F. Zuurbier, H. van Lint, S. Hoogendoorn, Data-model synchronization in extended Kalman filters for accurate online traffic state estimation, in: 2010 Proceedings of the Traffic Flow Theory Conference, Annecy, France, 2010.; T. Schreiter, C. van Hinsbergen, F. Zuurbier, H. van Lint, S. Hoogendoorn, Data-model synchronization in extended Kalman filters for accurate online traffic state estimation, in: 2010 Proceedings of the Traffic Flow Theory Conference, Annecy, France, 2010. |
| [22] | Smulders, S., Control of freeway traffic flow by variable speed signs, Transp. Res., 24, 2, 111-132 (1990) |
| [23] | Herrera, J.-C.; Bayen, A., Incorporation of lagrangian measurements in freeway traffic state estimation, Transp. Res., 44, 4, 460-481 (2010) |
| [24] | Sun, X.; Muñoz, L.; Horowitz, R., Mixture Kalman filter based highway congestion mode and vehicle density estimator and its application, (American Control Conference (ACC), 2004 (2004), IEEE: IEEE Boston,MA), 2098-2103 |
| [25] | C. Tampere, L. Immers, An extended Kalman filter application for traffic state estimation using CTM with implicit mode switching and dynamic parameters, in: Intelligent Transportation Systems Conference, 2007. ITSC 2007, Seattle, WA, 2007, pp. 209-216.; C. Tampere, L. Immers, An extended Kalman filter application for traffic state estimation using CTM with implicit mode switching and dynamic parameters, in: Intelligent Transportation Systems Conference, 2007. ITSC 2007, Seattle, WA, 2007, pp. 209-216. |
| [26] | Daganzo, C., The cell transmission model: a dynamic representation of highway traffic consistent with the hydrodynamic theory, Transp. Res., 28, 4, 269-287 (1994) |
| [27] | Daganzo, C., The cell transmission model, part II: Network traffic, Transp. Res., 29, 2, 79-93 (1995) |
| [28] | Mihaylova, L.; Boel, R.; Hegyi, A., Freeway traffic estimation within particle filtering framework, Automatica, 43, 2, 290-300 (2007) · Zbl 1111.93076 |
| [29] | Work, D.; Blandin, S.; Tossavainen, O.-P.; Piccoli, B.; Bayen, A., A traffic model for velocity data assimilation, Appl. Math. Res. eXpress, 1, 1, 1-35 (2010) · Zbl 1187.90098 |
| [30] | Gordon, N.; Salmond, D.; Smith, A., Novel approach to nonlinear/non-Gaussian Bayesian state estimation, (Radar and Signal Processing, IEE Proceedings F, vol. 140 (1993), IET), 107-113 |
| [31] | L. Mihaylova, R. Boel, A. Hegyi, An unscented Kalman filter for freeway traffic estimation, in: Proceedings of the IFAC Symposium on Control in Transportation Systems, Delft, the Netherlands, 2006, pp. 29-31.; L. Mihaylova, R. Boel, A. Hegyi, An unscented Kalman filter for freeway traffic estimation, in: Proceedings of the IFAC Symposium on Control in Transportation Systems, Delft, the Netherlands, 2006, pp. 29-31. |
| [32] | Lighthill, M.; Whitham, G., On kinematic waves, II: a theory of traffic flow on long crowded roads, Proc. R. Soc. Lond., 229, 1178, 317-345 (1956) · Zbl 0064.20906 |
| [33] | Richards, P., Shock waves on the highway, Oper. Res., 4, 1, 42-51 (1956) · Zbl 1414.90094 |
| [34] | Godunov, S., A difference method for numerical calculation of discontinuous solutions of the equations of hydrodynamics, Mat. Sb., 89, 3, 271-306 (1959) · Zbl 0171.46204 |
| [35] | Evans, L., (Partial Differential Equations (1998), American Mathematical Society: American Mathematical Society Providence, RI) · Zbl 0902.35002 |
| [36] | Evensen, G., Inverse methods and data assimilation in nonlinear ocean models, Physica D, 77, 1-3, 108-129 (1994) |
| [37] | Sorenson, H., Least-squares estimation: from Gauss to Kalman, Spectrum, IEEE, 7, 7, 63-68 (1970) |
| [38] | Stigler, S., Gauss and the invention of least squares, Ann. Stat., 465-474 (1981) · Zbl 0477.62001 |
| [39] | Jazwinski, A., Stochastic Processes and Filtering Theory (1970), Academic Press: Academic Press New York, NY · Zbl 0203.50101 |
| [40] | Sherman, S., Non-mean-square error criteria, IRE Trans. Inform. Theory, 4, 3, 125-126 (1958) |
| [41] | Federal Highway Administration, Next Generation Simulation, http://ngsim-community.org/; Federal Highway Administration, Next Generation Simulation, http://ngsim-community.org/ |
| [42] | Evensen, G., Using the extended Kalman filter with a multilayer quasi-geostrophic ocean model, J. Geophys. Res., 97, C11, 17905-17924 (1992) |
| [43] | Miller, R.; Carter, E.; Blue, S., Data assimilation into nonlinear stochastic models, Tellus A, 51, 2, 167-194 (1999) |
| [44] | Miller, R.; Ghil, M.; Gauthiez, F., Advanced data assimilation in strongly nonlinear dynamical systems, J. Atmospheric Sci., 51, 8, 1037-1056 (1994) |
| [45] | Julier, S.; Uhlmann, J.; Durrant-Whyte, H., A new method for the nonlinear transformation of means and covariances in filters and estimators, IEEE Trans. Automat. Control, 45, 3, 477-482 (2000) · Zbl 0973.93053 |
| [46] | A. Hegyi, D. Girimonte, R. Babuška, B. De Schutter, A comparison of filter configurations for freeway traffic state estimation, in: Intelligent Transportation Systems Conference, 2006, ITSC 2006, Toronto, CA, 2006, pp. 1029-1034.; A. Hegyi, D. Girimonte, R. Babuška, B. De Schutter, A comparison of filter configurations for freeway traffic state estimation, in: Intelligent Transportation Systems Conference, 2006, ITSC 2006, Toronto, CA, 2006, pp. 1029-1034. |
| [47] | Evensen, G., Sequential data assimilation with a nonlinear quasi-geostrophic model using Monte Carlo methods to forecast error statistics, J. Geophys. Res., 99, 10143-10162 (1994) |
| [48] | Burgers, G.; van Leeuwen, P.; Evensen, G., Analysis scheme in the ensemble Kalman filter, Mon. Weather Rev., 126, 6, 1719-1724 (1998) |
| [49] | Anderson, J., An ensemble adjustment Kalman filter for data assimilation, Mon. Weather Rev., 129, 12, 2884-2903 (2001) |
| [50] | Andrieu, C.; De Freitas, N.; Doucet, A.; Jordan, M., An introduction to MCMC for machine learning, J. Mach. Learn., 50, 1, 5-43 (2003) · Zbl 1033.68081 |
| [51] | Metropolis, N.; Ulam, S., The Monte Carlo method, J. Amer. Statist. Assoc., 44, 247, 335-341 (1949) · Zbl 0033.28807 |
| [52] | Hastings, W., Monte Carlo sampling methods using Markov chains and their applications, Biometrika, 57, 1 (1970) · Zbl 0219.65008 |
| [53] | Boel, R.; Mihaylova, L., A compositional stochastic model for real time freeway traffic simulation, Transp. Res., 40, 4, 319-334 (2006) |
| [54] | Snyder, C.; Bengtsson, T.; Bickel, P.; Anderson, J., Obstacles to high-dimensional particle filtering, Mon. Weather Rev., 136, 12, 4629-4640 (2008) |
| [55] | Van Der Merwe, R.; Doucet, A.; De Freitas, N.; Wan, E., The unscented particle filter, Adv. Neural Inform. Process. Syst., 13, 584-590 (2001) |
| [56] | Chorin, A.; Tu, X., Implicit sampling for particle filters, Proc. Nat. Acad. Sci., 106, 41, 17249-17254 (2009) |
| [57] | Greenshields, B., A study of traffic capacity, Proc. Highway Res. Board, 14, 1, 448-477 (1935) |
| [58] | Newell, G., A simplified theory of kinematic waves in highway traffic, Part II: queueing at freeway bottlenecks, Transp. Res., 27, 4, 289-303 (1993) |
| [59] | Li, T., Nonlinear dynamics of traffic jams, Physica D, 207, 1-2, 41-51 (2005) · Zbl 1074.35072 |
| [60] | Greenberg, H., An analysis of traffic flow, Oper. Res., 7, 1, 79-85 (1959) · Zbl 1414.90087 |
| [61] | M. Van Aerde, Single regime speed-flow-density relationship for congested and uncongested highways, in: 74th Annual Meeting of the Transportation Research Board, Washington, DC, 1995.; M. Van Aerde, Single regime speed-flow-density relationship for congested and uncongested highways, in: 74th Annual Meeting of the Transportation Research Board, Washington, DC, 1995. |
| [62] | Coclite, G.; Garavello, M.; Piccoli, B., Traffic flow on a road network, SIAM J. Math. Anal., 36, 6, 1862-1886 (2005) · Zbl 1114.90010 |
| [63] | Holden, H.; Risebro, N., A mathematical model of traffic flow on a network of unidirectional roads, SIAM J. Math. Anal., 26, 4, 999-1017 (1995) · Zbl 0833.35089 |
| [64] | J.-P. Lebacque, First-order macroscopic traffic flow models: Intersection modeling, network modeling, in: Proceedings of the 16th International Symposium on Transportation and Traffic Theory, Flow, Dynamics and Human Interaction, College Park, MD, 2005.; J.-P. Lebacque, First-order macroscopic traffic flow models: Intersection modeling, network modeling, in: Proceedings of the 16th International Symposium on Transportation and Traffic Theory, Flow, Dynamics and Human Interaction, College Park, MD, 2005. · Zbl 1137.90405 |
| [65] | Garavello, M.; Piccoli, B., (Traffic Flow on Networks. Traffic Flow on Networks, American Institute of Mathematical Sciences (2006), Springfield, MO) · Zbl 1136.90012 |
| [66] | Glimm, J., Solutions in the large for nonlinear hyperbolic systems of equations, Commun. Pure Appl. Math., 18, 697-715 (1965) · Zbl 0141.28902 |
| [67] | Leveque, R., Finite Volume Methods for Hyperbolic Problems (2002), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 1010.65040 |
| [68] | Bressan, A., Hyperbolic Systems of Conservation Laws: The One-dimensional Cauchy Problem (2000), Oxford University Press: Oxford University Press Oxford, UK · Zbl 0997.35002 |
| [69] | Claudel, C.; Bayen, A., Lax-hopf based incorporation of internal boundary conditions into hamilton-jacobi equation. part i: Theory, IEEE Trans. Automat. Control, 55, 5, 1142-1157 (2010) · Zbl 1368.49033 |
| [70] | Claudel, C.; Bayen, A., Lax-hopf based incorporation of internal boundary conditions into hamilton-jacobi equation. part ii: Computational methods, IEEE Trans. Automat. Control, 55, 5, 1158-1174 (2010) · Zbl 1368.49034 |
| [71] | Mazare, P. E.; Dehwah, A.; Claudel, C. G.; Bayen, A. M., Analytical and grid-free solutions to the Lighthill-Whitham-Richards traffic flow model, Transp. Res. Part B, 45, 10, 1727-1748 (2011) |
| [72] | Wong, S.; Wong, G., An analytical shock-fitting algorithm for LWR kinematic wave model embedded with linear speed-density relationship, Transp. Res., 36, 8, 683-706 (2002) |
| [73] | J.-P. Lebacque, The Godunov scheme and what it means for first order macroscopic traffic flow models, in: Proceedings of the 13th International Symposium on Transportation and Traffic Theory, Lyon, France, 1996, pp. 647-677.; J.-P. Lebacque, The Godunov scheme and what it means for first order macroscopic traffic flow models, in: Proceedings of the 13th International Symposium on Transportation and Traffic Theory, Lyon, France, 1996, pp. 647-677. |
| [74] | Payne, H., Models of freeway traffic and control, Math. Models Public Syst., 1, 1, 51-61 (1971) |
| [75] | Whitham, G., Linear and Nonlinear Waves (1974), John Wiley and Sons: John Wiley and Sons New York, NY · Zbl 0373.76001 |
| [76] | Aw, A.; Rascle, M., Resurrection of second order models of traffic flow, SIAM J. Appl. Math., 60, 3, 916-938 (2000) · Zbl 0957.35086 |
| [77] | Zhang, M., A non-equilibrium traffic model devoid of gas-like behavior, Transp. Res., 36, 3, 275-290 (2002) |
| [78] | Blandin, S.; Work, D.; Goatin, P.; Piccoli, B.; Bayen, A., A general phase transition model for vehicular traffic, SIAM J. Appl. Math., 71, 1, 107-121 (2011) · Zbl 1217.35116 |
| [79] | Colombo, R., On a \(2 \times 2\) hyperbolic traffic flow model, Math. Comput. Model., 35, 5-6, 683-688 (2002) · Zbl 0994.90021 |
| [80] | Helbing, D., Improved fluid-dynamic model for vehicular traffic, Phys. Rev. E, 51, 4, 3164-3169 (1995) |
| [81] | Zhang, H., Structural properties of solutions arising from a nonequilibrium traffic flow theory, Transp. Res., 34, 7, 583-603 (2000) |
| [82] | Huang, C.; Fallah, Y.; Sengupta, R.; Krishnan, H., Adaptive intervehicle communication control for cooperative safety systems, IEEE Netw., 24, 1, 6-13 (2010) |
| [83] | X. Sun, L. Muñoz, R. Horowitz, Highway traffic state estimation using improved mixture Kalman filters for effective ramp metering control, in: Proceedings of the 42nd IEEE Conference on Decision and Control, Maui, HI, 2003, pp. 6333-6338.; X. Sun, L. Muñoz, R. Horowitz, Highway traffic state estimation using improved mixture Kalman filters for effective ramp metering control, in: Proceedings of the 42nd IEEE Conference on Decision and Control, Maui, HI, 2003, pp. 6333-6338. |
| [84] | Bocquet, M.; Pires, C.; Wu, L., Beyond Gaussian statistical modeling in geophysical data assimilation, Mon. Weather Rev., 138, 2997-3023 (2010) |
| [85] | J. Chandrasekar, A. Ridley, D. Bernstein, A comparison of the extended and unscented Kalman filters for discrete-time systems with nondifferentiable dynamics, in: American Control Conference, ACC, 2007, pp. 4431-4436.; J. Chandrasekar, A. Ridley, D. Bernstein, A comparison of the extended and unscented Kalman filters for discrete-time systems with nondifferentiable dynamics, in: American Control Conference, ACC, 2007, pp. 4431-4436. |
| [86] | Cunha, M.; Dorini, F., Statistical moments of the solution of the random Burgers-Riemann problem, Math. Comput. Simulation, 79, 5, 1440-1451 (2009) · Zbl 1159.65008 |
| [87] | Huttunen, J.; Kaipio, J., Approximation errors in nonstationary inverse problems, Inverse Probl. Imaging, 1, 1, 77-93 (2007) · Zbl 1117.62102 |
| [88] | Huttunen, J.; Kaipio, J., Approximation error analysis in nonlinear state estimation with an application to state-space identification, Inverse Problems, 23, 2141-2157 (2007) · Zbl 1123.62068 |
| [89] | Tossavainen, O.-P.; Percelay, J.; Stacey, M.; Kaipio, J.; Bayen, A., State estimation and modeling error approach for 2D shallow water equations and Lagrangian measurements, Water Resources Research, 47, 10, W10510 (2011) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
