An Algorithm of the Adaptive Grid and Fuzzy Interacting Multiple Model

Yuan Zhang, Chen Guo, Hai Hu, Shubo Liu and Junbo Chu

1. College of Information Science and Technology, Dalian Maritime University, Dalian 116026, China 2. Department of Missile, Dalian Naval Academy, Dalian 116018, China

1 Introduction1

The maneuvering target tracking algorithms can be divided into the single model algorithm and the multiple model algorithm. Because the target motion character often changes while the target is maneuvering, it is difficult to describe the motion state accurately by only using a single model. The multiple model algorithm appears in this situation. It was initially presented by Magill while studying the optimal adaptive estimation (Yin, 2008). The development of the multiple model algorithm has experienced three generations (Zhang, 2010; Liuet al.,2009). The features of the first generation include the models’ number in the model set being fixed, and each basic filter runs alone independent of the other filters. The models’ number of the second generation (including the interacting multiple model, IMM) algorithm is also fixed,but there is interaction among the models (Zhen and Lang,1998; Wu and Li, 2009; Wu and Cheng, 1994; Tanjan, 2011;Gaoet al., 2012; Yi and Lv, 2006; Gonget al., 2010). Both the model sets of the first two generations have fixed members at different times, so they are called fixed structure multiple model (FSMM) algorithms. The models’posterior probability of the standard IMM algorithm is calculated through the models’ priority probability and the Markov transition probability. Instead of using the normal interacting method, this paper details the use of an intelligent interacting method to solve the problem of the higher calculation complexity of the model interacting probability in the standard IMM algorithm.

The FSMM algorithm has obvious defects. In reality, it’s usually not enough that the target maneuvering mode is only described by a few models, especially with multidimensional systems. But the increasing number of models will not only increase the amount of calculations,but will also not necessarily improve tracking performance.Too much detailed split model space may also damage the required model independence of Bayes reasoning. To solve the existing problems of the FSMM algorithm, the third generation multiple model algorithm, the variable structure multiple model (VSMM) algorithm (Leiet al., 2010; Zeng and Peng, 2012) appears, which has a variable model set. At the present time, there are not so many documents regarding the VSMM algorithm. The VSMM algorithm is composed of two parts: the model set adaptation (MSA) and the model set sequence’s condition estimation, in which the former is the most critical part. Three kinds of model set adaptation methods are presented: the model group switch (MGS) ( Liet al., 1999b), the likely-model set (LMS) ( Li and Zhang,2000) and the estimated mode augmentation (EMA). The corresponding realization methods of these three adaptive strategies based on the diagraph theory are as follows (Li and Jilkov, 2005): digraph switching (DS) (Huang, 2010;Huang and Peng, 2010; Xuet al., 2003), the adaptive digraph (AD) (Lu, 2010) and the adaptive grid (AG)( Chen,2008; Liet al., 1999a; Vahabianet al., 2004; Wanget al.,2003).

This paper mainly studies a variable structure interacting multiple model algorithm for the maneuvering target tracking based on adaptive grid and fuzzy interaction, which is called the adaptive grid and fuzzy interacting multiple model (AGFIMM) algorithm. The two-dimensional simulation results demonstrate the validity and superiority of this algorithm.

2 The establishing of the maneuvering target’s models

The system equations are usually described as follows:

When the target isn’t maneuvering, we can obtain the optimal estimation of the target’s position and velocity using the Kalman filter. And when the target is maneuvering,it can cause the mismatch between the model and the target’s motion mode because we cannot determine when and how the target begins maneuvering. As a result, the estimation is no longer optimal, which demands adjustment to the model through adjustingFkin Eq. (1), since the state transfer matrixFkis different in different models.

For the turn motion model,Fkin Eq.(1) is as Eq. (3):

In Eq.(3),Tis the sampling period, andjwis the turn rate.

For the straight-line motion model, we havewj? 0,in this situation,Fkin Eq. (1) is as follows:

The transitions between the straight-line motion model and the constant turn rate motion model can be realized through setting different turn rates for the turn motion model. So as a result, with the IMM algorithm, we can describe the different maneuvering forms using the combination of the straight-line motion model and the constant turn rate motion model.

3 Algorithm of the adaptive grid and fuzzy interacting multiple model

3.1 Steps of the algorithm

The calculation steps of the AGFIMM algorithm are as follows:

Step 1: Input interaction.

where:

