<figure><img src="image_1.png" /></figure>

HAL
open science

# How to manage conflict and ambiguities in localization and map matching

Dominique Gruyer, Rachid Belaroussi, Vincent Vigneron, Aurélien Cord

► To cite this version:

Dominique Gruyer, Rachid Belaroussi, Vincent Vigneron, Aurélien Cord. How to manage conflict and ambiguities in localization and map matching. Journal of Intelligent Systems, 2014, 23 (2), pp.171-182. 10.1515/jisys-2013-0076 . hal-00985760

HAL Id: hal-00985760

https://hal.science/hal-00985760

Submitted on 12 Jul 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Dominique Gruyer, Rachid Belaroussi*, Vincent Vigneron and Aurelien Cord

# How to Manage Conflict and Ambiguities in Localization and Map Matching

**Abstract:** Since the use of systems of satellite positioning such as the global positioning system (GPS), applications have tried to locate vehicles on maps representing the environment with their attributes. For one decade, this has led to both localization and navigation services for users. Recently, new researches have begun in order to extend the functionalities of the existing systems and thus to develop new applications using these technologies in the design of driver assistance systems. These new systems will indeed allow us to anticipate road departures or prevent overspeed turn approaches. Nevertheless, to deploy such new functionalities, it is imperative to ensure the association of vehicle position with one of the roadmap segments. In this article, we propose a new approach based on the belief theory taking into account the imperfections of available data in order to ensure the positioning and tracking of a vehicle on a roadmap and to manage conflicts and ambiguities using a multi-hypotheses decision.

**Keywords:** Data fusion, map matching, ICNSC'13.

## 1 Introduction

Since the use of satellite positioning systems such as the global positioning system (GPS), we also have been trying to locate vehicles on maps representing the environment with their attributes. For one decade, services of localization and navigation have been provided to road users. These navigation systems are in general powerful and efficient, ensuring vehicle guidance from a starting point to an arrival point. Nevertheless, the purpose of these applications is comfort and not safety. However, this is about to change: researches have begun to develop new systems based on these technologies for the design of driver assistance systems. Indeed, the use of an accurate roadmap gives important information for assessing and decreasing the risk level in potentially hazardous areas. These new systems would, for instance, anticipate road departures or prevent overspeed turn approaches.

However, to deploy such functionalities, it is imperative to ensure a set of tasks such as the selection of candidate road sections and the association of the vehicle state (position and orientation) with one or more of the road segments. To carry out this function, it is necessary to combine and merge a set of data coming from various information sources with different reliabilities (sensors and roadmap). Often, these data are heterogeneous, asynchronous, incomplete, and imperfect (inaccurate, uncertain). In this article, we propose a new approach based on the belief theory allowing us to take into account all these concepts. Our approach is focused on the stages of combination, association, and fusion to ensure the positioning and the tracking of one vehicle in a roadmap. This approach manages both conflicts and ambiguities on the decisions resulting from the combination and association stages.

In the first part, we briefly present the information sources that are accurate enough for roadmap localization dedicated to road safety and the set of imperfections affecting these data. This allows us to explain why it is imperative to combine them in order to increase the robustness.

In the second part, we present the principles of the belief theory. Then, we set out the different stages entering in the development of our approach. First, we present the stage of multi-criteria combination that

<footnote>*Corresponding author: Rachid Belaroussi, IFSTTAR, COSYS-LIVIC, 77 rue des chantiers Versailles 78000, France, Tel.: (+33)130844026, e-mail: rachid.belaroussi@ifsttar.fr</footnote>

<footnote>Dominique Gruyer and Aurelien Cord: IFSTTAR, COSYS-LIVIC, Versailles, France</footnote>

<footnote>Vincent Vigneron: Universite d'Evry Val d'Essonne, IBISC, Evry, France</footnote>
allows the fusion of the heterogeneous information sources. This step leads to the building of symbolic experts characterizing the current situation. Then, we show how to implement a stage of combination of experts to associate the vehicle position with a road segment. We show that the decision resulting from this stage can produce conflicts and ambiguities generated by contradictory experts.

In the third part, we describe a solution to manage conflicts and ambiguities by the means of a multi-hypotheses decision. Finally, a simulated example illustrates our theoretical approach.

# 2 Information Sources and Their Imperfections

