Bearings-Only Target Motion Analysis (BO-TMA) [1] is an analysis method for submarines using sonar bearings received from the hydrophone array. In this study we have only bearings information to track the target; this makes finding an optimal method for the study very hard.
Kalman filters [2] are very popular in Target Motion Analysis (TMA), but due to initial value and linearization problems, evolutionary strategies [3] are more feasible than Kalman like optimum filters. Genetic Algorithms [3], [4], Big Bang-Big Crunch Algorithm (BB-BC) [5]–[7] and Covariance Matrix Adaptation Evolutionary Strategies (CMA-ES) [8]–[10] are the evolutionary strategies which have been used for BO-TMA.
Cost function is simply the Euclidean distance between observed bearing angle and calculated bearing angle [4]. This cost function has complex calculations when getting calculated bearing angle. Because of that a new cost function [11] developed by formulating problem as to fit target courses such that the bearing lines divide the course candidates to equal distances and assuming bearings were measured at same constant time intervals. Equidistant line distance difference cost function is faster but not immune to noise.
In Section II we’ll introduce the BO-TMA and it’s important functions, in Section III we’ll introduce Target Motion Analysis with Genetic Algorithm (TMAGA) and investigate it, in Section IV we’ll introduce CMA-ES and it’s algorithm, in Section V using TMAGA trial dataset we’ll show the performance of CMA-ES, then in Section VI we’ll summarize the paper.
In this section, we will introduce BO-TMA and essential equations to use evolutionary strategies for tracking target. As we mentioned before, BO-TMA is an analysis method for submarines using sonar bearings received from the hydrophone array. In Fig. 1 we see actual target with dashes, observer with straight bold line. Observer must make a leg to get only one possible linear track candidate for target’s motion, otherwise there will be infinite possible linear track candidates.
Fig. 1: Possible track candidates for TMA.
A. Position Equations
If we know our initial position and
, target’s initial bearing
, initial range from observer
; then we can extract target’s initial position
and
from Eq. (1).
If we know our target’s course angle and velocity
; then we can extract target’s following positions
and
, which is changing in
equal time, from Eq. (2).
B. Cost Function
When we get the positions of target and
using evolutionary strategies, we can get estimated bearing angles using Eq. (3).
The cost function for target motion analysis depends on Euclidean distance between estimated bearing angles and observed ones
is given by Eq. (4). This cost function has more calculation complexity but more feasible than the equidistant line distance difference cost function [11].
We may know all parameters except target’s initial range from observer , course of target
and velocity of target
. Evolutionary strategies and genetic algorithms have been helping us for a long time to find these parameters in a short time and using a cost function. Exhaustive search can take so much time for large search areas; but evolutionary strategies gets help from statistics and cost functions to find true path to get true solution.
TMAGA [4] uses genetic algorithm to track target and has holding the best results in TMA studies. TMAGA has three principal structure; space narrowing and tuning chromosome lengths, N generation genetic algorithm and M times Monte Carlo runs. In each Monte Carlo run, 200 generation genetic algorithm runs for narrowing space then chromosomes are tuned using space limits; 500 generation genetic algorithm runs again to find best candidate. After 20 Monte Carlo runs system has 20 offspring to solve the problem. Then we take fitness weighted averages of these 20 offspring to get one solution.
In sections above, we will explain TMAGA in details and discuss the possible problems.
A. Target Motion Representation – Chromosome Structure
A solution individual is a chromosome bit array represents target motion. Solution individual’s structure is given in Eq. (5). and
are initial positions of target on X and Y axes respectively. C is the course angle and S is the velocity of target.
If we set a parameter bit-length for one of the four parameters above, we must know maximum Max and minimum Min value that parameter can get at limits. Then we use Eq. (6) with the degree of precision p, and the number of bits m. IEEE Standard for Floating-Point Arithmetic [12] says that for single precision floating point p parameter must be . If we set precision 7 and Max = 20000, Min = 0 meters for
and
parameters of chromosome, due to Eq. (6) our bit width will be 38. For C and S bitwidths are 32 and 28 due to limits [360 0] degrees and [25 0] meters/seconds respectively. Total 136 bits were used; but if we decide to use single precision floating point, we would use only 128 bits for representation.
Instead of representing position by known bearing and range R; the authors chose to use two parameters
and
. These values are correlated by the corresponding bearing. Then using two parameter; creates correlation problems, increases search dimension so enlarges search space causing more time to obtain correct solution. So ideal chromosome must look like Eq. (7), this form uses 96 bits single precision floating point numbers.
In summary, genetic algorithm is a memory exhaustive and slow method to use in 2009, real valued evolutionary strategies uses real values instead of bit strings, which is more suitable for high level computing, and uses less memory.
B. Narrowing the Parameter Space
Due to TMAGA, search space between estimation and limit values could be reduced 20% using 200 generations with 50 population size and 20 runs. If we think that in case of degrees, which is a quite high noise, generation and population size are quite low to converge to the ideal solution. Even if TMAGA says the parameter space’s being narrowed into an infeasible area is a very unlikely case, it seems like very likely case, because genetic algorithm does not care the numerical value of the individual chromosome and does not use a feedback mechanism to narrow the area except the cost function. Because of this genetic algorithm results are expected to converge a different point in every different 20 runs.
If route is perpendicular to observer, noise becomes more destructive because determining the breaking point becomes more critical and it changes whole track even with a minimal change. In this case it is impossible to narrow the area to get correct result, because even with clean bearing it is hard to track target.
C. Cost Function
TMAGA uses a non-metric cost function called Total Deviation and shown in Eq. (8) where and
are ground truth and calculated bearing angles of target at
sample point. So this could cause divergence instead of convergence.
The ideal cost function is must be like in Eq. (9) to obtain Euclidean distance properties and become a metric distance measure.
D. Selection, Mutation and Crossover Operators
Genetic algorithm’s mutation and crossover operators are somewhat weaker than real valued evolutionary strategy’s ones. Because bitwise crossover and mutation options are limited and binary numbers’ digit value is not meaningful by itself to these operators.
TMAGA uses the simplest selection method; individuals are weighted by their fitnesses obtained from cost function, then randomly picked from population using these weights. The highest weighted individual has the highest pick chance, but the lowest weighted one has being picked chance too. But this straight method is weak; because the highest two individual’s offspring won’t create a good individual every time, sometimes two bad individual could create the best individual; so stochastic universal sampling and elitism could help converge faster than used method.
TMAGA uses two piece crossover and randomly picked bitwise mutation methods. These methods are old fashioned for 2009 and their performances are not satisfying anymore. In real value measure non-uniform mutation and n-point real valued weighted averaging crossover methods could give much more better performance and easy to implement.
E. Function Evaluations
TMAGA’s main flow include two layered structure. Outer layer creates population, narrows search space and keeps track of best solution. Inner layer controls genetic algorithm operations. The flow can be seen in Fig. 2
Outer and inner layers have Monte Carlo runs separately; so Monte Carlo run increases exponentially. TMAGA uses 20 inner, 20 outer Monte Carlo runs. Inner Monte Carlo is used for narrowing space and genetic algorithm run, outer one is used for statistical analysis.
At the end of process, outer layer calculates weighted average of the best results from Monte Carlo runs and labels it as the best result.
TMAGA uses 50 population size, 200 generations for space narrowing, 500 generations for genetic algorithm, 20 statistical, 20 in-system Monte Carlo counts. If we calculate function evaluation count with these informations; 700000 function evaluation will be done in a single Monte Carlo of TMAGA, if 20 statistical Monte Carlo runs completed it will be 14000000. 14 million function evaluation is too much for
meters,
meters, limits(C) = [360, 0] degrees and limits(S) = [25, 0] meters/seconds.
Fig. 2: Main flow for TMAGA.
If we chose form Eq. (7) and limits(R) = [28000, 0] meters, limits(C) = [360, 0] degrees and limits(S) = [25, 0] meters/seconds; then search the space with 100 unit precision for R, 0.5 unit precision for C and 0.1 unit precision for S using brute force;
50400000 function evaluation needed. Results for brute force searching is given in Table II with ground truth values in Table I. Even with 50400000 function evaluations, we cannot get correct results.
TABLE I: Trials’ ground truth values.
From Table II we can see that even brute force cannot find a clear solution for that high noise levels. Thus we can say noise is disrupting useful information in bearing data.
TABLE II: Brute force search results.
F. Statistical Results
We said that TMAGA has not guaranteed results before; because in the paper [4] there is no information about variance of Monte Carlo runs and statistics are only given for means or the best results. Thus we cannot determine the real performance of the TMAGA. Higher performances on higher error standart deviations like and
in degree measure are suspicious. Additionally, perpendicular movement of target to observer makes tracking difficult; but TMAGA says it is tracking target very accurate with these error variances. Even we look at Table II, brute force couldn’t get the precise results.
If we look at Table 3 which is given by [4], we could see Monte Carlo is done two times and mean of the second Monte Carlo is given as the average result. There is no information about variance or standard deviation; so this type of reporting is not acceptable. Solutions are obtained by weighted averages of the first Monte Carlo’s results. There is no statistical relation between best solution and fitness in extra noisy data condition.
In this section, we will explain how the Covariance Adaptation Evolutionary Strategies [9] works and model a new TMA system by CMA-ES.
A. CMA-ES
CMA-ES is a kind of evolutionary strategy that uses statistical feedback and covariance matrix for capturing search space shape. CMA-ES uses cost weighted recombination instead of crossover; random number generation using Gaussian distribution instead of mutation.
is the favorite solution at the start of each generation and could be obtained using Eq. (10).
is the weight obtained from the cost of the parent i for the
offspring cluster,
is the
parent.
Covariance matrix C determines the shape of the random number generation and step size determines the width of probability density function. Initially we use
predefined around like a number 0.3 and C unit diagonal matrix. We learn them each generation via the methods described by Hansen[9]. Then we use Eq. (11) to get new population individuals
around the
favorite individual.
CMA-ES narrows the search space using statistical information learned by updating C and . This narrowing helps CMAES converge with less calculations than classical evolutionary strategies. Fig. 3 shows how CMA works and converges to the result by the help of C and
.
Fig. 3: Concept work of the CMA-ES.
We’re using CMA [9] with cost function given by Eq. (4) to solve the target motion analysis problem. CMA is a powerful method as it converges quickly to the solution without stucking to local minima. Our parameters for CMA is given in Table III
TABLE III: CMA parameters.
Results for CMA-ES searching is given in Table IV with ground truth values in Table I. represents Monte Carlo mean,
represents Monte Carlo standart deviation and |Dev.| represents the absolute deviation between estimation and ground truth. As we can see from Table IV, author’s error standart deviation is too much for tracking and result variates in wide ranges. If we reduce error standart deviation by 0.1x, we can see that results are becoming much more reliable. We can say that maximum error standart deviation is
°.
CMA-ES solves problem with 50000 function evaluation which is 14 times smaller than 700000 function evaluation of brute force and results’ standart deviation is smaller enough to trust.
TABLE IV: CMA-ES search results.
As conclusion we can say that genetic algorithm is a non- modern weak method to solve target motion analysis. Even using two different position parameters enlarges search space and creates correlation problems. Distance measure is wrong; because it don’t justify metric rules. Search space narrowing is useless because algorithm may converge to local minima with genetic algorithm, there is no feedback to avoid it. Statistical results are given in wrong way, and there is too much calculation to solve problem.
CMA-ES narrows space via statistical feedback and converges quickly without being stuck to local minima. Error standart deviation is too large to converge, with experiments we can say 0.2 is the maximum value for error standart deviation. As result we can get solution with 14 times smaller function evaluation count than brute force via CMA-ES.
[1] A. Aytun and S. Bulkan, “Bearing-Only Target Motion Analysis,” in Operations Research for Military Organizations. IGI Global, 2019, pp. 330–346.
[2] T. Kronhamn, “Bearings-only target motion analysis based on a mul- tihypothesis Kalman filter and adaptive ownship motion control,” IEE Proceedings-Radar, Sonar and Navigation, vol. 145, no. 4, pp. 247–252, 1998.
[3] H.-G. Beyer and H.-P. Schwefel, “Evolution strategies–A comprehensive introduction,” Natural computing, vol. 1, no. 1, pp. 3–52, 2002.
[4] L. Ince, B. Sezen, E. Saridogan, and H. Ince, “An evolutionary com- puting approach for the target motion analysis (TMA) problem for underwater tracks,” Expert Systems with Applications, vol. 36, no. 2, pp. 3866–3879, 2009.
[5] O. K. Erol and I. Eksin, “A new optimization method: big bang–big crunch,” Advances in Engineering Software, vol. 37, no. 2, pp. 106– 111, 2006.
[6] H. Genc and A. Hocaoglu, “Bearing-only target tracking based on big bang–big crunch algorithm,” in Computing in the Global Information Technology, 2008. ICCGI’08. The Third International Multi-Conference on. IEEE, 2008, pp. 229–233.
[7] A. Tokta, A. K. Hocao˘glu, and H. M. Genc¸, “Target motion analysis with fitness adaptive big bang-big crunch optimization algorithm,” in Signal Processing and Communications Applications Conference (SIU), 2017 25th. IEEE, 2017, pp. 1–4.
[8] N. Hansen, S. D. M¨uller, and P. Koumoutsakos, “Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES),” Evolutionary computation, vol. 11, no. 1, pp. 1–18, 2003.
[9] N. Hansen, “The CMA evolution strategy: A tutorial,” arXiv preprint arXiv:1604.00772, 2016.
[10] H. H. S¨onmez, A. K. Hocao˘glu, and H. M. Genc¸, “A new solution method for the passive target motion analysis problem using evolutionary strategies,” in Signal Processing and Communications Applications Conference (SIU), 2017 25th. IEEE, 2017, pp. 1–4.
[11] H. Genc¸, “A new solution approach for the bearing only target tracking problem,” in Soft Computing Applications (SOFA), 2010 4th International Workshop on. IEEE, 2010, pp. 95–100.
[12] D. Zuras, M. Cowlishaw, A. Aiken, M. Applegate, D. Bailey, S. Bass, D. Bhandarkar, M. Bhat, D. Bindel, S. Boldo, and others, “IEEE standard for floating-point arithmetic,” IEEE Std 754-2008, pp. 1–70, 2008.