Journal of Robotics, Networking and Artificial Life, Vol. 2, No. 3 (December 2015), 173-176

A Reduced-Complexity Interacting Multiple Model Algorithm for Location Tracking
in Heterogeneous Observation
Xiaoyan Fu

The College of Information Engineering, Capital Normal University, Beijing Advanced Innovation Center for Imaging
Technology, 100191, P.R. China
Yuanyuan Shang

The Beijing Key Laboratory of Electronic System Reliability Technology, Capital Normal University
Beijing, 100191, P.R. China
E-mail: fuxiaosg@163.com, syy@bao.ac.cn
www.cnu.edu

Abstract
This paper is devoted to the problem of state estimate of discrete-time stochastic systems. A low-complexity andhigh accuracy algorithm is presented to reduce the computational load of the traditional interacting multiple model
algorithm with heterogeneous observations for location tracking. By decoupling the x and y dimensions to simplify
the implementation of location, updated information is iteratively passed based on an adaptive fusion decision.
Simulations show that the algorithm is more computationally attractive than existing multiple model methods.
Keywords: data fusion, interacting multiple model algorithm, location tracking, wireless sensor networks.

1. Introduction
Date fusion deals with the problem of how to extractand utilize useful information contained in multiple setsof data in order to estimate unknown parameters or
1
processes , which has been widely applied in militaryand civilian fields, e.g., target tracking and localization,
air traffic control, guidance and navigation, fault
diagnosis, surveillance and monitoring. Estimation
fusion is one of the important applications involving
wireless sensor networks (WSNs), but the WSNs havevery limited sensing range and communication
bandwidth which restrict the application of thecentralized signal processing method. In other words,
not only are accurate positioning algorithms essential touseful location-estimation systems, but also to reduceenergy consumption is worth developing low2
complexity schemes for WSNs .
State estimate problem of discrete-time Markovian jump
linear system (MJLS) is always the focus of interest in
the community of maneuvering target tracking.
Multiple-model (MM) algorithms (such as generalized
pseudo-Bayesian (GPB), interacting multiple model(IMM), variable-structure MM (SVMM)) are generally
considered as mainstream approach to address thisproblem. Among them, IMM algorithm proposed by3
Blom is most prevalent.
Nevertheless, the high accurate location estimation for
maneuvering target based on the traditional IMM
algorithm requires models interacting and inverse
operations. The location data fusion algorithm with an
IMM technique has high computational complexity, andPublished by Atlantis Press
Copyright: the authors
173

Xiaoyan Fu, Yuanyuan Shang

direct implementation of the IMM algorithm may be toocomplex for practical systems. Moreover, local stationsin WSNs may not be able to afford IMM estimation due
4
to limited computational power . Consequently, it would
be useful to reduce the computational complexity of theIMM algorithm.
Our idea to deal with reduced-complexity state
estimation is to reconstruct the IMM algorithm. In
contrast to the existing reduced-complexity approach
including: alpha-beta filtering, Kalman filtering, ourproposed methods is based on a factor graph (FG) by
decoupling the x and y dimensions to simplify theimplementation of location and adaptive data decision
for state estimation of a MJLS.
2. Background2.1. Model
Consider the dynamic system of tracked target
described with the state space form. The mathematicalmodels on the target can be taken by the following
Markov jump linear system:(1)x(k  1)  Fj x(k )   j  j (k )z ( k )  H j x( k )   j ( k )(2)where the state x(k ) is an n-dimensional vector, theobservation z (k ) is an m-dimensional vector, and thesubscript j  S  {1,2, ,s } denotes the model.
The matrix functions F j ()  j () and H j () are known.
,The model-dependent process noise and measurement
noise are assumed to be a Gaussian random process.
kLet M j denotes the flight model j at time k. The model
dynamics are modeled as a finite Markov chain withknown model-transitions probabilities from model i attime k-1 to model j at time k.
 ij  Pr ob[M kj | M ik 1}  P{M kj | M ik 1}(3)
2.2. Operations of Factor Graphs
In terms of the operations of FG operations, one
advantage of multiplications is the distributive law. For
example, a  b  a  c  a  (b  c) , where the left-handside involves three arithmetic operations, and the righthand side involves only two operations. Furthermore,according to the inherent distributed feature of the belief
propagation algorithm to make the decomposition inaccordance with prediction-correction recursion, themessages of the reliable information are processed andpassed among the prediction phases and correction
5phases with the error propagation law .

