An Uncertainty Propagation Architecture for the Localization Problem

Arnaud CLERENTIN, Laurent DELAHOCHE, Eric BRASSART, Cyril CAUCHOIS

CREA - Centre de Robotique, d'Electrotechnique et d'Automatique

IUT, département Informatique, Avenue des Facultés, 80000 Amiens – France

{Arnaud.Clerentin, Laurent.Delahoche}@u-picardie.fr

ABSTRACT

In this article, a dynamic localization method based on multi target

tracking is presented. The originality of this method is its capability

to manage and propagate uncertainties during the localization

process. This multi-level uncertainty propagation stage is based on

the use of the Dempster-Shafer theory. The perception system we

use is composed of an omnidirectional vision system and a

panoramic range finder. It enables to treat complementary and

redundant data and thus to construct a robust sensorial model which

integrates an important number of significant primitives. Based on

this model, we treat the problem of maintaining a matching and

propagating uncertainties on each matched primitive in order to

obtain a global uncertainty about the robot configuration.

KEYWORDS : mobile robot localization, omnidirectional

vision, uncertainty management, multi target tracking

1 INTRODUCTION

Localization is a fundamental problem in mobile robotics.

Mobile robots have to be able to locate themselves in their

environment in order to accomplish their tasks. In order to act

in a robust way and to increase the reliability in operation, the

robot should consider data as uncertain and all decision

should be made using data of an appropriate level of

certainty. The localization method presented in this paper has

the particularity to integrate uncertainty quantification and to

propagate low-level data uncertainties along the localization

process. The goal is to obtain a global uncertainty about the

robot localization. In this purpose, we propose an architecture

which allows to manage and propagate uncertainty. The

Dempster-Shafer theory [8] is the key tool of this

architecture. Indeed, this formalism enables to easily treat

uncertainty since it permits to attribute mass not only on

single hypothesis, but also on union of hypothesis. We can

thus express ignorance. This is the main difference with

Bayesian theory.

Localization methods can be classified as being relative

(based on the use of proprioceptive data) or absolute (based

on the use of exteroceptive data). Absolute methods consist in

determining the robot’s position with the only use of

exteroceptive data: the robot’s configuration is calculated in

the environment reference without using previous

information [1][5]. But the problem of this kind of

localization is linked to the matching stage between the

sensorial model and the theoretical map of the environment:

this stage can be highly combinative and non robust in

connection with multiple solutions, for example with

symmetrical environments. In order to increase the reliability

and decrease the computation time of these methods, the use

of multi target tracking can be interesting. In the case of the

localization problem, multi target tracking can be seen as a

propagation of an initial matching. This paradigm is

abundantly treated is the literature, for example by Bar

Shalom [4]. The methods generally used are probabilistic

ones and the two main are JPDAF (Joint Probabilistic Data

Association Filter) [4] and MHT (Multiple Hypothesis

Tracker) [3]. But these two methods have some drawbacks.

They need to know the false alarm rate. The JPDAF takes

into account a fixed number of targets and doesn’t initialize

new tracks. The MHT has combinatorial problems.

Therefore, we propose in this paper a multi target tracking

method for the localization problem based on the DempsterShafer theory used in a framework called extended open

world [7]. Since this method uses DS theory, it naturally

integrates our uncertainty propagation architecture and

enables to manage an uncertainty for each target. It allows

also to treat the problem of target apparition and momentarily

disappearance.

This paper is organized as follow. In a first part, we present

our perception system. Then we deal with the target

classification stage based on the exploitation of the

complementary and redundancy of the data provided by our

perception system. Section 4 explains our target tracking

algorithm. The paper ends with experimental results

presentation.

2 THE OMNIDIRECTIONAL PERCEPTION

SYSTEM

Our original perception system uses two omnidirectional

sensors in cooperation: the omnidirectional vision system

SYCLOP and a panoramic range finder system [10] (Fig. 1).

These two sensors have been developed and used

independently within our laboratory. The range finder system

is an active vision sensor [10]. It allows to obtain a robust

omnidirectional range finding sensorial model. The interest of

this system is on the one hand its low cost and on the other

hand its robustness facing a high incidence angle. The

