Target Tracking on Computational Grids
Eduardo L. Pasiliao · 47th AIAA Aerospace Sciences Meeting including The New Horizons Forum and Aerospace Exposition · 2009
This paper presents analytical results and methodologies for exact and heuristic solution algorithms for the multidimensional assignment problem (MAP). The MAP is an NP-complete generalization of the classical linear assignment problem, and is central to multi-sensor data fusion and, particularly, the problem of multi-sensor multi-target tracking. The solutions are based on specific forms of tree-based representations of the MAP, which allow for decomposing its feasible set into several regions. This is expected to improve convergence rates of the computational procedures make them highly parallelizable. The computational grid implementation of the MAP has the goal of enabling a real-time tracking of ground targets by a formation of cooperative UAVs, without the need for centralized computations. The proposed solution procedures include several branch-and-bound algorithms that rely on different tree representations of the MAP, as well as multi-start greedy heuristics. The proposed variations of exact and heuristic algorithms will be specifically suitable for tackling MAP instances of various configurations: those where the number of dimensions is much greater than the number of elements per dimension, those where this relationship is reversed, and those where the number of dimensions and their sizes are approximately equal. I.