Fig. 1. Message passing from node to node
1) Message from Variable Nodes to Factor Nodes:
Assume that each message in the FG flows is a
Gaussian PDF. A message from a variable node to afactor node is the product of incoming messages. For
example, a variable node with two incoming messages
is illustrated in Fig. 1, where a variable node isrepresented by a circle; a factor node is represented by asolid square. In fact, the message from a variable node
to a factor node can be taken as the correction step inBayesian filtering, where the mean is the estimatedresult based on data reliability for location estimationand tracking.
2) Message from Factor Nodes to Variable Nodes: Fortwo continuous variables x and y, the marginal density
function of y is obtained by integrating the joint
distribution over variable x. This operation can be taken
as the prediction step using the Bayesian filtering
approach for location estimation and tracking.
3. Proposed Location Tracking Algorithm
This article focuses on location tracking approaches interms of the X and Y groups individually, and the X andY results of the state and the covariance equations aredecoupled as individual input. Moreover, others
heterogeneous observations can be viewed as individual
input, and corresponding state estimation can beobtained individually. All estimations combined withdata fusion algorithm, which can improve the accuracyof location estimation and tracking.
6
Given the computationally attractive feature of FGs ,this article proposes a location tracking scheme basedon the FG approach and the error for location and speed
estimations to implement the recursive Bayesian

Published by Atlantis Press
Copyright: the authors
174

A Reduced-Complexity Interacting Multiple

estimation and to reduce the computational load of thetraditional IMM algorithm. Furthermore, decoupling theX and Y dimensions for different tracking groups also
can reduce the computational complexity. Therefore, the2-D problem is reduced to two 1-D problems. The 2-Dproblem can be represented by two independent maingroups, the X-coordinate and the Y-coordinate groups.
7
According to the concept of undirected graph model ,the representation related to estimate speed and locationof the X-coordinate group is illustrated as the blackcolor diagram in Fig. 2, where a correction node isillustrated by a circle; a prediction node is illustrated bya solid square.

sx0 j (k | k)   i| j (k | k ) N (x ik 1 ;Sxk 1 , Vxk 1 )(5)i 1sx0 j (k | k)   i| j (k | k ) N (x ik 1 ;Sxk 1 , Vxk 1 )(6)

Step3: Filtering（j  ）Prediction statex j (k | k  1)  N oper 3 ( x j (k | k  1); S x0 j ( k |k ) ,Vx0 j ( k |k ) )(7)

x j (k | k  1)  N oper 2 ( x j (k | k  1); S x0 j ( k |k ) ,Vx0 j ( k |k ) )

(8)

i 1

Correction state

x kj  N oper1 ( x kj ;Sx j (k|k 1) , Vx j ( k |k 1) )(9)x  N oper1 ( x ;Sx j (k|k 1) , Vx j ( k |k 1) )

(10)

kj

kj

Step4: Combine the state estimates and corresponding covariance according to the updated weightssxI (k)    kj N (x kj ;Sxk , Vxk )

(11)

j 1
sxI (k)    kj N (x kj ;Sxk , Vxk )

(12)

j 1

Updated weight of model M kj is kjFig. 2. Graph model of the data-fusion location estimation for
X-coordinate group from the kth to (k+1)th.

The measurement model based on IMM algorithm is thesituation that the error propagation law can be applied to
the linear dynamical system, and then the proposed
IMM algorithm based on factor graphs (IMM-FG) for
location estimation and tracking are illustrated in thefollowing part.
Step 1: Calculate the mixed initial probability for thekfilter m-atched to model M（j j ）i | j ( k | k )P{M ik 1 M kj , z0:k 1}==

P{M kj M ik 1 , z0:k 1}  P{M ik 1 z0:k 1}
P{M kj z0:k 1}

 ij ik 1cj(4)i, j 

