Hierarchic Single Cluster Graph Partitioning: A Sequential Place Recognition Method

Localization and mapping are essential tasks in mobile robotics. A purely odometry-based pose estimation accumulates errors caused by factors such as unequal wheel-diameters or wheel-slippage and is, therefore, inaccurate. The resulting error can be corrected by recognizing previously observed places and constraining the robots' relative poses. A common challenge of such place recognition methods arises from the incorrect association of different places, which can corrupt the resulting pose correction and, consequently, any map update. Therefore, we propose a novel place recognition method that enables the selection of a correct place recognition hypothesis from a set of possible matches.In this work, we make use of the fact that multiple robots' trajectories run parallel in many scenarios, like in warehouse corridors or on public roads. In such situations, place recognition can be regarded as a sequential task along the robots' trajectories. We study the problem of repetitive, periodic and indistinguishable landmarks for place recognition on regularly-spaced guideposts on German rural roads. By interpreting place recognition hypotheses as nodes of a k-partite graph, we introduce our novel selection method, the Hierarchic Single Cluster Graph Partitioning, that enables the robust selection of the correct hypotheses by finding the optimal path within the graph. The selected place recognition information is used to build a map incorporating multiple observations acquired from multiple vehicles.