A NEW RELAXATION ALGORITHM AND PASSIVE SENSOR DATA ASSOCIATION

被引:164
作者
PATTIPATI, KR [1 ]
DEB, S [1 ]
BARSHALOM, Y [1 ]
WASHBURN, RB [1 ]
机构
[1] ALPHATECH INC,TECH STAFF,BURLINGTON,MA 01803
关键词
D O I
10.1109/9.121621
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
This paper is concerned with the static problem of associating measurements at a given time from three angle-only sensors in the presence of clutter, missed detections, and an unknown number of targets. The measurement-target association problem is formulated as one of maximizing the joint likelihood function of the measurement partition. Mathematically, this formulation of the data association problem leads to a generalization of the three-dimensional (3-D) assignment (matching) problem, which is known to be NP hard; that is, the complexity of an optimal algorithm increases exponentially with the size of the problem, since no known polynomial time algorithm exists. Suboptimal algorithms of quantifiable accuracy are therefore of considerable importance. The new solution to the optimization problem developed in this paper is a Lagrangian relaxation technique that successively solves a series of generalized two-dimensional (2-D) assignment problems, with the worst case complexity of O(3kn3), where k is the number of relaxation iterations and n is the number of reports from each sensor. The dual optimization problem is solved via an acclerated subgradient method. A useful feature of the relaxation approach is that the resulting dual optimal cost is a lower bound on the feasible cost and, hence, provides a measure of how close the feasible solution is to the (perhaps unknowable) optimal solution. For the passive sensor data association problem, the feasible solution costs are typically within 1% of their corresponding dual optimal costs. A comparison of our relaxation algorithm to the optimal branch-and-bound and suboptimal row-column algorithms demonstrates that our algorithm is superior to these alternative approaches in terms of computational complexity and/or measurement-target association accuracy. Finally, the algorithm is illustrated via several application examples.
引用
收藏
页码:198 / 213
页数:16
相关论文
共 57 条
[1]  
ALLEN TG, 1988, MISTC TR406 ALPH INC
[2]   GAUSSIAN SUM APPROACH TO MULTI-TARGET IDENTIFICATION-TRACKING PROBLEM [J].
ALSPACH, DL .
AUTOMATICA, 1975, 11 (03) :285-296
[3]  
[Anonymous], 2016, LINEAR NONLINEAR PRO
[4]  
[Anonymous], 1971, STOC 71, DOI DOI 10.1145/800157.805047
[5]   AN ALGORITHM FOR THE 3-INDEX ASSIGNMENT PROBLEM [J].
BALAS, E ;
SALTZMAN, MJ .
OPERATIONS RESEARCH, 1991, 39 (01) :150-161
[6]   SIGNATURE METHODS FOR THE ASSIGNMENT PROBLEM [J].
BALINSKI, ML .
OPERATIONS RESEARCH, 1985, 33 (03) :527-536
[7]   TRACKING IN A CLUTTERED ENVIRONMENT WITH PROBABILISTIC DATA ASSOCIATION [J].
BARSHALOM, Y ;
TSE, E .
AUTOMATICA, 1975, 11 (05) :451-460
[8]   TRACKING METHODS IN A MULTITARGET ENVIRONMENT [J].
BARSHALOM, Y .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1978, 23 (04) :618-626
[9]  
BARSHALOM Y, 1988, TRACKING DATA ASS
[10]  
Bertsekas D. P., 1988, Annals of Operations Research, V14, P105, DOI 10.1007/BF02186476