where c j is the normalization constant.
Step 2: Calculate the mixed initial state and corresponding covariance for the filter matched to modelkM（j j ）P{M kj Z k }=decision[P{M kj z1, k , s1, k }, P{M kj z2, k , s2, k },P{M kj s*, k }]=decision[  xk, j ,  yk, j , *,k j ]where xk, j (13)P{z x , k M kj , z0:k 1}  P{M kj z0:k 1}c
N [ z x , k ;Sx0 j (k|k) , Vx0 j (k|k) ]  c j(14)cIt's worth mentioning that decision [.] refers to adecision-making or data fusion process, for example,
mean[.], max[.], min[.] or more intelligent decision,different location and tracking problems can adopt
different data fusion for better tracking accuracy.
4. Simulation Results
In this section, we evaluate the performance of IMMFG algorithm, and the classical IMM algorithm using
the target tracking example. The results are obtained
from 100 Monte Carlo runs. The X position and velocity
RMSE are shown in Fig.3 and Fig.4, respectively. The Yposition and velocity RMSE are omitted due to limited
space. It can be found that accuracy estimate of thePublished by Atlantis Press
Copyright: the authors
175

Xiaoyan Fu, Yuanyuan Shang

IMM algorithm as nearly as the proposed IMM-FG
algorithm in almost time. Although IMM-FG algorithm
has a higher position estimate error than IMM algorithm
during the second maneuvering (time samples 61-66),
the estimate error converges to zero within a short time.
The occurrence of this phenomenon maybe due to that
the IMM-FG algorithm pays more attention to the rapidchange of the velocity during the high maneuvering. On
the whole, the estimation accuracy of the IMM-FG
algorithm is almost the same with the classical IMM
algorithm, but the computing time is short. It can beverified through the comparison computing time
between IMM and IMM-FG given in Table 1.

It is principally similar to the popular IMM algorithm.
The difference lies in the use of filtering. To avoid theinverse of covariance matrix and reducing thecomplexity of tracking algorithm, the FG algorithm andthe idea of decoupling the X and Y dimensions tosimplify the implementation of location estimation andtracking is induced to construction of IMM algorithm.
Computer simulations indicate that the IMM-FG
algorithm has almost the same tracking accuracy with
the IMM algorithm.
Acknowledgements
This work was supported by the NSFC (11178017,61373090, 61303104, 61203238) and the BNSFC(4132014).
References

Fig. 3. X position RMSE versus time step.

Fig. 4. X speed RMSE versus time step
Table1. Computing time between IMM and IMM-FG

50 Monte Carlo runs
100 Monte Carlo runs

IMM
1.37672.4825IMM-FG
1.12282.1691

5. Conclusion
The conclusion comes here. In the paper, IMM-FG
algorithm is presented for maneuvering target tracking.

1. D.Jeon, E. Yeonju and K. Hyounkyoung, ”Estimation
fusion with radar and ADS-B for air traffic surveillance”,
Information Fusion, 16th International Conference on,
2013, pp. 1328-1335
2. C.L.Wang, Y.S.Chiou and F.Tsai,”Reduced-complexity
tracking scheme based on adaptive weighting for location
estimation ”, IET communications, 2012, pp. 673-684.
3. Blom, H.A.P., Bar-Shalom, Y.,”The interacting multiple
model algorithm for systems with Markovian switchingcoefficients”, IEEE Transactions on Automatic Control,
1988, 33, (8), pp. 780–783.
4. Y.X. Gao, X.R. Li and Z.S. Duan, ”Estimation Fusion for
MarkovianJump
LinearSystemvia
Data
Transformation”, IEEE Transactions on Aerospace andElectronic Systems, vol. 50, no. 1, pp. 240-253, Jan.2014
5. Y.S. Chiou and F. Tsai, ”A Reduced-Complexity DataFusion Algorithm Using Belief Propagation for Location
Tracking in Heterogeneous Observations”, IEEETransactions on Cybernetics, vol. 44, no.6, pp. 922-935,Jun. 2014
6. C.L. Wang, Y.S. Chiou, and F. Tsai, ”Reducedcomplexity tracking scheme based on adaptive weighting
for location estimation”, IET Communication,vol. 7, no.
7, pp. 673C684, May. 2013
7. Y.-S. Chiou, F. Tsai, C.-L. Wang, and C.-T. Huang, ’A
reduced-complexity scheme using message passing forlocation tracking,’EURASIP J. Adv. Signal Process ., vol.
2012, Jun. 2012.
8. Ho, T.J., Farooq, M.: ’Comparing an interacting multiple
model algorithm and a multiple-process soft switchingalgorithm’.Information Fusion, 2000. pp. 17-24.

Published by Atlantis Press
Copyright: the authors
176