For each model, the covariance matrix of the initial state vector after mixing is:

Step 2: State vector updating of the matching model.

If we adopt the Kalman filter, then the Kalman filter equations provide the state vector’s updating calculation for modelMj(k).

a) The state vector’s prediction:

b) The covariance matrix of the state vector’s prediction error:

c) The innovation vector:

d) The covariance matrix of the innovation vector:

e) The filtering gain vector:

f) The state vector’s estimation:

g) The covariance matrix of the state vector’s estimation error:

Step 3: Fuzzy inference of the model posterior probability( See 3.2 of this paper).

Step 4: Output interaction.

The output vector (state vector’s estimation) and its covariance matrix are shown as Eqs.(16) and (17)respectively.

Step 5: Adaptive grid adjustment of the model set (See 3.3 of this paper).

The following focuses on the design of the fuzzy inference system of model posterior probability and the adaptive grid adjustment algorithm of the model set.

3.2 Design of the fuzzy inference system of model posterior probability

This paper uses the method of fuzzy inference, taking the weighted quadratic function of the measurement innovation as the input, and obtains the matching degree of each model in the model set which substitutes the model posterior probability calculation in the standard IMM algorithm. So there is no need to calculate the model priority probability or the Markov transition probability with the IMM algorithm, and thus reduces the complexity of the algorithm.

3.2.1 Calculation of the model inference system’s input

(1)理想整體發(fā)電效率隨負(fù)荷增加而單調(diào)增大。由于給水流量波動(dòng)導(dǎo)致的實(shí)時(shí)參數(shù)滯后，以及環(huán)境溫度對(duì)背壓和發(fā)電效率的影響，直接空冷機(jī)組的實(shí)際整體發(fā)電效率、汽輪發(fā)電機(jī)整體效率、汽輪機(jī)理想循環(huán)熱效率隨負(fù)荷增加并未表現(xiàn)出明顯單調(diào)遞增的規(guī)律。

Taking modeljin the model set as the example,according to the model filtering results, we can not only get the target’s current state vector’s estimation and its error covariance matrix, but we can also get the measurement innovation vectorvjand its covariance matrixjSof modelj. The input of the fuzzy inference system is defined as follows:

In the above formula,Ejis the normalized variance,subject to2cdistribution of 1 degree of freedom,andMis the model number of the model set.

3.2.2 Calculation of the model matching degree

The input variable of the fuzzy inference system isEj,with fuzzy subsets including S(small), M(medium) and B(big). We choose the Gauss function as the membership f unction ofthefuzzysubsets according to the character of the input functionEj,shown asFig. 1.The output variable is the model posterior probability

jm. Similarly, we define the same fuzzy subsets as S(small),M(medium) and B(big), adopting the trigonometric function as the membership function in the output space of the fuzzy inference system, shown as Fig. 2.

Fig.1 Membership function of the inputs

Fig. 2 Membership function of the outputs

Then according to the inference feature of the fuzzy inference system, some fuzzy rules of the models’ matching degree can be received as follows:

Based on these fuzzy rules, we can obtain the normalized fuzzy matching degreemj?[0,1] of modeljat timekthrough the fuzzy inference system.

3.3 Adaptive grid adjustment of the model set

Based on the maneuvering target’s models described in section 2 of this paper, taking the continuous interval of the turn rate as the model set’s grid, the design of the adaptive grid adjustment algorithm is as follows. Supposing the current turn rate of the maneuvering target is in the continuous range [ -wmax,wmax], we construct an FIMM algorithm of three time-varying models, whose model set at timekisM(k)=? [-wmax,wmax],and

Assuming this algorithm begins to initialize from, we adjust the turn rate through the adjustment of the grid center and the grid interval from timekto timek+1 .

3.3.1 Adjustment of the grid center

The adjustment of the grid center is shown as formula(19).

3.3.2 Adjustment of the grid interval

The adjustment of the grid interval is divided into three cases of non jump, left jump and right jump.

a) Non jump.

WhenmkC=, the adjustment strategy ofare shown as formulas (20) and (21).

In the formulas,1tis the impossible model’s probability threshold,wdis the least grid interval.

b) Left jump.

When, the adjustment strategy ofare shown as formulas (22) and (23).

wheret2is the important model’s probability threshold.

c) Right jump.

4 Simulation results and analysis

In order to verify the performance of the AGFIMM algorithm, we compared it with the IMM3 and IMM7, and the IMMn(n=3,7) represents the standard IMM algorithms whose model sets are composed of 3 and 7 fixed models respectively.

