In this paper we describe an algorithm to compute cycle constraints that can be used in many graph-based SLAM algorithms; we exemplify it in hierarchical SLAM. Our algorithm incrementally computes the minimum cycle basis of constraints from which any other cycle can be derived. Cycles in this basis are local and of minimum length, so that the associated cycle constraints have less linearization problems. This also permits to construct regional maps, that is, it makes possible efficient and accurate intermediate mapping levels between local maps and the whole global map. We have extended our algorithm to the multi-robot case. We have tested our methodology using the Victoria Park data set with satisfactory results.

In this paper, we present a hierarchical mapping method that allows us to obtain accurate metric maps of large environments in real time. The lower (or local) map level is composed of a set of local maps that are guaranteed to be statistically independent. The upper (or global) level is an adjacency graph whose arcs are labeled with the relative location between local maps. An estimation of these relative locations is maintained at this level in a relative stochastic map. We propose a close to optimal loop closing method that, while maintaining independence at the local level, imposes consistency at the global level at a computational cost that is linear with the size of the loop. Experimental results demonstrate the efficiency and precision of the proposed method by mapping the Ada Byron building at our campus. We also analyze, using simulations, the precision and convergence of our method for larger loops.