To locate a vehicle on a roadmap, we must use two types of information source. The first one is made up of a set of proprioceptive [inertial navigation system (INS), odometer, and wheel angle] and exteroceptive (GPS) sensors to estimate the global positioning of the vehicle. The second one is related to the roadmap and consists of a graph including nodes and segments representing the roads.

## 2.1 The GPS Information

Because it provides data about the absolute localization, the GPS receiver is the most important embedded sensor. Other sensors are used to complete and update the GPS information. Thus, taking into account errors and noises from these sensors is crucial. On the GPS level, the main errors are due to

- The precision of the estimated position;

- Satellite masking, which involves non-continuous GPS data;

- The problems of multi-ways of the waves of signals GPS.

Moreover, when GPS signals are masked, the proprioceptive sensors may provide the localization. In this case, position error grows with time and/or the distance covered.

## 2.2 The Roadmap Data

On typical roadmap data, many errors or imperfections could happen from various causes. The first cause is linked with the lack of details about the real roads. Generally, it is induced by small singularities, as a roundabout or highway modeled by its central axis. The second cause is related to the update of the road databases. Indeed, a roadmap may contain segments that do not exist anymore or some road sections may not have been taken into account yet. The third cause is due to the errors of conversion. Indeed, the transformation between the 3D coordinates WGS84 (GPS) and the plane coordinates of the roadmap (in France, Lambert coordinates) induce small errors, mainly due to round-offs. The same type of errors may appear when the vehicle's movement (in 3D) is projected on the plane coordinate (for instance, on an interchange with several levels).

## 2.3 Roadmap and GPS Data Fusion

In classical applications, the two types of information are matched in a very simplistic way. The estimated position of the vehicle is projected on the candidate segments by using deterministic, stochastic, or fuzzy-logic-based techniques. The history of the previous stages is often used to select the correct road segment. However, an error of mapping can be propagated a certain time before the system can detect and correct this mistake. These methods lack robustness; however, this is not a real problem in the case of navigation applications.

Many researches have been carried out to take into account data imperfections. Those often divide the problem into two distinct levels: first, a filtering part mainly based on Gaussian filters (Kalman filter,
particular filter, etc.); second, an association part handling the map-matching stage based on geometrical approaches [13] or topological approaches [3]. Despite their good performances, these techniques fail to manage the problems of ambiguities and conflicts.

For this reason, we have developed an alternative method, close to the work of El Najjar and Bonnifait [2], for the assignment of the vehicle localization with a roadmap segment. It handles the data imperfections, their non-fulfillment (sensor failure or asynchronous sensors), and their heterogeneity. On the basis of the belief theory, this method efficiently allows the management of conflict and ambiguities.

# 3 Belief Theory for Association and Combination Problems

## 3.1 Generalities

The belief theory, proposed by Shafer [11], allows both modeling and using uncertain and inaccurate data, as well as qualitative and quantitative data.

This theory is well known to “take into account what remains unknown and represents perfectly what is already known.”

In a general framework, the association problem consists in matching an object designated by a generic variable X among a set of hypotheses $H_i$. One of these hypotheses is supposed to be the solution. In our case, first we want to combine all the criteria representing the current state of a vehicle X (position, angle, speed, etc.) with a hypothesis $H_i$ (with the same criteria as X). Second, we want to associate a vehicle $X_i$ (deduced from multi-criteria combination) to a subset of road segments $H_j$.

In fact, the belief theory allows evaluating the veracity of $P_i$ propositions representing the matching of different objects. These propositions can be simple or complex:

$P_1$ = “vehicle X is on the segment $H_i$.”

$P_2$ = “vehicle X is on the segments $H_i$ or $H_j$.”

We must then define a magnitude characterizing the veracity of a proposition. This magnitude is the basic probabilistic mass $m_\Theta()$ defined on [0, 1]. This mass is very close to the probabilistic mass with the difference that this mass is not only shared on single elements but it is also distributed on all propositions of the definition referential $\Theta^0 = \{A|A \subseteq \Theta\} = \{H_1, H_2, ..., H_n, H_1 \cup H_2, ..., \Theta\}$. This referential is built through the frame of discernment $\Theta = \{H_1, H_2, ..., H_n\}$, which groups all admissible hypotheses. These hypotheses must be exclusive, i.e., $H_i \cap H_j = \emptyset, \forall i \neq j$. This distribution is a function of the knowledge about the source to model. The whole mass obtained is called “basic belief assignment.” The sum of these masses is equal to 1.