SYCLOP system [2], similar to the COPIS one [14], is

composed of a conic mirror and a CCD camera. It enables us

to get radial straight lines which characterize angles of every
vertical object such as, for example, doors, corners, edges

(Figure 2)...

Figure 1: The perception system and the prototype we built.

Figure 2: Principle of the omnidirectional sensor SYCLOP

This two omnidirectional sensors association is interesting

since it permits to manage some complementary and

redundant information within the same sensorial model :

 With SYCLOP, the radial straight lines give the angular

position of every vertical object, but the information of

depth cannot be achieved in one acquisition: it is not

possible to differentiate with this only sensor the notion

of opening (corridor, opening of door...) and the notion

of vertical object (closed door, radiator,...) (Figure 3).

 The range-finder system, following a segmentation stage

[10], permits to exploit sensorial primitives that are

segments. In this case we have the notion of depth, but it

is impossible to differentiate two vertical objects placed

in the same alignment: two closed doors placed on the

same wall. It misses the notion of angle that will be

provided by the SYCLOP system.

So this association enables to construct a highly descriptive

sensorial model, richer than the models obtained with each

sensor individually (Figure 3).

Figure 3: Principle of the omnidirectional sensorial cooperation.

3 SENSORIAL MODEL CONSTRUCTION

3.1- Segment primitives determination and associated

uncertainty computation

The final primitives of the sensorial model are segments.

They are determined with two types of approaches [6]:

 data complementarily approach. The first case concerns

the data detected by SYCLOP but not by the depth

sensor. In this case, the treatment consists in cutting up

segments gotten with the range finder in subsegments

according to the radial straight lines of the vision system

(case 2 of Figure 4). The second case concerns the data

detected by the depth sensor but not by SYCLOP. In this

case, the breakpoint gotten by the Duda Hart

segmentation method is directly considered (case 3 of

Figure 4).

 data redundancy approach. The redundant aspect is

characterized by the detection of a vertical landmark with

the two sensors (Figure 4). In this case, we use the radial

straight line to determine the segment endpoint. Indeed,

we consider that the SYCLOP sensor has a better angular

precision.

Figure 4: The different cases of the cooperation algorithm.

After the determination of the sensorial model, we compute

the reliability, i.e. the uncertainty of each segment. This stage

is preponderant for the multi-target tracking stage presented

in this article. In this purpose, we take into account five

criteria.

The first criteria is the mean distance between the range

finding points contained by the segment and this segment. If

this mean distance is high, it means that the points are not

very well aligned, so this segment is not very sure.

The second criteria is the number of points supported by the

segment. This criteria is only discriminative when the

segment contains very few points. In this case, it is not very

sure.

The third criteria is the segment density of points. As shown

in [10], a major drawback of this kind of triangulation depth

sensor is a decreasing resolution with an increasing distance.

So, this criteria, which is linked to the mean distance between

the sensor and the set of point, is a good indicator of the

segment reliability (more distant the set of points is, less the

precision is).

The fourth criteria analyzes if the segment is detected by

one or by the two sensors. The worst case occurs when the

two extremities of the segment are detected only by the laser

range finder (case 1 of Figure 5). The best case occurs when

the two extremities are detected by the two sensors (case 5 of

Figure 5). Between these extreme cases, we can distinguish

three others cases [6].
case 1

S1

Range finding

segments

Radial

line

Radial

line

case 5

Figure 5 : the two extreme cases of the fourth criteria.

The last criteria concerns a gray level curve extracted from

the SYCLOP image. We take into consideration five

concentric gray level circles whose average is made. We

obtain thus one gray level curve from 0 to 360 degrees. We

apply on the portions of curve which represent a segment a

least square algorithm. We obtain a straight line and we

compute the mean difference of the gray level values from

this line. If the difference is high, this means that the gray

level sector is not constant. This case occurs generally when a

landmark has not been detected by SYCLOP, so this segment

is not sure (Figure 6).

(gray level)

(degree)

Figure 6: an example of gray level curve concerning the fifth criteria.

The fusion of these five criteria is made thanks to the

Dempster-Shafer theory [8]. Our frame of discernment (FOD)

is composed of two elements: "YES" and "NO"