Assuming that the target’s motion is in theX-Yplane, and that the scenario is as follows (Zhanget al., 2011; Guoet al.,2011): The initial position is (3,000 m, ?1,000 m), the initial velocity is 59 m/s (the angle with thex-axis is 45°), and the simulation time is 200 s. The simulation trajectory consists of 5 segments. Segment 1, constant velocity motion; segment 2, turn right with a constant turn rate ofω=0.02 rad/s; segment 3, constant velocity motion; segment 4, turn left with a constant turn rate ofω=0.05 rad/s and segment 5, constant velocity motion.

During the simulation, the model sets are{w=-1°/s，w= 0°/s，w= 1°/s}and {w=-3°/s，w=-2°/s，w=-1°/s，w=0°/s，w=1°/s，w=2°/s，w= 3°/s} respectively in the IMM3 and IMM7 algorithms,and the filtering algorithm is the standard IMM algorithm.The IMM model transition probability of the IMM3 algorithm isp=[0.7,0.2,0.1;0.2,0.7,0.1;0.1,0.2,0.7], and the IMM model transition probability of the IMM7 algorithm is, wherepii=0.9,i=1,7;pii-1=0.1,i=2,…,7;pii+1=0.1,i=1,…,6. The measurement noise is the Gauss noise of zero mean, and its standard deviation is

The model set of the AGFIMM algorithm is composed of three models at any given time, and the model interaction probability is received from the fuzzy logic inference system. The impossible model’s probability thresholdt1=0.2,the important model’s probability thresholdt2=0.92, and the least grid intervaldw= 0.5°.

We conducted the Monte Carlo simulation 100 times for each algorithm with a sampling periodT=1s. The position and velocity RMSE simulation results of the IMM3, IMM7 and AGFIMM algorithm are shown in Table 1. The position and velocity RMSE (root mean squared error) simulation curves of the IMM3 and AGFIMM algorithm are shown in Figs. 3-6.

Table 1 100 times Monte Carlo simulation results of RMSE

Fig. 3 The position RMSE curve of X direction

Fig. 4 The position RMSE curve of Y direction

Fig. 5 The velocity RMSE curve of X direction

Fig. 6 The velocity RMSE curve of Y direction

From Figs. 3-6 and Table 1, we can draw conclusions as follows:

1) Although both AGFIMM and IMM3 algorithm use a model set composed of three models, the tracking precision of AGFIMM algorithm has been obviously improved compared with IMM3 algorithm.

2) Although the tracking precision of AGFIMM is similar to IMM7’s ( the tracking precision of the former has been slightly increased compared with the latter), AGFIMM algorithm uses the model set composed of three models,while IMM7 algorithm uses a model set composed of seven models. The computational complexity of AGFIMM algorithm has been reduced compared with IMM7 algorithm.

In conclusion, AGFIMM algorithm can significantly improve the tracking precision compared with FSMM algorithm, when the same number of models are used. In order to reach the same tracking precision of AGFIMM algorithm, FSMM algorithm must use 2~3 times’ number of models, and thus increase the complexity of calculation. In a word, AGFIMM algorithm needs less models, smaller computational complexity and improves the cost-efficiency ratio of the multiple model algorithm.

5 Conclusions

This paper mainly studies a variable structure interacting multiple model algorithm for the maneuvering target tracking based on adaptive grid and fuzzy interaction, which solves the existing problems of FSMM algorithm. In FSMM algorithm, when the model set has less models, it can not completely cover the target’s all kinds of maneuvering mode, which can cause the decrease in accuracy; When the model set has more models, it can cause the calculation burden and unnecessary competition among models, and thereby reduce the cost-efficiency ratio of the algorithm.

The Monte Carlo simulation results indicate that AGFIMM algorithm presented in this paper can significantly reduce the number of models, effectively reduce the computational complexity, improve the tracking accuracy, and be suitable for engineering applications.

Chen X (2008).The target tracking based on variable structure multiple model algorithm. M.S.degree thesis, Detection Technology and Automation Equipment, Nanjing Science and Technology Univercity, Nanjing, 13-14.(in Chinese)

Gao L, Xing JP, Ma ZL, Sha JC, Meng XZ (2012). Improved IMM algorithm for nonlinear maneuvering target tracking.2012 International Workshop on Information and Electronics Engineering, Harbin, 4117-4123.

