Fahed Abdallah

A multiple-hypotheses map matching method suitable for weighted and box-shaped state estimation for localization

A multiple-hypotheses map matching method suitable for weighted and box-shaped state estimation for localization

I. INTRODUCTION

Many research and industrial applications require accurate localization and/or tracking of moving vehicles [START_REF] Drawil | Intervehicle-Communication-Assisted Localization[END_REF] [START_REF] Xu | Development and Application of an Enhanced Kalman Filter and Global Positioning System Error-Correction Approach for Improved Map-Matching[END_REF] [START_REF] Skog | In-Car Positioning and Navigation Technologies A Survey[END_REF]. Satellitebased navigation systems like the global positioning system (GPS) are playing an important role in vehicle localization as a result of their [START_REF] Greenfeld | Matching GPS observations to localizations on a digital map[END_REF]-hour, all weather, free-of-charge availability. However, GPS by itself is not always the ideal solution. It was originally designed with an inherent error of at least 10 meters for non-military applications. Also, it suffers from line of sight issues that make it less effective in urban canyons. One possible solution for correcting GPS error is the integration of GPS data with other sensor data such as dead reckoning (DR) using a data fusion algorithm [START_REF] Toledo-Moreo | Lane-Level Integrity Provision for Navigation and Map Matching With GNSS, Dead Reckoning, and Enhanced Maps[END_REF].

A critical issue when designing data fusion algorithms is the representation of uncertainties that pervade both sensor measurements and the state space model. Two main categories of data fusion algorithms can be distinguished:

• Recursive Bayesian estimation, based on a probabilistic description of uncertainty;

• State bounding methods, based on a set-membership description of uncertainty.

Methods in the first category assume the measurement noise and state perturbations to be realizations of random variables with known statistical properties. This is the mainstream approach. The most common approaches are the Extended Kalman filter (EKF) and the particle filter (PF). The EKF linearizes the state and measurement equations and then applies the Kalman filter to obtain state estimates [START_REF] Bar-Shalom | Multitarget-Multisensor Tracking: Applications and Advances[END_REF] [START_REF] Gelb | Applied Optimal Estimation[END_REF], assuming the process and observation noises to be normal.

The state posterior probability distribution is approximated by a Gaussian distribution that is propagated analytically through the linearized system equations. However, the linearization is inherently local and may fail to produce reliable estimates, especially when the state model is highly non-linear. The statistical interpretation of covariance matrices is also unclear in this approach, as the statistical properties of the perturbations though non-linear equations is illknown.

Sequential Monte Carlo methods for recursive Bayesian filtering, often referred to as particle filters (PF), usually provide more accurate information about the state posterior probability distribution than does the EKF, especially if it has a multimodal shape or if the noise distributions are non Gaussian [START_REF] Sivaraman | A General Active-Learning Framework for On-Road Vehicle Recognition and Tracking[END_REF]. The efficiency and accuracy of the PF depends mainly on the number of particles and on the propagation method used to re-allocate weights to these particles at each iteration. To cope with high measurement uncertainty, a large number of particles has to be used, especially when the dimension of the state vector is large; this may be an issue for real time implementation of the PF. Several authors have tried to overcome these shortcomings by combining approaches (see [START_REF] Gustafsson | Particle filters for positioning, navigation, and tracking[END_REF] and references therein) or by adapting the size of sample sets during the estimation process [START_REF] Fox | Adapting the sample size in particle filters through KLDsampling[END_REF].

The classical data fusion algorithms mentioned above are strongly affected by several types of measurement errors like bias and drift, or even by partial or total conflict between the sources of information [START_REF] Arulampalam | A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking[END_REF][6] [START_REF] Chen | Bayesian estimation by sequential Monte Carlo sampling[END_REF]. Moreover, these methods critically rely on accurate state space and observation noise models, which are rarely available.

Methods in the second group, referred to as state bounding or bounded error methods, assume all variables to belong to known compact sets and attempt to build simple sets, such as boxes, guaranteed to contain all state vectors consistent with given constraints [START_REF] Jaulin | Applied Interval Analysis[END_REF].

These methods are deterministic approaches and handle only interval information acquired from multiple sources. The interval framework has been shown by several authors to be a good methodology for dealing with non-white and biased measurements [START_REF] Abdallah | Box Particle Filtering for non Linear State Estimation using Interval Analysis[END_REF][7] [START_REF] Gning | Constraints propagation techniques on intervals for a guaranteed localization using redundant data[END_REF][29] [START_REF] Jaulin | Nonlinear bounded-error state estimation of continuous-time systems[END_REF].

Recently, a relatively simple and fast method based on constraint propagation and interval analysis has been introduced in [START_REF] Gning | Dynamic vehicle localization using constraints propagation techniques on intervals. a comparison with Kalman filtering[END_REF] [START_REF] Gning | Constraints propagation techniques on intervals for a guaranteed localization using redundant data[END_REF] with an application to vehicle localization. The use of the box representation of the state is dictated by computational convenience: the main advantage of this representation is that intervals can easily be manipulated using interval analysis. The main interest of the bounded-error approach arises from the fact that it allows so-called validated computations, i.e., computations with guaranteed accuracy taking into account all possible sources of error, from data imprecision to rounding errors due to computer calculations. The major drawback of this approach is the difficulty in determining noise bounds. If the bounds are too tight, the data may become inconsistent with the system equations, in which case the method fails to provide a solution, but if the bounds are overestimated, the estimated state becomes very imprecise, and the method becomes overly pessimistic.

Integrated GPS/DR systems using data fusion usually fail to provide the current vehicle position on a given road segment [START_REF] Agamennoni | Robust Inference of Principal Road Paths for Intelligent Transportation Systems[END_REF][3][9] [START_REF] Taylor | Road reduction filtering for GPS-GIS navigation[END_REF]. The availability of an accurate digital road network makes it possible to find the vehicle position on a road segment. This technique is referred to as map matching (MM). The general purpose of an MM algorithm is to identify the correct road segment on which the vehicle is travelling and to compute the vehicle position on that segment. A number of different algorithms have been proposed for MM in different applications [START_REF] Chen | An integrated map-match algorithm with position feedback and shape-based mismatch detection and correction[END_REF][20] [START_REF] Jabbour | Map-Matching Integrity Using Multihypothesis Road-Tracking[END_REF][49] [START_REF] White | Some map matching algorithms for personal navigation assistants[END_REF]. In most existing MM algorithms, the parameters used to select a precise road segment are based on the proximity between the vehicle position and the road, the degree of correlation between the vehicle trajectory and the road centerline, and the topology of the map. In [START_REF] Jabbour | Map-Matching Integrity Using Multihypothesis Road-Tracking[END_REF] and [START_REF] Pyo | Development of a map matching method using the multiple hypothesis technique[END_REF], the authors proposed a MM algorithm in which the multiple hypotheses technique (MHT) is used in order to compute a more accurate estimate of the vehicle position on the road segment. MHT involves keeping track of several positions of the vehicle simultaneously, and, if possible, selecting the best candidate. In this approach, probability theory is used for identifying candidate roads and for selecting the best one [START_REF] Hummel | Dynamic and Mobile GIS: Investigating Changes in Space and Time, chapter Map Matching for Vehicle Guidance[END_REF], [START_REF] Pyo | Development of a map matching method using the multiple hypothesis technique[END_REF].

