Error bounds for Kalman filters on traffic networks

Ye Sun; Daniel B. Work; Ye Sun; Daniel B. Work

doi:10.3934/nhm.2018012

Networks and Heterogeneous Media

2018, Volume 13, Issue 2: 261-295. doi: 10.3934/nhm.2018012

Previous Article Next Article

Error bounds for Kalman filters on traffic networks

Ye Sun ^{1
,},
Daniel B. Work ^{2
,}

1.
University of Illinois at Urbana Champaign, 205 N. Mathews Ave., Urbana, IL 61801, USA
2.
Vanderbilt University, 1025 16th Ave. S., Suite 102, Nashville, TN 37212, USA

Received: 01 May 2017 Revised: 01 February 2018
Primary: 93B07; Secondary: 35L65, 93C20

This work analyzes the estimation performance of the Kalman filter (KF) on transportation networks with junctions. To facilitate the analysis, a hybrid linear model describing traffic dynamics on a network is derived. The model, referred to as the switching mode model for junctions, combines the discretized Lighthill-Whitham-Richards partial differential equation with a junction model. The system is shown to be unobservable under nearly all of the regimes of the model, motivating attention to the estimation error bounds in these modes. The evolution of the estimation error is investigated via exploring the interactions between the update scheme of the KF and the intrinsic physical properties embedded in the traffic model (e.g., conservation of vehicles and the flow-density relationship). It is shown that the state estimates of all the cells in the traffic network are ultimately bounded inside a physically meaningful interval, which cannot be achieved by an open-loop observer.
- Network traffic flow,
- junction models,
- Kalman filtering
Citation: Ye Sun, Daniel B. Work. Error bounds for Kalman filters on traffic networks[J]. Networks and Heterogeneous Media, 2018, 13(2): 261-295. doi: 10.3934/nhm.2018012

Related Papers:

Abstract

This work analyzes the estimation performance of the Kalman filter (KF) on transportation networks with junctions. To facilitate the analysis, a hybrid linear model describing traffic dynamics on a network is derived. The model, referred to as the switching mode model for junctions, combines the discretized Lighthill-Whitham-Richards partial differential equation with a junction model. The system is shown to be unobservable under nearly all of the regimes of the model, motivating attention to the estimation error bounds in these modes. The evolution of the estimation error is investigated via exploring the interactions between the update scheme of the KF and the intrinsic physical properties embedded in the traffic model (e.g., conservation of vehicles and the flow-density relationship). It is shown that the state estimates of all the cells in the traffic network are ultimately bounded inside a physically meaningful interval, which cannot be achieved by an open-loop observer.

References