corresponding to the assertions “The segment exists” and “the

segment does not exist”. We show on Figure 7 one of the five

BPAs which integrates the ignorance quantification. The

Dempster rule of combination [8] gives mseg(YES), mseg(NO)

and mseg(Θ). The segment uncertainty is denoted by this set

mass mseg. We have studied on 50 experimental sensed map

the conflict between these five criteria. Indeed, these five

criteria are redundant and conflict can arise. Experimentally,

we have noticed that it is not important (mean conflict =

0.13). This shows that these criteria are pertinent and lead to a

consensual decision. But, in certain cases, the conflict is high.

So, we have decided to work in an open world context [12],

i.e. not to normalize. Indeed, in case of high conflict, as

Zadeh showed, a normalization can lead to an aberration. On

the other hand, a non normalization gives us a precious

indication about the conflict between the five criteria. So we

report the conflict (the mass on ∅) to the ignorance Θ.

m1: mean distance of the range findings points from the 

segment

0

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

1

0 2,5 6

(cm )

B.P.A

B.P.A .ofYES

B.P.A .of{YES,NO}

B.P.A .ofNO

Figure 7: B.P.A of the first classification criterion ({YES,NO}=Θ)

3.2- High level primitives determination

The next stage consists in determining high semantic level

primitives which are: "corner", "edges", "wall" and "other"

(Figure 8). The "other" class characterizes landmarks which

are not "corner", "edges", "wall".

Figure 8: High level semantic primitives.

We use the high semantic level entities "corner", "edge" and

"other" because the azimuth angle of the junction of the two

segments is a "strong" angle (important existence

probability): it is a discriminating angle in connection with

the occultation problem. The angles of a segment primitive

can be false angle due to occultation.

As in the previous step, we compute an uncertainty linked

to each primitive. This uncertainty is determined by

propagating the segment(s) uncertainty(ies) computed on the

previous step. We reach this aim in two stages. Firstly, we

determine the type of the primitive. Secondly, we compute its

uncertainty.

We determine the primitive type by fusing two criteria

(Figure 9). The first criteria m1 is the angle α between two

consecutive segments S1 and S2 of the sensorial model. The

second criteria m2 is the minimal distance d between the

"junction" extremities of the two segments S1 and S2. The

belief functions of these two criteria are discussed on [9].

Figure 9: angle criteria and minimal distance criteria.

The fusion is made thanks to the Dempster rule of

combination and enables to obtain the mass set mtype by

fusing m1 and m2. The two criteria taken into account are

complementary, so there is no conflict. The taken decision is

the one which has the maximal credibility.

The second stage consists in computing the high level

primitive uncertainty. In this purpose, we take into account

two uncertainties:

 the uncertainty of the segment(s) composing the

primitive

 the uncertainty on the primitive type computed on the

first stage.

gray level curve of

segment 8. The

approximation is good,

this segment is sure

gray level curve of segment

18. The approximation is

bad, a landmark has not

been detected by Syclop
The FOD is composed of two elements: YES and NO

corresponding to the assertions “YES, the primitive exists”

and “NO, the primitive does not exist”. The first criteria

m1prim is linked to the segment uncertainty coefficient mseg.

For a primitive wall: 











Θ = Θ

=

=

( ) ( )

( ) ( )

( ) ( )

1

1

1

prim seg

prim seg

prim seg

m m

m NO m NO

m YES m YES

For a primitive corner, edge or other composed of two

segments S1 et S2:















Θ = Θ ⊕ Θ

= ⊕

= ⊕

( ) ( ) ( )

( ) ( ) ( )

( ) ( ) ( )

1 2

1

1 2

1

1 2

1

S

seg

S

prim seg

S

seg

S

prim seg

S

seg

S

prim seg

m m m

m NO m NO m NO

m YES m YES m YES

The second criteria m2prim for a primitive of type T is

computed according to the following rules:



















Θ = = −

= =

=

∑

∑

⊆Θ ≠ ∩ ≠∅

⊆Θ ∩ =∅

( ) ( ) ( ) ( )

( ) ( ) ( )

( ) ( )

, ,

2

,

2

2

m m A Pl T Cr T

m NO m A Cr T