In this paper, we propose an MM algorithm called Belief Map Matching (BMM), that combines bounded error state estimation with a rectangular road map representation and that manages multiple hypotheses using belief function theory, also referred to as Dempster-Shafer theory [START_REF] Nassreddine | Map matching algorithm using belief function theory[END_REF], [START_REF] Shafer | A mathematical theory of evidence[END_REF], [START_REF] Ph | The Transferable Belief Model[END_REF], [START_REF] Yager | Classic Works of the Dempster-Shafer Theory of Belief Functions[END_REF]. The rectangular road representation takes geometrical errors in the map and a priori information on road width into account. This representation makes it possible to combine map information with box state estimates in a convenient way. A belief function on a set of candidate roads is computed using geometrical and topological information provided by the map. This method allows us to handle multiple hypotheses at junctions or when roads are parallel, and to cope with missing data.

The paper is organized as follows. An overview of existing mapmatching algorithms is first presented in Section II. Section III introduces the background on basic tools used in this work, i.e., interval analysis and belief function theory. Our method is then introduced in Section IV. Experimental results with simulated and real data are presented in Section V. Finally, Section VI summarizes and discusses the main contributions of the paper.

II. REVIEW OF MAP-MATCHING ALGORITHMS

The goal of map-matching (MM) algorithms is to identify the road taken by a vehicle and to compute an estimate of the vehicle position on that road using a digital map. In this section, we present an overview of existing MM methods and we discuss their limitations as well as the motivations of our work.

A. Overview of Existing MM methods

MM algorithms can be classified into three categories. Algorithms in the first category consider only the geometric relationships between the estimated position of the vehicle and a digital map [START_REF] Taylor | Road reduction filtering for GPS-GIS navigation[END_REF] [START_REF] White | Some map matching algorithms for personal navigation assistants[END_REF].

Algorithms in the second category also consider the topology of the road network and historical data regarding the estimated position of the vehicle [START_REF] Greenfeld | Matching GPS observations to localizations on a digital map[END_REF]. Finally, methods in the third category, referred to as advanced methods, use sophisticated tools such as the Kalman Filter (KF) [START_REF] Jabbour | Map-Matching Integrity Using Multihypothesis Road-Tracking[END_REF], Bayesian networks [START_REF] Smaili | A Road Matching Method for Precise Vehicle Localization Using Hybrid Bayesian Network[END_REF], Dempster-Shafer theory (also known as Belief theory) [START_REF] El Najjar | A road matching method for precise vehicle localization using belief theory and Kalman filtering[END_REF] or fuzzy logics [START_REF] Syed | Fuzzy logic-based map-matching algorithm for vehicle navigation system in urban canyons[END_REF].

The most common geometric MM approach is based on a simple search concept [START_REF] Quddus | A general map matching algorithm for transport telematics applications[END_REF]. In this approach, the vehicle position is matched to the nearest node or shape point in the digital map. This approach is known as point-to-point matching [START_REF] Bernstein | An introduction to map matching for personal navigation assistants[END_REF]. It is easy to implement, but is strongly affected by the way in which the network was digitized [START_REF] Quddus | A general map matching algorithm for transport telematics applications[END_REF]. Another geometric MM approach is point-to-curve matching [START_REF] Taylor | Road reduction filtering for GPS-GIS navigation[END_REF] [START_REF] White | Some map matching algorithms for personal navigation assistants[END_REF]. In this approach, the vehicle position is matched to the nearest road (curve) in the road network. As each road is composed of several line segments, the distance between the vehicle position and each line segment is calculated. The line with the smallest distance is judged to be the one on which the vehicle is travelling. This approach is usually more efficient than point-to-point matching but it generates unstable results in dense urban networks [START_REF] Quddus | A general map matching algorithm for transport telematics applications[END_REF]. Curve to curve matching constitutes yet another geometric MM approach.

In this approach, the candidate nodes are first selected using pointto-point matching. Then, for each candidate node, piecewise linear curves are constructed from the set of paths that originate from that node. Also, a piecewise linear curve can be constructed using the vehicle trajectory. The distance between the trajectory and the road curve is then calculated. The road at the smallest distance from the vehicle trajectory is selected. Unfortunately, this approach is quite sensitive to outliers and it sometimes yields unexpected and undesirable results [START_REF] Quddus | A general map matching algorithm for transport telematics applications[END_REF].

In the second category of algorithms, in addition to geometric information, the result of the MM algorithm at time step k -1 is used for selecting candidate roads at time step k using the topology of the road network as a constraint [START_REF] Taylor | Road reduction filtering for GPS-GIS navigation[END_REF]. These methods are usually based on a weighted topological algorithm for selecting the vehicle's current road. Using the topology analysis of a road network and the coordinates or the trajectory information of the vehicle, this algorithm can compute the weight of each candidate road. The actual road taken by the vehicle is judged to be the one with the largest weight.

However, if the result given by the algorithm was wrong at time step k -1, then the result at time step k is also likely to be wrong, especially after a junction or where there are close parallel roads. This constitutes a major implementation problem and drawback of this method.

We may remark that most existing map matching algorithms apply a simple perpendicular projection of the position fixes onto the selected links, and ignore the numerous errors associated with the positioning sensors and the spatial road network data.

Advanced MM methods are based on more elaborate tools such as the KF, Demspter-Shafer theory, fuzzy logics and the MHT [START_REF] El Najjar | A road matching method for precise vehicle localization using belief theory and Kalman filtering[END_REF][31] [35][46].

In [START_REF] El Najjar | A road matching method for precise vehicle localization using belief theory and Kalman filtering[END_REF], a road selection method based on multi-criteria fusion using belief function theory is proposed. In this method, a confidence region is used for selecting a set of candidate roads (CRs). Proximity and angular criteria are used in order to define a belief function on a set of CRs. The road with the highest degree of belief is then selected. This method, however, can yield inaccurate results in the case of parallel roads, as it does not consider the topology of the road network when selecting the set of CRs. Also, when GPS measurements are not available, the estimated position can be attributed to the wrong road, as this method does not use the multiple hypotheses technique.

In [START_REF] Kim | Efficient use of digital road map in various positioning for ITS[END_REF], an MM method based on the KF and geometrical properties is presented. In this method, the most plausible road is chosen using the point-to-curve method. The orthogonal projected location of the position fix onto the link is used as the initial vehicle location. Due to the point-to-curve projection, the cross-track error is reduced, as compared to the point-to-point method. However, the along-track error remains a key issue. A KF is then designed to re-estimate the vehicle position with the objective of minimizing the along-track error. As stated above, the point-to-curve method is not sufficient for selecting the correct link, especially in dense urban road networks.

If the identification of the link is incorrect, then the inputs of the KF will also be inaccurate, which may result in further positioning errors.

In [START_REF] Syed | Fuzzy logic-based map-matching algorithm for vehicle navigation system in urban canyons[END_REF], the authors describe a map matching algorithm based on a fuzzy model. This algorithm is composed of two main steps. The first step, referred to as the first fix mode, is the initialization step. It is based on a fuzzy inference system (FIS), which is used to identify the correct road of the vehicle. The FIS selects a set of links that are within a given region of the GPS/DR position fix. A link is then identified based on the direction of the vehicle relative to the direction of the links and the heading change from the gyroscope. The location of the vehicle is then determined by an orthogonal projection of the position fixed onto that link. This step takes about 30 sec to identify the first road. In the second step, called the tracking mode, another FIS is used to find out whether the subsequent position fixes can be matched to the link identified in the first fix mode. The inputs are proximity, orientation and distance traveled by the vehicle along the link. If there are any outliers in the GPS/DR outputs, or if a turn is detected, then the algorithm goes back to the first fix mode. This method is not recommended in urban areas. Indeed, the algorithm may have to use the first fix mode frequently, which induces a delay in the identification of the first correct link. Also this method does not take into account the error sources associated with the navigation sensors and the digital maps and hence the determination of vehicle location is not robust.

