DOC

Improved Relaxation algorithm for Passive Sensor Data association

By Aaron Coleman,2014-05-29 19:48
11 views 0
Improved Relaxation algorithm for Passive Sensor Data association

    Improved Relaxation Algorithm for Passive Sensor Data Association

     Cheng OuyangHong-bingJiJin-long Yang

    (School of Electronic Engineering, Xidian University, Xi’an, 710071, China)

    Abstract: The Lagrangian relaxation algorithm is widely used for passive sensor data association. However, there are two major problems about it. Firstly, the cost function of the algorithm is computed by using least square estimation of the target position without taking the estimation errors into account. To solve this problem, a modified cost function is derived which can reflect the correlation between measurements more reasonably owing to the integration of estimation errors. Secondly, due to the fact that building the candidate assignment tree would take a lot of CPU time, we propose a statistic test based on indicator function with a great improvement of the computational efficiency. Simulation results show that both the correlation accuracy and the computational efficiency of the improved relaxation algorithm are higher than that of the traditional one.

    Key words: multidimensional assignment; Lagrangian relaxation; passive sensor; data association 1 Introduction

    In the passive sensor data association problem, it is a key issue to determine from which target, if any, a particular measurement originates. Such a problem can be solved by a wide range of algorithms including greedy heuristics, tabu search, simulated annealing, genetic algorithms, neural networks, and Lagrangian relaxation [1]. Among these algorithms, Lagrangian relaxation-based methods have been found to perform well in tracking applications [2]. The advantage of relaxation approach is that the resulting dual optimal cost is a lower bound of the feasible cost and, hence, provides a measure of how close the feasible solution is to the optimal solution. For the passive sensor data association problem, the feasible solution costs are typically within 1% of their corresponding dual optimal costs [3].

    The Lagrangian relaxation algorithm introduced in [3] solved a 3-D assignment problem as a series of 2-D subproblems, by relaxing the third constraint and appending it to the cost function using Lagrange multipliers. However, when , multiple sets of constraints have to be relaxed. In the method used by S?4

    Poore [4], the constraints are relaxed one set a time, and then the -1 dimensional subproblem can be S

    solved iteratively. However, the dimensional subproblem is not optimally solvable in polynomial S1

    time if , so Poore’s approach will take unacceptable computational resources for dense graphys. S?4

    Pattipati and Deb solved this problem by succesive relaxation and constraint enforcement, so all the S2

    dimensional constraints are relaxed simultaneously, and then the subproblem is a 2-D assignment problem that can be optimally solved in pseudo-polynomial time [5].

    These algorithms above are built upon the same cost function which represents a generalized likelihood so that track association becomes a generalized likelihood ratio test (GLRT). Unfortunately, the GLRT does not necessarily maximize the probability of correct track associations. Recently, Kaplan derived a cost function in [6] as the limit of the likelihood when the target state is random and uniformly distributed over a space that approaches infinite support. However, such a cost function is derived for active sensors, but not for passive sensors. This paper proposed a modified cost function derived for passive sensors and the performance of which is better than that of the generalized likelihood function owing to the integration of estimation errors.

    Another key issue to the Lagrangian relaxation algorithm is that building the candidate assignment tree would take a lot of CPU time. Chummun presented a fast data association algorithm which combined clustering techniques with a multidimensional assignment method in a systematic manner [7]. Because the

     1

    assignment problem is partitioned into small subproblems, the CPU time required for building the candidate assignment tree is reduced. However, the designed parameters used to estimate the variable cluster size are selected empirically, and the dihedral angles used in clustering can not sufficiently reflect the possibility that two lines of sight (LOS) come from the same target. A statistic test based on indicator function is proposed in this paper, which can achieve the same result as that of Lagrangian relaxation algorithm in some special cases, thus a part of correct pairs can be selected directly without redundant relaxation and enforcement processes, and then the possible set can be simplified according to the constraint conditions so that more correct pairs can be picked out by repeating such a process. 2 Problem formulation

    TSuppose that the actual position of target is , and the position of sensor is X(,,)xyzjsjjjj

    T, then the measurements from sensor are . zX(,,)xyzssisssss

    ????xxjs????arccos22????()()xxyy,?,v????jsjssisi??ss??(,)zXXv!!?!???h (1) ??sijssiss??v????si??ssi??szz????js??arctan??22??()()xxyy,?,jsjs??????

    where v is the measurement noise of sensor . Suppose that the measurement error is zero mean ssis

    TGaussian white noise, then and . Taking a measurement from each sensor, we E()0vE()vvRsisisissss

    zzz,,...,can build a -tuple set of , which has a joint Gaussian probability density function as S??12iiSi12S

    follow,

    f(,,,)zzzX12iiSij12S

    ui()s (2) S??PTui1()1s??D1s????????!,,,,exp(,)(,)1zXXRzXXhhP???sijsssijsD1/2??????sss??2??s12Rs??

    where is an indicator function, defined as ui()s

    0,0ifi?s (3) ui()?s1,otherwise?

    Suppose that clutters are uniformly distributed in the field of view, the joint probability density function of measurements from clutters is

    ui()sS??1f (4) ???cVs1s??

    where V is the volume of the field of view of sensor . ss

    zzz,,...,The cost function of -tuple associated with target is given by the negative Sj??12iiSi12S

    likelihood ratio as follow

     2

    ˆcff!,zzzXln(,,,|);?iiiiiSijc121212SS

    S??PVDss??!,,,[()1]ln(1)()lnuiPui (5) ?sDs1/2s??s12()Rs??

    T??1?????,,uihh()(,)(,)zXXzXX??ssijssijsss????2Rs??

    So the problem of passive sensor data association can be reformulated as the following -D Sassignment problem,

    nnnS12 (6) min~c???iiiiii1212SS!!!000iii12S

    subject to

    nnn3S2?~!;!1;1,2,,in????iii1112Siii000!!!23S?nnn?3S1?!;!1;1,2,,in~????iii2212S (7) iii000!!!?13S??nnnS112?!;!1;1,2,,in????iiiSS12S~iii000!!!?121S?

    where , represent the measurement number of sensor , and are binary association ~nsS,1,2,...,siiis12S

    zzz,,,variables such that ~1 if the -tuple is associated with a candidate target, S??12iiSiiii12S12S

    otherwise, it is set to zero.

    The computational cost of the -D problem grows exponentially with the increase of the number of S

    sensors and measurements. It is impossible to find the optimal solution in polynomial time even under the

    assumption of unity detection probability and no spurious measurements, hence is commonly referred to as

    NP-hard problem. The generalized -D assignment algorithm proposed by Pattipati and Deb solved this S

    problem by successive relaxation and constraint enforcement [5], so all the ()D constraints are S2relaxed simultaneously, and then the subproblem is a 2-D assignment problem that can be optimally solved

    by the auction algorithm as follows [8]:

    Consider persons wishing to divide among themselves objects. For each person there is a NNinonempty subset of objects that can be assigned to . An assignment is a set of person-object Ai()iS

    pairs (,)ij such that for all , for each person there is at most one pair , jAi()(,)ijS(,)ijSi

    and for each object there is at most one pair . Let arepresent a given integer value that a (,)ijSjij

    person associates with an object , and p represent the price of object , then the auction jAi()ijj

    algorithm proceeds iterative and terminates when a complete assignment is obtained. There are two phases

    in each iteration, i.e., the bidding phase and the assignment phase.

    Bidding Phase: For each person that is unassigned under the assignment : iS

    Compute the “current value” of each object given by jAi()

    vap!, (8) ijijj*Find a “best object” having maximum value j

    vvmax, (9) *jAiij()ij

    *and find the best value offered by objects other than j

    wap!,max. (10) ??**ijj,:(),ijjAijj

     3

    *(If is the only object in we define to be , or, for computational purposes, a number w,)Ai()j*ij

    that is much smaller than .) v*ij

    *Compute the “bid” of person for object given by ij

    . (11) bpvwaw!?,?!,?,,******ijjijijijij

    Assignment Phase: For each object : j

    Let be the set of persons from which receives a bid in the bidding phase of the iteration. Pj()j

    If is nonempty, increase to the highest bid Pj()pj

    , (12) pbmaxjiPjij()

    *remove any pair (if one exists) from the assignment , and add the pair to where (,)ij(,)ijSS

    * is some person in attaining the maximum above. Pj()i

    3 Improved Relaxation Algorithm

    3.1 Modified Cost Function

    The cost function is a key factor to the Lagrangian relaxation algorithm especially for passive sensor

    data association, where due to the nonlinearity in the measurement equation, the actual position of targets

    can not be observed directly, and a least square estimation would bring about some estimation errors.

    At a given instance of time, the likelihood function is given by

    ffffzzXzXzZXzZX,...,,,!??? (13) ;?;?;?;?1121:11:1kSkjijijSiSj112SS

    If X is the actual position of target , then the likelihood function is shown in Equation (2). jj

    ˆHowever, the actual position of target is unknown, so it is replaced by the least squares estimation , Xjj

    then the estimation errors should be taken into account. If letting represent the covariance matrix, then Cs

    the modified likelihood function can be expressed by

    ˆ(fzzzX(,,,)12iiSij12S

    ui()s (14) S??TP1()ui1sD??1sˆˆ????????zXXCzXXhhP!,,,,exp(,)(,)1???sijsssijsD1/2sss????????2??s1C2s??

    where

    TT??ˆˆ (15) CzXXzXXRHRH!,,?Ehh(,)(,);?;?XXssijssijssfss????

    ˆwhere R is the fusion covariance matrix of estimation X, and H is the Jacobian matrix represented fjX

    by

    ˆ?hXX(,)js (16) HX?XˆXXj

    Similar to the generalized likelihood function, the modified cost function can also be represented by

    the negative likelihood ratio as follow,

     4

    ˆ((cff!,zzzXln(,,,|);?iiiiiSijc121212SS

    S??PVDss??!,,,[()1]ln(1)()lnuiPui (17) ?sDs1/2s??s12()Cs??

    T??1?????,,ui()(,)(,)zhXXzhXX??ssijssijsss????2()Cs??

    As seen from the comparison of Equations (5) and (17), the modified cost function is different from the original one only in the covariance matrix. It is more reasonable because the least squares estimation of the actual position would bring about some estimation errors which should be considered in the covariance matrix.

    3.2 Statistic Test Based on Indicator Function *As seen from Equation (11), if is the only object in , w is defined to be ,), then the Ai()j*ij

    *“bid” of person for object is given by ij

    , (18) bpvw!?,?!)****ijjijij

    * for object is the highest, which means that no matter how many iterations it is, the “bid” of person ji

    *so the object can be only assigned to person in this case. ji

    *Consider the -tuple as a candidate person-object association, if is the only object in 2,ii??krr*, then the object can be only assigned to person . A()irkk

    Recall that each -D assignment problem consisted of lists with measurements in list nSSs

    . Each -tuple represents a candidate pair, and all the possible correct pairs are put (,...,)iisS1,...,S1S

    into a possible set P, M (19) Pii(,...,)??1Skk1k

    where M is the total number of candidate pairs.

    We define the indicator function as ?()is

     (20) ?()(,),1,...,iNUMPisS!!ss

    where the function means counting the number of element in set P. NUM()?is**If equals one, it indicates that is the only object in , where ?()iA()issk** (21) !!{,...,,...,}\,iiiiiiksSsss1kkkk

    *then we can assign to directly without relaxation and enforcement, and the possible set can be isk

    simplified according to the constraint Equation (7). After that, the indicator function will be calculated

    *******again, and there may be new , making , resulting in a chain reaction. iii,?()1issss

    According to this principle, a new method of statistic test based on indicator function is proposed. Firstly, a two-sensor statistic test using the distance between two lines of sight from two different sensors has been made [9], and a part of correct pairs is selected according to the indicator function. If there is no

    ** making , then a three-sensor statistic test based on the relationship between the angle ?()1iiss

    measurements from three different sensors will be made [9], and another part of correct pairs can be

    **selected until there is no making ?()1i again. After these two statistic tests, the size of the possible iss

    set will become very small, in some cases all the correct pairs can even be picked out directly, so the redundant relaxation and enforcement processes are avoided, a great improvement of the computational efficiency. A brief approach of the algorithm is presented as follows:

     5

    Step 1 Initialize, construct the possible set . Let the correct set and set , Pflag0ZNULL

    where is used to mark whether the three-sensor statistic test has been made or not. flag

    Step 2 Delete the impossible candidate pairs from the possible set through the two-sensor statistic P

    test.

    Step 3 If the possible set is not empty, go to Step 4, otherwise, the algorithm finishes and the P

    associated pairs in the correct set are the final results. Z

    *Step 4 Compute the indicator function of according to Equation (20). If there is P?()iiss

    **making , put the candidate pair including into the correct set and simplify the possible set Z?()1iiss

    ** according to Equation (7), then go to Step 3. If there is no making and , go to P?()1iflag0iss

    Step 5, otherwise, go to Step 6.

    Step 5 Delete the impossible candidate pairs from the possible set through the three-sensor P

    statistic test, then set and go to Step 3. flag1

    Step 6 Compute the modified cost functions of candidate pairs in P according to Equation (17).

    Step 7 Pick out the remaining correct pairs using the Lagrangian relaxation algorithm according to the modified cost functions, then the algorithm finishes and the associated pairs in the correct set Z are the

    final results.

    4 Simulation Results

    A. The comparison of different cost functions.

    In this simulation, a simple illuminative case with the probability of detection and the false P1d

    alarm density is considered. The number of sensors is three and the number of targets is two, so the P0f

    total number of possible assignment hypotheses is only four. Then we can compare the performances of different cost functions without considering the assignment algorithm in this case. The positions of the three sensors are , respectively, and the measurement standard deviation is sss0,10,0,10,0,0,0,0,0;?;?;?123

    . For a given target separation, 10000 independent Monte Carlo simulations were run. In each ?0.005s

    simulation, two targets with fixed distance are generated randomly in the filed of view. changes dd

    from 0.005km to 1km with a step of 0.005km. The resulting percent of correct assignment as the p(%)

    function of target separations are plotted in Fig. 1. dkm()

    As seen from Fig. 1, when the target separation is too big or too small, in which cases it is either too easy or too difficult to distinguish different targets. Thus, the two different cost functions can get almost the same result. However, when the target separation is appropriate, the modified cost function results in a significantly better performance than the original one. This is due to the fact that the modified function integrates the least squares estimation errors, which can reflect the correlation between measurements more reasonably.

     6

    Fig. 1 Percent of correct assignment versus target separation with . ?0.005s

    B. The performance of the algorithms with different target numbers.

    In this simulation, targets in a queue are observed by three sensors, where , and N{5,10,15,20}N

    NNN,,,111??????the positions of the targets are , , where means t(5,5,1)??jd?j!,,?,1,...,,(j??????222??????

    taking the integer part of the numbers and the target separation is . The positions of the three dkm1

    sensors are , respectively, and the measurement standard deviation is sss0,10,0,10,0,0,0,0,0;?;?;?123

    . A comparison of the two algorithms with different target numbers is made in the perfect ?0.01s

    detection case. The average results of 1000 Monte Carlo simulations are shown in Fig. 6, Fig. 7 and Fig. 8, respectively.

    The percent of correct assignment versus target number is shown in Fig. 2. An obvious trend in the results is that the large target number results in unreliable data association, which is due to the fact that a large number of targets may create a large number of ghosts, making deghosting difficult. However, the percent of correct assignment of the improved algorithm is always higher than that of the original one, the reason behind which lies in our modified cost function discussed before.

    The simulation time versus target number is shown in Fig. 3. It is obvious that when the target number is small, the running time of the two algorithms is close to each other. However, when the target number is large, the running time of the improved algorithm is much less than that of the original one, and the larger the target number is, the greater the gap is. This is due to the fact that when the target number is small, the candidate assignment tree is small, so the traditional Lagrangian relaxation algorithm requires only a few iterations to get the correct results and the advantage of the indicator function is not that obvious. However, when the target number is large, the candidate assignment tree is large, so the traditional Lagrangian relaxation algorithm requires a large number of iterations to get the correct results, while the improved relaxation algorithm can select a part of correct pairs by using the indicator function without iterations, and then the possible set can be simplified, a significant improvement of the computational efficiency.

    Fig 2. Percent of correct assignment. Fig. 3 Simulation time.

    5 Conclusion

    In this paper we present an improved relaxation algorithm for passive sensor data association, which improves the traditional one in two aspects.

    First, the cost function is a key factor to the Lagrangian relaxation algorithm especially for passive target tracking problems, where due to target state-to-measurement nonlinear, the actual position of targets can not be observed directly, and the least square estimation would bring about some estimation errors. However, the generalized likelihood function is computed by using least square estimation of the target

     7

    position without taking the estimation errors into account. So a modified cost function is derived which can reflect the correlation between measurements more reasonably and the performance of which is better than that of the generalized likelihood function owing to the integration of estimation errors.

    Second, due to the fact that building the candidate assignment tree would take a lot of CPU time. A statistic test based on indicator function is proposed which can improve the computational efficiency. It is proved that the method based on indicator function can get the same result as that of Lagrangian relaxation algorithm in some special cases, so a part of correct pairs can be selected directly without redundant relaxation and enforcement processes, then the possible set can be simplified according to the constraint conditions so that more correct pairs can be picked out by repeating such a process.

    The simulation results show that the correlation accuracy and computational efficiency of the improved relaxation algorithm are both higher than that of the traditional one, implying good application prospect.

    ACKNOWLEDGEMENTS

    This work was supported by the National Natural Science Foundation of China No. 60871074.

    References

    [1] Popp, R., Pattipati, K. R., and Bar-Shalom, Y. An M-best multidimensional data association algorithm for multisensor

    multitarget tracking. IEEE Transactions on Aerospace and Electronic Systems, 37, 1 (Jan. 2001), 22-39. [2] Poore, A., and Robertson, A. J., III (1997) A new class of Lagrangian relaxation based algorithms for a class of

    multidimensional assignment problems. Computational Optimization and Applications, 8 (1997), 129-150. [3] Pattipati, K., Deb, S., Bar-Shalom, Y., and Washburn, R. (1992) A new relaxation algorithm and passive sensor data

    association. IEEE Transactions on Automatic Control, 37, 2 (Feb. 1992), 197-213.

    [4] Poore, A., and Rijavec, N. (1993) A Lagrangian relaxation algorithm for multidimensional assignment problems arising

    from multitarget tracking. SIAM Journal of Optimization, 3, 3 (Aug.1993), 544-563.

    [5] Deb, S. Yeddanapudi, M., Pattipati, K., and Bar-Shalom, Y. (1997) A generalized S-D assignment algorithm for

    multisensor-multitarget state estimation. IEEE Transactions on Aerospace and Electronic Systems, 33, 2 (Apr. 1997),

    523-538.

    [6] Kaplan L., Bar-Shalom Y., Blair W. D. Assignment costs for multiple sensor track-to-track association. IEEE

    Transactions on Aerospace and Electronic Systems, 2008.

    [7] M. R. Chummun, T. Kirubarajan, K. R. Pattipati, Y. Bar-Shalom. Fast Data Association Using Multidimensional

    Assignment with Clustering. IEEE Transactions on Aerospace and Electronic Systems, 2001, 37, (3): 898-913. [8] Bertsekas D P. (1988) The auction algorithm: A distributed relaxation method for the assignment problem. Annals of

    Operat. Res., vol.14, 105-123, 1988.

    [9] Liu Hang, Dou Li-hua, Pan Feng, Dong Ling-xun. (2007) Research on data association in three passive sensors

    network. IEEE International Conference on control and Automation, May 30 to June 1, Guangzhou, China, 2007:

    3235-3238.

     8

Report this document

For any questions or suggestions please email
cust-service@docsford.com