Proceedings of SPIE Conference on Signal and Data Processing of Small T argets,
Orlando,FL,USA,April2002.Paper4728-60
A Survey of Maneuvering Target Tracking—Part IV:Decision-Based Methods
X.Rong Li and Vesselin P.Jilkov
Department of Electrical Engineering
University of New Orleans
New Orleans,LA70148,USA
504-280-7416(phone),504-280-3950(fax),xli@uno.edu,vjilkov@uno.edu
Abstract
This is the fourth part of a series of papers that provide a comprehensive survey of techniques for tracking maneuvering targets without addressing the so-called measurement-origin uncertainty.Part I[1]and Part II[2]deal with target motion models.Part III[3]covers the measurement models and the asso
ciated techniques.This part surveys tracking techniques that are based on decisions regarding target maneuver.Three classes of techniques are identified and described:equivalent noise, input detection and estimation,and switching model.Maneuver detection methods are also included.
Key Words:Target Tracking,Adaptive Filtering,Maneuver Detection,Survey
1Introduction
This is the fourth part of a series of papers that provide a comprehensive survey of the techniques for tracking maneuvering targets without addressing the so-called measurement-origin uncertainty.Part I[1]and Part II[2]deal with general target mo-tion models and ballistic target motion models,respectively.Part III[3]covers measurement models,including measurement model-based techniques,used in target tracking.
In the history of development of maneuvering target tracking(MTT)techniques,single model based adaptive Kalman filtering free of decision came into existencefirst.Decision-based techniques appeared next.This was followed by multiple-model algorithms,which have become quite popular.More recently,nonlinearfiltering techniques,such as sampling based algorithms,have been gaining moment.
This part surveys decision-based techniques for MTT,that is,techniques in which a key component is explicit decisions on target maneuver.In subsequent parts,multiple-model approach,exact and approximate nonlinearfilters,and sampling based algorithms will be surveyed;performance analysis and evaluation as well as applications will be addressed.A summary part will also be provided.
There are numerous methods for adaptive estimation andfiltering,decision making,and nonlinearfiltering in the literature. Only those that have been proposed for,applied to,or possess substantial potentials for MTT are included in this survey.On the other hand,it is our intention to cast problems and techniques in a slightly wider context than most previous treatments so as to make more clear the forest rather than just trees.
In target tracking,the actual measurement system is typically nonlinear,as described in Part III.In this part,however,we mainly focus on linear measurement systems for simplicity.This simplification has the following justification.Not only have the techniques that handle nonlinear measurements been covered in Part III,they are also to a large extent independent of the MTT techniques surveyed here,which focus on the uncertainty in the target motion due to possible maneuvers.
As stated repeatedly in the previous parts,we appreciate receiving comments and missing material t
hat should be included in this part.While we may not be able to respond to each correspondence,information received will be considered seriously for the refinement of this part for itsfinal publication in a journal or book.
The rest of the paper is organized as follows.Sec.2briefly describes the methods considered in this part as a whole.Sec. 3surveys maneuver detectors.Secs.4,5,and6cover three different classes of methods,referred to as equivalent noise,input detection and estimation,and switching model,respectively.Concluding remarks are given in thefinal section.
Research supported by ONR grant N00014-00-1-0677,NSF grant ECS-9734285,and NASA/LEQSF grant(2001-4)-01.
2Decision-Based Approach to Maneuvering Target Tracking
In the decision-based approach,target tracking as a hybrid estimation problem involving both estimation and decision is solved by combining estimation with explicit,hard decision.This approach is one of the most natural for MTT.It is covered with varying degrees in several books on target tracking[4,5,6,7,8,9,10].
This approach to MTT distinguishes itself from other approaches in that the adaptation in estimating the target state is directed by decisions regarding target maneuver,in particular,its onset and termination.This decision-directed adaptation may take different forms.Most of these techniques amount to using two types offilters,one with a narrow , low gain)for precision tracking in normal situations and the other with a wide ,high gain)for effective tracking during target maneuvers.In this way,it aims at achieving good tracking performance in both situations rather than a compromise.Thesefilters may be based on the same or different models.When a single model is used in the linear case, such adaptive techniques are traditionally considered as part of the so-called adaptive Kalmanfiltering.While more than one model may be used,only one is in effect at one time.
Decision-based techniques for MTT developed so far fall into three classes,referred to as equivalent noise,input detection and estimation,and switching model approaches and described in Secs.4,5,and6,respectively.
Wefirst survey techniques for maneuver detection developed so far in the next section.
3Maneuver Detection
Although the ultimate goal of MTT is estimation of the target state,in the decision-based approaches,estimation is directed by decision regarding maneuvers.This makes reliable and timely decision the key in these approaches.
The fundamental questions here are:“Is the target maneuvering?”In other words,whether the target is maneuvering is crucial information here.Answering this question is a decision problem,which can be formulated as a hypothesis testing problem
The target is not maneuvering;The target is maneuvering
Many solution techniques are available in statistics for such problems.
Both maneuver onset and termination represent a change in the target motion pattern.This change exhibits itself more or less in our observations of the target.Detection of maneuver onset and termination thus amounts to detecting a change in the observations—a random process.This is known as change-point detection in statistics1.It has a very large body of literature that includes abundant results(,[11,12,13,14,15,16,17,18,19]and references therein).Unfortunately, this treasure has been largely overlooked by the tracking community partly because most of it is not easily accessible by engineering-oriented researchers.However,it could certainly facilitate developm
ent and design of better maneuver detectors.
Two other fundamental questions are:“When did the target start maneuvering?”and“When did it stop maneuvering?”In other words,it is important to infer the onset time and termination time of a maneuver.The determination of maneuver onset and termination times can be cast either as an estimation or decision problem.Estimation and decision are twins.They both aim at inferring an unknown quantity using available information.Their basic difference is that decision is the selection from a discrete(oftenfinite)set of candidates,while all possible outcomes of estimation form a continuum.In the continuous-time case,it would be more natural to formulate the determination of onset and termination times as an estimation problem,but a decision framework appears to be more appropriate for the discrete-time case.
In maneuver detection,the focus is detection of maneuver onset,rather than maneuver termination.The two main reasons for this are level of difficulty and the consequence of an incorrect decision.In general,it is more difficult to detect maneuver termination than maneuver onset because nonmaneuver is a well-defined motion pattern—straight and level motion at a constant velocity—while maneuver essentially includes all other motion patterns.For instance,a maneuver model has a larger covariance of measurement residuals than a nonmaneuver model due to the fact that the latte
r has a larger state vector and assumes more motion uncertainty than the former.Fortunately,timely detection of maneuver termination is usually not as important as that of maneuver onset because tracking a maneuvering target assuming it is not maneuvering may have a serious ,track loss),while tracking a nonmaneuvering target assuming it is maneuvering usually only suffer minor performance degradation.
1Some people prefer“change detection.”
3.1Chi-Square Test Based
Most maneuver detectors used in MTT are(true,quasi,or pseudo)chi-square significance test based.They employ a statistic that is truly or approximately chi-square distributed under for maneuver onset detection or under for maneuver termi-nation detection.Assume is(approximately)chi-square distributed with degrees of freedom(denoted as)under .Then a chi-square test based maneuver detector will declare detection of a maneuver if
(1) where is the level of confidence,which should be set quite ,or).Note that does not imply absence of a maneuver.
刘銮雄扶正甘比It is well known that is distributed for any-dimensional Gaussian random vector .In this sense,chi-square test provides a check of the goodness offit to judge if indeed has the assumed distribution(or if this statistical distance between and matches the distribution).Chi-square test is perhaps the most popular statistical test because of its simplicity,even though it is not necessarily optimal in any sense.Rigorously speaking, the validity of a chi-square test relies on the assumption that individual terms are Gaussian and independent,which is not necessarily valid in practice.Nevertheless,chi-square tests are commonly used in these situations.
In maneuver detection,two popular choices for are measurement residual and input estimate.
Residual based.In this case,normalized residual squared is used,where is the measurement residual and cov.Its moving sum over a sliding window of length as well as fading-memory sum are
(2)
where is the effective window length of the fading-memory sum.Under the linear-Gaussian assumption and,residual sequence is zero-mean,Gaussian,and white.Then and are chi-square distributed with and degrees of freedom,,,),where.As a weighted sum of i.i.d.Gaussian variables, is not chi-square distributed,but by moment matching it can be approximatel
y treated as a scaled version of a chi-square variable,that is
with(3) Consequently,(1)can be used to detect maneuver onset,where,,or.Note that a variable has mean and variance,and thus ,each term in the sum)becomes less random as the window length(or)becomes larger,which however often implies a longer detection delay.The detection threshold can be obtained from their respective distributions.
As already mentioned,chi-square tests based on residuals have been a fairly standard tool for maneuver detection.Its applications are too numerous to list.A sample can be found in[20,4,21,5,6,9,22,7,10]and references therein.
Input estimate(IE)based.If the target is not maneuvering,its control ,acceleration or its increment)is zero,and thus any estimate of the input that is linear in the measurement residuals2under the linear-Gaussian assumption is zero-mean and Gaussian.As a result,is distributed under,where cov and. Consequently,(1)can be used to detect maneuver onset.Mainly because of their simplicity,the IE-based chi-square tests are present in many IE-based algorithms[23,24,25,26,27,28].The test can also be used to detect maneuver termination [20,10].It can be used based on a moving sum or fading-memory sum as well,where.However,the terms that f
吉克隽orm the sum are usually not independent and thus the sum is usually not really chi-square distributed.A rigorous analytical determination of the corresponding detection probability is virtually impossible since it depends on the generally unknown input.Evaluation of could be done by simulation.
3.2Generalized Likelihood Ratio Test Based
Let be the input that is responsible for maneuver and let be the maneuver onset time so that for and
for over the time window.Consider the following maneuver hypotheses in terms of input value
for all(4)
for some(5) 2This is true for almost all input estimates developed.
where the input level and the maneuver onset time are unknown.
The likelihood ratio of vs.with given and is
(6) where stands for set of measurements.Many optimal solutions of the above hypothesis testing pr
oblem are based on this likelihood ratio,which is however unknown due to its dependence on and.In such a case,a general principle widely used is to replace the unknown likelihood functions by their maxima over the unknown parameters;that is,re-place with,where
is the maximum likelihood estimate of.In essence,this principle replaces an unknown likelihood ratio with its most probable likelihood ratio,which does make sense.The resulting likelihood ratio is known as the generalized likelihood ratio. Then the generalized likelihood ratio(GLR)test compares this ratio or its equivalent with a threshold.
In the context of maneuver detection,the joint maximum likelihood estimate is found in two steps as follows. Denote by the log-likelihood ratio.First,find as the input estimate given onset time and then
(7)
The main reason for this two-step approach is the ease atfinding.Then the GLR maneuver detector declares detection of a maneuver if the generalized log-likelihood ratio
(8)
exceeds a properly chosen threshold.In this case,the GLR estimates of the input and onset time and
obtained by(7)are validated(see Sec.5.1).
As shown in Sec.5.1,under the linear-Gaussian assumption,is easily obtainable(in fact,it is the least-squares estimate of given),where MSE is the mean-square error matrix of and is given later by(43);further,it can be easily verified that
去除白蚁的最好方法是什么(9) where is the residual at time under and cov.The increment due to the unknown input is given by
(10) Note,however,that.As such,the above GLR test does not lead to the following maneuver detector
(11)
or(not equivalently)
(12) These two detectors are nevertheless used in some algorithms.Note that(11)is in general not a chi-square test since given by(7)is not necessarily linear in the residuals.Also,implementation of the double maximization(7)over an window requires input estimators running for each.
Development and applications.The above GLR detector was proposed in[29]for fault detection and u
sed in many MTT algorithms.More details were given in[29,19].Prior to[29],a GLR-based maneuver detector was proposed in[30]in a less general setting.The maneuver detection is based on the GLR test for detecting a maneuver-induced bias in the constant-velocity(CV)filter’s residual sequence.This bias is modeled as,where,is the current time,is the maneuver onset time,is the sampling period,and is an unknown constant related to the maneuver input magnitude.It was presented therein that with
The proposed GLR bias(maneuver)detector over the window is
(13) and the estimate of the maneuver onset is.To reduce the computational burden of the algorithm,an approximate detector has also been developed therein.Application of the GLR-based maneuver detection in a1D trackingfilter,discussed in Sec.5.3.5,can also be found in[31].
As discussed in[19,32],while providing an appealing analytical framework for change detection,the GLR method has its major drawbacks in the heuristic choosing of decision threshold and heavy computational burden.
3.3Other Detectors
Marginalized likelihood ratio test.The marginalized likelihood ratio(MLR)method,proposed recently in[33],appears to be more efficient than the GLR test assuming more prior information.Its basic idea is to obtain the marginal ML estimate that has the maximum likelihood for an average,rather than using the joint MLE,as given by(7).In essence, MLR test checks the ratio of average likelihoods,as opposed to the ratio of most probable likelihoods in the GLR test.The hypotheis testing problem for vs.is formulated with respect to the marginalized log-likelihood ratio(MLR)
(14) where
(15)
(16) where is the maximum MLR.
In this formulation the input is considered as a random variable,in contrast to the GLR method where it is assumed a deterministic constant.The prior of can be chosen,for example,as diffuse uniform(noninformative).The input level is eliminated by averaging over all possible levels.Clearly the crucial problem of threshold determination of the GLR test is circumvented in the MLR formulation.U
nder some condition and with a special choice of the GLR threshold,both tests coincide.Fairly efficient algorithms for estimating were also presented in[33].The MLR test is also more robust than the GLR test to unknown noise levels.
没带身份证怎么坐高铁Gaussian significance test based.In this detector,a maneuver is declared if a component of input estimate(assumed to be Gaussian distributed)is statistically significant,that is,,where var and the threshold is determined from the standard Gaussian distribution.It is used ,[34,21,4,7,28].
CUSUM based.The popular cumulative sum(CUSUM)algorithm[35,36,17,19]can be applied to maneuver detection with an input estimate as follows:Declare a maneuver if,where
is the cumulative sum of log-likelihood ratios.The rationale behind is the observation that generally goes down with time in the absence of maneuver,but goes up during maneuver,and thus the maneuver onset time corresponds roughly to the time reached its minimum.In the linear Gaussian case,is simply a sum of normalized residual squared.A maneuver detector for2D tracking was developed in[37].It uses the normalized residual with its scalar measure
每个月的情人节with
which has the standard Gaussian distribution if the residual sequence is Gaussian and white.and other possible distance measures were discussed in[19]and relevant references therein.This detector is decoupled from input estimation and computationally more efficient than the standard detector.The use of fading-memory sum,known as geometric moving avarage in statistics,is well established in tracking,but it is only one of a wide variety of choices available for change-point detection.A successful use of a CUSUM maneuver detector was reported recently in[19].
发布评论