m YES Cr T

A A T A T

prim type

A A T

prim type

prim

The mass for the YES is equal to the belief we have on T,

i.e. the credibility of T Cr(T). The mass for the NO is equal to

the disbelief on T, i.e. the mass which is not on T. The mass

for Θ represents the uncertainty about T, i.e. the mass which

is on focal elements which include T. Doing this, we respect

the constraint that the mass sum must be equal to 1.

By fusing the two criteria m1prim et m2prim, we obtain the

uncertainty of the primitive through mprim(YES), mprim(NO)

and mprim(Θ). Doing this, we estimate the uncertainty of the

high level primitives by propagation of the segments

uncertainty.

So, at the end of this step, we have four lists of primitives (a

list of corners, of edges, etc.) with an associated uncertainty

for each primitive through the set mass mprim. This uncertainty

includes the uncertainty about the type of the primitive and

the uncertainty about the existence (the reliability) of the

segments which compose the primitive.

4 DYNAMIC LOCALIZATION METHOD

4.1 - Algorithm

Our localization method is based on a tracking of high

semantic level primitives: we propagate the matching made at

an acquisition n on an acquisition n+1. So, the problem to

solve is the following: propagation of an initial matching on

the acquisitions realized during the robot’s displacement. The

initial matching is done in manual way or with the absolute

localization method presented in [6]. Then we try to pursue

the matching. To confirm a matching propagation, we must

before generate a prediction which will be compared to the

observations. So we have developed a prediction system

based on a linear extrapolation of the azimuth angle curves of

the high level primitives (on experimental results, we can

note that the angles variation is locally linear): we generate a

predictive observation vector composed of angles got by

linear extrapolation (Figure 11). For example, if we examine

the evolution of the landmark angles Θ1, Θ2 and Θ3 (Figure

10), we remark that the curve can be extrapolated in order to

have a prediction Θ4p. If a matching is done between Θ4p

and an angle observation, the track is propagated.

Figure 10: evolution of landmark angles.

Figure 11: principle of angular measures extrapolation.

Our prediction heuristic is robust since it is based on angle

curves of high level primitives: the extrapolated measures

correspond to “strong” angles whose evolution curves can not

confuse themselves because they do not suffer of occultation

phenomena.

At this level, the problem is to match for each type of

primitive the p angular observations obtained at the

acquisition t with the q predictions. These q predictions are

computed from the Nmes last observations. To reach this aim,

we use the Dempster-Shafer theory in the framework of

extended open word [7] because of the introduction in the

FOD of an element noted * which represents all the

hypothesis which are not modeled.

For each prediction Qj (j∈[1,q]), we apply the following

algorithm.

 The frame of discernment Θ is composed of:

 the p observations (Pi means “the prediction Qj is

matched with the observation Pi”)

 and the element * which means “the prediction Qj

cannot be matched with one of the p observations”.

So:Θ = {P1,P2 ,...Pp ,*}

 The matching criterion is the angular difference between

observation Pi and prediction Qj (Figure 11).

 For each observation Pi, we compute :

 ( ) mi Pi the mass associated with the proposition “Pi is

matched with Qj”.

 ( ) mi Pi the mass associated with the proposition “Pi is

not matched with Qj”.

 ( ) mi Θi the mass represented the ignorance concerning

the observation Pi.

The BPAs are shown on Figure 12.
m1: difference in angle between prediction and 

observation

0

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

1

0 15 30 (degrees)

BPA

m(Pi)

m(Pi U Pi)

m(Pi)

Figure 12: BPA of the matching criterion.

After the treatment of all the Pi observations, we have p

triplets : ( ) m1 P1 ( ) m1 P1 ( ) m1 Θ1

( ) m2 P2 ( ) m2 P2 ( ) m2 Θ2

...

( ) mp Pp ( ) mp Pp ( ) mp Θp

We fuse these triplets and we get mmatch(P1), mmatch(P2),...,

mmatch(Pp), mmatch(*) and mmatch(Θ) by using the condensed

formulas obtained by Gruyer in [11].

 The final decision is the one which has the maximal BPA.

Experimentally we can note that ambiguities can appear

after this step, but only on the segment primitives: a segment

