UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Roadmap enhanced improvement to the VSIMM tracker via a constrained stochastic context free grammar Gao, Sijia


In this thesis, we aim to improve the tracking accuracy for targets that are moving confined to a roadmap given target observations. We build a 3-level model for this roadmap constrained target tracking problem. At the first level, the roadmap is formulated as a directed, weighted graph; at the second level, the target's trajectory is characterized via an ordered sequence of intersections it traverses. The target's roadmap constrained trajectory exploits moving directions and road or intersection names and is modeled via a CSCFG (constrained stochastic context free grammar). CSCFG arises from language processing models and is more general than Markov chains and SCFGs (stochastic context free grammar). Bayesian signal processing algorithms for CSCFGs with polynomial time complexity are also derived; finally, the target's kinematics are described by the baseline VSIMM (variable structure interacting multiple model). Based on the 3-level model, we present a novel CSCFG driven sequential particle filtering algorithm that estimates the target's states. This algorithm comprises a CSCFG meta-level parsing algorithm that operates in conjunction with a base-level VSIMM tracking algorithm. Extensive numerical results using simulated ground moving target indicator (GMTI) radar measurements show substantial improvement in target tracking accuracy compared with VSIMM tracker. To further evaluate the effectiveness of CSCFG, we also illustrate two anomalous trajectories for targets moving on grid roadmap. These trajectories show suspicious intents of targets and cause attention of radar operators. Numerical examples using simulated GMTI radar measurements show that CSCFG based Viterbi tracker can significantly decrease the tracking error compared with HMM (hidden Markov model) Viterbi tracker. Future work include more flexible constructions of the roadmap graph and extensions from CSCFGs to matrix grammars to model more complicated spatio-temporal trajectories.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International