Global Localization Based on a Rejection Differential Evolution Filter

Abstract

One of the most interesting properties of the RDE (Rejection Differential Evolution) filter is its efficiency in terms of convergence speed. The algorithm is able to exploit the perceptual information to converge in the initial perception cycle if, from the initial pose, the robot perceives any distinctive characteristic of its environment. A second characteristic is the low number of pose solutions required to successfully localize the robot. For the test environment under consideration, a population of 100-150 elements is enough, except in non-informative situations where the number of hypotheses can grow up very fast and a certain number of pose solutions is required to maintain a feasible area. The number of population elements required to avoid the premature elimination of feasible hypotheses has not been determined theoretically in the evolutive algorithms field, but in our experimental tests, a number between 10 and 25 poses is required to maintain all feasible hypothesis. In case of non informative situations where the sensors only let the robot perceive a small part of the environment (for instance, when a robot is in a corner) the potential number of hypotheses can rise very fast, which originates that the algorithm fails when using a normal pose set size. This problem can be addressed in two ways: turning the robot until a maximum environment area is perceived by the sensors or to detect the uninformative situation and increase the pose set size. The first approach is easier and requires less computational resources. As in the majority of the population-based optimization methods, the algorithm robustness increases with the population set size. If we consider the effect of the population size on the accuracy of the algorithm, we need to consider the explored number of poses, since the total number of explored poses is roughly speaking the product of the iteration number and the population size. But in our test, the accuracy is maintained up to a certain number of explored poses. This behavior differs completely from Monte Carlo method. As noticed by several authors (Doucet, 1998; Liu & Chen, 1998), the basic Monte Carlo filter performs poorly if the proposal distribution, which is used to generate samples, places not enough samples in regions where the desired posterior probability distribution is large. This problem has practical importance because of time limitations existing in on-line applications. The use of a rejection threshold and a stopping criteria adjusted to the statistical characteristics of the objective function allows us to decrease considerably the population size while maintaining the accuracy level of the method. In previous works, a minimum population set of 250 ­ 300 elements were required, while in the RDE version a population