Algorithms for Multitarget Multisensor Tracking

摘要

This report results from a contract tasking Technical University of Crete as follows: I. Construction of a set of problem instances of multidimensional assignment problems in the context of target tracking. These will be used as benchmark problems. They will be constructed so that their optimal solution will be known, and they will vary in size and dimension. Furthermore they will be nontrivial to solve, since they will be used for evaluation of the proposed algorithms in the experimental runs. 2. Design and implementation of data structures to represent the massive sparse data sets associated with each instance of the problem. These data structures will be general enough to handle variable dimension and degrees of sparsity. Specific tasks to be performed by the algorithms, such as function evaluation and construction of feasible and partial solutions, should require minimum computational effort and memory. 3. Design and implementation of heuristic and exact algorithms for solving the multidimensional assignment problem. The heuristic algorithm will receive the dimension of the instance and the sparse multidimensional array as inputs, and it will provide the partitions that represent the targets. The exact algorithm will use a branch-and-bound scheme to provide exact solutions to the problem. All the codes will be written using the C programming language.