شبیه سازی مبتنی بر الگوریتم هیوریستیک برای یافتن وضعیت جهت یاب

A direction finder is a military weapon that is used to find locations of targets that emit radio frequencies. Multiple direction finders are used in a direction finder system for finding locations of targets in an area of interest. We present a two-stage heuristic algorithm for disposing direction finders in a direction finder system for the objective of maximizing the accuracy of estimation of the location of a target that is assumed to be located in the area of interest. In the suggested heuristic algorithm, a simulation-based method is used for estimating the probability of coverage, the probability that a target is in a given region (of a given size) surrounding the estimated location of the target, and another simulation-based method and a local search method are used to determine locations of direction finders that result in the maximum probability of coverage. Performance of the suggested algorithm is evaluated through computational experiments and results show that the algorithm gives a good disposition plan in a reasonable amount of computation time.

In modern warfare, it is critical for military operations to detect the enemy as early as possible in order to have advantage over the enemy. This can be achieved by using high technology equipment or skilled human forces for information collection. One of such equipment is a direction finder (DF), which is an electronic warfare weapon designed to detect the location of a target that emits radio frequencies as well as to monitor the movement and to jam the wireless communication of the target (Johnson, 1993). DFs can also be used in other areas, such as rescue operations and wild animal tracking. Among various functions of the DF, we focus on the function of detecting the location of a target in this paper. Since a direction finder can give only directional data about the location of a target, i.e., the azimuth (angle) of an incoming radio frequency signal emitted from a target, a system of two or more DFs is necessary to estimate a two-dimensional location. In this paper, an n-DF system denotes a direction finder system composed of n-DFs that are used together to estimate the location(s) of a target or targets. Since information on directional data can be obtained and analyzed very quickly, radio frequencies emitted from multiple targets can be handled individually by a DF. The performance of a DF system in location estimation is affected by several factors such as the mechanical accuracy of the direction finders, the effectiveness or accuracy of the algorithm used for location estimation and the disposition of DFs relative to the target, but the disposition of DFs may be the most critical factor as argued by Jenkins (1991). When the area of interest, the area where a target or targets are expected to turn up, is given, the accuracy of location estimation can be enhanced by disposing DFs in such a way that the area of interest is most effectively covered by the DFs. In this paper, we consider the problem of disposing DFs, i.e., determining the locations of DFs, in an n-DF system for the objective of maximizing the accuracy of estimation of the location(s) of a target (or targets) that is assumed to be located at some place in the area of interest. In general, neither the number of targets nor the exact locations (or distributions) of the targets are known a priori. However, without an exact information on the distribution of targets, one can conjecture possible areas where the target(s) may be located by considering the configuration of the ground, enemy’s intent and possible routes for movements of the target(s). The problem considered here is to determine the locations of DFs in such a way that they can estimate the locations of the targets accurately wherever they are located. We develop a method to find a disposition plan with which we can most effectively find the locations of the targets. We focus on cases where n = 3, i.e., three-DF systems, although the method suggested in this study can be applied to more general cases where n ⩾ 2. Note that three-DF systems are commonly used in practice by forces of many countries including the Korean Army. This research is motivated by a practical need for the operation of DF systems in the Korean Army, which has developed new DFs and plans to deploy them into the fields. Although the accuracy of the DF has been improved significantly through technical advances, there has been little advance, if any, in the (effective) operation of DF systems. Since disposition of DFs may be the most critical factor for the performance of a DF system as stated earlier, we focus on the development of a method for optimal disposition of DFs in this study. One should determine locations of DFs considering the shape and size of the area of interest and restrictions on disposition. It is assumed in this research that the area of interest is given. In general, the system operator selects the area of interest using information on the deployment of enemy troops, configuration of the ground, and road conditions. In practical situations, the area of interest may be composed of several mutually disjoint and disconnected areas due to geographical features of the ground or operational reasons. In addition, the importance of these areas may differ for different areas, which means that the probabilities that the target is in different areas may be different. We devise a heuristic method to dispose DFs for an accurate estimation of the location of a target in the area of interest. Because of errors occurring when a DF generates directional data, one cannot estimate the location of a target exactly, but can estimate only the probability that the target is in a (probable) region of which the size and location are estimated or specified by the system operator. This probability will be called the probability of coverage (POC) throughout the paper. From the definition, one can see that the POC depends of the size of the region, that is, under the same condition, if the region is larger, the POC is larger. When a certain disposition plan of DFs is given, POC can be estimated by an analytical method or a simulation-based method using one of location estimation algorithms such as the point method, the angle method and the line method (Li & Quek, 1998). In this study, POC is used as the criterion to measure the goodness of a certain disposition alternative. There are a number of studies on the problem of estimating location of a target. Stansfield (1947) suggests an algorithm called the line method, and Sklar and Ladany (1993) present a transformation method in which a line is transformed to a point and linear regression is used to estimate the location of a target. Li and Quek (1998) compare several algorithms and suggest a two-stage angle method, in which a weighting strategy is applied to the line method. Recently, Lee and Kim (2008) develop a new analytical method based on a nonlinear programming formulation for the line method, which can be applied to three-dimensional (3D) location estimation. In addition, Lee and Kim (2007) suggest a method for determining a route of a search resource to search visually multiple areas of interest of which POCs are given and assumed to decrease as time passes. On the other hand, research on the disposition of DFs is very rare. Jenkins, 1991 and Poisel, 2002 suggest empirical strategies for disposition of DFs. For instance, to cover a certain area of interest using a three-DF system, they recommend the centroid method, in which the distance between the locations of the DFs is approximately the same as the distance between the centroid of the area of interest and the centroid of the DF locations. However, these strategies cannot be applied to problems of disposing DFs to find the location of even a single target that is expected to be located at one of several separated areas of interest. We cannot use the strategies of Jenkins and Poisel to find locations of multiple targets that are expected to be scattered over two or more areas of interest. To our best knowledge, there has been no quantitative method for evaluation of disposition alternatives. In this paper, we suggest a two-stage heuristic method to determine a disposition plan of DFs that results in the maximum POC for a region of a given size (area), i.e., the most accurate location estimation for a given area of interest. If the location of the target is known, an optimal disposition of DFs can be determined by maximizing the POC associated with a given region. However, since the location of the target is not known, we need to consider all probable sites for the target. If we are given the probabilities that the target is located in all possible sites within the area of interest, we can evaluate disposition alternatives with the weighted average of POCs associated with those possible sites (weighted by the probabilities the target is located in the sites). Since we need to evaluate disposition alternatives when we solve the disposition problem, we need a method for computing the POC for a given region as well as a method for location estimation. In the algorithm suggested in this study, we use the line method, a well-known algorithm for location estimation, for estimating the target location and a simulation-based method for estimating POC. Using these methods, we solve the disposition problem in two steps. In the first step, we solve a one-dimensional disposition problem in which locations of DFs are restricted to be on a predetermined line. In the second step, we solve a two-dimensional disposition problem in which the restriction is relaxed, using the result of the first step. In both steps, local search methods are used for improving solutions. In this research, we assume: the area of interest may be composed of multiple mutually disjoint and disconnected sub-areas; the importance of these sub-areas may differ (the probabilities that the target is in the sub-areas may be different), and their relative importance is given; errors in the directional data of the DFs follow the normal distribution (Lee & Jung, 2001); and there is no information distortion on the directional data due to topography (configuration of land such as mountains and hills). 2. Estimating the target location and associated probability of coverage In this section, we describe methods used in this research for estimating the location of a target and the probability of coverage (POC) associated with the estimated target location. As mentioned earlier, we use the line method for estimating the location of a target. Once the target location is given, we estimate the POC associated with a region that encloses the estimated target location. This POC will be used as a measure for the goodness of a disposition alternative in the algorithm suggested in this research.

