Polynomial-Time Algorithms for the Exact MMOSPA Estimate of a Multi-Object Probability Density Represented by Particles

In multi-object estimation, the traditional minimum mean squared error (MMSE) objective is unsuitable: a simple permutation of object identities can turn a very good estimate into what is apparently a very bad one. Fortunately, a criterion tailored to sets-minimization of the mean optimal sub-pattern assignment (MMOSPA)-has recently evolved. Aside from special cases, exact MMOSPA estimates have seemed difficult to compute. But in this work we present the first exact polynomial-time algorithms for calculating the MMOSPA estimate for probability densities that are represented by particles. The key insight is that the MMOSPA estimate can be found by means of enumerating the cells of a hyperplane arrangement, which is a traditional problem from computational geometry. Although the runtime complexity is still high for the general case, efficient algorithms are obtained for two special cases, i.e., (i) two targets with arbitrary state dimensions and (ii) an arbitrary number of one-dimensional targets.