observation Pi can be matched with two segment predictions

Qi, this case is impossible in the reality. So we use, like

Gruyer, only for this class of primitives, a traditional

assignment Hungarian algorithm to match one observation

with one prediction [11].

Finally, this matching method enables us to easily manage

primitive appearances and disappearances:

 If an element Pi of the FOD cannot be matched, Pi is an

appeared primitive and a track can be initialized.

 If a prediction Qj is matched with *, the track is

temporarily or definitively lost.

4.2 - Management of an appearance

From the position computed with the matched primitives,

we try to match the appeared primitives with the primitives of

the theoretical map which is composed of four lists (a list of

wall, a list of corner, etc.). In other words, we try to initiate a

new track. We have to distinguish two cases: primitives wall

and the other primitives.

For each appeared primitive wall, we have considered three

correspondence tests applied on all the theoretical wall

primitives [13] :

 angular difference α between the two segments,

 difference in length (Ls-Lm) between the two segments,

 distance D between the centers of the two segments.

Figure 13: The three matching criteria.

The fusion of these three treatments is made thanks to the

Dempster-Shafer theory. Our FOD is composed of two

elements: YES and NO corresponding to those assertions :

"Yes, we can match the two walls" and "No, we can not

match the two walls". For each criterion, we have determined

the BPAs m1, m2 , m3 (see Figure 14 for an example of BPA).

m1: difference in angle between the two segments

0

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

1

0 7,5 15

(degrees)

B.P.A.

B.P.A. of YES

B.P.A. of {YES,NO}

B.P.A. of NO

Figure 14: :basic probability assignments of the first matching criteria

({YES,NO}=Θ)

We can then perform the combination calculation thanks to

the Dempster-Shafer rules without renormalization [12] in

order to get a mass set mm. The non-renormalization gives us

a precious indication about the conflict. Generally, we have

experimentally noticed that this conflict is null, but, in a few

cases, it can be high. This occurs for example when we

examine two parallel walls. So, if the conflict k is superior to

0.7, we think this value is too high and we take a prudent

decision: we don't match the two segments. If k<0.7, we can

take a decision and the segments are matched if BPA for the

YES mm(YES) is superior to the BPA for the NO mm(NO).

For each other primitive (corner, edge, other), we consider

two correspondence tests (Figure 15):

 The difference between the robot-sensorial primitive

distance dseg and the robot-map primitive distance dmap.

 The difference between the sensed primitives angle Θseg

and the theoretical primitive angle Θmap.

 

Figure 15: The two matching criteria

As the previous case, our FOD is composed of two

elements: YES and NO. The fusion is realized according to

the same strategy as the wall primitives.

4.3 - Management of a disappearance

As we will see in paragraph 4.4, if a matching is not

propagated, the track is not immediately cancelled but its

uncertainty increases. If this uncertainty becomes too high,

we definitively cancel this track.

4.4 - Track uncertainty management

For each track, we manage an associated uncertainty with

the help of the Dempster-Shafer theory. Our FOD for each

track is composed of two elements: “YES” and “NO” which

mean “Yes, the track exists” and “No, the track does not

exist”. Two stages are managed:
Uncertainty initialization stage. In the case of a primitive

appearance, the initial uncertainty mtrack 0 at time 0 takes into

account the uncertainty of the primitive mprim (paragraph 3.2)

and the uncertainty of the first matching mm (paragraph 4.2).

So, the two criteria are:













Θ = Θ

=

=

( ) ( )

( ) ( )

( ) ( )

1

1

1

prim

prim

prim

m m

m NO m NO

m YES m YES

m1 takes into account the uncertainty of the primitive.

 m2 which takes into account the uncertainty of the first

matching through mm(YES) [9].

We have noticed on experimental results that conflict can

appear, but it occurs in only one case: a good matching of an

unreliable primitive. Our strategy to manage this conflict is to

reduce the weight of the primitive uncertainty m1 by an

operation of discounting [8]:

if m1(YES)>0 :











Θ = − −

= × −

= × −

( ) 1 ( ) ( )

( ) ( ) (1 ( ))

( ) ( ) (1 ( ))

1 1 1

1 1 1

1 1 1