In [START_REF] Pyo | Development of a map matching method using the multiple hypothesis technique[END_REF], a map matching algorithm using MHT is proposed. The main contribution of this work is the use of MHT to solve the MM problem in some crucial situation such as junctions and parallel roads. MHT, which uses measurements from a validation region, is reformulated as a single target problem to develop the map matching method. Pseudo-measurements are generated for all links within the validation region defined as the error ellipse from the GPS/DR system. Pseudo-measurements (position and heading) are defined as the projected points of the GPS/DR positions on the links. The topological analysis of the road network (connectivity, orientation, and road design parameters) together with the pseudo-measurements are used to derive a set of hypotheses and their probabilities for each GPS/DR sensor output. Hypotheses with probabilities below a certain threshold are rejected. The map matching is only applied to the valid hypotheses and then a KF is executed to estimate the vehicle position on the CR corresponding to each hypothesis. The estimated position corresponding to the hypothesis with the highest probability is selected as the most plausible position of the vehicle.

B. Motivations of this Work

Map matching methods are based on combining an available state estimate with data extracted from a map database. These methods differ according to whether they are applied to probabilistic or bounded state estimates, to the subset of attributes used from the available map database, and to how these data are merged.

Classical MM methods rely on a Bayesian representation of the state uncertainty and are not suitable for handling bounded error estimation.

Box or bounded representation of the state has proved to be efficient in many applications, as shown in [START_REF] Abdallah | Box Particle Filtering for non Linear State Estimation using Interval Analysis[END_REF] [START_REF] Jaulin | Nonlinear bounded-error state estimation of continuous-time systems[END_REF]. As a consequence, a new map matching method based on this type of state representation is becoming increasingly necessary. This in fact is one of the principle motivations of the BMM method presented in the paper. Furthermore, using a state box representation seems to be more intuitive when dealing with a rectangular road representation. The Multiple hypothesis assumption of the MM problem constitutes one of the advantages of the method. Depending on the estimation approach, criteria based on the proximity, historical navigation information and the topology of the road network have to be adapted.

One major problem of some existing MM methods is that they do not consider exhaustively the map error and the road width in the selection of the correct link and in the determination of the vehicle position. In the proposed MM method, a rectangular representation of the roads is used to overcome the problem of existing MM method by taking into account in a natural way map errors and road widths, which are quantities available in recent map databases.

Furthermore, the rectangular representation of the map allows us to take into account several types of error on the available digital map, as it is more exhaustive than other representations used in some existing works [START_REF] Jabbour | Map-Matching Integrity Using Multihypothesis Road-Tracking[END_REF] [START_REF] El Najjar | Road Selection Using Multicriteria Fusion for the Road-Matching Problem[END_REF]. In addition, state boxes and rectangular road representations fulfil naturally the integrity requirements studied in [START_REF] Quddus | Integrity of map matching algorithms[END_REF]. This is explained in more details in Section IV-E.

Belief function theory will be used for road selection and to handle multiple hypotheses. As will be shown, the use of belief functions makes it possible to detect missing map data (a common problem in MM) in a simple and efficient way. In contrast, this issue requires more complex procedures in existing classical map matching methods [START_REF] Chen | An integrated map-match algorithm with position feedback and shape-based mismatch detection and correction[END_REF] [START_REF] Jabbour | Map-Matching Integrity Using Multihypothesis Road-Tracking[END_REF]. Furthermore, the management of multiple hypothesis cases (junction and parallel road situations) requires a complicated implementation under the Bayesian framework because of combinatorial problems [START_REF] Jabbour | Map-Matching Integrity Using Multihypothesis Road-Tracking[END_REF]. As will be shown, the theory of belief functions makes it possible to design a simple solution to this problem, using the topology of the map and historical navigation information (link ID, vehicle location, vehicle heading and speed or elementary displacement).

Table I set out the information requirements of the different methods to be implemented in this paper. This table clearly shows that only our method is well adapted to bounded error approaches. Also, this method gathers simultaneously, and in a simple manner, different topological attributes of the map database. Note that even though the similarity in orientation criterion is not used in the BMM method, the flexibility of the belief function theory used to merge information makes it easy to take into account this criterion (or any other criterion) in the BMM algorithm.

Table II summarizes the ideas behind some MM algorithms that are discussed in the paper. This table also shows the advantages and the limitations of the different algorithms.

III. BASIC TOOLS

In this section, the basic tools used in this paper are briefly introduced. Interval analysis is first presented in Subsection III-A, and the necessary background on belief functions is recalled in Subsection III-B.

A. Interval Analysis

We briefly present interval analysis and we describe the constraint propagation technique, also referred to as the consistence technique by some authors.

1) Basic Notions: Usually, interval analysis is used to model quantities that vary around a central value within certain bounds.

A real interval, denoted [x], is defined as a closed and connected subset of R:

[x] = [x, x] = {x ∈ R/x ≤ x ≤ x},
where x and x are the lower and upper bounds of

[x]. A box [x] of
R n is defined as a Cartesian product of n intervals:

[x] = [x1] × [x2] • • • × [xn].
The set of n-dimensional boxes will be denoted by IR n .

All set-theoretic operations, e.g., ∩, ∪, . . . as well as the four elementary arithmetic operations {+, -, * , /} can be extended to the interval context. In general, the image of a box [x] ∈ IR n by a function f may have any shape. It may be non-convex shape or even multiply connected if f is discontinuous, as shown in Figure 1

. An interval function [f ] from IR n to IR m is said to be an inclusion function for f if f ([x]) ⊆ [f ]([x]), ∀[x] ∈ IR n . (1)
Inclusion functions may be very pessimistic, as shown by Figure Let us assume that vector x is known to belong to some prior domain [x], and we want to compute the set of all x in the prior domain verifying the constraints. This defines a constraint satisfaction problem (CSP), which can be denoted as

The inclusion function

[f ] is minimal if, for any [x], [f ]([x]) is the smallest box of R m containing f ([x]
f ([x]) [x] [f ] * ([x]) [f ]([x])
H : (f (x) = 0, x ∈ [x]). (3)
The solution set of H is defined as:

S = {x ∈ [x] | f (x) = 0}. (4)
x 1 x 1 x 1 x 2 x 1 x 2 x 2 x 2 f (x 1 , x 2 ) = 0 Fig. 2. A CSP in R 2 .
of CSP. The method used in this paper is the forward-backward propagation technique, also referred to as the Waltz contractor [START_REF] Jaulin | Applied Interval Analysis[END_REF].

The Waltz contractor is based on the propagation of primitive constraints for real variables. A primitive constraint is a constraint involving a single operator (such as +, -, * or /) or a single function (such as cos, sin or sinh). The method proceeds by contracting H with respect to each of the primitive constraints until convergence to a minimal domain. The complete description of the Waltz algorithm goes beyond the scope of this paper. It can be found in [29, page 77]. This algorithm was applied to state estimation in [START_REF] Gning | Constraints propagation techniques on intervals for a guaranteed localization using redundant data[END_REF] and [START_REF] Nassreddine | State estimation using interval analysis and belief function theory: Application to dynamic vehicle localization[END_REF].

B. Belief Function Theory 1) Basic Concepts:

