Mobile Localization and Interval Analysis

Defender: Q. BREFORT      Advisors: M. CEBERIO, L. JAULIN, V. KREINOVICH
ENSTA Bretagne - UTEP - Université d'Angers


To improve robotic research, a key point is localization. Indeed in order to accomplish its tasks, the robot must know first its environment in order to interact with it. There is numerous method to achieve localization in an unknown area, such as Kalman filter or Monte Carlo algorithm. Although they have proven their reliability, we will try to reduce the prerequisite of these method. For example Kalman filter assume that we have data on the previous position of the robot and Monte Carlo algorithm rely on random samplings. The aim of this paper is to focus on a new way to globally localize a robot, even with the presence of faulty measurements, through interval analysis with fewer prerequisite.
The problem of localization can be modeled as a constrained system and that we can solve using interval analysis and contractors. This way, through a paver, we find an area where the robot is guaranteed to be. But if false data are added, we cannot find the robot anymore. With Guaranteed Outlier Minimum Number Estimator algorithm implemented on the Ibex API, we ensure that even with faulty measurements the robot is localized in an area, independently of its previous state and without choosing random sampling. Furthermore we guarantee an accurate estimation of the number of outliers present on the model, which means an accurate localization. To accelerate the computation time, we used a Pairing method which only takes the best data of two beacons to localize the robot but also the data of the previous localization. The data selection is done by a maximum interval intersection and thus manages to omit the possible outliers too.

Interval analysis

In robotics, to model the surrounding environment of the robot we use sensors. Thus, the robot is loaded with many sensors, and each one of them send data that need to be processed in order to be useful for the robot. This operation is called data processing and it can be achieved with computers. But the main problem of the measurements are that they are not absolutely precise.
The measurement of a physical quantity x (e.g. body temperature) may differ from the true value. E.g., if you took your temperature and you measured 37.8 °C this does not mean you are exactly 37.8 °C. If the scales have an accuracy of +/- 0.3°C then your actual temperature is truly in [37.5°C,38.1°C]. Therefore, if the data we measure is inaccurate, the data we process will be also inaccurate and the resulting modeled environment will be false. The problem is to estimate the resulting inaccuracy.
Interval analysis is a tool to solve this problem. Instead of having classic values for a variable x, we have an interval such as x=[x-e;x+e] with e the given inaccuracy of the sensor.

Localization as a constrained system

We model our localization of a robot with a set of numerous beacons sending signal to the robot.

In underwater robotics, those beacons are sonars and we measure the distance between the two by using the time elapsed between the emission and the reception computed with the underwater sound speed. Thus we have a set of distance which we can represent as circle or rings with the inaccuracy which intersection should be the location of the robot. To plot the result as the Figure below we use a paver and the SIVIA algorithm. SIVIA, for Set Inversion via Interval Analysis, is explained in details in my thesis. We can say that from a constraint, SIVIA plot its representation with red boxes for inside, yellow for perhaps boxes, and blue the result is outside of this box. To improve computation time we also use contractors from the Ibex API.

Outliers and GOMNE

To plot the result of localization without outliers, we plot the intersection of all constraint to get the position of the robot. But with outliers, the intersection is empty. The goal of this research is to find a way to localize the robot in presence of outliers. First we used GOMNE with Ibex, Guaranteed Outlier Minimal Number Estimator, to eradicate the possible outliers. In the next table we can see the algorithm procedure. We run SIVIA and run test inclusion if we have any perhaps boxes or inside boxes and adjust parameters to rerun another SIVIA with updated parameters. ε is the SIVIA accuracy and q is the number of inliers.

GOMNE(in: ε=ε_{max},q=nb_{beacons})
1 Run Sivia(ε,q)
2 if box_{1}.isempty() == false, then break;
3 if box_{[0,1]}.isempty() == true, then q=q-1;
4 if box_{[0,1]}.isempty() == false, then ε =ε / 2;

The video shows you a quick demonstration of the algorithm with its results.

Pairing algorithm

To localize our robot in 2D we use multiple sensors but those informations may be redundant. Indeed in a 2D case, we need at least three distances to localize our robot. If we only have two, we still can localize the robot but we will have to differentiate two possible locations. Thus with x⃗=(x1,x2) the position of the robot, s⃗1,...,s⃗n the known sonar positions, we measure the distances di=d(s⃗i,x⃗) corresponding to each sonar. Without outliers, this problem is solvable but in our case we add outliers which can represent sonar deficiency.

To solve this problem we will use a pairing method: for each combination of sensor we get a new location for the robot at a different time t. The interval of maximum intersection of those location will be the updated location. The video shows you a quick demonstration of the algorithm with its results.