## 3.2 Combination Framework

To reduce the combinative complexity, we have proposed a specific set of masses in order to generalize conjunctive combination rules. The generalized combination can be applied in three distinct frameworks.

The first one is the framework called “closed world.” This is based on the strong hypothesis that the frame of discernment is exhaustive. In this case, the conflict mass must be empty. This constraint implies the normalization of the combination.

The second framework is called “open world.” Defined by Smets [12], it allows removing the exhaustive constraints of hypotheses. Then, it is possible to use a non-exhaustive framework. The appearance of a new hypothesis is carried out with the interpretation of the conflict mass $m()$. Unfortunately, we cannot make the distinction between a new hypothesis and a real conflict.
This observation has led us to create a third framework called “extended open world” [10]. Thus, for an object X to be associated among N known objects $H_1, H_2$, and $H_3$, we will have the following framework of discernment:

$$ \Theta = \{H_1, H_2, \dots, H_N, H_*\}, \qquad (1) $$

where $H_i$ means that “X and $H_i$ are supposed to be the same object” or, in our particular application, “vehicle X is on segment $H_i$.” To be sure that the frame of discernment is really exhaustive, a last hypothesis noted $H_*$ is added. This hypothesis can be interpreted as the association of a vehicle position with none of the road segments. In fact, the hypotheses represent a local view of the world and the hypothesis $H_*$ represents the rest of the world. In this context, $H_*$ means “an object is associated with nothing in local knowledge set.”

For instance, if $N = 3$ segments are available, the referential of definition is built according to

$$ 2^{\theta} = \left\{ \begin{array}{l} H_*, H_1, H_2, H_3 \\ H_1 \cup H_2, H_1 \cup H_3, H_1 \cup H_*, H_2 \cup H_3, H_2 \cup H_3, \\ H_1 \cup H_2 \cup H_3 \\ \Theta \end{array} \right\}. $$

$\overline{H}_i$ means X is not in relation with $H_i$.

This referential contains singleton hypotheses of the frame of discernment to which are added representations of uncertainty by using complex propositions (hypotheses disjunction). Total ignorance is represented with the set $\Theta$, which is the set of all the hypotheses of the frame of discernment. The conflict is given by the hypothesis, which corresponds to the empty set.

# 4 Map Matching with the Belief Theory

## 4.1 Problem Statement

The localization of the vehicle is seen by a set of sensors that provide a set of $n$ criteria characterizing the vehicle’s state. Our goal is to compute the confidence in the association between this vehicle and a subset of the segments of the road map (hypothesis of the world). This stage is called map matching. This confidence must handle all the available criteria even if they are in conflict. However, like the current distance function, the contrary advice must not reject the relation between a vehicle location (observations) and a segment (hypothesis and knowledge of the world). To achieve this map matching and take the best decision, we need to carry out a set of operations in a four-step process:

- The generation of the $n$ expert advices from a distance function;

- A multi-criteria combination of expert advices in the closed world (because all criteria are known) that quantify the knowledge of all criteria for one segment and produce intermediate masses;

- A final combination of all those masses in order to take the decision;

- Ambiguities and conflict management by means of multi-hypotheses techniques. It starts with the generation of the $n$ expert advices from a distance function; then comes the first level of combination, fusing the output of all criteria (expert advices) for each hypothesis. The second one combines all the hypotheses.

## 4.2 Dissimilarity Function

To represent the expert advice in a symbolic framework, we need, in a first step, to compute the similarity between a vehicle localization and each potential map segment according to specific criterion such as distance, angle, or speed. For instance, using only distance and orientation, $n = 2$ criteria are available:
- $c_1$ computes the distance between the vehicle's position and each road segment.

- $c_2$ computes the similarity between the vehicle's yaw and each segment orientation.

The similarity is computed for each criterion used for association: it outputs an $n \times N$ array ($d_{ij}$), where element $d_{ij}$ is related to the dissimilarity between the ith characteristic of the vehicle's state and the jth segment of the road. Moreover, in our case, the distance $D_{ij}$ should answer to the following constraints:

- It should be scaled between 0 and 1 if the ith characteristic of the jth segment of the road is associated with the corresponding vehicle's characteristic.

- It should be greater than 1. Otherwise

- It must use both object covariance matrices (data inaccuracy modeling).