In recent decades, the theory of belief functions, also known as Dempster-Shafer or Evidence theory, has emerged as a flexible framework for handling imprecise and uncertain information [START_REF] Shafer | A mathematical theory of evidence[END_REF][45] [START_REF] Yager | Classic Works of the Dempster-Shafer Theory of Belief Functions[END_REF]. Belief functions can be used to replace the probability-based representation of uncertainty adopted in classical MM and MHT methods. The theory of belief functions makes it possible to model various states of knowledge ranging from complete ignorance to probabilistic uncertainty [START_REF] Yager | Classic Works of the Dempster-Shafer Theory of Belief Functions[END_REF]. A belief function may be viewed both as a generalized set [START_REF] Dubois | A set-theoretic view of belief functions: logical operations and approximations by fuzzy sets[END_REF] and as a generalized (

A categorical belief function is a belief function that satisfies m(A) = 1 for some A ⊂ Ω. The belief function on Ω which has m(Ω) = 1

is the vacuous belief function.

The plausibility function, denoted pl, quantifies the maximum amount of potential specific support that could be given to A ⊆ Ω. It is obtained by adding all the masses given to focal sets B that satisfy

B ∩ A = ∅: pl(A) = B∩A =∅ m(B) = bel(Ω) -bel(A), (6)
where A denotes the complement of A.

Assume that a source of information provides a mass function m, and that we have a degree of confidence α ∈ [0, 1] in the reliability of that source. Then, m can be discounted with discount rate 1α, resulting in the following discounted mass function [START_REF] Shafer | A mathematical theory of evidence[END_REF]:

α m(A) =      α m(A) if A ⊂ Ω, 1 -α(1 -m(Ω)) if A = Ω.
Two mass functions m1 and m2 defined on the same frame of discernment Ω and induced by distinct sources of information can be combined by the conjunctive rule [START_REF] Ph | The combination of evidence in the Transferable Belief Model[END_REF] defined as:

(m1 ∩ m2)(A) = B∩C=A m1(B)m2(C), ∀A ⊆ Ω. (7)
The quantity (m1 ∩ m2)(∅) is called the degree of conflict between the information sources. Under the so-called open-world assumption [START_REF] Ph | The combination of evidence in the Transferable Belief Model[END_REF], a high degree of conflict may sometimes be interpreted as resulting from the non exhaustivity of the frame of discernment, i.e., the existence of a hypothesis not included in Ω.

Let m be a mass function on Ω after combining all available items of evidence. Assume that we have to select an element of Ω. Several decision rules have been proposed. The most common ones consist in selecting the element with the highest plausibility [START_REF] Appriou | Uncertain data aggregation in classification and tracking processes[END_REF], [START_REF] Denoeux | Analysis of evidence-theoretic decision rules for pattern classification[END_REF], or the element with the highest pignistic probability [START_REF] Ph | The Transferable Belief Model[END_REF]. Given a mass function m such that m(∅) < 1, the pignistic probability function betp is defined as:

betp(ω) = {A⊆Ω|ω∈A} m(A) (1 -m(∅))|A| , ∀ω ∈ Ω, (8)
where |A| denotes the cardinality of A. The pignistic probability function is thus obtained from m by distributing equally each normalized mass m(A)/(1m(∅)) among the elements of A.

2) Image of a Mass Function by a Multi-valued Mapping :

Let us now consider the case where we have two variables X and Y defined on frames of discernment Ω and Θ. Assume that X and Y are linked by a multi-valued mapping ϕ : Ω → 2 Θ , such that if X = ω, then we know that Y ∈ ϕ(ω). This mapping can be extended to 2 Ω as follows:

ϕ(A) =      ω∈A ϕ(ω), if A ⊆ Ω, A = ∅, ∅ if A = ∅. (9)
Let us further assume that we have a mass function m Ω on Ω representing our state of knowledge about X. A mass function m Θ on Θ can be built by transferring each mass m Ω (A) to ϕ(A) [START_REF] Denoeux | Inner and outer approximation of belief structures using a hierarchical clustering approach[END_REF].

Formally, m Θ is then defined as follows:

m Θ (B) = {A⊆Ω|ϕ(A)=B} m Ω (A), ∀B ⊆ Θ.
This may also be written

m Θ (B) = A⊆Ω Mϕ(B, A)m Ω (A), ∀B ⊆ Θ, (10)
with

Mϕ(B, A) =      1 if B = ϕ(A), 0 otherwise.

IV. BELIEF MAP MATCHING METHOD

In this section, we present a belief function-based MM method (BMM) based on bounded error estimation techniques as well as geometrical and topological information. The method builds a mass function on a set of candidate roads (CRs) extracted from an existing local map, which makes it possible to provide a more accurate estimation of the vehicle position and to handle multiple hypotheses as well as missing data.

First, under the interval framework, and using a state space model, sensor data is integrated with GPS measurements via a multi-sensor fusion algorithm in order to compute an estimated position. Then, from a rectangular road representation of a two-dimensional geographical information system (GIS), a set of CRs is determined based on the proximity between the vehicle position and rectangular roads.

An estimate of the vehicle position on each CR is then computed.

Finally, the CR with the highest pignistic probability is selected. Note that the estimated positions on all CRs are computed, but only the one corresponding to the best CR is considered as the most plausible vehicle position.

In the following, we first present the geometry of the available rectangular road map in Section IV-A. The state space model is introduced in Section IV-B, and the construction of the mass function on the set of CRs is described in Section IV-C. An overview of the BMM method is then presented in Section IV-D, and the integrity of the method is discussed in Section IV-E.

A. Road Map Representation

Digital maps are usually based on a single line road network representation. Each road is characterized by a finite sequence of points and is thus represented by a set of lines linking these points and representing the centerlines of the road. Figure 3 shows an example of a road modeled by four segments connecting five points A 1 , . . . , A 5 .

Points A 1 and A 5 are the end points of the road and are referred to as nodes, while A 2 , A 3 and A 4 are referred to shape points.

In order to take into account road width and geometrical errors of the map, a piecewise rectangular representation of a road can be defined as illustrated in Figure 4.

By considering the positional error, we assume that the node points of road r can be anywhere within a circle of radius l [START_REF] Noronha | Map accuracy and location expression in transportation reality and prospects[END_REF], [START_REF] Quddus | Integrity of map matching algorithms[END_REF]. The Node point

Shape point

Shape segment

A 1 A 2 A 3 A 4 A 5
Fig. 3. Road representation in the planar model. Empty circles represent shape points (A 2 , A 3 , A 4 ) and filled circles represent node points (A 1 , A 5 ). Two circles of radius l characterize the positional error. ∆β characterizes the shape error and w is the road width.

shape error of r is thus represented by an angle ∆β. As a result, road r can be considered to lie anywhere within a rectangle R as shown in Figure 4. The rectangular road representation [r] of road r can be constructed by adjusting the width of R using the predefined road width w. Figure 5 shows an example of a road representation where shape points are involved in the construction. In this figure, road r1 is characterized by a shape point A 2 and two node points A 1 and

A 3 .
The rectangular representation of roads allows us to take into account several types of errors on digital map data, as it is more exhaustive than other representations used in some existing works [28][18].

However, in some situations (inclined roads), combining a box state with a rectangular road may increase the error on the state estimation result. This error is caused by the wrapping effect, which is a well

A 1 A 2 A 3 r1
Node point Node point Shape point Fig. 5.

Piecewise rectangular representation of r 1 = (A 1 , A 2 , A 3 ) constructed using geometrical error of the map data and the road width. known issue when using interval methods. It can be reduced using a contractor such as the Waltz contractor (cf. Section III-A).

B. Dynamic State Space Model

Consider a car-like vehicle with front-wheel drive. The vehicle position is represented by the Cartesian coordinates (x k , y k ) of the point M corresponding to the center of the rear axle as shown in Figure 6. The heading angle is denoted by θ k . The state x k = (x k , y k , θ k ) T is calculated at each time step k using the following discrete representation:

         x k+1 = x k + δ S,k cos(θ k + δ θ,k
2 )

