Robust Global Feature Based Data Association With a Sparse Bit Optimized Maximum Clique Algorithm

This paper presents a robust solution to the mobile robotics data association problem based on solving the maximum clique problem (MCP) in a typically sparse correspondence graph, which contains compatibility information between pairs of observations and landmarks. Bit sparse optimizations are designed and implemented in a new algorithm BBMCS, which reduces computation and memory requirements of a leading general purpose maximum clique solver, to make it possibly the best exact sparse MCP algorithm currently found in the literature. BBMCS is reported to achieve very good results in terms of robustness with few assumptions on noise and visibility, while managing very reasonable computation time and memory usage even for complex large data association problems.