27 July 1999 Partial branch and bound algorithm for improved data association in multiframe processing
Author Affiliations +
A central problem in multitarget, multisensor, and multiplatform tracking remains that of data association. Lagrangian relaxation methods have shown themselves to yield near optimal answers in real-time. The necessary improvement in the quality of these solutions warrants a continuing interest in these methods. These problems are NP-hard; the only known methods for solving them optimally are enumerative in nature with branch-and-bound being most efficient. Thus, the development of methods less than a full branch-and-bound are needed for improving the quality. Such methods as K-best, local search, and randomized search have been proposed to improve the quality of the relaxation solution. Here, a partial branch-and-bound technique along with adequate branching and ordering rules are developed. Lagrangian relaxation is used as a branching method and as a method to calculate the lower bound for subproblems. The result shows that the branch-and-bound framework greatly improves the resolution quality of the Lagrangian relaxation algorithm and yields better multiple solutions in less time than relaxation alone.
© (1999) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Aubrey B. Poore, Aubrey B. Poore, Xin Yan, Xin Yan, } "Partial branch and bound algorithm for improved data association in multiframe processing", Proc. SPIE 3720, Signal Processing, Sensor Fusion, and Target Recognition VIII, (27 July 1999); doi: 10.1117/12.357166; https://doi.org/10.1117/12.357166

Back to Top