y k+1 = y k + δ S,k sin(θ k + δ θ,k 2 ) θ k+1 = θ k + δ θ,k , (11)
where δ S,k is the elementary linear displacement and δ θ,k is the measure of the elementary rotation given by an ABS sensor and a gyrometer, respectively. The observation of the position at time step k, z k = (xGP S , yGP S ), is given by a GPS sensor. The longitude and latitude estimated by the GPS are converted to a Cartesian local frame and standard deviations σx and σy on both coordinates are obtained from the NMEA GPGST (Pseudorange Noise Statistics) sentence 1 [START_REF] Gning | Constraints propagation techniques on intervals for a guaranteed localization using redundant data[END_REF].

A box is built around δ S,k and δ θ,k using standard deviations σs and σ θ estimated from specific static tests:

[δ S,k ] = [δ S,k - κ • σs, δ S,k + κ • σs] and [δ θ,k ] = [δ θ,k -κ • σ θ , δ θ,k + κ • σ θ ],
where κ is a constant. In the same way, we build a box around GPS

measurement z k : [z k ] = ([x k,GP S ], [y k,GP S ]) T where [x k,GP S ] = [x k,GP S -κ • σx, x k,GP S + κ • σx] and [y k+1,GP S ] = [y k,GP S -κ • σy, y k+1,GP S + κ • σy].
1 GPS receiver communication is defined within the specification given by the National Marine Electronics Association (NMEA). This specification was first set up in order to define the interface between various pieces of marine electronic equipment. Most computer programs that provide real time position information understand and expect data to be in the NMEA format. In the simulations presented below, we have followed common practice in state bounding estimation [START_REF] Abdallah | Box Particle Filtering for non Linear State Estimation using Interval Analysis[END_REF][22] and have chosen κ = 3.

[x k ] [x k+1 ] [r 1 ] [r 1 ] [r 2 ] [r 2 ] [r 3 ] [r 3 ] [r 4 ] [r 4 ] Time step k Time step k + 1
This is justified by the well known fact that, under Gaussian assumptions, the corresponding interval contains the true value of the quantity of interest with 99.87% probability. (From Tchebychev's inequality, this probability cannot be smaller than 8/9, whatever the error distribution, if the measurement is unbiased). Experimental results have shown that a smaller value such as κ = 2 might still provide acceptable results. However, the state bounding approach relies on the concept of guaranteed estimation; consequently, the method must be provided with intervals containing unknown quantities with probability close to one.

Note that the value of κ has a critical influence on the precision and reliability of the BMM method. If κ is overestimated, pessimistic state boxes are produced, resulting in imprecise state estimates. Conversely, if κ is underestimated, inconsistencies between measurements, state predictions and map data may occur.

C. Mass Function Construction

Given a state box [x k ] and a rectangular road map, a set R k of CRs can be selected in such a way that any rectangular road [r] in

R k satisfies: [x k ] ∩ [r] = ∅.
The associated mass function at time step k, m R k , can be computed using topology and similarity criteria. This is done as follows:

• Topology criterion: Using the topology of the map and mass

function m R k , a mass function m R k+1 1
on R k+1 can be computed as shown by the following example.

Consider the case of Figure 7, where road r 2 is linked to roads

ϕ(r 1 ) = {r 1 }, (12)
ϕ(r 2 ) = {r 2 , r 3 , r 4 }, (13)
where ϕ(r) denotes the possible positions at time k + 1, given that the vehicle was on road r at time k. As explained in Section III-B2, ϕ can be extended to 2 R k using ( 9), and a mass function

m R k+1 1
can be built on R k+1 using [START_REF] Chen | Bayesian estimation by sequential Monte Carlo sampling[END_REF]. Here, the computation

of m R k+1 1
from m R k can be detailed as follows:

-m R k (∅) is transferred to m R k+1 1 (∅); -m R k ({r 1 }) is transferred to m R k+1 1 ({r 1 }); -m R k ({r 2 }) is transferred to m R k+1 1
({r 2 , r 3 , r 4 }) as r 2 is linked to r 3 and r 4 ;

-m R k ({r 1 , r 2 }) is transferred to m R k+1 1
({r 1 , r 2 , r 3 , r 4 }).

In general, matrix Mϕ (hereafter referred to as the transition matrix) to be used in [START_REF] Chen | Bayesian estimation by sequential Monte Carlo sampling[END_REF] is computed from the topology of the road network, and we have m

R k+1 1 (B) = A⊆R k Mϕ(B, A)m R k (A), ∀B ⊆ R k+1 . ( 14
)
[x k+1 ] [r i ] [r j ] [x j k+1 ] [x i k+1 ]
Fig. 8. State update using [x k+1 ] and two rectangular roads [r i ] and [r j ].

• Similarity criterion: Using a measure of similarity between the rectangular roads in R k+1 and the state box

[x k+1 ], a mass function m R k+1 2
on R k+1 is calculated. This similarity is characterized by the area of the intersection between [x k+1 ] and the rectangular roads. For geometrical convenience it is calculated as the area of the minimal box containing this intersection. Let

L i = |[x i k+1 ]| |[x k+1 ]| ,
where [x i k+1 ] is the minimal box containing the intersection between the rectangular road [r i ] and [x k+1 ] as shown in Figure 8. L i can be seen as a geometrical likelihood of the road given a state box [x k+1 ]. Using L i , a mass function mi can be computed as follows [START_REF] Appriou | Uncertain data aggregation in classification and tracking processes[END_REF]:

         mi({r i }) = 0 mi({r i }) = αi(1 -L i ) mi(R k+1 ) = 1 -αi(1 -L i ) (15)
where {r i } is the complement of {r i } in R k+1 and αi is a coefficient associated with road r i . The mass function m

R k+1 2
is the combination of all mi using the conjunctive rule of combination [START_REF] Ashokaraj | Sensor Based Robot Localisation and Navigation: Using Interval Analysis and Extended Kalman Filter[END_REF]:

m R k+1 2 = ∩ i mi. ( 16
)
The mass functions m Note that the heading angle θ is not directly observed, and is initialized as

R k+1 1 and m R k+1 2 are then combined in order to compute m R k+1 as m R k+1 = m R k+1 1 ∩ m R k+1 2 . ( 17
[θ0] = [0, +2π]. From [x0]
and the rectangular road map, a set R0 of CRs is selected as explained in Section IV-C. As there is no prior information on the vehicle position at time step k = 0, m R 0 1 should be initialized as a vacuous mass function on R0. The mass function m R 0 2 is calculated using [START_REF] Dubois | A set-theoretic view of belief functions: logical operations and approximations by fuzzy sets[END_REF] and [START_REF] El Najjar | Multi-criteria fusion for the selection of roads of an accurate map[END_REF]. The final mass function m R 0 is thus the result of the combination of m R 0 1 and m R 0 2 according to [START_REF] El Najjar | A road matching method for precise vehicle localization using belief theory and Kalman filtering[END_REF]. As the vehicle should be on a road,

[x0] is replaced by {[x i 0 ]} n R 0
i=1 as shown in Figure 8.

2) Prediction:

In this step, state boxes {[x i k ]} n R k
i=1 associated with all CRs are updated using [δ S,k ], [δ θ,k ] together with the evolution equation ( 11) via the application of the interval tools recalled in Section III-A [START_REF] Gning | Constraints propagation techniques on intervals for a guaranteed localization using redundant data[END_REF], [START_REF] Jaulin | Applied Interval Analysis[END_REF]. Note that, as inclusion functions are used, we may obtain suboptimal predicted state boxes

{[x i k+1 ]} n R k i=1 at time step k + 1.
3) GPS correction: The GPS measurement box [z k+1 ] is used in order to adjust state boxes. The intersection between a state box