m m YES m NO

m NO m NO m NO

m YES m YES m NO

α α α

α

α

We obtain mtrack 0 (YES), mtrack 0 (NO) and mtrack 0 (Θ) by

merging mα

1 and m2 using the Dempster combination rule.

If mtrack 0 (NO) > mtrack 0 (YES), then we consider that the

uncertainty is too high and we don’t initialize the track. This

taking into account of the primitive uncertainty enables us not

to work with all the primitives, we privilege the “robust” and

reliable primitives.

Uncertainty propagation stage. Then, if the matching can

be propagated, the track uncertainty is updated by taking into

account:

 In relation with time t-1: the track uncertainty at time t-1

 In relation with time t: the primitive uncertainty and the

matching uncertainty at time t.

Let be mtrack t-1 the mass set of the track at time t-1. The

three set masses m1, m2 and m3 concerning the 3 criteria are:

 









Θ = Θ

=

=

( ) ( )

( ) ( )

( ) ( )

1

1

1

prim

prim

prim

m m

m NO m NO

m YES m YES

m1 takes into account the

primitive uncertainty at time t.

 m2 takes into account the uncertainty of the matching at

time t mmatch computed on paragraph 4.1 [9].

















Θ = Θ

=

=

−

−

−

( ) ( )

( ) ( )

( ) ( )

3 1

3 1

3 1

track t

track t

track t

m m

m NO m NO

m YES m YES

m3 takes into account the track

uncertainty at time t-1.

We adopt the strategy described in the uncertainty

initialization stage: a high conflict only appears when we

realize a good matching of an unreliable primitive and we

discount the mass of the primitive uncertainty.

mtrack t(YES), mtrack t(NO) and mtrack t(Θ) are obtained by

fusing m1, m2 and m3.

If the matching is not propagated, the uncertainty of the

track increases. In this case, we fix the BPA mmatch as follow:











Θ =

=

=

( ) 0.8

( ) 0.2

( ) 0

match

match

match

m

m NO

m YES

This mass set has been determined experimentally in order

to obtain a regular increase of the track uncertainty. So, if

mtrack t-1 is the BPAs of the track at time t-1, we update the

uncertainty mtrack t using the Dempster rule of combination

with mtrack t-1 and mmatch.

If mtrack t(NO)>mtrack t(YES), then we consider that the track

uncertainty is too high and the track is definitively lost. Here

again, the taking into account of the primitive uncertainty

enables us to privilege the tracks with reliable primitives.

Transition between a primitive wall and an other

primitive. We manage in our system the transition between

the primitives corner, edge, other and the primitives wall. An

example of such transition is shown on Figure 16. At time t,

the robot detects one of the two faces of the edge and this

face is classified as a wall primitive. At time t+1, the two

edge faces are visible from the robot and it detects an edge

primitive. The wall detected at time t and the edge detected at

time t+1 correspond to the same track. So we use the

uncertainty of the wall track at time t to initiate the

uncertainty of the edge track at time t+1.

Figure 16: an example of transition wall → edge

4.5 - Localization uncertainty

The last step of our uncertainty propagation architecture is

to compute the uncertainty of the robot localization. This aim

is reached with the help of the Demspter Shafer theory and

the FOD is composed of the two elements YES and NO

corresponding to the assertions “Yes, the localization is

correct” and “No, the localization is not correct”. We take

into account p+2 criteria.

The first criterion is the number of high level primitives

used to localize the robot. Indeed, if we use few primitives,

the localization is not reliable.

The second criterion is a ratio concerning the number of

detected primitives and the number of matched primitives.

Indeed, if we detect a lot of primitives but if we match only a

little few primitives, this can mean that a problem occurs in

the classification process or in the matching process. So the

localization may be unreliable.

number of detected primitives

number of matched primitives ratio =

The last p criteria are the uncertainty of the p tracks

managed by the robot, i.e. the p mass sets mtrack t computed in
the paragraph 4.4. If the tracks are uncertain, the localization

will be uncertain. Since we merge an important number of

mass sets and since the Dempster operator is not idempotent,

we apply an operation of discounting on the p mass sets mtrack

t. The discounting coefficient is different if the mass set mtrack