Gong S, Wu HL, Tao C, Huang SG. (2010). Tracking maneuvering target on airport surface based on IMM-UKF algorithm.International Conference on Optoelectronics and Image Processing,Haiko, 671-675.

Guo YF Zhang X, Lin XY (2011). Low altitude maneuvering target tracking with acoustic network based on DS-VSMM.Opto-Electronic Engineering, 38(8), 1-7. (in Chinese)

Huang XY (2010).Highly maneuvering target tracking algorithm based on variable structure multiple-model algorithm. M.S.degree thesis, Pattern Recognition and Intelligent, Electron Science and Technology University of Hangzhou, Wu han, 36-37. (in Chinese)

Huang XY, Peng DL (2010). A VSMM algorithm based on unscented digraph switching for maneuvering target tracking.Opto-Electronic Engineering, 37(12), 30-34.(in Chinese)

Lei SW, Wu CL, Sun W (2010). A method of adaptive maneuvering target tracking based on VSMM.Modern Rada,32(6), 54-58.

Li XR, Jilkov VP (2005). Survey of maneuvering target tracking.Part V: Multiple-model methods. IEEE Transactions on Aerospace and Electronic Systems, 41(4), 1297-1298.

Li XR, Zhi XR, Zhang YM (1999a). Multiple-model estimation with variable structure. Part III: Model-group switching algorithm.IEEE Transactins on Aerospace and Electronic Systems, 35(1), 225-241.

Li XR, Zhang YM, Zhi XR (1999b). Multiple-model estimation with variable structure. Part IV: Design and evaluation of model-group switching algorithm.IEEE Transactins on Aerospace and Electronic Systems, 35(1), 242-254.

Li XR, Zhang YM (2000). Multiple-model estimation with variable structure. Part V: likely-model set algorithm.IEEE Transactins on Aerospace and Electronic Systems, 36(2), 448-466.

Liu GF, Gu XF, Wang HN (2009). Design and comparison of two MM algorithms for strong maneuvering target tracking.Journal of System Simulation, 21(4), 965-968.

Lu JY (2010).The Research on IMM tracking algorithm of high speed and high maneuvering target. M.S.degree thesis, Guidance,Guidanuce and Control, Nanjing Science and Technology Univercity, Nanjing, 43-44. (in Chinese)

Tanjan H (2011). A switched IMM-extended Viterbi estimatorbased algorithm for maneuvering target tracking.Automatica,47, 92-98.

Vahabian A, Sedigh AK, Akhbardeh A (2004). Optimal design of the variable structure IMM tracking filters using genetic algorithms.

Proceeding of the 2004 IEEE International Conference on Control Applications, Taipei, 25-27.

Wang XZ, Subhash C, Rob E (2003). Variable structure IMM using minimal sub-model-set switching.Proceedings of SPIE, 80-91.

Wu PL, Li XX (2009). Passive multi-sensor maneuvering target tracking based on UKF-IMM algorithm.WASE International Conference on Information Engineering, Taiyuan, 135-138.

Wu WR, Cheng PP (1994). A nonlinear IMM algorith for maneuvering target tracking.IEEE Transactions on Aerospace and Electronic Systems, 30, 875-885.

Xu JH, Ji CX, Zhang YS, Chen K (2003). Digraph switching IMM algorithm based current statistical mode.Fire Control >amp; Command Control, 28(2), 52-56.

Yi L, Lv M (2006). Research method for tracking high speed and highly maneuvering target.6th International Conference on ITS Telecommunications Proceedings, Chengdu, 1236-1239.

Yin HB (2008).The research on radar maneuvering target tracking filter algorithm. M.S.degree thesis, Communication and Information System, Dalian Maritime University, Dalian,50-51.(in Chinese)

Zeng D, Peng DL (2012). Adaptive variable structure multiple model algorithm for high maneuvering target tracking.

Computer System Application, 21(10), 114-117.

Zhang AQ, Wang WS, Zheng RG, Lv J (2011). Research on non-linear filter for naval vessel radar target tracking.Ship Science and Technology, 33(4), 98-101.

Zhang M (2010).Variable structure multiple model estimation based on particle filter.M.S.degree thesis, Communication and Information System, University of Science and Technology of China, Hefei, 10-12. (in Chinese)

Zhen D, Lang H (1998). A distributed IMM fusion algorithm for multi-platform tracking.Signal Processing, 64,167-176.