([x i k+1 ], [y i k+1 ]) T and the GPS box [z k+1 ]: [I i ] = [x i k+1 ] ∩ [z k+1
], characterizes the proximity between the prediction and the measurement. This intersection is used to contract [x i k+1 ] using the Waltz algorithm (see Section III-A) according to the constraints of system [START_REF] Chen | An integrated map-match algorithm with position feedback and shape-based mismatch detection and correction[END_REF] [1] [START_REF] Jaulin | Applied Interval Analysis[END_REF]. Note that CRs associated with the predicted state boxes that have no intersection with [z k+1 ] are eliminated from R k+1 .

4) GIS correction:

After the GPS correction, the piecewise rectangular representation of CRs is used to adjust the state boxes and to compute a state estimate of the vehicle. Figure 9 shows an example where, starting from road r 1 , there is no possible transition to another road, whereas there is a possibility of transition from r 2 to r 3 or r 4 .

Regarding junction situations, two cases should be considered:

• If the distance between the center of [x i k ] and any node or shape point of road r i is less than the elementary displacement δ S,k given by the rear wheel ABS sensors, then it is possible that the vehicle is leaving road r i . For this reason, at time step k + 1, the set R k of CRs must be replaced by a set R k+1 . This is done as follows. Let S i be the set of all roads directly linked to r i (r i ∈ S i ) and that have an intersection with

[x i k ]. The set R k+1 is then updated as: R k+1 =R k ∪ S i .
Using a transition matrix Mϕ calculated from the topology of the map, the mass function m R k+1 1 is then calculated from m R k from [START_REF] Drawil | Intervehicle-Communication-Assisted Localization[END_REF].

• If the distance between the center of state box [x i k ] and each node and shape point of road r i is greater than δ S,k , then resulting from the similarity criterion is computed using [START_REF] Dubois | A set-theoretic view of belief functions: logical operations and approximations by fuzzy sets[END_REF] and [START_REF] El Najjar | Multi-criteria fusion for the selection of roads of an accurate map[END_REF]. By combining m R k+1 1

R k+1 = R k . [x 1 k ] [x 2 k ] [x k ] [x 1 k+1 ] [x 2 k+1 ] [x 3 k+1 ] [x 4 k+1 ] [r 1 ] [r 1 ] [r 2 ] [r 2 ] [r 3 ] [r 3 ] [r 4 ] [r 4 ] Time step k Time step k + 1
and m R k+1 2 using (17), the final mass function m R k+1 is then obtained.

Note that, if there is no intersection between state boxes and any road in R k+1 , then the resulting state boxes

{[x i k+1 ]} n R k
i=1 should be retained, as the vehicle may be moving on a road that is not included in the map. In this case, we update the set of CRs as follows:

R k+1 = R k ∪ T , where T includes all roads linked to any r i ∈ R k .
This rule is introduced as an attempt to match the estimated position of the vehicle on a road in case of failure of the algorithm. If this solution is not adequate, an initialization of the algorithm is needed.

In the other case, i.e., if at least one road r j is matched, each available box [x i k+1 ] is replaced by the minimal box [x j k+1 ] containing the intersection between [x i k+1 ] and the rectangular road [r j ].

5) Overall Estimation:

In the final step of the algorithm, the CR with the highest pignistic probability (8) is selected, and the state box intersecting the selected road is chosen. In the case where several boxex intersect the selected road, the state box is taken as the minimal box enclosing all boxes associated with the road. The point estimate of the vehicle position is defined as the center of the final state box.

The confidence in the estimated coordinates x and y is then defined as the width of the box along the corresponding dimension.

The BMM algorithm is summarized in Appendix A. The integrity issue is briefly discussed in the following subsection.

E. Integrity of the BMM Method

The integrity of a map-matching algorithm is the measure of the confidence that can be placed in the correctness of the positions delivered by the system [START_REF] Quddus | Integrity of map matching algorithms[END_REF]. It is related to the ability of the system to correctly identify a link and to accurately determine the vehicle location on the link. In [START_REF] Quddus | Integrity of map matching algorithms[END_REF], the authors propose an integrity measure based on three criteria:

• Distance residuals: This criterion quantifies the proximity between the vehicle position fix P and the corresponding mapmatched position M on a link. Let D(P, M ) be the distance between P and M and R be a constant computed based on the noise of the navigation system and the road width. The integrity of the map is high if D(P, M ) -R is less than or close to zero.

• Heading residuals: This criterion quantifies the proximity between the vehicle and the road heading. Let θ be the vehicle heading, β the road heading and HE a constant computed based on the map error and the navigation system error. The integrity of the map is high if |θ -β| -HE is less than or close to zero. system with probability close to one, D(V, M ) is usually small and is less than or equal to w 2 +l, where w is the road width and l represents the geometrical error of the map. We may therefore conclude that the BMM method naturally complies with the integrity requirements proposed in [START_REF] Quddus | Integrity of map matching algorithms[END_REF].

V. EXPERIMENTS

In this section, we first illustrate the behavior of the BMM method using simulated data and show comparative results in Subsection V-A.

Results with real data are then presented in Subsection V-B.

A. Simulated Results

The performances of the BMM algorithm were studied using simulation data. The vehicle position, heading, elementary displacement and elementary rotation were generated using the Matlab Simulink toolbox. Uniform GPS measurement noise was used, with bounds w were assumed to be equal to 1 and 6 meters, respectively. This leads to a rectangular road width equal to 8 meters (w + 2 * l).

Figure 10 shows the simulated map and the vehicle trajectory. All distances in the following figures are in meters.

Figure 11 shows how several hypotheses can be managed with the BMM method when approaching a junction. 1) Performance comparison: Our method was compared with two recent MM algorithms proposed by Quddus et al. [START_REF] Quddus | A general map matching algorithm for transport telematics applications[END_REF] and by El Najjar and Bonnifait [START_REF] El Najjar | A road matching method for precise vehicle localization using belief theory and Kalman filtering[END_REF], [START_REF] El Najjar | Road Selection Using Multicriteria Fusion for the Road-Matching Problem[END_REF]. We first give a short description of these two algorithms:

• The algorithm developed by Quddus et al. [START_REF] Quddus | A general map matching algorithm for transport telematics applications[END_REF] is a relatively simple geometric algorithm. The MM matching process is initiated with point-to-point matching to identify a link among the links connected with the closest node to the position fix.

Based on various similarity criteria between the derived position fixes and the network topology, a weighting system is used to select the correct link. The criteria used in the algorithm are the similarity in orientation, proximity of the point to the link and the position of the fix relative to the link.

• The advanced MM algorithm introduced by El Najjar and

Bonnifait in [START_REF] El Najjar | A road matching method for precise vehicle localization using belief theory and Kalman filtering[END_REF], [START_REF] El Najjar | Road Selection Using Multicriteria Fusion for the Road-Matching Problem[END_REF] is based on Kalman filtering and belief functions. The EKF first combines the GPS and ABS sensor measurements to produce an approximation of the vehicle position, which is used to select the most likely road segment in the database. The selection strategy uses several criteria based on distance, direction and velocity measurements, each expressed as a mass function and pooled using the conjunctive rule of combination. A new observation is then built using the selected segment, and the estimated position is adjusted in a second Kalman filter stage.

These three methods were applied to the simulated map in 2) Result with Missing Map Data: In this section, we demonstrate the behavior of the BMM method when some roads are missing from the map. Figure 12 illustrates such a situation. As can be seen in In this case, it is assumed that the vehicle is travelling on a road and the state box. Consequently, the vehicle is considered to be travelling on r 5 and m R k ({r 5 }) = 1. Figure 14 shows the results of applying the BMM and reference methods to the trajectory depicted in Figure 12. Globally, both methods perform well as they detect the incompleteness of the map for the most part of the trajectory.