t concerns a wall primitive or an other primitive (corner, edge

and other): we privilege in the fusion process the “strong”

primitives corner, edge and other.

These p+2 criteria are fused according to the Dempster rule

and we obtain a mass set ml which quantifies the localization

uncertainty. This uncertainty is directly issued of the

uncertainties of the low-level data which have been

propagated, as shown on Figure 17.

Figure 17 : Uncertainties propagation during the localization process.

5 EXPERIMENTAL RESULTS

We have tested our algorithm on several acquisitions

made in an indoor environment (the end of a corridor shown

Figure 18 whose theoretical map in possession of the robot is

on Figure 19). The omnidirectional acquisitions and the

localization algorithm are computed in a Pentium PC located

on our mobile robot.

On Figure 18, we show an example of high level

primitives sensed map. We report on Table 1 the different

masses about the primitives uncertainty.

Figure 18: high level primitive map and the real environment.

On a two paths made in the corridor by our robot mobile

SARAH, we can note on 42 acquisitions made every 30 cm

that the robot’s position is determined correctly with a good

precision: the mean error is equal to 13 cm in position and 3

degrees in orientation (Figure 19).

On Figure 18, we represent only the tracked landmarks of

the second trajectory. We can remark that our tracking is

robust and efficient: among all the important number

sensorial primitives, the tracked primitives are correctly

identified and the tracks are generally never lost until the

landmarks become invisible from the robot. We show on

Figure 21 the uncertainty evolution of edge 6. The initial

matching is done manually and the mass set is set as follow:

mtrack 0(YES)= mtrack 0(Θ)=0.5, mtrack 0(NO)=0. The landmark

is tracked until acquisition 7, so the BPA for YES mtrack

t(YES) increases. Then, it becomes invisible from the robot.

So the BPA for YES decreases until acquisition 12 where the

BPA for NO is superior to the BPA for YES. So the track is

definitively lost.

Primitive number Type m(YES) m(NO) m(θ)

1 Edge 0.72 0.08 0.20

2 Corner 0.64 0.16 0.20

3 Wall 0.64 0 0.36

4 Wall 0.91 0 0.09

5 Wall 0.07 0 0.93

6 Wall 0.83 0 0.17

7 Edge 0.33 0.25 0.42

8 Edge 0.70 0.03 0.27

9 Wall 0.50 0 0.50

10 Wall 0.11 0 0.89

11 Wall 0.47 0 0.45

12 Corner 0.78 0.03 0.18

Table 1: uncertainties of the primitive model.

0

100

200

300

400

500

600

700

Edge 6

Edge 13

Segment 10 Segment 11

Segment 20

Edge 12

Segment 48

Figure 19: theoretical map and localization results ('+'=real position,

'x'=computed position).

20 22 24 26 28 30 32 34 36 38 40

0

50

100

150

200

250

300

350

Segment 20

Edge 13

Segment 10

Segment 48

Edge 12

Angle

(degree)

Acquisition numbe

Figure 20: the tracked landmarks (‘+’=corner,point=edge, segment=wall)

6 2

1

5 4 3

7

8

9

11

10

12
y g

0

0,2

0,4

0,6

0,8

1

1 2 3 4 5 6 7 8 9 10 11 12

acquisition number

B

P

A

m track t (YES) m track t(NO) m track t ({YES,NO})

Figure 21: uncertainty evolution of landmark edge 6.

Finally, we see on Figure 16 an example of a double

transition edge-segment-edge. Until acquisition 32, the two

faces of the edge are visible. On acquisition 33, one face is

visible, so a primitive segment is detected but we don’t

initiate a new track since this segment belong to the edge

previously tracked. On acquisition 37, the robot can detect a

new edge (edge 12 on Figure 19) that contains the segment.

As the previous case, we don’t initiate a new track but we

prolong the current track.

Uncertainty evolution of edge 13/segment 48/edge12

0

0,2

0,4

0,6

0,8

1

1,2

22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

acquisition number

BPA

m track t(YES) m track t(NO) m track t({YES, NO})

Figure 22: uncertainty evolution of edge 13/segment 48/edge 12.

On Figure 23, we show the evolution of the localization

