Place Recognition Using Keypoint Similarities in 2D Lidar Maps

摘要

In addition to presenting a place recognition framework capable of constructing 2D laser SLAM maps at scales of hundreds of kilometers, we have also provided an application-based comparison of approximate nearest neighbor algorithms. While we were able to produce large-scale maps in our previous SLAM research [Bosse and Zlot, 2008a], we were somewhat limited in scale by the requirement of using pose uncertainty when searching for loop closures. Maintaining a place recognition algorithm independent of map building alleviates this limitation. In comparing static and dynamic variants of three approximate nearest neighbor algorithms (kd-trees, locality sensitive hashing, and spill-trees) for both offline and online place recognition, we have observed that kd-tree-based structures have the best performance in terms of accuracy, query time, build time, and memory usage. We further found that we can use a very large approximation factor, thereby reducing the query time by two orders of magnitude while still maintaining sufficient accuracy. By utilizing multiple salient keypoint matches to identify submap matches, the effective probability of detection is significantly boosted. We have produced similar results on other datasets collected while driving through city and suburban streets, and have additionally applied our algorithm to data collected during day-to-day operations at an industrial site.