Target tracking method
In target tracking, the multi-fractional order estimator (MFOE) is an alternative to the Kalman filter. The MFOE is focused strictly on simple and pragmatic fundamentals along with the integrity of mathematical modeling. Like the KF, the MFOE is based on the least squares method (LSM) invented by Gauss and the orthogonality principle at the center of Kalman's derivation. Optimized, the MFOE yields better accuracy than the KF and subsequent algorithms such as the extended KF and the interacting multiple model (IMM).
The MFOE is an expanded form of the LSM, which effectively includes the KF and ordinary least squares (OLS) as subsets (special cases). OLS is revolutionized in for application in econometrics. The MFOE also intersects with signal processing, estimation theory, economics, finance, statistics, and the method of moments. The MFOE offers two major advances: (1) minimizing the mean squared error (MSE) with fractions of estimated coefficients (useful in target tracking) and (2) describing the effect of deterministic OLS processing of statistical inputs (of value in econometrics)
Description.
Consider equally time spaced noisy measurement samples of a target trajectory described by
formula_1
where "n" represents both the time samples and the index; the polynomial describing the trajectory is of degree J-1; and formula_2 is zero mean, stationary, white noise (not necessarily Gaussian) with variance formula_3.
Estimating x(t) at time formula_4 with the MFOE is described by
formula_5
where the hat (^) denotes an estimate, "N" is the number of samples in the data window, formula_4 is the time of the desired estimate, and the data weights are
formula_7
The formula_8 are orthogonal polynomial coefficient estimators. formula_9 (a function detailed in) projects the estimate of the polynomial coefficient formula_10 to the desired estimation time formula_4. The MFOE parameter 0≤formula_12≤1 can apply a fraction of the projected coefficient estimate.
The combined terms formula_13 effectively constitute a novel set of expansion functions with coefficients formula_12. The MFOE can be optimized at time formula_4 as a function of the formula_12s for given measurement noise, target dynamics, and non-recursive sliding data window size, "N". However, for all formula_17, the MFOE reduces and is equivalent to the KF in the absence of process noise, and to the standard polynomial LSM.
As in the case of coefficients in conventional series expansions, the formula_12s typically decrease monotonically as higher order terms are included to match complex target trajectories. For example, in the formula_12s monotonically decreased in the MFOE from formula_20 to formula_21 , where formula_22 for m ≧ 6. The MFOE in consisted of five point, 5th order processing of composite real (but altered for declassification) cruise missile data. A window of only 5 data points provided excellent maneuver following; whereas, 5th order processing included fractions of higher order terms to better approximate the complex maneuvering target trajectory. The MFOE overcomes the long-ago rejection of terms higher than 3rd order because, taken at full value (i.e., formula_23), estimator variances increase exponentially with linear order increases. (This is elucidated below in the section "Application of the FOE".)
Fractional order estimator.
As described in, the MFOE can be written more efficiently as formula_24 where the estimator weights formula_25 of order "m" are components of the estimating vector formula_26. By definition formula_27 and formula_28. The angle brackets and comma formula_29 denote the inner product, and the data vector formula_30 comprises noisy measurement samples formula_31.
Perhaps the most useful MFOE tracking estimator is the simple fractional order estimator (FOE) where formula_32 and formula_33 for all "m" ; 3, leaving only formula_34. This is effectively an FOE of fractional order formula_35, which linear interpolates between the 2nd and 3rd order estimators described in) as
formula_36
where the scalar fraction formula_37 is the linear interpolation factor, the vector formula_38, and formula_39 (which comprises the components formula_40) is the vector estimator of the 3rd polynomial coefficient formula_41 ("a" is acceleration and Δ is the sample period). The vector formula_42 is the acceleration estimator from formula_43.
The mean-square error (MSE) from the FOE applied to an accelerating target is
formula_44,
where for any vector formula_45, formula_46.
The first term on the right of the equal sign is the FOE target location estimator variance formula_47 composed of the 2nd order location estimator variance and part of the variance from the 3rd order acceleration estimator as determined by the interpolation factor squared formula_48. The second term is the bias squared formula_49 from the 2nd order target location estimator as a function of acceleration in formula_50.
Setting the derivative of the MSE with respect to formula_37 equal to zero and solving yields the optimal formula_37:
formula_53
where formula_54 , as defined in.
The optimal FOE is then very simply
formula_55
Substituting the optimal FOE into the MSE yields the minimum MSE:
formula_56
Although not obvious, the formula_57 includes the bias squared. The variance in the FOE MSE is the quadratic interpolation between the 2nd and the 3rd order location estimator variances as a function of formula_58. Whereas, the formula_57 is the linear interpolation between the same 2nd and the 3rd order location estimator variances as a function of formula_60. The bias squared accounts for the difference.
Application of the FOE.
Since a target's future location is generally of more interest than where it is or has been, consider one-step prediction. Normalized with respect to measurement noise variance, the MSE for equally spaced samples reduces for the predicted position to
formula_61
where "N" is the number of samples in the non-recursive sliding data window. Note that the first term on the right of the equal sign is the variance from estimating the first coefficient (position); the second term is the variance from estimating the 2nd coefficient (velocity); and the 3rd term with formula_62 is the variance from estimating the 3rd coefficient (which includes acceleration). This pattern continues for higher order terms. Furthermore, the sum of the variances from estimating the first two coefficients is formula_63). Adding the variance from estimating the 3rd coefficient yields formula_64.
Estimator variances obviously increase exponentially with unit order increases. In the absence of process noise, the KF yields variances equivalent to these. (A derivation of the variance from a 1st degree polynomial corresponding to formula_65 for the generalized case of arbitrary estimation time and sample times is given in reference. In addition, establishing a multi-dimensional tracking gate at the predicted position can easily be aided with the simple approximation of the error function in.)
Kalman filter tuning.
Tuning the KF consists of a trade-off between measurement noise and process noise to minimize the estimation error. The KF process noise serves two roles: First, its covariance is sized to account for the maximum expected target acceleration. Second, process noise covariance establishes an effective recursive data window (analogous to the non-recursive sliding data window), described by Brookner as the Kalman filter memory.
Contrary to process noise covariance as a single independent parameter in the KF serving two roles, the FOE has the advantage of two separate independent parameters: one for acceleration and the other for sizing the sliding data window. Therefore, as opposed to being limited to just two tuning parameters (process and measurement noises) as is the KF, the FOE includes three independent tuning parameters: measurement noise variance, the assumed maximum deterministic target acceleration (for simplicity both target acceleration and measurement noise are included in the ratio of the single parameter formula_66), and the number of samples in the data window.
Consider tuning a 2nd order predictor applied to the simple and practical tracking example in to minimize the MSE when the target acceleration is formula_67; the zero mean, stationary, and white measurement noise is described as formula_68; and formula_69 = 1 second. Thus,
formula_70
Setting formula_71 in the normalized prediction MSE yields for the 2nd order predictor applied to an accelerating target,
formula_72
where the first term on the right of the equal sign is the normalized 2nd order one-step prediction variance and the second term is the normalized bias squared from acceleration. This MSE is plotted as a function of "N" in Figure 1 along with both the variance and bias squared.
Clearly, only integer order steps are possible in a non-recursive estimator. However, for use in approximating the tuned 2nd order KF, this MSE plot is stepped in tenths of a unit to show more precisely where the minimum occurs. The minimum MSE of 4.09 occurs at N = 2.9. The tuned KF can be approximated by sizing the process noise covariance in the KF such that the effective recursive data window—i.e., the Kalman filter memory—matches "N" = 2.9 in Figure 1 (i.e., formula_73 and formula_74), where formula_75and formula_76. This hints at the fallacy of using a 2nd order estimator on accelerating targets as described in. Comparing this with the filtered position in demonstrates that the minimum MSE is a function of the time formula_4 of the desired estimate.
FOE as a multiple-model estimator.
The FOE can be viewed as a non-recursive multiple-model (MM) estimator composed of 2nd and 3rd order estimator models with the fraction formula_34 as the interpolation factor. Since the filtered position is generally used for comparisons in the literature, consider now the normalized MSE for the position estimate:
formula_79
Note that this differs from the one-step prediction MSE in that the signs within the parentheses containing "N" are reversed. The higher order pattern continues here also.
Normalized with respect to the measurement noise variance, the minimum position MSE reduces for equally spaced samples to
formula_80
where formula_81
in formula_82
A plot of the position formula_57 as a function of "N" for various values of formula_66 is shown in Figure 2, where there are several points of interest: First, the 2nd and 3rd order MSEs track each other very closely and bound all the formula_57 (interpolated) curves. Second, the curves drop rapidly to a knee. Third, the formula_57 curves flatten out beyond the knee yielding virtually no increase in accuracy until they begin to approach the 3rd order MSE (variance). This suggests that choosing a window at the knee of the curve is advantageous—to be demonstrated below.
Consider again the scenario of, in this case as the target maneuvers. After traveling at a constant velocity, the target accelerates at formula_67 for 20 seconds and then continues again at a constant velocity. At worst case acceleration, formula_88. The formula_57 is plotted in Figure 3 of as a function of "N". Also shown are the 2nd order MSE as well as the 2nd and 3rd order MSEs (variances only since the bias is zero in each case) similar to those in Figure 2. There is a fifth curve not previously addressed: the variance portion of the optimal MSE. The variance also levels off for several increments of "N" like the formula_57. Both the variance and formula_57 approach the 3rd order variance as formula_92.
As the acceleration varies from zero to maximum, the MSE is automatically adjusted (no external tinkering or adaptivity) between the variance at formula_93 and maximum formula_57 at formula_95. In other words, the MSE rides up and down the quadratic curve of the variance plus bias squared as a function of changes in acceleration formula_66 for any given value of "N" in the position estimate:
formula_97
Choosing "N" = 4 at the knee of the formula_57 curve in Figure 3 yields the RMSE (square root of the MSE, which is more often used for comparison in the literature) shown in Figure 4. On the other hand, choosing "N" = 8 yields the second curve in Figure 4. As shown in Figure 3, the optimal 8–point FOE is essentially a 3rd order non-recursive estimator which yields less than 4% RMSE improvement over the optimal 4-point FOE in the case of no acceleration. However, in the case of maximum acceleration the optimal 8-point MSE is markedly volatile and has large error spikes that can confuse a tracker, one spike exceeding the optimal 4-point MSE for worst case acceleration by more than the optimal 4-point MSE exceeds the optimal 8-point MSE in the absence of acceleration. Obviously, higher values of "N" produce larger error spikes.
Since trackers encounter greatest difficulties and often lose track during target maneuvers at maximum acceleration, the much smoother formula_57transition of the optimal 4-point FOE has a major advantage over larger data windows.
IMM compared with the optimal FOE.
The 4-point FOE in Figure 4 yields much smoother MSE transitions than the IMM (as well as the KF) in the parallel 1 Hz case of. It produces no error spikes or volatility as do the 8-point FOE and the IMM. In this example only 4 multiplies, 3 adds, and a window shift are required to implement the 4-point FOE, significantly few operations than required