uncertainty. The uncertainties of the first acquisitions are

weak : the number of tracked primitives is high. Then this

number decreases, so the uncertainty increases, i.e. ml(YES)

decreases. After acquisition 46, several new tracks are

initialized and the uncertainty becomes weak.

0

0,2

0,4

0,6

0,8

1

2225283134374043464952

Acquisition number

BPA

m(YES)

m(NO)

m({YES,NO})

Figure 23 : localization uncertainty.

6 CONCLUSION

In this paper, we have studied and implemented a multi

level uncertainty propagation architecture. After a multi

criteria fusion stage based on the use of the Dempster-Shafer

theory, we obtain a multi-valued sensorial map which permits

to quantify the credibility of the high level primitives. These

primitives are then used in our dynamic localization method

based on a propagation of an initial matching This method

solves two problems linked to the multi target tracking: the

propagation of an uncertainty concerning the landmark tracks

and the treatment of the apparition and momentary

disappearance of a track. This multi-target tracking paradigm

has been tested on several robot’s path in a large structured

indoor environment and has provided good results concerning

the matching maintaining and the preciseness of the

localization. An extension of this work could concern the

linear angular prediction which is mono criteria. A prediction

based on a dynamic model or combining 'proprioceptive'

could be used and would allow the system to operate on fast

moving vehicles.

7 REFERENCES

[1] S. Thrun, "Finding Landmarks for Mobile Robot Navigation",

IEEE Int. Conf. on Robotics and Automation, May 1998, pp.

958-963.

[2] L. Delahoche, B. Marhic, C. Pégard, P. Vasseur - “A

navigation system based on an omnidirectional vision sensor”,

Proc. of Int. Conf. on Intelligent Robots and Systems, France,

Sept. 1997.

[3] D.B. Reid, “An algorithm for tracking multiple target”, IEEE

trans. on automatic control, vol. AC24, n. 6, pp. 843-844,

Dec. 89

[4] Y. Bar-Shalom, « Multitarget-Multisensor tracking :

Applications and Advances vol.II. », Artech House, 1992.

[5] H.R Beom, H.S. Cho, “Mobile robot localization using a

single rotating sonar and two passive cylindrical beacons”,

Robotica, Vol. 13, pp. 243-252, 1995.

[6] A. Clérentin, L. Delahoche, E. Brassart, “A multi sensor

cooperative approach for the mobile robot localization

problem”, Proc. of the workshop Performance metrics for

Intelligent Systems. PERMIS2000, Washington, Aug 00

[7] C. Royère, D. Gruyer, V. Cherfaoui, « Data association with

believe theory », 3rd int. conf. on information fusion FUSION

2000, Paris, France, 2000

[8] G.A. Shafer, “A mathematical theory of evidence”, Princeton :

university press, 1976.

[9] A. Clérentin, L. Delahoche, E. Brassart “Omnidirectional

sensors cooperation for multi-target tracking”, IEEE Int. Conf.

on Multisensor Fusion and Integration MFI 2001, Aug. 01,

Germany, pp. 335-340

[10] A. Clérentin, C. Pégard, C. Drocourt “Environment

exploration using an active vision sensor”, Proc. IEEE Int.

Conf. on Intelligent Robots and Systems (IROS’99), Korea,

Oct. 1999.

[11] D. Gruyer, V. Berge-Cherfaoui, “Matching and decision for

vehicle tracking in road situation”, Proc. IEEE Int. Conf. on

Intelligent Robots and Systems (IROS’99), Korea ,Oct. 1999.

[12] Smets Ph., « The nature of the unnormalized beliefs

encountered in the transferable belief model », Proceedings of

the 8th Conference on Uncertainty in Artificial Intelligence,

San Mateo, Californie, (1992) 292-297

[13] Crowley J., « Navigation for an intelligent mobile robot » -

IEEE Journal on Robotics and Automation, Vol. RA-1, n°1,

pp. 31-41, March 1985

[14] Y. Yagi, Y. Nishizawa, M. Yachida, “Map-based navigation

for a mobile robot with omnidirectional image sensor COPIS”,

IEEE Trans. on Rob. and Aut. Vol 11, pp. 634-648, Oct. 1995.