A Scalable Localization Algorithm for High Dimensional Features and Multi Robot Systems

Abstract

Feature-based localization is a fundamental problem of multi robot systems. A robot has to estimate its self- position with respect to the environment, given a map or a database of environment features built by another mapper robot. Recent years, the robustness of high dimensional, descriptive features has been widely recognized. However, a computational difficulty arises from the fact that the time and the space costs of querying a high dimensional feature database is significant, in proportion to the size of database. Moreover, most of existing databases are not incremental, difficult to be built online by a mapper robot. Considering the problems, in this paper, we focus on the use of exact euclidean locality sensitive hashing (E2LSH), which has received much attention in approximate near neighbor (ANN) community. Based on the E2LSH technique, we extend the algorithm of Monte Carlo localization, and propose a novel algorithm that is scalable to high dimensional databases.