A parallel maximum likelihood algorithm for robot mapping

Several recent algorithms address simultaneous localization and mapping as a maximum likelihood problem. While many proposed methods focus on efficiency or on online computation, less interest has been devoted to investigate a parallel or distributed organization of such algorithms in the perspective of multi-robot exploration. In this paper, we propose a parallel algorithm for map estimation based on Gauss-Seidel relaxation. The map is given in the form of a constraints network and is partioned into clusters of nodes by applying a node-tearing technique. The identified clusters of nodes can be processed independently as tasks assigned to different processors. The graph decomposition induces also a hierarchical organization of nodes that could be exploited for more sophisticated relaxation techniques. Results illustrate the potential and flexibility of the new approach.