In this paper, we considered the problem of disposing direction finders (DFs) for better operation of direction finders for the objective of maximizing the accuracy of location estimation. Because of the difficulty in developing an exact method for the problem, we presented a two-stage heuristic algorithm in which a simulation-based method is used for estimating probability of coverage for each disposition alternative and a local search method using the cyclic coordinate descent method is used for finding the best locations of the DFs. In the first stage, locations of DFs are restricted to be located on the baseline, and then the restriction is relaxed in the second stage to find better locations for the DFs. Results of computational experiments on a number of test problems showed that the algorithm can give good disposition plans in a reasonable amount of CPU time. Even though there exist slight differences in the locations of DFs obtained from different replications (because of the nature of simulation), one can get a general idea on where to locate DFs to cover the area of interest effectively. In this study, we focused on three-DF systems since three-DF systems are most commonly used in real situations. Without much modification, however, the suggested method can be applied to more general cases, in which there are more than three-DFs in a system. Also, with certain modifications, one can devise a method for the disposition problem for cases in which a DF system is used along with a nearby DF system to estimate the location of a target. It is assumed in this study that there is no information distortion on the directional data due to topography (configuration of land such as mountains and hills), although there actually may be in real circumstances. Development of a method for adjusting directional data based on geographical analysis is needed for accurate directional data and a better performance of a DF or a DF system, and it is left for a future study. In addition, we need to solve another type of decision problems in the battlefield. Once multiple targets are detected and associated target regions are estimated by a DF system, we need to physically search the target region in order to identify the types and exact locations of the targets for further military operations. Since the targets may move, we need to complete the physical search as quickly as possible. In this case, it is necessary to solve a problem of finding the target within a limited time by determining a route for the physical search.