However, the BMM algorithm detects earlier that the vehicle has left the main road (k = 67, 68), and the reference method tends to select the nearest road on the map too early at time k = 87.

B. Results on Real Data

In this section, results with the BMM method applied to real data are reported. The test trajectory was carried out in Compiègne,

France with the experimental vehicle of the Heudiasyc laboratory 2 .

The measurement of the position (xGP S , yGP S ) was provided by a GPS receiver. The elementary rotation and displacement between two samples were obtained with good precision using a fiber optic gyrometer and two rear wheel ABS sensors. In this application, the positional error l was assumed to be equal to one meter, and the road width w was equal to 6 meters. The map is shown in Figure 15. 2 We thank Philippe Bonnifait and his group for providing and allowing us to use these data. As can be seen, at time step k1, there are three CRs and the BMM method provides an estimate of the position on each CR. At time step k1 + 1, only two CRs remain (see Figure 16-c), as the third one has been eliminated by the BMM algorithm.

As the exact trajectory of the vehicle is not known in this application, positioning errors cannot be computed like they were in the simulation Section. However, the performances of the BMM method can be assessed quantitatively by computing the fraction of time the correct link was selected. The correct link at each time step is known here thanks to a camera that was fixed on the vehicle during the experiment. A data player makes it possible to visualize the road scenes together with the sensor data and to identify the true trajectory on the map. also shown for comparison. As can be seen, the advanced method developed El Najjar and Bonnifait significantly outperforms the geometric reference method, while the BMM algorithm brings further improvement. The scale of the digital map is of no importance in the evaluation of the algorithm, since only the percentage of detected road is given.

VI. CONCLUSION

In this paper, a new method for map matching and state estimation has been presented. This method combines the outputs from existing bounded error estimation techniques with piecewise rectangular roads selected using evidential reasoning. The basic idea of this work is the selection of a set of CRs at each time step using the topology of the map and a similarity criterion. Then, a mass function on the set of CRs is calculated using a multiple criteria fusion algorithm.

In this method two criteria are used: map topology and similarity.

After selecting CRs and computing the associated mass function, an overall estimate of the vehicle position is calculated using a decision rule from belief function theory. This method enables us to handle multiple hypotheses efficiently at road junctions, and to cope with missing map data. In addition, its implementation is quite simple as it is based on geometrical properties of boxes and rectangular roads.

Results on simulated and real data have demonstrated the ability of the method to handle ambiguous situations (such as junctions or close :

• IF the distance between the center of [x i k ] and a node or a shape point of road r i is less than δ S,k , then: -Let S(r i ) be the set of all roads directly linked to r i including r i . Let ns be the number of roads included in S(r i ). Initialize S i = ∅ -For j = 1 : ns

-if [r j ] ∩ [x i k ] is not empty then * S i = S i ∪ {r j } * [x j k+1 ] = [x i k+1 ] ∩ [r j ] -ENDFOR j -R k+1 = R k+1 ∪ S i and m R k+1 1 = M.m R k+1 1
, where M is the transition matrix computed in such way that m R k+1 1

({r i }) is transferred to m R k+1 1

(S i )

• ELSE R k+1 and m R k+1 1

remain unchanged and:

[x i k+1 ] = [x i k+1 ] ∩ [r i ] • ENDIF • IF {[x i k ] ∩ [r i ] = ∅} n R k i=1 then -{[x i k+1 ]} n R k i=1 are kept -R k+1 = R k ∪ T , T

Fahed Abdallah ,

 Abdallah Ghalia Nassreddine and Thierry Denoeux Abstract-The goal of map-matching algorithms is to identify the road taken by a vehicle and to compute an estimate of the vehicle position on that road using a digital map. In this paper, a map-matching algorithm based on interval analysis and belief function theory is proposed. The method combines the outputs from existing bounded error estimation techniques with piecewise rectangular roads selected using evidential reasoning. A set of candidate roads is first defined at each time step using the topology of the map and a similarity criterion, and a mass function on the set of candidate roads is computed. An overall estimate of the vehicle position is then derived after the most probable candidate road has been selected. This method allows multiple road junctions hypotheses to be handled efficiently, and can cope with missing data. Also, the implementation of the method is quite simple as it is based on geometrical properties of boxes and rectangular road segments. Experiments with simulated and real data demonstrate the ability of this method to handle junction situations and to compute an accurate estimate of the vehicle position. Index Terms-Map-matching, Dempster-Shafer theory, Evidential reasoning, Multi-sensor fusion, Interval analysis, Bounded error estimation, Multiple Hypotheses technique.

Fig. 1 .

 1 Fig. 1. Images of a box [x] by a function f , a pessimistic inclusion function [f ] and the minimal inclusion function [f ] * .

  probability measure: DS theory thus encompasses set-based as well as probabilistic formalisms. In this section, we introduce the main concepts of Belief function theory. Let Ω denote a finite set of mutually exclusive and exhaustive hypotheses, called the frame of discernment. A mass function m is a mapping from 2 Ω to [0, 1], satisfying: A⊆Ω m(A) = 1. Each quantity m(A) represents a mass of belief that is committed to A, and cannot be assigned to any strict subset of A, based on a given piece of evidence. Every subset A of Ω such that m(A) > 0 is called a focal set of m. If m(∅) = 0 then m is said to be normal. The belief function induced by m is the function bel : 2 Ω -→ [0, 1] satisfying: bel(A) = ∅ =B⊆A m(B) for all A ⊆ Ω.

2 Fig. 4 .

 24 Fig. 4. Rectangular road [r] constructed using map data, geometrical errors and the road width. The road r is represented by two node points (A 1 , A 2 ).

Fig. 6 .

 6 Fig. 6. Definition of the frames.

Fig. 7 .

 7 Fig. 7. State box and rectangular roads at time steps k (top) and k + 1 (bottom).

r 3 and r 4

 4 and road r 1 is parallel to r 2 and r 3 . The vehicle positions at time steps k and k + 1 are represented by two solid rectangles [x k ] and [x k+1 ]. Based on [x k ], the set of CRs at time step k is R k = {r 1 , r 2 }. The available mass function attime step k is m R k with focal sets ∅, {r 1 }, {r 2 }, {r 1 , r 2 }. Note that m R k ({r i , r j })represents the mass of belief assigned to the hypothesis that the vehicle is on road r i or r j at time step k, and m R k (∅) represents the mass of belief assigned to the hypothesis that the vehicle is moving on a road that is not included in the map database at time step k.Based on [x k+1 ], four possible positions of the vehicle on r 1 , r 2 , r 3 or r 4 may occur and thus R k+1 = {r 1 , r 2 , r 3 , r 4 }.Consequently, from the fact that r 2 is linked to {r 3 , r 4 }, and given that r 1 has no intersections with any other roads, the locations of the vehicle at time steps k and k + 1 are linked by the following multi-valued function ϕ : R k → 2 R k+1 :

  ) D. Overview of the BMM Method 1) Initialization: At time step k = 0, an initial state box is constructed using the GPS measurement and the standard deviations σx and σy estimated in real time by the GPS receiver: [x0] = [x0,GP S -3 • σx, x0,GP S + 3 • σx] and [y0] = [y0,GP S -3 • σy, y0,GP S + 3 • σy].

Fig. 9 .

 9 Fig. 9.Possible scenarios when managing multiple hypotheses due to junctions. The bold black boxes represent the state after GIS correction.