The chosen function is an extension of Mahalanobis' distance with a normalization part [6]. It is then thresholded to be in the range [0 1]:

$$d_{i,j} = D_{i,j} \quad \text{if} \quad D_{i,j} \in [0, 1] \quad \text{else} \quad d_{i,j} = 1.$$

## 4.3 Generation of the Specialized Sources

The distances of similarities computed from the previous function are used to generate a set of basic mass distributions. These distribution functions use the strong hypothesis: an object cannot be in the same time associated and not associated to another object (see Figure 1).

The initial distributions of masses used for the combination and representing the knowledge of the world are the following:

- $m_{ij}(H_j)$ means $X$ is in relation with $H_j$, according to criterion $i$.

- $m_{ij}(\bar{H}_j)$ means $X$ is not in relation with $H_j$, according to criterion $i$.

- $m_{ij}(\Theta)$ is mass representing ignorance, according to criterion $i$.

In this mass distribution, the index $j$ denotes the road segments. If this index is replaced by a dot, then the mass is applied to all segments. Moreover, if we use an iterative combination, the mass $m(H_j)$ is not part of the initial mass set and appears only at the last combination. It replaces the conjunction of the combined masses $m_{ij}(H_j)$.

The closer $d_{ij}$ is to 0, the more likely is the hypothesis $H_j$, according to criteria $j$:

