A NEW RELAXATION ALGORITHM AND PASSIVE SENSOR DATA ASSOCIATION
A NEW RELAXATION ALGORITHM AND PASSIVE SENSOR DATA ASSOCIATION
复制标题
DOI：
10.1109/9.121621
复制
发表时间：
1992-02-01
影响因子：
6.8
通讯作者：
WASHBURN, RB
中科院分区：
文献类型：
--
作者：
PATTIPATI, KR;DEB, S;WASHBURN, RB
本文研究了在杂波、漏检和目标数目未知的情况下，在给定的时间内，三个角度传感器的测量值相关联的静态问题。 将测量-目标关联问题转化为最大化测量划分的联合似然函数问题。 在数学上，这种数据关联问题的公式化导致了三维（3-D）分配（匹配）问题的泛化，这是已知的NP困难;也就是说，最佳算法的复杂性随着问题的大小呈指数级增加，因为不存在已知的多项式时间算法。 因此，具有可量化精度的次优算法具有相当大的重要性。 本文开发的优化问题的新的解决方案是一个拉格朗日松弛技术，连续解决了一系列广义二维（2-D）分配问题，最坏情况下的复杂度为O（3 kn 3），其中k是松弛迭代次数和n是从每个传感器的报告数。 对偶优化问题通过加速次梯度法求解。 松弛方法的一个有用的特征是，由此产生的对偶最优成本是可行成本的下限，因此，提供了一个衡量可行解与最优解（可能是不可知的）有多接近的度量。 对于被动传感器数据关联问题，可行解的成本通常在其相应的对偶最优成本的1%以内。 我们的松弛算法的最佳分支定界和次优行列算法的比较表明，我们的算法是上级这些替代方法的计算复杂度和/或测量目标关联精度。 最后，通过几个应用实例说明了该算法。
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.