Modified switched IMM estimator based on autoregressive extended Viterbi method for maneuvering target tracking

doi:10.21629/JSEE.2018.06.04

Abstract

Abstract:

In this paper, a new approach of maneuvering target tracking algorithm based on the autoregressive extended Viterbi (AREV) model is proposed. In contrast to weakness of traditional constant velocity (CV) and constant acceleration (CA) models to noise effect reduction, the autoregressive (AR) part of the new model which changes the structure of state space equations is proposed. Also using a dynamic form of the state transition matrix leads to improving the rate of convergence and decreasing the noise effects. Since AR will impose the load of overmodeling to the computations, the extended Viterbi (EV) method is incorporated to AR in two cases of EV1 and EV2. According to most probable paths in the interacting multiple model (IMM) during nonmaneuvering and maneuvering parts of estimation, EV1 and EV2 respectively can decrease load of overmodeling computations and improve the AR performance. This new method is coupled with proposed detection schemes for maneuver occurrence and termination as well as for switching initializations. Appropriate design parameter values are derived for the detection schemes of maneuver occurrences and terminations. Finally, simulations demonstrate that the performance of the proposed model is better than the other older linear and also nonlinear algorithms in constant velocity motions and also in various types of maneuvers.

Key words: interacting multiple model (IMM) filter, constant acceleration (CA), autoregressive (AR), extended Viterbi (EV), autoregressive extended Viterbi (AREV), extended Kalman filter (EKF)

Mahmoudreza HADAEGH, Hamid KHALOOZADEH. Modified switched IMM estimator based on autoregressive extended Viterbi method for maneuvering target tracking[J]. Journal of Systems Engineering and Electronics, 2018, 29(6): 1142-1157.

Figures/Tables 8

Table 1

The proposed AREV model"