$$ \text{if } d_{ij} \le \tau: \left\{ \begin{array}{l} m_{ij}(H_j) = \alpha \left[ 1 + \cos \left( \pi \frac{d_{ij}}{\tau} \right) \right] \\ m_{ij}(\bar{H}_j) = 0 \\ m_{ij}(\Theta) = 1 - m_{ij}(H_j) \end{array} \right. , \qquad (2) $$

where $\tau$ is an experimental threshold and $\alpha$ is a parameter linked to the confidence granted to the criterion. Otherwise, the initial masses are set according to the following equations:

$$ \text{if } d_{ij} \ge \tau: \left\{ \begin{array}{l} m_{ij}(H_j) = 0 \\ m_{ij}(\bar{H}_j) = \alpha \left[ 1 + \cos \left( \pi \frac{1-d_{ij}}{\tau} \right) \right] \\ m_{ij}(\Theta) = 1 - m_{ij}(H_j) \end{array} \right. . \qquad (3) $$

These initial masses are plotted with respect to $d_{ij}$ in Figure 1 in neutral cases where $\tau = 0.5$. Notice that $m_{ij}(\Theta) = 1 - [m_{ij}(H_j) + m_{ij}(\bar{H}_j)]$.
<figure><img src="image_3.png" /><figcaption>Figure 1. Functions of Mass Distributions.</figcaption></figure>

These functions have three significant parameters (see Figure 1). (i) $\tau$ index, which represents the borderline between the association and the non-association. If this index is >0.5, we are in a pessimistic context (the mass will be more strongly placed on the non-association hypothesis). On the contrary, we are in an optimistic context (the mass will set on the association hypothesis). (ii) $d_{ij}$ is the distance index. (iii) $\alpha$ takes into account the reliability on the data source and is specific for each criterion.

## 4.4 Generalized Combination Rules for Multi-criteria Association

The set of mass distributions $m_{ij}()$ previously built is combined to obtain a more synthetic set of masses, integrating the advices of all experts [4, 9]. The set of multi-criteria equations allowing the combination are computed in an open world, where we keep the conflict mass without redistributing it on the other masses. This mass is kept because it perfectly represents the conflict between the criteria

$$m_{c_1...c_n}(H_j) = \prod_{k=1}^{n}(1 - m_{c_k j}(\overline{H}_j)) - \prod_{k=1}^{n}m_{c_k j}(\Theta), \quad (4)$$

$$m_{c_1...c_n}(\overline{H}_j) = \prod_{k=1}^{n}(1 - m_{c_k j}(H_j)) - \prod_{k=1}^{n}m_{c_k j}(\Theta), \quad (5)$$

$$m_{c_1...c_n,j}(\Theta) = \prod_{k=1}^{n}m_{c_k j}(\Theta), \quad (6)$$
$$ m_{c_i, \dots, c_n, j}(\emptyset) = 1 - m_{c_i, \dots, c_n}(\overline{H_j}) + m_{c_i, \dots, c_n}(H_j) + m_{c_i, \dots, c_n, j}(\Theta). \quad (7) $$

When only a subpart of the full information is available, a correct processing of the remaining information must be guaranteed. This issue occurs in case of asynchronous data and when only a part of the expert can provide an advice. The other part cannot bring any information. With our approach, either we do not take into account these experts or we just model the ignorant expert by a full repartition of the mass on $m_{c_i, j}(\Theta)$.

## 4.5 Generalized Combination Rules for Multi-object Association

From the set of mass distributions $m_{c_i, \dots, c_n}()$ built from the criteria combination, a global and final distribution of masses made up of the masses is computed:

- $m(H_j)$ means vehicle X is in relation with segment $H_j$.

- $m(\overline{H_j})$ means X is not in relation with $H_j$.

- $m(\Theta)$ represents ignorance about vehicle X.

- $m(H_*)$ means X is in relation with nothing: the vehicle is out of known roads.

This final set of masses will be used in a last stage in order to take a decision. This last set of masses represents the global combination of all expert advices about the localization of a vehicle and the subset of road segments that are possible candidates [5]. In fact, in our previous works, we have observed a general behavior of the iterative combination with n mass sets. This behavior enables us to express the final mass set according to the initial mass sets (there the partial set of masses built with the multi-criteria combination rules).

The final masses for the singleton hypothesis are the following:

$$ m(H_j) = m_{c_1, \dots, c_n}(H_j) \prod_{k \neq j} (1 - m_{c_1, \dots, c_n}(H_k)), \quad (8) $$

$$ m(H_*) = \prod_{k=1}^{N} m_j(\overline{H_k}). \quad (9) $$

The masses allocated to the other subsets are obtained with the use of the following equation. This equation is true for the subset of hypotheses from the order 2 to the order $n-1$ [10]:

$$ m(H_k \cup \dots \cup H_*) = \prod_{j=k, \ell} m_{c_1, \dots, c_n, k}(\Theta) \prod_{k \neq j} m_{c_1, \dots, c_n}(\overline{H_k}). \quad (10) $$

The set $\Theta$ gives a global mass on the unknown (ignorance):

$$ m(\Theta) = \prod_{k=1}^{N} m_{c_1, \dots, c_n, k}(\Theta). \quad (11) $$

The conflict mass is then the sum of the multi-criteria combination conflict and the multi-object combination conflict:

$$ m(\emptyset) = 1 - \left[ \prod_{j=1}^{n} (1 - m_{c_1, \dots, c_n}(H_j)) + \prod_{j=1}^{n} m_{c_1, \dots, c_n}(H_j) \prod_{k \neq j} (1 - m_{c_1, \dots, c_n}(H_k)) \right]. \quad (12) $$

This mass is useful for quantifying either the conflict mass or the assumption “this object does not exist in the current discernment framework.” In this case, it may be a new hypothesis. In an open-world framework, this
mass will be used for building a renormalization coefficient $K$. This coefficient would allow redistributing the mass $m(\emptyset)$ on the other final masses.

Index “*” is the notion of “emptiness” or more explicitly “nothing.” With this hypothesis, we can deduce that a vehicle is out of known roads. The database of the road map may not be up-to-date and a new segment probably needs to be added to the database. The following stage consists in establishing the best decision on association using the belief matrix obtained previously. As we use a referential of definition built with single-ton hypotheses, except $\Theta$, the use of credibilistic measures would not add any useful information. This redistribution will simply reinforce the $\Theta$ masses. This is why we use as the decision the maximum of credibility.

If we want to more accurately handle the uncertainty on the expert advices, we can use the whole set of masses and then the pignistic probability is a good redistribution function in order to take a decision. However, in the case where the conflict mass is >0 or if we have ambiguities on the decision, then we need to efficiently manage this situation of conflict.

# 5 Conflict and Ambiguity Management

## 5.1 Classical Solutions

To manage problems of conflicts due to contradiction between experts, many solutions have been proposed in the literature. If the concerned information sources are known, the solution is easy. It simply consists in weakening with a reliability index the masses generated for these sources.

In the case of unknown and/or unreliable sources, other solutions have been proposed. Among these, we can quote (i) Dempster's coefficient of renormalization, (ii) Yager's operator [14] (redistribution of the conflict mass on the unknown mass), (iii) Dubois and Prade's operator [1] (redistribution on the hypotheses disjunctions providing the conflict), (iv) Lefèvre's operators [7], or (v) Royere's conjunctive/disjunctive operator, which try to identify the concerned sources to obtain a more efficient redistribution of the conflict mass. This last operator is very interesting in our framework because it then becomes associative.

## 5.2 Multi-hypotheses Management

In any case, many remarks can be made about the current methods described above. First, the manipulated information is not completely explored (particularly in case of conflict). However, when the conflict is redistributed, this leads to a huge quantity of operations. Besides, most of these operators are not associative. Meanwhile, the system tries to associate a vehicle with one of the candidate segments maximizing the total belief in this final association. This method can eventually generate unreliable local associations.

Indeed, in our method, when the global belief is maximized, the vehicle can even be seen in a new road (an unknown segment in the database) while the conflict mass is very weak; this can occur when we have a very strong conflict. In this case, we can question if it is really pertinent to take this decision, given that the measurement is drawn in the conflict. To consider this measurement as a false alarm is probably the best option. This situation can be found when the vehicle drives through a junction (see Section 5.3).

One solution to this problem would be to develop a multi-hypothesis filter based on our former studies. To be able to create this new filter, the strong hypothesis that we initially used is disregarded (the hypothesis said: a vehicle can be associated to a unique segment). In this new proposal, the system can generate multiple hypotheses or simply not make a decision.

To solve this problem, two strategies were proposed in Ref. [8]. The first approach is a cascade method, whereas the second is an approach with threshold. The method with threshold is less complex than the cascade method. It also has the advantage of considering the information over the conflict to calculate the selection threshold of the proposition degrees to be calculated. Actually, given the already calculated belief
matrix, we calculate the weighed threshold $s = k_s(1 - m(\emptyset))$ with a weight $k_s$ determining the order of the proposition that we will keep. The system will only save the associations that have a probability or a belief above this threshold. This multi-hypotheses management allows us to consider the information that we have about the conflict and makes it possible to manage ambiguities. As a result, the system is now capable of tolerating the case of non-association when the conflict is too important. In most ambiguity cases, we will propagate the hypothesis set that was saved.

## 5.3 Application

This part deals with an ambiguous driving situation that provides conflict and ambiguities. The ego-vehicle is crossing a junction and has some trouble with the GPS data. From the segment selection stage (using the vehicle location), four candidate segments are selected. The only criteria that can be used are the distance from the vehicle location to each segment and the error between the vehicle orientation and each segment (see Figure 2).

From this situation, a set of dissimilarities are computed. The smaller the distance, the closer the criterion to the equivalent segment criterion. From this set of dissimilarity indices, an ambiguity can already be noticed between segments 1 and 2, as shown in Figure 3. In this figure, four candidate segments are selected:

<figure><img src="image_4.png" /><figcaption>**Figure 2.** Map Matching in a Junction.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Figure 3.** Dissimilarity Index $d_{ij}$ by the Criterion for the Selected Segments.</figcaption></figure>
$H_1, H_2, H_3, H_4$. Two criteria are used: the $c_1$ criterion is the distance vehicle-segment (first column), and the $c_2$ criterion is the orientation error (second column). A low dissimilarity corresponds to a good match, whereas a high value corresponds to a segment unlikely to match the vehicle position. After computing the multi-criteria combination, the problem remains (see Figure 4A,B). However, we know that we have a reject of segments 3 and 4 with the appearance of a conflict (Figure 4C,D).

From the multi-object combination, a lot of useful information can be extracted. The first one confirms our first guess. From Figure 5, segments 1 and 2 are potentially the good solution; however, we have an ambiguity. Moreover, we know that we have a conflict between at least two experts and we have a certain ignorance of the experts.

To take a final decision, we applied our multi-hypotheses decision with a weight that limits the maximal number of potential hypotheses. To limit this maximal number to 3, we set $k_s = 0.3$. One to three segments can then be selected for the decision (see Figure 6). With this $k_s$ value and the conflict mass ($m(\emptyset) = 0.322$), the threshold is equal to $s = 0.2034$. Therefore, segments 1 and 2 are kept for the next step. The discrimination between these two segments remains to be made in the next stages.

<figure><img src="image_6.png" /><figcaption>**Figure 4.** Masses Combination of Criteria $c_1$ and $c_2$ for Hypothesis $j = 1, ..., 4$. The columns are $m_{c_1 c_2}(H_j)$, $m_{c_1 c_2}(H_i)$, $m_{c_1 c_2, j}(\Theta)$, and $m_{c_1 c_2, j}(\emptyset)$ values computed from Eqs. (4)–(7), respectively.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>**Figure 5.** Multi-object Combination, in the Following Order: $m(H_j)$ for $j = 1, ..., 4$, $m(H_i)$, $m(\Theta)$, and $m(\emptyset)$.</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>**Figure 6.** Number of Potential Hypotheses for the Decision Stage.</figcaption></figure>

# 6 Conclusion and Future Works

In this article, we introduce the theoretical aspects of a new algorithm of matching between a vehicle localization and a road map. This approach has the advantage of, first, taking into account the data imperfections; second, allowing the modeling of the uncertainty on the possible association propositions between a vehicle and a segment; and third, managing the conflict aspect and the ambiguities of a situation. We presented the different stages entering in the building of this approach. Each stage has been developed separately in previous researches in tracking algorithms. Then, we couple the advantage of all these studies to obtain a more efficient algorithm of map matching. The first part shows how to generate the expert advises allowing the conversion of the numerical data in a symbolic referential. To combine all the data about the vehicle state and one segment, we have presented the multi-criteria combination rules. Following this stage, we introduce the multi-segment association stage. From this step, a decision can be taken. However, in some particular conditions, we can obtain either a solution with a strong conflict, or a solution with an ambiguity. The last theoretical part of this article shows how we can solve both problems and reduce the influence of the questionable matching. It is important to note that the set of stages used to design this algorithm ensures an efficient data processing and a reliable associative and commutative data combination.

Moreover, in future works, this map-matching module will enter as parts of a more global architecture, which could dynamically build a road map from data coming from vehicles and infrastructure.

# Bibliography

[1] D. Dubois and H. Prade, On the Dempster-Shafer framework and new combination rules, *Computer Intelligence* 4 (1988), 244-264.

[2] M.-E. El Najjar and P. Bonifait, A roadmap matching method for precise vehicle localization using belief theory and Kalman filtering, in: *Proceedings of the 11th IEEE International Conference on Advanced Robotics (ICAR'03)*, 2003.

[3] J. S. Greenfeld, Matching GPS observation to locations on a digital map, in: *Proceedings of the 81st Annual Meeting of the Transportation Research Board (TRB'02)*, 2002.

[4] D. Gruyer, C. Royere and V. Cherfaoui, Heterogeneous multi-criteria combination with partial or full information, in: *International Conference on Information Fusion (FUSION'03)*, 2003.

[5] D. Gruyer, C. Royere, R. Labayrade and D. Aubert, Credibilistic multi-sensor fusion for real time application: application to obstacle detection and tracking, in: *IEEE International Conference on Advanced Robotics (ICAR'03)*, 2003.

[6] R. Labayrade, C. Royere, D. Gruyer and D. Aubert, Cooperative fusion for multi-obstacles detection with use of stereovision and laser scanner, *Autonomous Robots* 19 (2005), 117-140.

[7] E. Lefevre, O. Colot, P. Vannoorenberghe and D. De Brucq, A generic framework for resolving the conflict in the combination of belief function, in: *International Conference on Information Fusion (FUSION'00)*, 2000.
[8] B. Mourllion, D. Gruyer, C. Royere and S. Theroude, Multi-hypotheses tracking algorithm based on the belief theory, in: *International Conference on Information Fusion (FUSION'05)*, 2005.

[9] M. Rombaut, Decision in multi-obstacle matching process using theory of belief, in: *Advances in Vehicle Control and Safety (AVCS'98)*, 1998.

[10] C. Royere, D. Gruyer and V. Cherfaoui, Data association with believe theory, in: *International Conference on Information Fusion (FUSION'00)*, 2000.

[11] G. Shafer, *A mathematical theory of evidence*, Princeton University Press, Princeton, NJ, 1976.

[12] P. Smets, The combination of evidence in the transferable belief model, *IEEE Transactions on Pattern Analysis and Machine Intelligence* **12** (1990), 447–458.

[13] C. E. White, D. Bernstein and A. L. Kornhauser, Some map matching algorithms for personal navigation assistants, *Transportation Research Part C* **8** (2000), 91–108.

[14] R. R. Yager, On the Dempster-Shafer framework and new combination rules, *Information Sciences* **4** (1987), 93–138.