In this paper we present a novel approach to global localization using an RGB-D camera in maps of visual features. For large maps, the performance of pure image matching techniques decays in terms of robustness and computational cost. Particularly, repeated occurrences of similar features due to repeating structure in the world (e.g., doorways, chairs, etc.) or missing associations between observations pose critical challenges to visual localization. We address these challenges using a two-step approach. We first estimate a candidate pose using few correspondences between features of the current camera frame and the feature map. The initial set of correspondences is established by proximity in feature space. The initial pose estimate is used in the second step to guide spatial matching of features in 3D, i.e., searching for associations where the image features are expected to be found in the map. A RANSAC algorithm is used to compute a fine estimation of the pose from the correspondences. Our approach clearly outperforms localization based on feature matching exclusively in feature space, both in terms of estimation accuracy and robustness to failure and allows for global localization in real time (30Hz).
MCL overcomes the limitations of EKFs as mentioned earlier. It was successfully used in @cite_21 for vision-based localization of a tour-guide robot in a museum using a map of the ceiling and a camera pointing to it. In contrast to this approach, we do not rely on odometry measurements to predict the pose, and are not restricted to planar motion. Additionally, MCL would report incorrect locations after unexpected robot motions or sensor outages. Sensor Resetting Localization @cite_15 partially substitutes particles by new ones directly generated from the sensor measurements when the position estimate is uncertain. Mixture-MCL @cite_16 combines standard MCL with dual-MCL to drastically reduce computational cost and localization error. Dual-MCL also generates particles from the current sensor measurements and was shown to deal well with the kidnapped robot problem when properly combined with standard MCL. We do not need a reset process, since our estimation is independent from the prior state. Our approach could be used in combination with Monte Carlo Localization (MCL) for efficient particle initialization and weighting. However, the results of our experiments show that our estimate is accurate enough to be used as final result, without any filtering.
@cite_15 @cite_21 @cite_16
2131865378 2160584648
Mobile robot localization is the problem of determining a robot’s pose from sensor data. This article presents a family of probabilistic localization algorithms known as Monte Carlo Localization (MCL). MCL algorithms represent a robot’s belief by a set of weighted hypotheses (samples), which approximate the posterior under a common Bayesian formulation of the localization problem. Building on the basic MCL algorithm, this article develops a more robust algorithm called MixtureMCL, which integrates two complimentary ways of generating samples in the estimation. To apply this algorithm to mobile robots equipped with range finders, a kernel density tree is learned that permits fast sampling. Systematic empirical results illustrate the robustness and computational efficiency of the approach.  2001 Published by Elsevier Science B.V. This paper presents a new algorithm for mobile robot localization, called Monte Carlo Localization (MCL). MCL is a version of Markov localization, a family of probabilistic approaches that have recently been applied with great practical success. However, previous approaches were either computationally cumbersome (such as grid-based approaches that represent the state space by high-resolution 3D grids), or had to resort to extremely coarse-grained resolutions. Our approach is computationally efficient while retaining the ability to represent (almost) arbitrary distributions. MCL applies sampling-based methods for approximating probability distributions, in a way that places computation "where needed." The number of samples is adapted on-line, thereby invoking large sample sets only when necessary. Empirical results illustrate that MCL yields improved accuracy while requiring an order of magnitude less computation when compared to previous approaches. It is also much easier to implement. A cluster algorithm for graphs called the (MCL algorithm) is introduced. The algorithm provides basically an interface to an algebraic process defined on stochastic matrices, called the MCL process. The graphs may be both weighted (with nonnegative weight) and directed. Let @math be such a graph. The MCL algorithm simulates flow in @math by first identifying @math in a canonical way with a Markov graph @math . Flow is then alternatingly expanded and contracted, leading to a row of Markov Graphs @math . Flow expansion corresponds with taking the @math power of a stochastic matrix, where @math . Flow contraction corresponds with a parametrized operator @math , @math , which maps the set of (column) stochastic matrices onto itself. The image @math is obtained by raising each entry in @math to the @math power and rescaling each column to have sum @math again. The heuristic underlying this approach is the expectation that flow between dense regions which are sparsely connected will evaporate. The invariant limits of the process are easily derived and in practice the process converges very fast to such a limit, the structure of which has a generic interpretation as an overlapping clustering of the graph @math . Overlap is limited to cases where the input graph has a symmetric structure inducing it. The contraction and expansion parameters of the MCL process influence the granularity of the output. The algorithm is space and time efficient and lends itself to drastic scaling. This report describes the MCL algorithm and process, convergence towards equilibrium states, interpretation of the states as clusterings, and implementation and scalability. The algorithm is introduced by first considering several related proposals towards graph clustering, of both combinatorial and probabilistic nature. A discrete uncoupling process for finite spaces is introduced, called the Markov Cluster Process or the MCL process. The process is the engine for the graph clustering algorithm called the MCL algorithm. The MCL process takes a stochastic matrix as input, and then alternates expansion and inflation, each step defining a stochastic matrix in terms of the previous one. Expansion corresponds with taking the @math th power of a stochastic matrix, where @math . Inflation corresponds with a parametrized operator @math , @math , that maps the set of (column) stochastic matrices onto itself. The image @math is obtained by raising each entry in @math to the @math th power and rescaling each column to have sum 1 again. In practice the process converges very fast towards a limit that is invariant under both matrix multiplication and inflation, with quadratic convergence around the limit points. The heuristic behind the process is its expected behavior for (Markov) graphs possessing cluster structure. The process is typically applied to the matrix of random walks on a given graph @math , and the connected components of (the graph associated with) the process limit generically allow a clustering interpretation of @math . The limit is in general extremely sparse and iterands are sparse in a weighted sense, implying that the MCL algorithm is very fast and highly scalable. Several mathematical properties of the MCL process are established. Most notably, the process (and algorithm) iterands posses structural properties generalizing the mapping from process limits onto clusterings. The inflation operator @math maps the class of matrices that are diagonally similar to a symmetric matrix onto itself. The phrase diagonally positive semi-definite (dpsd) is used for matrices that are diagonally similar to a positive semi-definite matrix. For @math and for @math a stochastic dpsd matrix, the image @math is again dpsd. Determinantal inequalities satisfied by a dpsd matrix @math imply a natural ordering among the diagonal elements of @math , generalizing the mapping of process limits onto clusterings. The spectrum of @math is of the form @math , where @math is the number of endclasses of the ordering associated with @math , and @math is the dimension of @math . This attests to the uncoupling effect of the inflation operator.