Vehicle relocation is the problem in which a mobile robot has to estimate the self-position with respect to an a priori map of landmarks using the perception and the motion measurements without using any knowledge of the initial self-position. Recently, RANdom SAmple Consensus (RANSAC), a robust multi-hypothesis estimator, has been successfully applied to offline relocation in static environments. On the other hand, online relocation in dynamic environments is still a difficult problem, for available computation time is always limited, and for measurement include many outliers. To realize real time algorithm for such an online process, we have developed an incremental version of RANSAC algorithm by extending an efficient preemption RANSAC scheme. This novel scheme named incremental RANSAC is able to find inlier hypotheses of self-positions out of large number of outlier hypotheses contaminated by outlier measurements.
There are also some offline algorithms that are scalable to large environments. They aim to estimate the self-position by matching between the global landmark map and a local feature map. The essence of these algorithms is to generate a small set of good initial hypotheses by matching minimal set of features and landmarks @cite_6 @cite_7 . As briefly described in section , RANSAC is one of such algorithms. Their computational cost depends not on the environment size but on the number of features, therefore they are efficient especially in sparse environments @cite_1 . However, even these algorithms are not directly applicable to online relocation, where available computation time is always limited and typically constant. Moreover, larger number of features would be required in the case of dynamic environments since there are usually many outlier features. This makes it difficult even to apply some pre-computed lookup tables that could accelerate the map matching @cite_13 .
@cite_13 @cite_1 @cite_7 @cite_6
1601378499 1986909116 2135493014 2118121744
Localization, that is the estimation of a robot's location from sensor data, is a fundamental problem in mobile robotics. This papers presents a version of Markov localization which provides accurate position estimates and which is tailored towards dynamic environments. The key idea of Markov localization is to maintain a probability density over the space of all locations of a robot in its environment. Our approach represents this space metrically, using a fine-grained grid to approximate densities. It is able to globally localize the robot from scratch and to recover from localization failures. It is robust to approximate models of the environment (such as occupancy grid maps) and noisy sensors (such as ultrasound sensors). Our approach also includes a filtering technique which allows a mobile robot to reliably estimate its position even in densely populated environments in which crowds of people block the robot's sensors for extended periods of time. The method described here has been implemented and tested in several real-world applications of mobile robots, including the deployments of two mobile robots as interactive museum tour-guides. In this paper we study the global localization problem in SLAM: the determination of the vehicle location in a previously mapped environment with no other prior information. We show that, using a grid sampling representation of the configuration space, it is possible to evaluate all vehicle location hypotheses in the environment (up to a certain resolution) with a computational cost that is bilinear: linear both in the number of map features and in the number of sensor measurements. We propose a pairing-driven algorithm that considers only individual measurement-feature pairings and thus, in contrast with current correspondence space algorithms, it avoids searching in the exponential correspondence space. It uses a voting strategy that accumulates evidence for each vehicle location hypothesis, assuring robustness to noise in the sensor measurements and environment models. The general nature of the proposed strategy allows the consideration of different types of features and sensor measurements. Using the popular Victoria Park dataset, we compare its performance with location-driven algorithms where the solution space is usually randomly sampled. We show that the proposed pairing-driven technique is computationally more efficient in proportion to the density of features in the environment. Many generic position-estimation algorithms are vulnerable to ambiguity introduced by nonunique landmarks. Also, the available high-dimensional image data is not fully used when these techniques are extended to vision-based localization. This paper presents the landmark matching, triangulation, reconstruction, and comparison (LTRQ global localization algorithm, which is reasonably immune to ambiguous landmark matches. It extracts natural landmarks for the (rough) matching stage before generating the list of possible position estimates through triangulation. Reconstruction and comparison then rank the possible estimates. The LTRC algorithm has been implemented using an interpreted language, onto a robot equipped with a panoramic vision system. Empirical data shows remarkable improvement in accuracy when compared with the established random sample consensus method. LTRC is also robust against inaccurate map data. In this paper we propose an algorithm to deter- mine the location of a vehicle in an environment represented by a stochastic map, given a set of environment measure- ments obtained by a sensor mounted on the vehicle. We show that the combined use of (1) geometric constraints considering feature correlation, (2) joint compatibility, (3) random sampling and (4) locality, make this algorithm lin- ear with both the size of the stochastic map and the number of measurements. We demonstrate the practicality and ro- bustness of our approach with experiments in an outdoor environment.