•

  Confidence of the map matched position: This criterion is based on the proximity between the map matched position M and the real vehicle position V . Let D(M, V ) be the distance between M and V . The confidence of the map matched position is high if D(M, V ) ≤ r f where r f is a constant computed from the map error, sensor error and road width. The BMM method has the advantage of naturally meeting the integrity criteria mentioned above. The map matched position of the vehicle is included in the intersection of the bounded estimation box and the rectangular representation of the roads. As the map error and road width are taken into account when constructing the rectangular roads of the map, and the noise sensors are integrated in the bounded estimation of the vehicle position, it is clear that D(P, M ) -R and |θ -β| -HE are usually less than or close to zero. Since the real vehicle position is included in the box provided by the GPS/DR

Fig. 10 .

 10 Fig. 10. Simulated road map and vehicle trajectory (blue bold lines).

[

  -7m, +7m] and [-9m, +9m] on x and y respectively. The noise in the input data (elementary movement and rotation) was also assumed to be uniform with on the interval [-0.25m, +0.25m] and [-0.002 deg, +0.002 deg]. The positional error l and the road width

Figure 11 illustrates

 11 Figure 11 illustrates the management of multiple hypotheses by the BMM method after time step k = 182. As can be seen, at time steps k = 182 and k = 183, there are four CRs R k = {r 1 , r 2 , r 3 , r 4 }. At time step k = 184, there is only one CR left r k = {r 4 }, as the other three {r 1 , r 2 , r 3 } are eliminated by the similarity criterion.

4 Fig. 11 .

 411 Fig. 11. Simulation results at a junction starting at k = 182. Rectangular roads are represented by solid rectangles. The real and GPS positions are represented by ( ) and ( * ) points, respectively. Dashed blue rectangles represent the box state associated to CRs where the associated estimated positions are plotted by (∇) points. The state box corresponding to the selected road is plotted as a bold red rectangle and the overall estimated positions are represented by (o) points.

Figure 10 .

 10 Figure 10. Mean squared errors (MSE) on x and y are reported in TableIII(results with the GPS alone are also included for

Figure 12 -

 12 Figure 12-b, after time step k = 66 the vehicle leaves road r 4 and proceeds to travel along a road that is not included in the map. At time step k = 88, the vehicle is once again travelling on an existing road, r 5 .Figure 13-a shows the zoomed result at time steps k = 66 and k = 67. As can be seen, at time step k = 66 there is only one CR and thus R k = {r 4 } and m R k ({r 4 }) = 1. At time step k = 67 there is no intersection between the state box and the CR.

Fig. 12 .Fig. 13 .

 1213 Fig. 12. Simulated map and trajectory in the case of missing map data. Figure (a) shows the vehicle trajectory represented by bold blue lines. Figure (b) shows the vehicle trajectory (represented by dashed line) on missing road between time steps k = 66 and k = 88.

Figure 16 -

 16 Figure 16-a displays the BMM estimated positions near a road junction (time step k1). Figures 16-b and c show the estimated positions corresponding to all CRs at time steps k1 and k1 + 1.

Fig. 14 . 1 Fig. 15 .

 14115 Fig. 14. Comparison between the BMM algorithm and the method developed by El Najjar and Bonnifait (reference method) in the case of missing map data. The true positions of the vehicle are plotted by (.) points. Estimated positions computed using the BMM and reference methods are plotted as (o) points and (+) points, respectively.

3 Time step k 1 + 1 Fig. 16 .

 3116 Fig. 16. Experimental results at a junction. BMM results and GPS positions are plotted as (o) and ( * ) points, respectively (a). In sub-figures (b) and (c), the estimated positions on CRs, overall estimated positions and GPS measurements are represented by (∇) points, (o) points and ( * ) points, respectively. The dashed and bold rectangles represent the box states of CRs and the box states corresponding to the selected road, respectively.

2 2) 1 = m R k 3 )

 213 parallel roads) and to compute an accurate and reliable estimation of the vehicle position. k = 0 and create a state box [x0] using the GPS measurement b) For each road r i included in the local map, construct the associated rectangular road [r i ] c) From all rectangular roads [r i ] and [x k ], construct a setR k of CRs such that [r i ] ∩ [x k ] = ∅. Let nR k be the number of roads included in R k . d) State update: [x i k ] = [x k ] ∩ [r i ], i = 1, . . . , nR k . e) Construct a mass function m R k 2 using (15) and (16) onR k . Set m R k = m R k Set R k+1 = R k and m R k+1 For i = 1 : nR k 4) Prediction: • Input boxes: [δ S,k ] = [δ S,k -3 • σs, δ S,k -3 • σs] and [δ θ,k ] = [δ θ,k -3 • σ θ , δ θ,k -3 • σ θ ] • Calculate [x i k+1 ] using [δ S,k ], [δ θ,k ] and(11) 5) GPS correction: a) Using the GPS data, build a measurement box: [z k+1 ] = ([x k+1,GP S ], [y k+1,GP S ]) , [x k+1,GP S ] = [x k+1,GP S -3•σx, x k+1,GP S +3•σx] and [y k+1,GP S ] = [y k+1,GP S -3 • σy, y k+1,GP S + 3 • σy]b) The innovation is given by:[I i ] = [x i k+1 ] ∩ [z k+1 ] c) IF [I i ] is not empty then • Contract [x i k+1 ] using [I i ]and by applying the Waltz algorithm according to system (11) d) ELSE [x i k+1 ] is eliminated 6) GIS correction: a) Update R k+1 and m R k+1 1

- 1 ∩ m R k+1 2 9)

 12 includes all roads linked to r i in R k If this solution is not adequate, then an initialization step is needed• ENDIF b) Construct a mass function m R k+1 2on R k+1 using[START_REF] Dubois | A set-theoretic view of belief functions: logical operations and approximations by fuzzy sets[END_REF] and (16)7) ENDFOR i 8) Compute m R k+1 = mR k+1 Overall estimation: a) Select the road with the highest pignistic probability computed from m R k+1 b) The state box is the smallest box enclosing all boxes associated to the best road c) The state estimate is the center of the state box 10) k = k + 1. Go to 2 until k = k end

  TableIII(results with the GPS alone are also included for comparison). As can be seen, the advanced method developed by El Najjar and Bonnifait outperforms the simple geometric method developed by Quddus et al., and the BMM algorithm brings further improvement. We remark that the latter two methods use the theory of belief functions to combine the road selection criteria. The main difference between the two methods resides in the fact that El Najjar and Bonnifait use a Bayesian approach for state estimation, whereas the BMM method uses a bounded error approach for both state

TABLE III MEAN

 III SQUARED ERRORS ON x AND y FOR THE GPS, THE TWO REFERENCE METHODS AND THE BMM ALGORITHM.

		GPS	[36]	[17]	BMM
	MSE on x(m 2 )	25.3	14.1	12.0	10.7
	MSE on y(m 2 )	27.8	17.6	14.6	12.3
	one step running time (ms)	-	81	93	98
	estimation and road representation. Table III also gives the mean
	of the execution time of one step for each algorithm using a 3GHz
	Pentium 4 and a Matlab implementation. It is clear that the BMM
	method satisfies real time constraints despite the use of interval
	arithmetic programs under Matlab and without code optimization. We
	note that the other methods have a small advantage over the BMM
	method inasmuch as the BMM method handles the case of multiple-
	hypothesis and also in general takes into account more attributes of
	the map database.

TABLE IV COMPARISON

 IV OF BMM, QUDDUS METHOD AND REFERENCE METHODS

		[36]	[17]	BMM
	Correct link Identification (%)	89.2	96.8	99.2