IEEE Robotics & Automation Magazine - September 2017 - 71

●

●
●

For the experiments, the sensors used are:
odometry that gives us the relative movement of wheels,
framerate of 50 Hz
one to five lidars SICK LMS151-10100, range data in
[0; 50 m], angle in [−45°; 225°], resolution of 0.25°, framerate of 50 Hz
low-cost GPS with accuracy of about 5 m
Ashtech proflex 800 GPS RTK receiver (only used for
results evaluation).

Perceptive Triplets
At the moment, to validate our concept, we use a perfect
map. A proprietary database has been developed (even if we
plan to use OpenStreetMap later). At each time, our system
needs to know the available triplets, i.e., the triplets for
which the features are in the field of view of one sensor (at
least) and not occluded. Then the corresponding request
will provide all landmarks that are contained in this area
and detectable by our system (for example, white lines are
not observed by the laser so are not useful here). Moreover,
with any landmark, the database provides the corresponding
occlusion area.
Kidnapped Robot
In this section, the vehicle is initially located with a high
uncertainty. We show the behavior of our algorithm in
two situations.
Experimentation with One Lidar and with Initial
16-m Uncertainty on the Localization
For this experiment, the initial vehicle position provided to
the algorithm has an 11 m error in a 16-m uncertainty area.
The evolution of the algorithm is visible in Figure 6. To
begin, the system evaluates that the more interesting landmark to detect for our objective (here, a confidence higher
than 0.9 and an accuracy of 5 # 5 cm 2) is the wall identified
by number 61. The system tries to detect a line in the
data laser-range finder in a huge ROI because of the low
accuracy of the vehicle position. After that, the system realizes an update by associating the line returned by the detector with the searched landmark 61. The system tries to
detect another landmark in an area smaller than the previous one but not yet very precise. Then the system fails to
detect the next two selected triplets. At this moment, the
probability of detecting the good triplet becomes very low,
so the process reassociates the first observation. Here, there
are a lot of neighbors for the first triplet, so the system has to
often reassociate the observation without doing a true association. Finally, the localization is achieved after 17 steps.
With One Lidar, One GPS Receiver, and
22-m Initial Uncertainty
For this experiment, a GPS receiver is available. It provides a
position with approximately 5-m accuracy and is treated as
another available sensor. The selection process of the best
triplet is exactly the same as described in the "Perceptive Trip-

lets" section. Adding a GPS just adds a triplet. To begin, the
process selects the GPS because it is the most relevant (highest criterion C, see the "Triplet Selection Criterion" section).
After the GPS has triggered an update, other triplets are
selected because they provide better accuracy. After that, the
GPS is no longer used because it is no longer relevant. Finally,
the localization objective is achieved after only three steps.
Results for a Moving Vehicle
The vehicle is equipped with two range finders, one behind
the vehicle and one in front. Its initial uncertainty is fixed to
5 m. Our system will select naturally the best triplet, i.e., the
best landmark with the most appropriate range finder. The
error of estimated trajectory has a 9.1 cm mean value, a
median value of 7.8 cm, and a standard deviation of 5.4 cm
(Figures 7 and 8).
In the environment used, the land is sloping, but our system does not take that into account. Moreover, the map used
is not exact, even if the precision is supposed to be better than
5 cm for each landmark. These points explain why we do not
have a perfect localization.
Confidence: 1

Confidence: 0.014

Real
Position
Initial
Position
61

61
69
(a)

(b)

Confidence: 0.0147

Confidence: 0.998

(c)

(d)

Figure 6. The evolution of the algorithm in the kidnapped robot
situation. (a) The election of the first triplet; the landmark to detect
is number 61. The ambiguity is very high because there is possible
confusion with eight other landmarks (in blue). (b) The detection
of the first landmark, The system tries to detect landmark 61 (in
red) but sees the wall 69 (black) and achieves (false) updating.
(c) Update 13: the reassociation of the first observation 69. Now,
the estimated position is corresponding to the real one (even if
the accuracy is not yet good). (d) Update17: the real position with
good precision (about 10 cm) and good confidence (0.99).

SEPTEMBER 2017

IEEE ROBOTICS & AUTOMATION MAGAZINE

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - September 2017