Advanced Search
Article Contents
Article Contents

Error bounds for Kalman filters on traffic networks

This material is based upon work supported by the National Science Foundation under Grant No. CMMI-1351717.
Abstract Full Text(HTML) Figure(5) / Table(1) Related Papers Cited by
  • 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.

    Mathematics Subject Classification: Primary: 93B07; Secondary: 35L65, 93C20.


    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  The triangular fundamental diagram in (10)

    Figure 2.  A diverge and a merge junction connected by three cells indexed by $i$, $j$, and $l$

    Figure 3.  Three scenarios in the junction solver [24] for the diverge junction shown in Figure 2a, where cell $l$ diverges to cell $i$ and cell $j$. The blue vertical (resp. horizontal) solid line denotes the receiving capacity of cell $i$ (resp. cell $j$). The intercepts of the blue dashed line denote the sending capacity of cell $l$. The shaded area denotes the feasible values of the flux from cell $l$ to $i$ and the flux from cell $l$ to $j$. The slope of the black dotted line is the prescribed distribution ratio $\alpha_{\text{d}}$. The fluxes computed by the junction solver is marked by the red dot, whose horizontal axis and vertical axis values are the obtained ${\rm{f}}(\rho^{l}_{k}, \rho^{i}_{k})$ and ${\rm{f}}(\rho^{l}_{k}, \rho^{j}_{k})$, respectively. Note that in diverge case Ⅱ and diverge case Ⅲ, the receiving capacities of cell $i$ and cell $j$ are not necessarily smaller than the sending capacity of cell $l$, and the graphical illustration of the flux solutions is also applicable for ${\rm{r}}(\rho_k^i)\ge {\rm{s}}(\rho_k^l)$ and/or ${\rm{r}}(\rho_k^j)\ge {\rm{s}}(\rho_k^l)$.

    Figure 4.  A local section with $n$ cells, three links and a junction

    Figure 5.  The evolutions of the estimation errors (A) and the trace of the error covariance (B) when using the KF to track the unobservable system (39)-(40)

    Table 1.  Mode definition and observability of the SMM-J

    Mode F/C$^1$ status of cell(s) Transition$^{3}$ on link Diverge case Obser-vability$^4$
    $1$ $n_1+n_2$ $n$ near junction$^{2}$ 1 2 3
    1 F F F F none none none O
    2 F F F C Sh. Ep. Ep. U
    3 F F F C Sh. Ep. Ep. U
    4 F F F C Sh. Ep. Ep. U
    5 C C C C none none none U
    6 C C C C none none none U
    7 C C C C none none none U
    8 C C C F Ep. Sh. Sh. U
    9 F C C C Sh. none none U
    10 F C C C Sh. none none U
    11 F C C C Sh. none none U
    12 F C C F none Sh. Sh. U
    13 C C F C none none Ep. U
    14 C C F C none none Ep. U
    15 C C F C none none Ep. U
    16 C C F F Ep. Sh. none U
    17 C F C C none Ep. none U
    18 C F C C none Ep. none U
    19 C F C C none Ep. none U
    20 C F C F Ep. none Sh. U
    21 C F F F Ep. none none O
    22 C F F C none Ep. Ep. U
    23 C F F C none Ep. Ep. U
    24 C F F C none Ep. Ep. U
    25 F C F F none Sh. none U
    26 F C F C Sh. none Ep. U
    27 F C F C Sh. none Ep. U
    28 F C F C Sh. none Ep. U
    29 F F C F none none Sh. U
    30 F F C C Sh. Ep. none U
    31 F F C C Sh. Ep. none U
    32 F F C C Sh. Ep. none U
    1 "F" and "C" stand for freeflow and congestion, respectively.
    2 Cells indexed by $n_1$, $n_1+1$ and $n_1+n_2+1$.
    3 "Sh." and "Ep." stand for shock (i.e., transition from freeflow to congestion) and expansion fan (i.e., transition from congestion to freeflow), respectively.
    4 "O" stands for uniformly completely observable and "U" stands for unobservable. Note that the observability results are derived under sensor locations shown in Figure 4.
     | Show Table
    DownLoad: CSV
  • [1] B. Anderson and J. Moore, Optimal Filtering, Prentice-Hall, inc, Englewood Cliffs, N. J., 1979.
    [2] S. BlandinA. CouqueA. Bayen and D. B. Work, On sequential data assimilation for scalar macroscopic traffic flow models, Physica D: Nonlinear Phenomena, 241 (2012), 1421-1440.  doi: 10.1016/j.physd.2012.05.005.
    [3] G. BrettiR. Natalini and B. Piccoli, Numerical approximations of a traffic flow model on networks, Networks and Heterogeneous Media, 1 (2006), 57-84.  doi: 10.3934/nhm.2006.1.57.
    [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] S. ContrerasS. Agarwal and P. Kachroo, Quality of traffic observability on highways with Lagrangian sensors, IEEE Transactions on Automation Science and Engineering, 15 (2018), 761-771.  doi: 10.1109/TASE.2017.2691299.
    [7] C. F. Daganzo, The cell transmission model: a dynamic representation of highway traffic consistent with the hydrodynamic theory, Transportation Research Part B: Methodological, 28 (1994), 269-287.  doi: 10.1016/0191-2615(94)90002-7.
    [8] C. F. Daganzo, The cell transmission model, part Ⅱ: Network traffic, Transportation Research Part B: Methodological, 29 (1995), 79-93.  doi: 10.1016/0191-2615(94)00022-R.
    [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] S. Godunov, A difference method for the numerical calculation of discontinuous solutions of hydrodynamic equations, Mathematics Sbornik, 47 (1959), 271-306. 
    [12] K. HanB. Piccoli and W. Szeto, Continuous-time link-based kinematic wave model: Formulation, solution existence, and well-posedness, Transportmetrica B: Transport Dynamics, 4 (2016), 187-222.  doi: 10.1080/21680566.2015.1064793.
    [13] J. C. HerreraD. B. WorkR. HerringX. J. BanQ. Jacobson and A. M. Bayen, Evaluation of traffic data obtained via GPS-enabled mobile phones: The mobile century field experiment, Transportation Research Part C: Emerging Technologies, 18 (2010), 568-583.  doi: 10.1016/j.trc.2009.10.006.
    [14] M. Herty and A. Klar, Modeling, simulation, and optimization of traffic flow networks, SIAM Journal on Scientific Computing, 25 (2003), 1066-1087.  doi: 10.1137/S106482750241459X.
    [15] H. Holden and N. H. Risebro, A mathematical model of traffic flow on a network of unidirectional roads, SIAM Journal on Mathematical Analysis, 26 (1995), 999-1017.  doi: 10.1137/S0036141093243289.
    [16] S. Jabari and H. Liu, A stochastic model of traffic flow: Gaussian approximation and estimation, Transportation Research Part B: Methodological, 47 (2013), 15-41.  doi: 10.1016/j.trb.2012.09.004.
    [17] A. H. Jazwinski, Stochastic Process and Filtering Theory, Academic Press, Cambridge, MA, 1970.
    [18] W. Jin, Continuous kinematic wave models of merging traffic flow, Transportation Research Part B: Methodological, 44 (2010), 1084-1103.  doi: 10.1016/j.trb.2010.02.011.
    [19] W. Jin, A Riemann solver for a system of hyperbolic conservation laws at a general road junction, Transportation Research Part B: Methodological, 98 (2017), 21-41.  doi: 10.1016/j.trb.2016.12.007.
    [20] W. Jin and H. M. Zhang, On the distribution schemes for determining flows through a merge, Transportation Research Part B: Methodological, 37 (2003), 521-540.  doi: 10.1016/S0191-2615(02)00026-7.
    [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] L. MihaylovaR. Boel and A. Hegyi, Freeway traffic estimation within particle filtering framework, Automatica, 43 (2007), 290-300.  doi: 10.1016/j.automatica.2006.08.023.
    [27] L. MihaylovaA. HegyiA. Gning and R. Boel, Parallelized particle and Gaussian sum particle filters for large-scale freeway traffic systems, IEEE Transactions on Intelligent Transportation Systems, 13 (2012), 36-48.  doi: 10.1109/TITS.2011.2178833.
    [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] L. MunozX. SunR. Horowitz and L. Alvarez, Piecewise-linearized cell transmission model and parameter calibration methodology, Transportation Research Record, 1965 (2006), 183-191.  doi: 10.3141/1965-19.
    [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] P. I. Richards, Shock waves on the highway, Operations Research, 4 (1956), 42-51.  doi: 10.1287/opre.4.1.42.
    [33] A. Y. L. Roux, On the convergence of the Godounov's scheme for first order quasi linear equations, Proceedings of the Japan Academy, 52 (1976), 488-491.  doi: 10.3792/pja/1195518212.
    [34] T. SeoA. M. BayenT. Kusakabe and Y. Asakura, Traffic state estimation on highway: A comprehensive survey, Annual Reviews in Control, 43 (2017), 128-151.  doi: 10.1016/j.arcontrol.2017.03.005.
    [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] Y. Sun and D. B. Work, Scaling the Kalman filter for large-scale traffic estimation, IEEE Transactions on Control of Network Systems, (2017), 1-1.  doi: 10.1109/TCNS.2017.2668898.
    [38] J. Thai and A. M. Bayen, State estimation for polyhedral hybrid systems and applications to the Godunov scheme for highway traffic estimation, IEEE Transactions on Automatic Control, 60 (2015), 311-326.  doi: 10.1109/TAC.2014.2342151.
    [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] R. WangS. Fan and D. B. Work, Efficient multiple model particle filtering for joint traffic state estimation and incident detection, Transportation Research Part C: Emerging Technologies, 71 (2016), 521-537.  doi: 10.1016/j.trc.2016.08.003.
    [41] Y. Wang and M. Papageorgiou, Real-time freeway traffic state estimation based on extended Kalman filter: A general approach, Transportation Research Part B: Methodological, 39 (2005), 141-167.  doi: 10.1016/j.trb.2004.03.003.
    [42] D. B. WorkS. BlandinO.-P. TossavainenB. Piccoli and A. Bayen, A traffic model for velocity data assimilation, Applied Mathematics Research eXpress, 2010 (2010), 1-35. 
    [43] Y. YuanJ. van LintR. WilsonF. van Wageningen-Kessels and S. Hoogendoorn, Real-time Lagrangian traffic state estimator for freeways, IEEE Transactions on Intelligent Transportation Systems, 13 (2012), 59-70.  doi: 10.1109/TITS.2011.2178837.
  • 加载中




Article Metrics

HTML views(606) PDF downloads(468) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint