Both air traffic control and military applications have strict requirements
on tracking algorithms. They should be accurate, survivable and fault tolerant
and should require low computation and communication complexity. A lot of research
work has been devoted to investigate tracking algorithms that fulfill the requirements
of modern surveillance. Many works have proposed the use of variable update
rate trackers to reduce the computation processing. However, most of them use
single model filters and decisions oriented techniques and cannot, therefore,
cope well with all possible target behaviors. For a better tracking accuracy,
it is necessary to recourse to multiple models algorithms. Many of these algorithms
have been developed, among which the Interacting Multiple Models (IMM) (Bar
Shalom, 1995) is widely used. The main feature of this algorithm is its
ability to estimate the state of a dynamic system, which can switch from one
behavior mode to another.
For a real time implementation, data processing is an important issue. Many
researchers have focused on reducing the computation time. A moving bank multiple
models adaptive algorithm has been proposed by Mayback and Hentz (1987). Li
and Bar-Shalom (1996) introduced the idea of multiple models sets and presented
a variable structure multiple model algorithms. Lin and Atherton
(1993)presented a selected filter IMM (SFIMM) algorithm in which models
close to target acceleration are selected. Hong (1999),
Hong and Dig (2000) and Hong et
al. (1998 ) presented a Multirate Multiple Model (MRIMM) algorithm that
uses a multi-resolution filtering approach, where each model works with a rate
appropriate to a motion of the target.
In fact, Time is the most precious resource for real time application, especially when using multi function radar, such as a Phased Array Radar, whose occupancy by the tracking task should be kept as low as possible.
The Phased Array Radar has the ability to direct the antenna beam in any direction without moving mechanically the radar. It performs surveillance in a number of regions, to identify new targets; it then maintains tracks on the targets by directing the beam to the predicted target position, for each updated track. Each track may be updated at a variable rate.
Many approaches have been proposed for selecting the next update time. Some
approaches (Efe and Atherton, 1998; Kirubarujan
et al., 1995; Daeipour et al., 1994;
Efe and Atherton, 1996) select the next update time from
a set of a predefined update times and assign one of these to each track, so
that the track is maintained over a target trajectory. Usually, a high update
rate is chosen for a manoeuvring motion and a lower update rate is chosen for
a non manoeuvring motion. Another approach (Sarunic and Evan,
1997) uses an iterative selection of the next update time, whereas Van
Keuk (1977, 1979), Watson (1994)
and Shin (1995) an empirical form is used. In Ahmeda
et al. (1997), an exact formula for computing the next update time
in the JPDAF is derived, using on the Van Keuk criterion. This formula has been
generalised to the IMMJPDAF in Benoudnine et al. (1999a,
In Benoudnine et al. (2006), a Fast AIMM algorithm
(FAIMM algorithm), which computes the next update time by using the probabilities
of action of models is presented. A considerable amount of computational time
is saved, by this algorithm, in comparison with the AIMM that uses the Van Keuk
criterion. In Benoudnine et al. (2007), the incorporation
of a variable update time into the MRIMM improved the performance of this algorithm.
This study describes in more details the work presented in Benoudnine
et al. (2006, 2007). Its also presents new
TARGET AND SYSTEM MODELS
The problem addressed in this paper is the estimation of the state (position,
velocity and acceleration) of a target moving in a plane. The motion of the
target is assumed to obey several possible models. The discrete state equation
for such a target is:
xj (k+1) = Fj (k)
xj (k)+wj (k), j = 1,
where, xj (k) is the state vector of the target, Fj (k)
is the transition matrix and wj (k) is the process noise, assumed
to be a zero mean Gaussian process with a known covariance Qj. All
these quantities are at time k and for model j.
The measurement equation is given by:
z(k) = Hj (k)xj
where, z(k) is the (m×1) measurement vector at time k, due to the return from
the target, Hj is the (mxn) measurement matrix for model j and v
is the measurement noise vector, with zero mean and known covariance R.
DESCRIPTION OF TRACKING ALGORITHMS
IMM algorithm: The Interacting Multiple Models (IMM) algorithm has been
proposed for tracking a manoeuvring target (Bar Shalom, 1995).
It is a sub-optimal well documented method for solving the problem of state
estimation, in the case of a manoeuvring target. In this algorithm, several
filters are run in parallel, each filter being matched to an assumed model for
the targets motion. The jumps between models are assumed to be governed by
a Markov Chain. The overall estimated state is formed by summing the estimates
from different filters, weighed by the probabilities of models. The IMM consists
of the following steps:
Step 1: Mixing of state estimates from the previous time: For
each target, starting with the state estimates
matched to the models Mj(k), their covariances and
the model probabilities μi/j(k-1|k-1), the mixed state estimate
its covariance are
computed according to:
where, r denotes the number of interacted models and μi/j (k-1|k-1)
is the probability that model Mi was in effect at time (k-1) given
that Mj is in effect at time k-1, conditioned on zk-1,
the set of measurements up to k-1:
In the above equation, pij is the a prior probability of transition
from model i to model j, μi(k-1) is the probability that model
i is in effect at time k-1 and
are normalising constants:
Step 2: Kalman filtering: Based on the initial states estimates Eq.
3, their covariances Eq. 4 and the received measurements,
the state estimate and
its covariance are
updated using the jth Kalman Filter in the IMM algorithm.
Step 3: Computation of the likelihood function: The likelihood Λj(k)
of model Mj(k) is updated from:
Step 4: Update of the models probabilities: The probability that model
Mj(k) is in effect at time k is computed from:
defined in Eq. 6 and c is the normalisation constant for
μj(k) given by:
Step 5: Combination of the model conditioned estimates: For each target,
the overall state estimate and
its corresponding error covariance are
updated as follows:
MRIMM algorithm: The Multirate IMM (MRIMM) algorithm is derived by Hong
et al. (1998), at different multi-resolution levels, by using a discrete
wavelet transform, a hierarchy of models and a data structure. The tracking
algorithm is applied to this hierarchical structure and final tracking outputs
can be obtained at specified levels (rates). In Fig. 1 a diagram
of one cycle of a two models MRIMM algorithm is presented. In the algorithm
considered in this work, the first model is a constant acceleration (CA) model.
It operates at full rate (level 0) and is suitable for a manoeuvring motion.
The second model, named half rate Multirate Constant Velocity (MRCV) model,
was derived by Hong (1999) and Hong
et al. (1998) from a geometrical interpretation of a discrete wavelet
transform. It operates at half rate (level 1) and is appropriate for a non-manoeuvring
motion. The superscript ()m is used to denote a quantity related
to the manoeuvring model (CA) and ()n a quantity related to the non
manoeuvring model (MRCV). The measurements and state for the non manoeuvring
model are processed at level 1, whereas for the CA model the state and the measurements
are processed at level 0. The results from the two models are mixed and combined
at the same level (level 0 is used here).
||A Two- model, two- level MRIMM algorithm
Transformation details of non manoeuvring
quantities between level 0 and level 1 are given in Hong
(1999), Hong et al. (1998) and (Hong
and Ding, 2000). The main steps of the MRIMM starting at tk-2 and ending at tk consist of the following.
Step 1: Mixing of state estimates from the previous time: Assuming that
the state estimates and their covariances matched to each model at level 0
are available at time tk-2, the multirate models probabilities and
the multirate states are derived as follow:
the non manoeuvring and the manoeuvring mixing Multirate model probability at
is the Markovian model probabilities transitional matrix, which defines the transition between the two models.
The mixed half rate and full rate state vectors are then derived as:
The corresponding mixing multirate covariances are derived in the same way.
Step 2: Transformation of the non maneuvering quantities: The initial
state estimate and its covariance for the MRCV model are transformed to level
1, to yield (details
transformation can be found in Hong (1998, 1999)
and Hong and Ding (2000).
Step 3: Multirate propagation
||Full rate propagation from for
the maneuvering model is derived using the following equation:
The state is composed of position, velocity and acceleration, for example in
one dimensional Cartesian coordinates is:
||Half rate propagation from to
tk for the non maneuvering model is derived using the following
the predicted state estimate at level 1 composed of low and high component of
are, respectively, the two taps Haar low pass and high pass filters coefficients,
for Wavelet decomposition.
Step 4: Propagation of the manoeuvring model: The propagation from to
tk for the manoeuvring model is given by:
Step 5: Updating at time tk: A full rate update is performed
on the manoeuvring model sequence, yielding The
half rate updates are
transformed to level 0 to yield the non manoeuvring states and covariance vectors
Also the probabilities of models are updated at time tk yielding .
The output of MRIMM algorithm at time tk is then:
REVIEW OF SOME ADAPTIVE UPDATE TIME METHODS FOR PHASED ARRAY RADAR
Criteria for the update time choice: The next update time is calculated,
according to some technical considerations:
||To maintain track in different situations (manoeuvring and non manoeuvring),
the update time should be small enough so that, at the next illumination,
the target will be within the predicted region, scanned by the radar beam,
with a high enough probability
||The update time should be not too small, to minimise the use of the radar
resources. This will allow the radar to do more within a given time
Hence, a large update time should be used for tracking a non manoeuvring target
and a faster update is needed to track a manoeuvring target or fast targets,
which accelerate harder or change range and which may possibly escape from the
beam of the antenna.
Most of the algorithms proposed in the literature for the selection of the next update time are based on Van Keuk criterion.
Van keuk criterion: It can be observed, in any target tracking algorithm, that when the target manoeuvres, the uncertainty in the estimates increases, this is reflected by an increase in the value of the error covariance. One can exploit this observation, for selecting the sample time: Reducing it when the target manoeuvres, not to lose its track and increasing it when the target stops manoeuvring, not to waste radar resources.
This is the idea behind the Van Keuk criterion (Van Keuk,
1977, 1979), who proposed that the next update time
should be selected so that the predicted error variance in position is kept
under a given threshold. Based on this criterion an empirical formula for calculating
the next update time T has been derived:
where, v0 is a constant, is
the measurement error covariance, τm is the manoeuvre correlation
time and is
the covariance of target acceleration.
However, Van Keuk uses a single model to update a track. Many researchers;
Watson et al. (1994), Shin
et al. (1995) and Benoudnine et al. (1999a,
b) have extended the use of Van Keuk criterion to multiple
models based tracking algorithms.
Revisit time controlled using the IMM algorithm: In this algorithm (Watson,
1994), three models are used in the IMM for tracking a manoeuvring target.
The first one is a Constant velocity model (CV), the second one is Exponentially
Increasing Acceleration (EIA) and the third one is a three Dimensional Turning
Rate (3DTR). The next update time is scheduled when the predicted error covariance
in position exceeds a given threshold. The sample time, T, is computed such
the errors covariance of the predicted position and a
threshold. Since is
a matrix and T is a scalar, the trace operator Tr is introduced and T is computed
with T. T is chosen from the condition:
The sample time is determined by solving Eq. 28, using
Newtons methods and choosing the next update time to be the maximum of the
Adaptive update rate control in the IMM algorithm: The detection probability
of the target is dependent on the accuracy of the beam pointing, which depends
on the accuracy in the target position prediction. Shin et
al. (1995) integrate the Van Keuk criterion and use the empirical formula
Eq. 25 to update the next update time in the IMM algorithm.
The IMM is used to estimate the manoeuvre parameter δm:
where, μj (k) is the probability of model j at time k, r is
the total number of models used in the IMM and is
the assumed acceleration covariance for model j.
Adaptive IMM algorithm (AIMM): This algorithm uses the IMM, with two
models: Constant Velocity (CV) and Constant Acceleration (CA) (Benoudnine
et al., 1999a, b). The tracking is made in
2 Cartesian co-ordinates (x, y). A variable update time is incorporated into
the IMM algorithm using the Van Keuk (1977, 1979)
method. For the x direction, the update time Tx(k) at the kth scan
is determined from:
the (1,1) element of the predicted covariance matrix, [R]11 is the
measurement variance in the x direction and v0 is a constant.
The expression for the (1,1) element of the predicted covariance matrix is
where, μj(k|k-1) is the predicted probability of model j:
In Eq. 31 Fj and Qj denote the transition
matrix and the process noise covariance matrix, both matched to model Mj.
It can be shown from Eq. 30-31 that
a bi-quadratic polynomial in Tx(k) whose coefficients depend on the
elements of the matrices ,
the variances of the process noises used in the models, the components of the
initialisation state vectors and
the predicted model probabilities μj(k|k-1). The next update
time Tx(k) can then be determined by zeroing the bi-quadratic polynomial
and taking the maximum real and positive root.
Similarly, the update time Ty(k), for the y direction, can be obtained
by solving the following equation:
the (4,4) element of the predicted covariance matrix and [R]22 is
the measurement variance in the y direction.
The update T(k) at the kth scan is taken as the time which guarantees a minimum for the position covariance error in x and y.
Fast adaptive IMM algorithm (FAIMM): In Benoudnine
et al. (2006), a Fast Adaptive IMM algorithm (FAIMM) was proposed
to select a next update time, which is appropriate to the motion of the target.
In this algorithm, two models are used: (CV) and (CA). We assign to each model
in the IMM a suitable rate: Tmax to the non manoeuvring model and
Tmin to the manoeuvring model. Then, the next update time at scan
k is obtained by computing the following mean:
where, μj(k) is the probability of model j at time k, r is equal to 2, T1 = Tmax and T2 = Tmin.
Adaptive MRIMM algorithm (AMRIMM): In Benoudnine et
al. (2007), a variable update time is incorporated into the MRIMM algorithm;
the resulting algorithm is called the Adaptive MRIMM algorithm (AMRIMM). One
of the properties of the MRIMM algorithm is that the state estimate is obtained
every second scan (k-2, k, k+2,
,etc), so we propose to calculate the next
update time in the MRIMM at each second scan and keep it constant between these
two scans. The selected update time is weighted by accurate models probabilities,
updated at each second scan.
We assign to each model in the MRIMM a suitable rate: Tmax to the
non manoeuvring model (MRCV) and Tmin to the manoeuvring model (CA).
Then, the next update time at scan k is obtained using the Eq.
Monte Carlo simulations are often used to assess the performance of constant
update tracking algorithms. The squares of the estimation errors are computed
at each time point, for each run and then the root mean square estimation errors
are obtained by averaging over all runs and taking the square root. Plots of
these RMS errors versus time give an indication of the tracking accuracy times
dependence. This procedure can be used to compare the performance of the algorithms
that use a constant update time such as the IMM and the MRIMM.
In the case of the algorithms that use variable update, there is a difficulty in applying this procedure, since the updates occur at different times, from run to run. To overcome this difficulty, we have divided the target trajectory into segments of equal length (10 sec). The mean square error, in each segment, was obtained by averaging over all the points that lie in this segment. Thus the time step in the plots relative to the FAIMM, AIMM and AMRIMM is equal to 10 sec.
To avoid that the update time becomes too small or too large in the AIMM, FAIMM and AMRIMM, it is limited between 0.25 and 5 sec. The full rate in the IMM and MRIMM algorithms is equal to 2 sec.
The measurement noise is generated in polar coordinates with standard deviations of 185.2 m and 2.5x10-3 radian in range and bearing, respectively. The range and bearing are then converted to two dimensional Cartesian co-ordinates. The probability of switching between the two models is equal to 0.05 in both algorithms.
The modeling statistics were chosen so that the MRIMM work on its best performance
(Hong, 1998, 1999): and
qCAx = qCAy = 30for the MRIMM and qCVx = qCVy
= 0.1 and qCAx = qCAy = 15 for the IMM algorithm.
The update time in the algorithms CMRIMM and CIMM is constant and equal to 2 sec.
Targets trajectories: Two target trajectories are used to evaluate the performance of the algorithms; both trajectories consist of three segments.
Trajectory 1: 90° Manoeuvre: The trajectory duration is 246 sec (Fig. 2). The first segment is a non manoeuvring segment with a constant velocity in x equal to 308.67 m sec-1, it lasts 120 sec, starting at the initial position of (129650, 0 m). It is followed by a manoeuvring segment from 120 to 136.48 sec and a non manoeuvring segment from 136.5 to 246 sec.
Trajectory 2: 180° Manoeuvre: The trajectory duration is 200 sec (Fig. 3). Starting at the initial position of (0, 9166.942 m), the target travels at a constant velocity in x and y equal to 218.26 m sec-1, for 80 sec. It then undertakes a manoeuvre from 80 to 113 sec, before resuming to a quiescent motion for the remaining of the trajectory.
The first results concern the IMM and MRIMM with a constant update time. The
RMSE in position on x and y coordinates obtained over 1000 Monte Carlo are presented
in Fig. 4-7 for trajectory one and two,
We can observe from these figures that the performance of the MRIMM algorithm
is better than that of the IMM during the non manoeuvring segments and that
the two algorithms have approximately the same performance during the manoeuvring
segment with a significant error at the onset of the manoeuvre and lateness
in detecting the end of manoeuvre, especially for the MRIMM. This lateness in
the case of the MRIMM can be explained by the fact that its non manoeuvring
model is updated at half rate.
||True and estimated target trajectory 1 (90° manoeuvre)
||True and estimated target trajectory 2 (180° manoeuvre)
||RMSE in x coordinates for CIMM and CMRIMM algorithms, for trajectory 1
However, the MRIMM is faster than the IMM. It
can save between 15 and 25% of the IMMs computation time.
For a fair comparison between the algorithms that use a variable update time
and those that use a constant update time, the constant update time has been
chosen equal to the mean update time obtained by the FAIMM, the AIMM and AMRIMM
over 1000 Monte Carlo simulations.
In Fig. 8 and 9, the RMSE in x and y co-ordinates
for the FAIMM, AIMM and CIMM obtained over 1000 Monte Carlo simulations are
presented. It can observed that for the same mean update time (3.5 and 2.8 sec,
for trajectory 1 and 2, respectively), the performance of the FAIMM algorithm
is better than those of the AIMM and the IMM during the manoeuvring segments.
We also observe that the FAIMM has approximately the same performance as the
AIMM during the non manoeuvring segments.
||RMSE in y coordinates for CIMM and CMRIMM algorithms, for trajectory 1
||RMSE in x coordinates for CIMM and CMRIMM algorithms, for trajectory 2
||RMSE in y coordinates for CIMM and CMRIMM algorithms, for trajectory 2
||RMSE in x and y coordinates for FAIMM, AIMM and CIMM algorithms over 1000
Monte Carlo simulations, for trajectory 1
||RMSE in x and y coordinates for FAIMM, AIMM and CIMM algorithms over 1000
Monte Carlo simulations, for trajectory 2
However, about 25 to 40% of computation can be saved by using the FAIMM algorithm,
instead of the AIMM algorithm.
In Benoudnine et al. (2007), it has been shown,
that for the same mean update time, the performance of the AMRIMM is better
than that of the CMRIMM and CIMM during the manoeuvring segments and it is approximately
the same as that of the CMRIMM, during the non manoeuvring segments. However,
at the onset of the manoeuvre, the CIMM is more responsive than the MRIMM algorithm.
The results of RMSE in x and y co-ordinates, obtained over 1000 Monte Carlo
simulations using trajectory 2, for FAIMM and AMRIMM are presented in Fig.
10 and 11.
It can be observed that the performance of the FAIMM is better than that of
the AMRIMM at the onset of the manoeuvre and has roughly the same performance
during the manoeuvring and non manoeuvring segments.
In Fig. 12, the averaged update times over 1000 Monte Carlo
runs, for the FAIMM and the AMRIMM algorithms are plotted versus the time for
This shows that AMRIMM and the FAIMM adapt their update time to the motion
of the target. It is reduced in response to a manoeuvre of the target and again
increased when the manoeuvre ceases.
||RMSE in x coordinates for FAIMM and AMRIMM algorithms, for trajectory
||RMSE in y co-ordinates for FAIMM and AMRIMM algorithms, for trajectory
||Update time versus time for FAIMM and AIMM algorithms, for trajectory
A comparison of two adaptive manoeuvring target tracking algorithms namely
the IMM and MRIMM is presented. The results show that both IMM and MRIMM have
a good trade off between complexity and performance. The following conclusions
can be made:
||The MRIMM improves the tracking accuracy of the IMM during the non manoeuvring
||The MRIMM has the same performance as the IMM algorithm, during the manoeuvring
||The IMM is more sensitive to any change in the motion of the target (onset
and offset of manoeuvre)
||About 15 to 25% of the computation time is saved when using the MRIMM
instead of the IMM algorithm
In the second part, a fast method for selecting adaptively the next update
time in a Phased Array Radar is incorporated into the IMM and the MRIMM algorithms.
The resulting algorithms are named, respectively, Fast Adaptive IMM (FAIMM)
and Adaptive MRIMM (AMRIMM). The following conclusions can be drawn:
||Compared to the AIMM and CIMM algorithms, the FAIMM has globally a better
performance in terms of tracking accuracy and complexity
||The AMRIMM algorithm improves the tracking accuracy and computation complexity
of the MRIMM algorithm by using an adaptive variable Update time
Both FAIMM and AMRIMM achieve a good compromise between complexity and tracking
accuracy and are therefore good candidates for tracking a manoeuvring target.