Initialization (for j = 1, 2, ..., n)
n: the number of parallel models in IMM.
M: the number of AR model coefficients.
N: the highest degree of polynomial used to approximate the range.
Attention: M >N + 1.
m: the most probable paths used in the EV algorithm.
Attention: 1≤m ﹤ n (m = 1 in EV1 and m = 2 in EV2).
x₀^jandP₀^jare initial estimate and initial covariance;
The process noise covariance: Q = qrTI (T is sampling time, and Iis identity matrix;
Initial model probability: μ0(j) = 1/n;
Model transition probability: P = {pij}, i, j = 1, 2, ..., n.
Step 1 Calculation of transition matrix (for j = 1, 2, ..., n)
In every time step, the convex quadratic programming problem (25) should be solved, and the transition matrix Aj k\|k?1 is obtained by (5) in every AR model.
Attention: It is the special part of the proposed method in which the AR idea is incorporated.
Step 2 Model-conditioned re-initialization (for j = 1, 2, ..., n & s = 1, 2, ..., m)
$\mu_{k-1}(l_{sj}\|j) = \dfrac{\max^s_{1{\leqslant} i{\leqslant} n}\{p_{ij}\mu_{k-1}(i)\}}{{ }\sum^m_{s = 1}{\max}^s_{1{\leqslant} i{\leqslant} n}\{p_{ij}\mu_{k-1}(i)\}}$
$\mu_{k-1}(l_{sj}\|j) = \dfrac{\max^s_{1{\leqslant} i{\leqslant} n}\{p_{ij}\mu_{k-1}(i)\}}{{ }\sum^m_{s = 1}{\max}^s_{1{\leqslant} i{\leqslant} n}\{p_{ij}\mu_{k-1}(i)\}}$
Mixing estimate: $\widehat{{{{\mathit{\boldsymbol{x}}}}}}^{0j}_{k-1} = { }\sum^m_{s = 1}\widehat{{{{\mathit{\boldsymbol{x}}}}}}^{l_{sj}}_{k-1}\mu_{k-1}(l_{sj}\|j)$
Mixing covariance: ${{{\mathit{\boldsymbol{P}}}}}^{0j}_{k-1} = { }\sum^m_{s = 1}\mu_{k-1}(l_{sj}\|j)\{{{{\mathit{\boldsymbol{P}}}}}^{l_{sj}}_{k-1}+ [\widehat{{{{\mathit{\boldsymbol{x}}}}}}^{l_{sj}}_{k-1}-\widehat{{{{\mathit{\boldsymbol{x}}}}}}^{0j}_{k-1}]\times[\widehat{{{{\mathit{\boldsymbol{x}}}}}}^{l_{sj}}_{k-1}-\widehat{{{{\mathit{\boldsymbol{x}}}}}}^{0j}_{k-1}]'\}$.
Step 3 Model-conditioned filtering (for j = 1, 2, ..., n)
Predicted state: $\widehat{{{{\mathit{\boldsymbol{x}}}}}}^{j}_{k\|k-1} = {{{\mathit{\boldsymbol{A}}}}}^{j}_{k\|k-1}\widehat{{{{\mathit{\boldsymbol{x}}}}}}^{0j}_{k-1\|k-1}$
Predicted covariance: ${{{\mathit{\boldsymbol{P}}}}}^j_{k\|k-1}\! = \!{{{\mathit{\boldsymbol{A}}}}}^j_{k\|k-1}{{{\mathit{\boldsymbol{P}}}}}^{0j}_{k-1\|k-1}({{{\mathit{\boldsymbol{A}}}}}^j_{k\|k-1})^{{{\rm{T}}}}\!+\!{{{\mathit{\boldsymbol{Q}}}}}^j$
Filter gain: ${{{\mathit{\boldsymbol{K}}}}}^j_{k} = {{{\mathit{\boldsymbol{P}}}}}^j_{k\|k-1}({{{\mathit{\boldsymbol{H}}}}}^j_k)^{{{\rm{T}}}}({{{\mathit{\boldsymbol{S}}}}}^j_k)^{-1}$
${{{\mathit{\boldsymbol{S}}}}}^j_k = {{{\mathit{\boldsymbol{H}}}}}^j_k{{{\mathit{\boldsymbol{P}}}}}^j_{k\|k-1}({{{\mathit{\boldsymbol{H}}}}}^j_k)^{{{\rm{T}}}}+{{{\mathit{\boldsymbol{R}}}}}^j_k$
Updated state: $\widehat{{{{\mathit{\boldsymbol{x}}}}}}^j_{k\|k} = \widehat{{{{\mathit{\boldsymbol{x}}}}}}^j_{k\|k-1}+{{{\mathit{\boldsymbol{K}}}}}^j_k{{{\mathit{\boldsymbol{d}}}}}^j_k$, where ${{{\mathit{\boldsymbol{d}}}}}^j_k = {{{\mathit{\boldsymbol{z}}}}}_j-{{{\mathit{\boldsymbol{H}}}}}^j_k\widehat{{{{\mathit{\boldsymbol{x}}}}}}^j_{k\|k-1}$
Updated covariance: ${{{\mathit{\boldsymbol{P}}}}}^j_{k\|k} = [{{{\mathit{\boldsymbol{I}}}}}^j-{{{\mathit{\boldsymbol{K}}}}}^j_k{{{\mathit{\boldsymbol{H}}}}}^j_k]{{{\mathit{\boldsymbol{P}}}}}^j_{k\|k-1}$
Step 4 Model probability update (for $j = 1, 2, \ldots, n$)
Model probability update (for $j = 1, 2, \ldots, n$)
Model likelihood: ${\it\Lambda}^j_k = N({{{\mathit{\boldsymbol{d}}}}}^j_k; 0, {{{\mathit{\boldsymbol{S}}}}}^j_k)$ Model probability: $\mu_k(j) = \dfrac{{ }{\it\Lambda}_k\sum^m_{s = 1}{\max}^s_{1{\leqslant} i{\leqslant} n}\{p_{ij}\mu_{k-1}(i)\}} {{ }\sum^n_{j = 1}{\it\Lambda}_k(j)\sum^m_{s = 1}{\max}^s_{1{\leqslant} i{\leqslant} n}\{p_{ij}\mu_{k-1}(i)\}}$
Step 5 Calculation of m largest model probabilities (for $r = 1, 2, \ldots, m$)
$\widetilde{\mu}_k(\widetilde{l}_r) = \dfrac{\max^r_{1{\leqslant} i{\leqslant} n}\{\mu_{k}(j)\}}{{ }\sum^m_{r = 1}{\max}^r_{1{\leqslant} i{\leqslant} n}\{\mu_{k-1}(j)\}'}$
$\widetilde{l}_{r} = \arg\{\max^r_{1{\leqslant} i{\leqslant} n}\{\mu_{k}(j)\}\}$
Step 6Estimate fusion
Overall estimate: $\widehat{{{{\mathit{\boldsymbol{x}}}}}}_k = { }\sum^m_{r = 1}\widetilde{\mu}_k(\widetilde{l}_r)\widehat{{{{\mathit{\boldsymbol{x}}}}}}_k^{\widetilde{l}_r}$

Table 1

Fig 1

Fig 2

Fig 3

Table 2

Comparison of position and velocity estimations for proposed and older algorithms"

Comparison of position estimations for different algorithms according to (56)	Time interval/s	$C\!M\!P_{p\mbox{-}{\rm S\mbox{-}AREV}\; {\rm vs}\; {\rm CA}}$	$C\!M\!P_{p\mbox{-}{\rm S\mbox{-}AREV}\; {\rm vs}\; {\rm AR}}$	$C\!M\!P_{p\mbox{-}{\rm S\mbox{-}AREV}\; {\rm vs}\; {\rm EV2}}$	$C\!M\!P_{p\mbox{-}{\rm AR}\; {\rm vs}\; {\rm CA}}$	$C\!M\!P_{p\mbox{-}{\rm EV2}\; {\rm vs}\; {\rm CA}}$
	0–200	5.423	7.558	8.165	0.978	1.235
	200–400	12.165	10.125	19.267	13.836	2.030 3
	400–600	11.433	2.158 7	9.346 9	2.899	1.469
	600–800	66.229	1.785	85.719	24.919	2.443
	800–1000	23.154	3.458	35.746	19.743	1.584

Comparison ofx-velocity estimationsfor differentalgorithmsaccording to (57)	Time interval/s	$C\!M\!P_{vx\mbox{-}{\rm S\mbox{-}AREV}\; {\rm vs}\; {\rm CA}}$	$C\!M\!P_{vx\mbox{-}{\rm S\mbox{-}AREV}\; {\rm vs}\; {\rm AR}}$	$C\!M\!P_{vx\mbox{-}{\rm S\mbox{-}AREV}\; {\rm vs}\; {\rm EV2}}$	$C\!M\!P_{vx\mbox{-}{\rm AR}\; {\rm vs}\; {\rm CA}}$	$C\!M\!P_{vx\mbox{-}{\rm EV2}\; {\rm vs}\; {\rm CA}}$
	0–200	1.068	1.584	1.021	0.877	1.005
	200–400	1.055	1.615	1.051	0.915	1.154
	400–600	5.401	1.159	5.491	2.651	1.166
	600–800	1.255	1.687	1.548	1.054	1.114
	800–1000	9.762	8.746	9.154	7.119	7.256

Comparison of y-velocity estimations for different algorithms according to (57)	Time interval/s	$C\!M\!P_{vy\mbox{-}{\rm S\mbox{-}AREV}\; {\rm vs}\; {\rm CA}}$	$C\!M\!P_{vy\mbox{-}{\rm S\mbox{-}AREV}\; {\rm vs}\; {\rm AR}}$	$C\!M\!P_{vy\mbox{-}{\rm S\mbox{-}AREV}\; {\rm vs}\; {\rm EV2}}$	$C\!M\!P_{vy\mbox{-}{\rm AR}\; {\rm vs}\; {\rm CA}}$	$C\!M\!P_{vy\mbox{-}{\rm EV2}\; {\rm vs}\; {\rm CA}}$
	0–200	1.178	1.072	0.987	0.824	0.912
	200–400	1.101	1.856	1.142	0.826	1.151
	400–600	6.455	1.106	9.852	2.954	1.002
	600–800	1.167	2.065	1.507	1.007	1.523
	800–1000	10.875	8.166	8.462	8.463	5.451

Table 2

Fig 4

Fig 5

Table 3

References 29

1	LI X R, JILKOV V P. A survey of maneuvering target tracking. Part IV: decision-based methods. Proc. of SPIE Conference on Signal and Data Processing of Small Targets, 2002: 4728-4760.
2	BAR-SHALOM Y, BIRMIWAL K. Variable dimension filter for maneuvering target tracking. IEEE Trans. on Aerospace Electronics Systems, 1982, 18 (5): 621- 629.
3	ZHANG Z, WU Y, SUN W. Modeling and adaptive motion/force tracking for vertical wheel on rotating table. Journal of Systems Engineering and Electronics, 2015, 26 (5): 1060- 1069. doi: 10.1109/JSEE.2015.00115
4	WANG S, DA X, LI M, et al. Adaptive back-tracking search optimization algorithm with pattern search for numerical optimization. Journal of Systems Engineering and Electronics, 2016, 27 (2): 395- 406. doi: 10.1109/JSEE.2016.00041
5	YANG J, LI P, LI Z, et al. Multiple extended target tracking algorithm based on Gaussian surface matrix. Journal of Systems Engineering and Electronics, 2016, 27 (2): 279- 289. doi: 10.1109/JSEE.2016.00028
6	KHALOOZADEH H, KARSAZ A. Modified input estimation technique for tracking maneuvering targets. IET Radar Sonar & Navigation, 2009, 3 (1): 30- 41.
7	MAZOR E, AVERBUCH A, BAR-SHALOM Y, et al. Interacting multiple model methods in target tracking: a survey. IEEE Trans. on Aerospace Electronics Systems, 1998, 34 (1): 103- 123. doi: 10.1109/7.640267
8	FU X, JIA Y, DU J, et al. New interacting multiple model algorithms for the tracking of the maneuvering target. IET Control Theory Applications, 2010, 4 (10): 2184- 2194. doi: 10.1049/iet-cta.2009.0583
9	HO T J. A switched IMM-extended Viterbi estimator-based algorithm for maneuvering target tracking. Automatica, 2011, 47, 92- 98. doi: 10.1016/j.automatica.2010.10.005
10	FOO P H, NG G W. Combining the interacting multiple model method with particle filters for maneuvering target tracking. IET Radar Sonar & Navigation, 2011, 5 (3): 234- 255.
11	BOERS Y, DRIESSEN J N. Interacting multiple model particle filter. IEE Proceeding of Radar, Sonar and Navigation, 2003, 150 (5): 344- 349. doi: 10.1049/ip-rsn:20030741
12	LANEUVILLE D, BAR-SHALOM Y. Maneuvering target tracking: a Gaussian mixture based IMM estimator. Proc. of IEEE/AIAA Aerospace Conference, 2012: 1-12.
13	LAN J, LI X R, JILKOV V P, et al. Second-order Markov chain based multiple-model algorithm for maneuvering target tracking. IEEE Trans. on Aerospace Electronics Systems, 2013, 49 (1): 3- 19. doi: 10.1109/TAES.2013.6404088
14	LI X R. Multiple-model estimation with variable structure. IEEE Trans. on Automatic Control, 2000, 45 (11): 2047- 2060. doi: 10.1109/9.887626
15	YU C H, CHOI J W. Interacting multiple model filter-based distributed target tracking algorithm in underwater wireless sensor networks. International Journal of Control, Automation and Systems, 2014, 12 (3): 618- 627.
16	LI X R, JILKOV V P. Survey of maneuvering target tracking. IEEE Trans. on Aerospace Electronics Systems, 2005, 41 (4): 1255- 1321. doi: 10.1109/TAES.2005.1561886
17	JING L, VADAKKEPAT P. Interacting MCMC particle filter for tracking maneuvering target. Digital Signal Processing, 2010, 20, 561- 574. doi: 10.1016/j.dsp.2009.08.011
18	SINGIRESU S R. Engineering optimization: theory and practice. 4th ed New York: Wiley, 2009.
19	LI X R, JILKOV V P. Survey of maneuvering target tracking. IEEE Trans. on Aerospace Electronics Systems, 2003, 39 (4): 1333- 1364. doi: 10.1109/TAES.2003.1261132
20	SESHADRI N, SUNDBERG C E W. List Viterbi decoding algorithms with applications. IEEE Trans. on Communications, 1994, 42 (2/3/4): 313- 323. doi: 10.1109/TCOMM.1994.577040
21	JIN B, JIU B, SU T, et al. Switched Kalman filter-interacting multiple model algorithm based on optimal autoregressive model for maneuvering target tracking. IET Radar, Sonar & Navigation, 2014, 9 (2): 199- 209.
22	HO T J. A switched IMM-extended Viterbi estimator-based algorithm for maneuvering target tracking. Automatica, 2011, 47 (1): 92- 98. doi: 10.1016/j.automatica.2010.10.005
23	VÄLIVIITA S, OVASKA S J, VAINIO O. Polynomial predictive filtering in control instrumentation: a review. IEEE Trans. on Industrial Electronics, 1999, 46 (5): 876- 888. doi: 10.1109/41.793335
24	XU L, LI X R, DUAN Z, et al. Modelling and state estimation for dynamic systems with linear equality constraints. IEEE Trans. on Signal Processing, 2013, 61 (11): 2927- 2939. doi: 10.1109/TSP.2013.2255045
25	MEYER C D. Matrix analysis and applied linear algebra. Philadelphia: SIAM, 2000.
26	BAR-SHALOM Y, LI X R. Estimation and tracking, principle, techniques and software. Boston: Artech House, 1993.
27	HO T J, CHEN B S. Novel extended Viterbi-based multiplemodel algorithms for state estimation of discrete-time systems with Markov jump parameters. IEEE Trans. on Signal Processing, 2006, 54 (2): 393- 404. doi: 10.1109/TSP.2005.861753
28	HERAB H M, KHALOOZADEH H. Extended input estimation method for tracking non-linear maneuvering targets with multiplicative noises. IET Radar, Sonar & Navigation, 2016, 10 (9): 1683- 1690.
29	RAHMATI H, KHALOOZADEH H, AYATI M. Novel approach for nonlinear maneuvering target tracking based on input estimation. Proc. of the International Conference on Mechanical and Aerospace Engineering, 2012: 4415-4423

Time interval/s	$C\!M\!P_{p-{\rm S\mbox{-}AREV}\; {\rm vs}\; {\rm EKF}}$	$C\!M\!P_{vx-{\rm S\mbox{-}AREV}\; {\rm vs}\; {\rm EKF}}$	$C\!M\!P_{vy-{\rm S\mbox{-}AREV}\; {\rm vs}\; {\rm EKF}}$
0–200	36.32	–5.760	–7.180
200–400	43.06	1.013	0.963
400–600	52.20	12.02	19.490
600–800	67.16	0.897	0.388
800–1000	85.18	7.020	3.260

[1]	Zhuanhua ZHANG, Gongjian ZHOU. Maneuvering target state estimation based on separate modeling of target trajectory shape and dynamic characteristics [J]. Journal of Systems Engineering and Electronics, 2022, 33(5): 1195-1209.
[2]	Yuan ZENG, Wenbin LU, Bo YU, Shifei TAO, Haosu ZHOU, Yu CHEN. Improved IMM algorithm based on support vector regression for UAV tracking [J]. Journal of Systems Engineering and Electronics, 2022, 33(4): 867-876.
[3]	Halil Ersin S¨oken and Chingiz Hajiyev. REKF and RUKF for pico satellite attitude estimation in the presence of measurement faults [J]. Journal of Systems Engineering and Electronics, 2014, 25(2): 288-297.