انتساب بهبود یافته بهینه سازی کلونی مورچه ردیابی چند هدف

Detecting and tracking ground targets is crucial in military intelligence in battlefield surveillance. Once targets have been detected, the system used can proceed to track them where tracking can be done using Ground Moving Target Indicator (GMTI) type indicators that can observe objects moving in the area of interest. However, when targets move close to each other in formation as a convoy, then the problem of assigning measurements to targets has to be addressed first, as it is an important step in target tracking. With the increasing computational power, it became possible to use more complex association logic in tracking algorithms. Although its optimal solution can be proved to be an NP hard problem, the multidimensional assignment enjoyed a renewed interest mostly due to Lagrangian relaxation approaches to its solution. Recently, it has been reported that randomized heuristic approaches surpassed the performance of Lagrangian relaxation algorithm especially in dense problems. In this paper, impelled from the success of randomized heuristic methods, we investigate a different stochastic approach, namely, the biologically inspired ant colony optimization to solve the NP hard multidimensional assignment problem for tracking multiple ground targets.

Typically, target tracking starts with track initiation where successive measurements are analyzed to determine whether they constitute a trajectory, so that presence of a target could be declared. Then the generated track is maintained by updating the target kinematics with the measurements obtained. If there are not (frequent) enough measurement collected from the target then the track is dropped. There are several reasons why a track does not receive a valid measurement for updating. The main reason is that the probability of detection (PD) of the sensors used is always less than perfect. Target being obstructed by an object and not being able to assign the correct measurement due to the presence of other targets are amongst other reasons. When there is more than one target present in the surveillance region it is referred to as multiple target tracking and data association problem, i.e., assigning the right measurement to the right track, has to be addressed efficiently. Although multi-target tracking has been widely studied (Bar-Shalom and Blair, 2000, Deb et al., 1999, Popp et al., 2001 and Wang et al., 1999), most of the algorithms have weaknesses when targets move close to one another, as they are in a convoy. Efficient and fast measurement to target assignment with reduced computational load has an increased importance in such applications. Since the problem to be dealt with is a NP hard problem, there is no complete solution available, thus, near optimal solutions with reduced computation becomes more important in terms of resource management as the computation time saved could be used to perform other tasks within the surveillance system. Thus, the data association problem, where the measurements are assigned to the established tracks, is a crucial step in multi-target tracking applications. From the simple nearest neighbor method to a complex multiple hypothesis tracking, tracking literature is filled with a plethora of solutions in finding which measurement came from which target in a complex multi-target environment. These methods show progressive advancement in performance by exploiting the escalating computational capacities available. Recently, research on assignment methods has shown great success for solving the data association problem (Bar-Shalom and Blair, 2000, Deb et al., 1999, Popp et al., 2001, Sinha and Kirubarajan, 2004 and Wang et al., 1999). In the assignment method, the data association problem is converted to a 0–1 optimization problem where the total distance/benefit of assigning targets to measurements is minimized/maximized (Wang et al., 1999). The early assignment algorithms use only a list of measurements from a single time scan, which will be correlated with the targets being tracked. This way, the resulting data association problem can be formulated as a 2D asymmetric assignment problem, which can be solved efficiently by polynomial time algorithms such as Munkres, auction and JVC (Bar-Shalom & Blair, 2000). With cheap computational power available however, a desire arose to exploit further lists of measurements in making data association decisions. Unfortunately, additional lists render the assignment a multidimensional problem, which is well known to be NP hard (Deb et al., 1999). Thus, a variety of approximations were proposed to find solutions to the multidimensional assignment problem. In the state of the art method, Lagrangian relaxation is used to find a solution in polynomial time (Sinha & Kirubarajan, 2004). This method also provides a measure of accuracy for the solution found (Bar-Shalom and Blair, 2000, Deb et al., 1999, Popp et al., 2001 and Sinha and Kirubarajan, 2004). However, in Sinha and Kirubarajan (2004) it is stated that with this method, a complete assignment hypothesis tree is needed and over 90% of the computing power is spent on the creation of this assignment hypothesis tree rather than solving the assignment problem. To reduce the computational effort, a randomized method was proposed in Sinha and Kirubarajan (2004) to build the assignment hypothesis tree randomly and to solve the assignment problem on this reduced tree. This method has demonstrated superior performance both in computational time and accuracy. Furthermore, the randomized method was able to create multiple assignment hypotheses without any additional computation; i.e., it can produce “m” good solutions, which can also be exploited by multiple-target tracking algorithms. Inspired by this success, we turn to investigate a different randomized method for solving the assignment problem encountered in multi-target tracking applications. Our interest lies in a biologically inspired algorithm, the ant colony optimization (ACO). The ACO is colony based algorithm designed to solve a wide range of discrete combinatorial problems such as traveling salesman and quadratic assignment problems (Demirel and Toksari, 2006, Gambardella et al., 1999, Schaub and Mermoud, 2009, Tsutsui, 2008 and Wong and See, 2009). Also, in Randall (2004) ACO was utilized to address the generalized assignment problem. Moreover, there are various examples that ACO has been employed to solve real life problems such as the weapon-target assignment problem for resource management (Shang, 2008) or the cell assignment problem in PCS networks (Shyua, Linb, & Hsiaoa, 2006). Although there have been successful applications of ACO for finding approximate solutions to NP hard problems of multidimensional assignment, the application of the method to the assignment problem in multi-target tracking has been rather limited. The only direct application, to the authors’ best knowledge, is presented in Xu and Wang (2006) where ACO was used to solve the association problem both between measurements and measurements and tracks in a bi-static sonar system. There are several variants of ACO algorithm for different applications and in this study, we will be using the MAX–MIN ant system (MMAS) variant of the ACO for the solution of multidimensional assignment problem in GMTI tracking. This paper is organized as follows; in Section 2 mathematical definition of the multidimensional assignment problem is presented where the ACO approach is outlined Section 3. Section 4 describes the simulation environment and simulation results are presented in Section 5. Last section gives some concluding remarks.

In this paper we presented an ant colony optimization based assignment algorithm for multi-target tracking in a scenario. The proposed algorithm has been tested on a challenging ground target tracking scenario involving targets moving in formation, i.e., a convoy, as well as crossing targets. For the high detection probabilities, the ACO tracker was able to successfully track all of its targets by integrating measurement information from different time scans. This information gain through measurement integration is crucial for tracking targets that move in formation within the measurement update rate considered in our simulations. Because the crossing targets were close to each other for a limited number scans, measurement integration gain was less stringent for that case. When the detection probability got lower, the ACO algorithm was still able to track the crossing targets accurately. However, increased errors were introduced for the group of targets that move in formation. Measurement update rate was not adequate to cover the target maneuvers considered in that case. The ACO solver was able to find the optimum assignment with a very high probability for the dense multidimensional assignment problem considered. Furthermore, as a swarm optimization algorithm it not only found the optimal assignment but also gave a ranked list of alternative assignments without any additional computational cost. This list of alternative solutions may provide important information in target tracking applications as the assignment with the optimum cost may not be congruent with the ground truth. The proposed assignment scheme has proved to be a good candidate to address the challenging and equally important task of precise tracking of individual target moving in a convoy.