[1]	B. Anderson and J. Moore, Optimal Filtering, Prentice-Hall, inc, Englewood Cliffs, N. J., 1979.
[2]	On sequential data assimilation for scalar macroscopic traffic flow models. Physica D: Nonlinear Phenomena (2012) 241: 1421-1440.
[3]	Numerical approximations of a traffic flow model on networks. Networks and Heterogeneous Media (2006) 1: 57-84.
[4]	C. Chen, Linear System Theory and Design, 3rd edition, Oxford University Press, 1999.
[5]	H. Chen and H. A. Rakha, Prediction of dynamic freeway travel times based on vehicle trajectory construction, in "Proceedings of the 15th IEEE Conference on Intelligent Transportation Systems", (2012), 576-581. doi: 10.1109/ITSC.2012.6338825
[6]	Quality of traffic observability on highways with Lagrangian sensors. IEEE Transactions on Automation Science and Engineering (2018) 15: 761-771.
[7]	The cell transmission model: a dynamic representation of highway traffic consistent with the hydrodynamic theory. Transportation Research Part B: Methodological (1994) 28: 269-287.
[8]	The cell transmission model, part Ⅱ: Network traffic. Transportation Research Part B: Methodological (1995) 29: 79-93.
[9]	M. Garavello, K. Han and B. Piccoli, Models for Vehicular Traffic on Networks, American Institute of Mathematical Sciences, Springfield, MO, 2016.
[10]	M. Garavello and B. Piccoli, Traffic Flow on Networks, American Institute of Mathematical Sciences, Springfield, MO, 2006.
[11]	A difference method for the numerical calculation of discontinuous solutions of hydrodynamic equations. Mathematics Sbornik (1959) 47: 271-306.
[12]	Continuous-time link-based kinematic wave model: Formulation, solution existence, and well-posedness. Transportmetrica B: Transport Dynamics (2016) 4: 187-222.
[13]	Evaluation of traffic data obtained via GPS-enabled mobile phones: The mobile century field experiment. Transportation Research Part C: Emerging Technologies (2010) 18: 568-583.
[14]	Modeling, simulation, and optimization of traffic flow networks. SIAM Journal on Scientific Computing (2003) 25: 1066-1087.
[15]	A mathematical model of traffic flow on a network of unidirectional roads. SIAM Journal on Mathematical Analysis (1995) 26: 999-1017.
[16]	A stochastic model of traffic flow: Gaussian approximation and estimation. Transportation Research Part B: Methodological (2013) 47: 15-41.
[17]	A. H. Jazwinski, Stochastic Process and Filtering Theory, Academic Press, Cambridge, MA, 1970.
[18]	Continuous kinematic wave models of merging traffic flow. Transportation Research Part B: Methodological (2010) 44: 1084-1103.
[19]	A Riemann solver for a system of hyperbolic conservation laws at a general road junction. Transportation Research Part B: Methodological (2017) 98: 21-41.
[20]	On the distribution schemes for determining flows through a merge. Transportation Research Part B: Methodological (2003) 37: 521-540.
[21]	H. Khalil, Nonlinear Systems, 3rd edition, Prentice Hall, 2002.
[22]	J. Lebacque, Intersection modeling, application to macroscopic network traffic flow models and traffic management, in "Traffic and Granular Flow'03", Springer, (2005), 261-278. doi: 10.1007/3-540-28091-X_26
[23]	J.-P. Lebacque, The Godunov scheme and what it means for first order traffic flow models, in International Symposium on Transportation and Traffic Theory, (1996), 647-677.
[24]	Y. Li, C. G. Claudel, B. Piccoli and D. B. Work, A convex formulation of traffic dynamics on transportation networks, SIAM J. Appl. Math., 77 (2017), 1493-1515, arXiv: 1702.03908. doi: 10.1137/16M1074795
[25]	M. Lighthill and G. Whitham, On kinematic waves. Ⅱ) a theory of traffic flow on long crowded roads, Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences, 229 (1955), 317-345. doi: 10.1098/rspa.1955.0089
[26]	Freeway traffic estimation within particle filtering framework. Automatica (2007) 43: 290-300.
[27]	Parallelized particle and Gaussian sum particle filters for large-scale freeway traffic systems. IEEE Transactions on Intelligent Transportation Systems (2012) 13: 36-48.
[28]	I. Morarescu and C. Canudas de Wit, Highway traffic model-based density estimation, in Proceedings of the American Control Conference, 3 (2011), 2012-2017.
[29]	F. Morbidi, L. L. Ojeda, C. Canudas de Wit and I. Bellicot, A new robust approach for highway traffic density estimation, in Proceedings of the 13th European Control Conference, (2014), 1-6. doi: 10.1109/ECC.2014.6862333
[30]	Piecewise-linearized cell transmission model and parameter calibration methodology. Transportation Research Record (2006) 1965: 183-191.
[31]	R. Olfati-Saber, Kalman-consensus filter: optimality, stability, and performance, in Proceedings of the 48th IEEE Conference on Decision and Control, (2009), 7036-7042. doi: 10.1109/CDC.2009.5399678
[32]	Shock waves on the highway. Operations Research (1956) 4: 42-51.
[33]	On the convergence of the Godounov's scheme for first order quasi linear equations. Proceedings of the Japan Academy (1976) 52: 488-491.
[34]	Traffic state estimation on highway: A comprehensive survey. Annual Reviews in Control (2017) 43: 128-151.
[35]	X. Sun, L. Munoz and 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, (2003), 6333-6338. doi: 10.1109/CDC.2003.1272322
[36]	Y. Sun, A Distributed Local Kalman Consensus Filter for Traffic Estimation: Design, Analysis and Validation, Master's thesis, University of Illinois at Urbana-Champaign, 2015. doi: 10.1109/CDC.2014.7040406
[37]	Scaling the Kalman filter for large-scale traffic estimation. IEEE Transactions on Control of Network Systems (2017) 1-1.
[38]	State estimation for polyhedral hybrid systems and applications to the Godunov scheme for highway traffic estimation. IEEE Transactions on Automatic Control (2015) 60: 311-326.
[39]	C. Vivas, S. Siri, A. Ferrara, S. Sacone, G. Cavanna and F. R. Rubio, Distributed consensusbased switched observers for freeway traffic density estimation, in Proceedings of the 54th IEEE Conference on Decision and Control, (2015), 3445-3450. doi: 10.1109/CDC.2015.7402672
[40]	Efficient multiple model particle filtering for joint traffic state estimation and incident detection. Transportation Research Part C: Emerging Technologies (2016) 71: 521-537.
[41]	Real-time freeway traffic state estimation based on extended Kalman filter: A general approach. Transportation Research Part B: Methodological (2005) 39: 141-167.
[42]	A traffic model for velocity data assimilation. Applied Mathematics Research eXpress (2010) 2010: 1-35.
[43]	Real-time Lagrangian traffic state estimator for freeways. IEEE Transactions on Intelligent Transportation Systems (2012) 13: 59-70.

Reader Comments

Your name:*

Email:*
© 2018 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)