Evidential based approach for trajectory planning with tentacles, for autonomous vehicles Hafida Mouhagir 1,2 , Reine Talj 1 , Véronique Cherfaoui 1 , François Aioun 2 , Franck Guillemard 2 Abstract-Driving is a combination of continuous mental risk assessment, sensory awareness, and judgment, all adapting to extremely variable surrounding conditions. Several research projects are working on autonomous vehicle to robotize this complex task. The work presented in this paper focuses on reactive local trajectory planning in uncertain environment.

The environment uncertainty is one of the challenges that we face in trajectory planning. For autonomous vehicle, to be efficient, they need to be able to deal with this kind of uncertainty. In this work, we show that the theory of belief functions with its ability to distinguish between different types of uncertainty is able to provide significant advantages in the context of trajectory planning.

Using the belief functions, we build evidential grid that represents the surrounding environment. To plan a local trajectory, we generate a set of clothoid tentacles in the egocentred reference frame related to the ego-vehicle. Those tentacles represent possible trajectories that consider the current dynamical state of the vehicle and make a smooth variation in the vehicle dynamic variables. Once the representation of the environment and the possible trajectories are generated, an evaluation of each trajectory is carried out according to several criteria and the choice of the trajectory is made using the decision formalism of Markov Decision Process.

To demonstrate the effectiveness of our evidential approach, we apply it to scenarios where ego-vehicle has to make decision in uncertain dynamical environments, using a driving simulator (SCANeR™Studio).

I. INTRODUCTION

Autonomous vehicles (AVs) development is currently at the heart of academic and industrial research [START_REF] Montemerlo | Junior : The Stanford Entry in the Urban Challenge[END_REF], [START_REF] Bengler | Three decades of driver assistance systems: Review and future perspectives[END_REF] because of many potential benefits: reducing traffic accidents, congestion, parking problems and pollution emissions. However, autonomous vehicle technology also presents new challenges. One important problem is how to plan a safe trajectory for a vehicle, given uncertain knowledge about the surrounding environment.

The main purpose of local trajectory planning is to provide the vehicle with a safe and collision-free trajectory, while taking into account vehicle dynamics, the presence of static and dynamic obstacles, and traffic rules.

Planning approaches for autonomous on-road driving have been inventoried and summarized in the survey [START_REF] Katrakazas | Real-time motion planning methods for autonomous on-road driving: State-ofthe-art and future research directions[END_REF]. There are two main categories of trajectory planning: incremental approaches and local approaches.

Incremental approaches aim to find a complete path from the initial position to the final position based on the most possibly complete representation of the environment. Two techniques are primarily used: Rapidly-exploring Random Trees (RRTs) [START_REF] Lavalle | Rapidly-exploring random trees: A new tool for path planning[END_REF], [START_REF] Kuwata | Real-time motion planning with applications to autonomous urban driving[END_REF] and Lattice Planners (LP) [START_REF] Kavraki | Probabilistic roadmaps for path planning in high-dimensional configuration spaces[END_REF]. These approaches provide trajectories that match the dynamic and kinematic constraints of the vehicle. But these trajectories are discontinuous and not smooth, with a relatively long planning horizon, so a significant calculation time.

On the other hand, local approaches search for a local trajectory to follow for a computation step. This feature has a great advantage because it allows the vehicle to navigate in a dynamic and uncertain environment. Local approaches are also divided into two categories: Geometric Curve Optimization and Model Predictive Control (MPC).

The first approach is based on a geometric curve optimization, in wich a single trajectory optimization is performed [START_REF] Delsart | Real-time trajectory generation for car-like vehicles navigating dynamic environments[END_REF] or several lateral shifts of a curve (e.g. splines, Bezier curves, clothoids, polynomials...) are evaluated [START_REF] Montemerlo | Junior : The Stanford Entry in the Urban Challenge[END_REF].

The Model Predictive Control approach combines aspects of control engineering within the planning module [START_REF] Ferguson | Motion planning in urban environments[END_REF] [START_REF] Madas | On path planning methods for automotive collision avoidance[END_REF]. Within MPC, a dynamic model for the vehicle is used and with the controller inputs the optimization problem of finding the best trajectory is solved. With this technique, the more variables used to model the vehicle the more harder it gets to find a real-time trajectory.

In our work, we used the clothoid tentacle approach [START_REF] Montemerlo | Junior : The Stanford Entry in the Urban Challenge[END_REF], [START_REF] Chebly | A local trajectory planning and tracking for autonomous vehicle navigation using clothoid tentacles method[END_REF]. The main advantage of this method is combining the search space and taking into consideration the vehicle dynamics limits while being a fast reactive method. A set of clothoid tentacles is generated in the egocentered reference frame related to the vehicle. Generated tentacles in a egocentered grid represent smooth and feasible trajectories by the vehicle. Choosing the best tentacle to execute is based on a Markov Decision Process evaluating several criteria. One of the criteria that interests us in this paper is the occupation criterion evaluated through evidential grids (representation of the vehicle surrounding environment).

Autonomous vehicles interact with their environment through sensors and actuators. The goal is to choose the "right" action according to their internal state and the perception of the surrounding environment. In general, the physical limitations and computing resources make the environment only partially known by the ego-vehicle. As a result, a vehicle operating in a real environment faces many sources of uncertainty: the time course of driving situations can not be predicted without uncertainty because other road users behave in an unpredictable way and their goals and plans can not be measured. More importantly, the ego-vehicle can only perceive part of the current situation with its sensors, because the measurements are noisy and part of the environment is occulted.

Partially Observable Markov Decision Process (POMDP) [START_REF] Cassandra | Learning policies for partially observable environments: Scaling up[END_REF] is a framework used to solve the environment unpredictability as well as the uncertainty of the perception and other road users behavior. In [START_REF] Brechtel | Probabilistic decisionmaking under uncertainty for autonomous driving using continuous POMDPs[END_REF], the authors use continuous POMDP in decision making to address both problems of noisy sensor measurements and the environment occlusion in intersection scenarios. This method is promising but remains very expensive in computing time.

In our study, we take into account the uncertainties of the environment through the use of the evidential occupancy grids.

The occupancy grids are used to model the environment. The ego-vehicle's surrounding environment is discretized into grid cells where each cell has a probability of being occupied. There are a variety of successful probabilistic algorithms based on occupancy grid maps for path planning [START_REF] Sabe | Obstacle avoidance and path planning for humanoid robots using stereo vision[END_REF], [START_REF] Meyer | Map-based navigation in mobile robots: Ii. a review of map-learning and path-planning strategies[END_REF], and exploration [START_REF] Thrun | Learning occupancy grid maps with forward sensor models[END_REF].

One of the limitations of probabilistic occupation grids is the impossibility of distinguishing the various types of uncertainty [START_REF] Reineking | Dimensions of uncertainty in evidential grid maps[END_REF]. The belief functions [START_REF] Shafer | A mathematical theory of evidence[END_REF], [START_REF] Smets | The transferable belief model[END_REF] provide a powerful alternative to classical probability theory because the mass of belief can not only be assigned to an occupied cellO or freeF, but also to the subset of the two states{O, F} as well as to the empty set ∅, thus providing the robot (egovehicle) with additional information on the environment. The mass assigned to {O, F} explicitly expresses ignorance (the robot has not observed the cell) whereas the mass attributed to ∅ represents contradictory evidence, indicating contradictory measures were obtained.

Using a probabilistic grid, the uniform distribution of probabilities P (O) = P (F ) = 0.5 could correspond to ignorance or conflict, even if the reaction of the robot could be different. For example, in the case of high ignorance, the robot must move to the corresponding zone during the exploration in order to obtain measurements of the cell. On the other hand, a high degree of conflict indicates that the area is potentially dangerous because different states of occupation have been observed, and simply obtaining additional measures may not resolve the situation (for example, there may be unexpected dynamics in the environment as pedestrians moving around the robot).

The additional information provided by evidential grid maps have been used to solve problems in a number of works. Evidential occupancy grid maps were first proposed in [START_REF] Pagac | An evidential approach to map-building for autonomous vehicles[END_REF] for a robot using sonar sensors, but other sensors like radar [START_REF] Mullane | Evidential versus bayesian estimation for radar map building[END_REF] and laser scanners [START_REF] Yang | Evidential mapping for mobile robots with range sensors[END_REF] have also been used. Different combination rules have been investigated [START_REF] Moras | Grid occupancy estimation for environment perception based on belief functions and pcr6[END_REF], [START_REF] Li | A successful application of dsmt in sonar grid map building and comparison with dst-based approach[END_REF]. A typical application of evidential grid maps, for example, is assessing the quality of maps [START_REF] Carlson | Conflict metric as a measure of sensing quality[END_REF] and detecting moving objects [START_REF] Kurdej | Controlling remanence in evidential grids using geodata for dynamic scene perception[END_REF], [START_REF] Ike | Evidence based analysis of internal conflicts from inverse sensor models[END_REF].

In the context of trajectory planning under perception uncertainties, evidential grids were used [START_REF] Clemens | An evidential approach to slam, path planning, and active exploration[END_REF], [START_REF] Sermanet | Mapping and planning under uncertainty in mobile robots with longrange perception[END_REF], where the approach was designed and validated for robots with a very simple action configuration (moving from one cell to another). Our goal in this paper is to use the evidential grids for autonomous vehicles where the action space is more complicated (steering angle and/or deceleration or acceleration). The planning strategy used is the planning method with clothoid tentacles [START_REF] Himmelsbach | Autonomous off-road navigation for mucar-3, improving the tentacles approach: Integral structures for sensing and motion[END_REF] that considers the current dynamical state of the vehicle and makes a smooth variation in the vehicle dynamic variables. To choose the best trajectory to execute, we use reward system of a Markov Decision Process-like model to evaluate generated tentacles regarding several criteria considering uncertainty represented by the evidential grid.

Based on our previous results [START_REF] Mouhagir | A markov decision process-based approach for trajectory planning with clothoid tentacles[END_REF][31], this paper presents a trajectory planning method combining the clothoids and MDP techniques with the use of evidential grids to integrate perception uncertainty. Then, it proves the performances of the approach by a global validation, under the simulator SCANeR™Studio. These simulation tools allow to integrate the dynamics of vehicle in closed-loop with different developed modules. Moreover, we have been able to test more complicated and realistic scenarios in the presence of several vehicles.

The remainder of this paper is structured as follows. In Section II, we present the trajectory planning algorithm based on clothoid tentacles as well as the construction of the evidential grids for trajectory planning. In Section III, we explain how we do use MDP reward system with evidential grids. First results using real data and SCANeR™Studio simulator are discussed in Section IV followed by a conclusion of the paper including an outlook in Section V.

II. TRAJECTORY PLANNING STRATEGY

At a local on-road level, the trajectory planning goal is the computation of an obstacle free route while following a desired global reference trajectory defined on a global map. The generated trajectory must satisfy the vehicle's kinematic limits based on vehicle dynamics and constrained by the navigation comfort, respect lane boundaries and traffic rules, while avoiding, at the same time, static and dynamic obstacles.

Our trajectory planning strategy can be divided into three main steps (Fig. 1):

• Generating tentacles which will represent dynamically feasible trajectories. • Creating and updating occupancy grid with data coming from exteroceptive sensors. • Choosing of the best tentacle that the vehicle will execute.

A. Clothoid tentacles for trajectory planning

In this work, we use the clothoid tentacles method for local on-road trajectory planning. This method is based on generating a set of clothoids tentacles as possible trajectories on a egocentric occupancy grid around the vehicle [START_REF] Himmelsbach | Autonomous off-road navigation for mucar-3, improving the tentacles approach: Integral structures for sensing and motion[END_REF]. Clothoid is a curve whose curvature varies linearly with curvilinear abscissa, also known as an Euler spiral, Cornu spiral or linarc. Its expression is presented by (1):

ρ = 2 k 2 s ( 1
)
where ρ is the clothoid curvature, s is the curvilinear abscissa and k is a constant, representing the clothoid parameter.

The initial curvature ρ 0 of the tentacles is calculated from the current vehicle steering angle δ 0 .

ρ 0 = tan δ 0 L where L is the vehicle's wheelbase. For a fixed velocity, all the tentacles begin at the center of gravity of the vehicle and take the shape of clothoids (Fig. 2).

The last step for generating a set of tentacles is to specify the maximal curvature ρ max that the vehicle can execute at its current speed, without losing its stability:

ρ max = a max V 2 x ( 2
)
wherea max is the maximum lateral acceleration of the vehicle and V x is the current speed. Thereafter, we generate a set of clothoid tentacles with a curvature that varies from -ρ max to ρ max whiten a given distance from the origin of the tentacles. The length of tentacles increases with the increase of the velocity. We assume that all tentacles generated for a given velocity have the same length.

After tentacles generation, we classify them as navigable or not navigable using the information of the occupancy grid. Each tentacle is overlaid on the occupation grid and a support zone is defined around it. The support zone's width corresponds to Ego-vehicle width. Then, the occupancy of the cells of the support zone is evaluated. If a tentacle passes by an obstacle on a radius of L s = 1s * V x (with V x : the egovehicle velocity) in front of the Ego-vehicle, this tentacle will be classified as not navigable, otherwise it's navigable (Fig. 2).

In case no tentacle is navigable, we choose the clearest tentacle (with the largest distance from the obstacle wich is the curvilinear distance along the tentacle from the clothoid root to the intersection with the obstacle) to brake, and we reevaluate again the tentacles in the next iteration. This enables a safe navigation while decelerating.

The main advantage of the clothoid approach is taking into consideration the current dynamical state of the vehicle and making a smooth variation in the vehicle dynamic variables.

Figure 2: Clothoid tentacles generated on a egocentric occupancy grid (black space represents occupied space, and white space represents free space). Red tentacles are not navigable and the blue ones are navigable. Road edges are considered obstacles.

The selection of the best navigable tentacle to execute is based on several criteria:

-The occupation criterion to evaluate if the tentacle is free from obstacles using occupancy grid.

-The trajectory criterion to evaluate the distance between each tentacle and the reference trajectory.

-Traffic rules criterion: we take into consideration the respect of safety distance while overtaking.

In the following, we will explain how we build an occupancy grid used to evaluate the occupancy of the environment surrounding the vehicle.

B. Evidential occupancy grid

The occupancy grids are used as environment model. If the grid cells are filled with obstacle information in the form of evidence (mass or belief values for instance II-B), we call this kind of grids the "Evidential occupancy grids".

Evidential framework

The theory of belief functions, also known as Dempster-Shafer theory (DST), was proposed by Dempster [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF], and developed, among others, by Shafer [START_REF] Shafer | A mathematical theory of evidence[END_REF] and Smets [START_REF] Smets | Decision making in the tbm: the necessity of the pignistic transformation[END_REF]. This formalism gained its popularity thanks to various interesting properties. DST not only generalizes the probability theory, but the possibility theory as well.

Let w be an unknown quantity with possible values in a finite domain Ω, called the frame of discernment. A piece of evidence about w may be represented by a mass function m on Ω, defined as a function

2 Ω → [0, 1] , such that m(∅) = 0 and A⊆Ω m(A) = 1.
In the theory of Dempster-Shafer, a frame of discernment Ω is defined to model a specific problem. In the occupancy grid framework, the frame of discernment is defined as: Ω = {O, F }, referred as the states (occupied or free) of each cell. The power set is defined as

2 |Ω| = {∅, F, O, Ω}, with | Ω | is the cardinality of the set.
For quantitatively supporting the cell states, a mass function (also referred as Basic Belief Assignment BBA) is calculated and provides four beliefs

[m(F ) m(O) m(Ω) m(∅)] ,
where m(A) represents respectively the quantity of evidence that the space is F ree, Occupied, U nknown or Conf lict.

Evidential occupancy grids generation

In this section, we present the perception grids used in our approach. The construction of these grids is based on three kind of input data: 1) Data coming from a range sensor in order to be able to have information about the occupancy of the cells. 2) Road limits or lane information in order to distinguish between free navigable or not navigable space. 3) Absolute velocity of dynamic obstacles.

The first step consists on building the P erceptionGrid from different data sensors. For every sensor measurement, a Grid is built with sensor model that translates the sensor information into an ego-centered grid. The value of masses depends of the resolution of the grids and sensor performances. The different Grids are combined in an unique resulting P erceptionGrid (Fig. 5.a).

After P erceptionGrid processing, each cell has a mass function with four beliefs on the state of the cell

[m(F ) m(O) m(Ω) m(∅)]. Let consider a concrete case to il- lustrate these concepts,[m(F ) m(O) m(Ω) m(∅)]=[0 0.7 0.3 0] indicates an Occupied cell with 0.7 as a belief, the rest of the mass is in U nknown. [m(F ) m(O) m(Ω) m(∅)]=[0.6 0 0.4 0]
shows a belief of 0.6 in F ree state, the rest of mass being on U nknown.

TheP erceptionGrid gives us information about the occupation of the environment, this information helps us to plan a trajectory to avoid collisions. However, autonomous vehicles must be capable of avoiding collision, lane keeping and carrying out an overtaking maneuver while keeping safety distances. Therefore, we build a P lanGrid (planning grid) based on the P erceptionGrid by adding road limits and by expanding obstacles on the road to include safety distances.

The second step as mentioned above is using map information to add a simple mask to theP erceptionGrid in order to integrate the edges of the road by changing the BBA of their cells (Fig. 5.b).

The next section explains how we include safety distances.

C. Respect of safety distance

In Europe road regulation, road driving users should, under normal conditions, maintain a minimum distance from vehicles ahead, while following and after an overtaking manoeuver. This distance corresponds to the distance traveled during a time interval of two seconds (Fig. 3). To respect safety distances, we propose a longitudinal expansion of obstacles on the road in the occupancy grid.

In a first version of our algorithm [START_REF] Mouhagir | Integrating safety distances with trajectory planning by modifying the occupancy grid for autonomous vehicle navigation[END_REF], we expanded the obstacles by the distance travelled by it in two seconds taking into consideration its velocity. But this distance was too conservative therefore we adopted the formula of [START_REF] Althoff | Can automated road vehicles harmonize with traffic flow while guaranteeing a safe distance[END_REF] that takes into consideration the relative velocity between the two vehicles and the difference between human and machine reaction time:

S saf e (v p , v f , a max , δ) = 1 2a max (v 2 f -v 2 p ) + v f τ (3)
wherev f ,v p are respectively the velocity of the following and preceding vehicles, a max is a potential acceleration and τ is the reaction delay. The difference in reaction time between the human being (τ human = 2 s [START_REF] Mcgehee | Driver reaction time in crash avoidance research: Validation of a driving simulator study on a test track[END_REF]) and the machine (τ machine = 0.3 s [37]) will make it possible for the egovehicle to harmonize with traffic flow while guaranteeing a safe distance.

The expansion is made by adding circles (ϕ) with varying diameter which satisfies the following equation:

d i-f ront = d 0 -i d 0 -0.5 S saf e2 i = 1..S saf e2 (4)
with d 0 = 3m is the diameter of the circle representing the preceding vehicle (ϕ 1 ). S saf e1 (Fig. 4) represents the safety distance to keep before overtaking. S saf e2 (Fig. 4) is the second safety distance to keep between the two vehicles in the end of the overtaking maneuver. This longitudinal extending of the obstacle is done by changing the masses attributed to the front cells of an obstacle within a safety distance (Fig. 5. c). The spatial propagation modeling of an obstacle according to its velocity is inspired by the discounting operation method. Discounting in its basic form requires the decay factor α to be specified, and it is defined as follows:

α k m Cij (O) = (1-α k )•m Cij (O) + α k if C ij ∈ ϕ k (5) α k m Cij (B) = (1-α k )•m Cij (B) ∀B = O with m Cij (O)
being the mass about the Occupied state of the cell with the coordinate (i, j). The decay factor α decreases as follows:

α k = α -k α -0.02 S saf e2 k = 1..S saf e2 (6)
with α = 0.8. Figure 5 illustrates the different stages of the P lanGrid construction. The resulting P lanGrid provides a virtual occupation of the environment, for example the road edges are considered occupied even if they are free of obstacles in order to respect traffic rules.

III. MARKOV DECISION PROCESS BASED ON EVIDENTIAL GRIDS

A. Markov Decision Process

After classifying the tentacles, we evaluate the navigable tentacles using several criteria: the tentacle's occupation, its distance from the reference trajectory and the overtaking criterion. To model the problem of planning with all the criteria to be taken into consideration [START_REF] Mouhagir | A markov decision process-based approach for trajectory planning with clothoid tentacles[END_REF], we used a M arkov Decision P rocess (M DP) like model.

A M DP is a discrete-time state-transition system. The agent (Ego-vehicle) observes the state (environment around each tentacle) and performs an action (tentacle execution) accordingly. The system then makes a transition to the next state and the agent receives some reward.

It can be described formally with 5 components (S, A, T, R, γ):

• Sis the set of states, they are represented by circles around tentacles of diameter2m(Fig. 6), their diameter represents the width of the vehicle. Each tentacle is composed of n s states, and we generate n t tentacles • A(s) : S → A is the set of actions, each tentacle represents an action, so we dispose of n t actions • T : S × S × A → [0, 1]defines the transition probabilities from one state to another, we assume that we do not have a possible transition from one tentacle to another • R : S × A → R is the reward given to the agent depending on its current state and the action taken. We define a different reward for each state according to several criteria mentioned above • γ ∈ [0, 1) is the discount rate used to calculate the longterm attenuation

Reference trajectory criterion

The reference trajectory corresponds to the global path that the ego-vehicle must follow all the time. However, the Egovehicle can deviate from the reference trajectory to avoid obstacles or to carry out an overtaking but must return to it. We use the lateral distance (Fig. 7) between each tentacle and the reference trajectory to evaluate the tentacles regarding this criterion. Details are presented in [START_REF] Mouhagir | A markov decision process-based approach for trajectory planning with clothoid tentacles[END_REF]. The crash distance l c is the distance required to stop a vehicle with a velocity V x , with a maximum longitudinal deceleration a m = 1.5 m/s 2 which maintains the comfort of the passengers. It is calculated by:

l c = V 2 x 2a m (7)
For each tentacle, a set of measurements d i is calculated by taking both the lateral distance a i and relative tangent orientations α i between the tentacle and the reference trajectory. Each d i is calculated at a curvilinear distance, κ i l c from the vehicle position, on the tentacle

d i = a i + c α α i (8)
here,c α represents a scale between the linear distance and the tangent's angle. We combine all the distances as follows:

d = n i=1 λ i d i (9)
with λ i is weighting constants. All states of the same tentacle receive a reward R(s |trajectory ) according to the distance d: R(s |trajectory ) = R trajectory -d [START_REF] Chebly | A local trajectory planning and tracking for autonomous vehicle navigation using clothoid tentacles method[END_REF] with R trajectory = R t , a fixed constant reward corresponding to the maximum reward related to the proximity to the reference trajectory.

Overtaking criterion

A small additional reward R(overtaking) = R l is added to the tentacles of the left. This reward takes effect in case of total symmetry of tentacles (δ 0 = 0) when executing an overtaking manoeuver, which allows an overtaking by the left.

Occupancy criterion

Each tentacle is evaluated in regard of its occupation. Grid information is used to assign appropriate rewards.

A tentacle discretization is made by using circles (their diameter represent the width of the vehicle with a margin of security). This discretization helps us to judge the tentacle's occupancy and serves to have a support zone around the tentacle which will allow the Ego-vehicle to circulate in a secure manner. Rewards are given to each circle based on its occupancy.

Using the binary grid, the state (circle) is considered as occupied if more than f s (threshold) cells inside the state are occupied, otherwise it is considered as a free state. Then, an occupation reward is given

R(s |occupancy ) = R o < 0 if s is occupied R f > 0 if s is f ree (11)
During overtaking scenarios while using binary grids, the ego-vehicle had a conservative behavior due to the widening of obstacle, because this widening is considered as a real obstacle. To rectify this, we used evidential grids instead. Explanations on the calculation of the occupancy reward using evidential grids are given in the next section.

Then the total reward of a tentacle is:

R(tentacle) = ns k=0 γ k t R(s k|trajectory ) + ns k=0 γ k o R(s k|occupancy ) +R(overtaking) (12)
whereγ t , andγ o (Equ. 12) are discount factors that can be used to change the behavior of our approach, and that represent distance attenuation of each kind of reward. n s is the number of states per tentacle, s k is the state number k in the tentacle.

The planning algorithm has been evaluated using binary grids [START_REF] Mouhagir | A markov decision process-based approach for trajectory planning with clothoid tentacles[END_REF], [START_REF] Mouhagir | Integrating safety distances with trajectory planning by modifying the occupancy grid for autonomous vehicle navigation[END_REF]. We noted that the selected trajectories are conservative. Therefore, we propose to use evidential grids which contain more information that we can use during the decision-making process (selecting a tentacle).

With the use of the evidential grids in place of the binary grids, the trajectory criteria and overtaking criteria remain unchanged. On the other hand, the occupancy criterion through the occupation reward changes because we have more information about the cell occupation that we can exploit with the evidential grids.

B. Occupancy Reward definition based on evidential grid

We dispose of an evidential grid in which we draw states as circles around each tentacle. The overlaying of the states on the grid gives matrix storing cells, with belief mass values (Fig. 8). In order to define a reward regarding the occupancy of the state, we propose to process cells information using three different rules [START_REF] Mouhagir | Trajectory planning for autonomous vehicle in uncertain environment using evidential grid[END_REF], [START_REF] Mouhagir | Using evidential occupancy grid for vehicle trajectory planning under uncertainty with tentacles[END_REF]. We consider that each cell is a source of information about the occupancy of the state. All cells are defined in the same frame of discernment. For each rule, we attribute a different reward (Equations 11 to 13, where a 1 , a 2 , a 3 , a 4 are weighting parameters):

• Conjunctive rule: the first rule consists in combining all masses of the state matrix with conjunctive rule, the resulting mass function is

m ∩ () = ∩ n i=1 m celli () , cell i ∈ matrix Reward occupation-conj = a 1 m ∩ (F) + a 2 m ∩ (O) +a 3 m ∩ (Ω) + a 4 m ∩ ( / O) (13)
with m 1∩2 (A) = B∩C=A m 1 (B)m 2 (C) , ∀A ⊆ Ω is the resulting mass using conjunctive rule proposed by Smets [START_REF] Smets | The transferable belief model[END_REF]. This rule is used to combine several BBAs provided by reliable and distinct information sources. By applying this rule, we obtain a consensus between all sources of information. The mass assigned to the empty set m 1∩2 (∅) quantifies the degree of disagreement between the two combined sources.

• Dempster's rule: the second rule consists in combining all masses of the state matrix with Dempster's rule [START_REF] Shafer | A mathematical theory of evidence[END_REF], the resulting mass function is m () = ⊕ n i=1 m celli () , cell i ∈ matrix. The occupation reward is defined:

Reward occupation-demp = a 1 m ⊕ (F ) + a 2 m ⊕ (O) +a 3 m ⊕ (Ω) (14) with m 1⊕2 (A) = K m 1∩2 (A) , ∀A ⊆ Ω and m 1 ⊕ m 2 (∅) = 0 where K = (1 -m 1∩2 (∅)) -1 .
This rule is a normalized version of the conjunctive rule where the mass of the empty set must be reallocated over all focal elements when m 1∩2 (∅) = 0 using a normalization factor K.

• Cells number: with this rule, we count the number of occupied, f ree and uncertain cells of the state matrix by making a decision about their state. For that, we attribute the element A ∈ 2 Ω if m(A) > 0.5.

Reward occupation-cellN umb = a 1 N b(F ) + a 2 N b(O) +a 3 N b(Ω) (15)
In the next section, we present some results with a study of the different parameters a 1 , a 2 , a 3 , a 4 .

IV. RESULTS

A. System set-up and real example

There are three inputs in our perception system: vehicle pose, exteroceptive acquisition data and a map. First, a globally referenced pose is needed to localize the vehicle in the environment in terms of position and orientation compared with reference trajectory. The pose can typically be provided by a GPS system hybridized with an inertial measurement unit. Secondly, we use a Lidar as a perception sensor. This sensor can distinguish between free, occupied or uncertain space and to model it in 2D (x, y coordinates) with respect to the vehicle body frame. We assume that we have the velocity of obstacles using Radar or car-to-car communication. In the validation tests, we used two vehicles: one with the Lidar sensor and the second one served as an obstacle to overtake with the velocity information. Finally, the map data provides information about the road surface.

The Lidar data was acquired at 10 Hz frequency. The egomotion between two acquisitions is estimated using CAN data. For the purpose of demonstration, the scan grids of (20 * 40m 2 ) are built with uniform cells of size (0.1 * 0.1m 2 ). We used the evidential grids generated by a C++ code [START_REF] Moras | Moving objects detection by conflict analysis in evidential grids[END_REF] with data acquired on the experimental platform PACPUS [START_REF] Ph | System architecture of a driverless electric car in the grand cooperative driving challenge[END_REF].

The values of the other parameters of our algorithm are given in the following table:

c α κ 1 κ 2 κ 3 λ 1 λ 2 λ 3 R t R l 0.7

B. Choice of occupancy reward parameters and evaluation

One typical scene is chosen to compare the different combination approaches. The resulting P lanGrid is shown in Figure 9. The ego-vehicle velocity was set at 20 m/s, and the preceding vehicle's velocity was 14 m/s.

The values of the parameters of the combination rules were determined empirically. During our tests, we collected perception data as evidential grids. These grids have been processed with M atlab as an input to our planning algorithm. We tested the different rules of combination in an overtaking situation using theP lanGrid of Figure 9. The criterion used to compare them is the safety distance at the end of the overtaking maneuver and the calculation time.

And in order to compare with the binary grids, we transform the P erceptionGrid (Fig. 9-c The result shows that the use of evidential grid enables us to process information about the unknown differently from the occupied space. In Figure 10, we observe that the binary grid choice is more conservative than the evidential grid ones. However, the used combination rules require a significant computation time (Table. III) comparing to the cell-number rule and the binary grid approach. More we need to consider uncertainties on perception, more the computation time is increased. Hence, the choice of the rule will be a compromise between reducing computation time and improving the planning behavior. Note that the computation time could be reduced by modifying the grid resolution.

C. System set-up for simulation results

To test our trajectory planning algorithm, we performed co-simulations using SCANeR ™ studio, a vehicle simulator, and Matlab/Simulink. The diagram in Fig. 11 summarizes the overall architecture of co-simulation between SCANeR ™ studio and Matlab/Simulink. Using the SCANeR ™ studio sensors, the information necessary for the construction of the occupancy grid is collected as well as the data on the vehicle dynamics and the reference trajectory (center of the right lane). This information is then processed as input data of our planning algorithm, which sends after processing an acceleration or deceleration setpoint and a steering angle setpoint that the ego-vehicle must execute on the SCANeR ™ studio scenario.

SCANeR ™ studio Sensors

In order to build a representation of the environment surrounding the ego-vehicle through occupancy grids, we could use the simulator ground truth but this solution is not generic with our simulator. So, we opted for the use of the information provided by different sensors available on SCANeR ™ studio. And for time computational reasons, simplified models of these sensors have been used to create simplified evidential grids.

Indeed, a reconstruction of the environment requires the detection of the obstacles present and the determination of the navigable space as well as the information on the road. Figure 12 shows the sensor configuration adopted on SCANeR ™ studio. • Camera with horizontal field of view of 120°and vertical of 60°.

• LIDAR with a horizontal field of view of 360°with a pitch of 3°and a range of 80m.

Creating the binary grid

To create a binary occupancy grid, we use two types of sensors: the radar for the detection of obstacles and the camera for detecting the edges of the road in front of the ego-vehicle. All cells in the grid are initialized to zero (0) as a free state.

The radar provides the position of the obstacles as well as their type (car, pedestrian, truck) and velocity. Depending on the position and the category of the obstacle, we attribute value "1" to the occupied cells (for example, a car has a width 1.5m and a length of 4m). The rest of the cells are considered free (value "0"). The camera provides us with information about road edges in front of the ego-vehicle which we consider as an occupied space (cell filled by the value "1").

On a SCANeR ™ studio scenario and with a frequency of 10 Hz, our algorithm generates binary grids at each time step. Figure 13 shows an example of the resulting bit map and the corresponding scene.

Creating the evidential grid

The creation of an evidential occupancy grid [START_REF] Hadid | Creation of evidential grid for autonomous vehicles[END_REF] is based on the combination of three grids because each sensor provides information about a component of the environment. The camera provides information about the edges of the road while the radar provides on the position, type and velocity of obstacles and the Lidar provides information on free space.

The creation of an evidential occupancy grid steps are: 1. Creation of the road grid: from the road marking points coming from the camera sensor, we determine the borders of the road. This detection is done only in front of the egovehicle. The cells C ij of coordinates (i, j) belonging to the borders of the road have the following mass:

m 1 (C ij ) = [m 1 (∅) m 1 (F ) m 1 (O) m 1 (Ω)] = [0 0 0.6 0.4]
The rest of the cells have the following mass:

m 1 (C ij ) = [m 1 (∅) m 1 (F ) m 1 (O) m 1 (Ω)] = [0 0 0 1]
2. Creation of the Radar grid (obstacles): from the information on the obstacles detected by the Radar sensor, namely the classification, the position, the speed, the yaw angle, and the dimensions, the cells occupied are determined and a widening of obstacle is made. The occupied cells have the following mass:

m 2 (C ij ) = [m 2 (∅) m 2 (F ) m 2 (O) m 2 (Ω)] = [000.80.2]
The rest of the cells have the following mass:

m 2 (C ij ) = [m 2 (∅) m 2 (F ) m 2 (O) m 2 (Ω)] = [0 0 0 1]
3. Creation of the Lidar grid (free space): from the points of impact obtained with the Lidar sensor, we calculate the cells which constitute the free space around the egovehicle. The free cells have the following mass:

m 3 (C ij ) = [m 3 (∅) m 3 (F ) m 3 (O) m 3 (Ω)] = [0 0.75 0 0.25]
The rest of the cells have the following mass:

m 3 (C ij ) = [m 3 (∅) m 3 (F ) m 3 (O) m 3 (Ω)] = [0 0 0 1]
4. Combination of the grids: let C ij be a coordinate cell (i, j) of the final grid, the allocation of the masses is carried out according to this equation:

m(C ij ) =      m 1 (C ij ) if m 1 (O) > m 2 (O) m 2 (C ij ) if m 1 (O) < m 2 (O) m 3 (C ij ) if m 1 (O) = m 2 (O) = 0 (16)
The choice of the BBA values (initial masses) was made for the purpose of havingm(O)of cells occupied by obstacles greater thanm(O)of the cells occupied by the road edges. The cells corresponding to obstacles represent real occupied cells, however, the road borders don't represent a real occupation, but should be avoided to respect the road driving rules. m2 and m3 are generated from simulation of Radar and Lidar sensors, which give information about the occupation of the neighboring space [START_REF] Kurdej | Controlling remanence in evidential grids using geodata for dynamic scene perception[END_REF]. m1 are generated from the information of a map on the road borders [START_REF] Yu | Semantic evidential lane grids with prior maps for autonomous navigation[END_REF], which are zones to be avoided, but can be tolerated if necessary for emergency situations. Figure 14 shows an example of the three grids (Road, Radar, Lidar) and the final occupancy grid.

D. Simulation results

The tests presented below were carried out in order to test our planning algorithm taking into account the dynamics of the vehicle on different driving scenarios. The occupation grids are generated at a frequency of 10 Hz. At each computation step, the algorithm generates 41 tentacles and evaluates each tentacle using the three decision criteria:

-The occupation criterion: this criterion allows to evaluate if the tentacle is free from obstacles -The reference trajectory criterion: this criterion evaluates the proximity of each tentacle to the reference trajectory -The criterion of the traffic code: this criterion allows the overtaking by the left and the respect of the distance of security.

Regarding the control part of the steering angle and egovehicle speed, the planning algorithm sends the steering angle that corresponds to the chosen tentacle and an acceleration or deceleration setpoint that SCANeR ™ studio applies through a control block specific to the simulator.

Test scenario : In this scenario, we placed a static obstacle ahead the ego-vehicle (velocity of 25 m/s), and a dynamic obstacle with16.5 m/svelocity in the right lane (Fig. 15). The combination rule used in this scenario is the Cells number rule. The distance between the static and dynamic obstacles is chosen to include the safety distance with a safety margin that the ego-vehicle must respect during the folding maneuver. We consider that the reaction time of the red vehicle driver is τ human = 2 s, and a max = 10 m/s 2 . The safety distance to be respected is 15.5m. The ego-vehicle is programmed to circulate at a speed of 25m/s. In case no tentacle is navigable, the ego-vehicle will decelerate until it finds navigable tentacles and in this case it will accelerate until it regains its initial speed. Indeed, the proposed planning algorithm treats only the lateral trajectory, by considering the actual speed of the vehicle. The only modification of vehicle speed that the algorithm could propose, is to brake the vehicle when no navigable tentacle is detected. The speed is controlled in another module, to follow a given reference speed defined elsewhere. In our test scenarios, we implemented a basic speed controller and we defined a speed profile that respects stability conditions, to be able to test in closed-loop our planning algorithm.

Using binary grid in this scenario, the ego-vehicle decelerates and stops (Fig. 16). Due to the extending of dynamic obstacle, the ego-vehicle don't find any navigable tentacle to change lane to the right. Using evidential grids, the ego-vehicle manages to return to the reference trajectory but after a significant deceleration as shown in Figure 17. This deceleration is due to the mass values chosen for the road edges; we recall that with the rule of number of cells, a cell is considered occupied if m(O) > 0.5. So the tentacles that meet the edges of the road in a radius less than the safety distance are classified as not navigable.

We changed the mass on the road edges in the road grid:

m 1 (C ij ) = [m 1 (∅) m 1 (F ) m 1 (O) m 1 (Ω)] = [0 0 0.5 0.5] instead of m 1 (C ij ) = [0 0 0.6 0.4]
Given that both cases give the same result with binary grid, the interest of this comparison is to study the influence of introduction of semantic rules in occupancy grid (consider the off-road space as occupied). By changing the masses of m 1 from [0 0 0.6 0.4] to [0 0 0.5 0.5] , we reduce the occupation constraint of the road borders; instead of being occupied, it will be considered as uncertain space. The mass of [0 0 0.5 0.5] , allows to have more navigable tentacles, even those who attain the road borders. It should be noted that the choice of the best tentacle will take into account the mass on (uncertainty), to avoid the road borders if possible, and prioritize the lane.

In this case, the road edges are not considered occupied. Therefore, the planning algorithm did not classify the tentacles that reach the road edges within the security distance as not navigable tentacles, allowing the ego-vehicle to overtake the dynamic obstacle while avoiding the static obstacle.

Figure 18 shows the longitudinal speed and the lateral acceleration of the ego-vehicle. Note that the safety distance has been respected all along the overtaking maneuvers given that the safety distance is already integrated in the tentacle planning approach.

We can notice that the vehicle trajectory when m1 = [0 0 0.6 0.4] is closer to the boundary of the road compared to the case when m1 = [0 0 0.5 0.5] . What should be noticed in the comparison between both tests is the longitudinal speed. We see in Figure 17.a that the vehicle decelerates from 25 m/s to 5 m/s, when the mass m1 = [0 0 0.6 0.4] . That means that no navigable tentacle was found, that's why after overtaking, the vehicle overlaps laterally at a speed of 5 m/s. Despite the proximity to the border, the trajectory was safe because of the reduced speed. However, in the second case, with m1 = [0 0 0.5 0.5] , the vehicle speed in Figure 18.a still approximately unchanged, what means that the planning algorithm arrives to identify navigable tentacle, almost on all the overtaking maneuver, due to the reduced constraint on the road border. Then, the vehicle still far from the border, due to its highest speed (25 m/s). Note that the planning algorithm calculates only feasible safe trajectories with respect to the vehicle speed, at any time.

The proposed planning method does not depend on the vehicle dynamics; it only considers some limit constraints with respect to these dynamic aspects. Hence, less amount of online computation is needed, compared to other modelbased approaches like MPC. The proposed method is a reactive local trajectory planning method, suitable for the use of occupancy grid for environment representation. Note that the originality of the approach is to consider perception uncertainties through the use of evidential grids. The geometric form of the clothoids and the chosen MDP method used to select the best tentacle involve also relatively simple algorithms, suitable for real-time application.

However, some drawbacks could be mentioned, and will be addressed in future works. The Dempster and conjunctive rules, used to calculate the occupancy reward for the states using an evidential grid, need more computation time, compared to the cell-number rule and the binary grid approach. This issue will be checked in real-time tests. On the other hand, even that the form of clothoids is suitable for local maneuvers because it respects the dynamic constraints of the vehicle and the real form of roads on near horizon, however, the evaluation of the clothoid for middle and long distance is not so realistic. The vehicle should return parallel to the road direction for long horizons, instead of following the same chosen clothoid. This issue could be improved by coupling the clothoid method with a maneuver planner, an intermediate level between the local and the global planners.

V. CONCLUSION AND PERSPECTIVES

In this work, the goal is to integrate uncertainty of the environment in the planning trajectory using evidential grid. Therefore, the potential use of the evidential grids was tested in the planning of trajectories with different combination rules. Real data was used and processed with M atlab. The simulation results show good performance of our algorithm in avoiding obstacles under uncertainty. However, the used combination rules require a significant computation time which makes its use in real time challenging. Otherwise, we worked under the assumption that each cell is a source of partial information of the overall state. In order to avoid working under this assumption, one of the perspectives is to compute masses on events as "more thanncells are occupied" where n is a threshold to be determined.

Another perspective would be to use evidential grids with semantic lane information [START_REF] Yu | Semantic evidential lane grids with prior maps for autonomous navigation[END_REF]; Through the use of this kind of grid, we can have access to road edges and specially to traffic direction, which is important information that will allow the respect of traffic rules.

At this stage of our experiments we can already insist on the possibilities that the use of evidential grids allows for the planning of trajectories. We plan to continue the study with other scenarios and optimize the calculation time of the algorithm to test the other combination rules; and to test experimentally our approach on a robotized vehicle.

Figure 1 :

 1 Figure 1: Trajectory planning strategy ( V: the vehicle velocity,δ0: the current steering angle,ρ: the curvature setpoint andacc acceleration setpoint).

Figure 3 :

 3 Figure 3: Longitudinal safety distance before ( S saf e1 ) and after ( S saf e2 ) overtaking.

Figure 4 :

 4 Figure 4: Example of an obstacle widening

Figure 5 :

 5 Figure 5: The yellow triangle represents the Lidar position in the front of the vehicle. TheP lanGrid(b)representsP erceptionGrid(a)with the road's edges information. TheP lanGrid(c)presents a longitudinal obstacle widening.

Figure 6 :

 6 Figure 6: Modeling the problem of planning with tentacles using MDP. The red line represents the reference trajectory.

Figure 7 :

 7 Figure 7: The distance between the tentacle and the reference trajectory.

Figure 8 :

 8 Figure 8: The discretization of each tentacle in circles (states), and the result of the overlaying with the cells of aP lanGrid.

  II: Parameters of different combination rules.

Figure 9 :

 9 Figure 9:(a)represents a picture of the scene.(b)represents corresponding occupancy grid where Green represents Free space, Red represents Occupied space, black represents Unknown space and Blue represents Conflict cells. (c) represents the expansion of the mobile obstacle with road's edges adding.

  ) into a binary grid using pignistic transformation. A cell is considered to be occupied if betP (O) > betP (F ), and free otherwise; with betP (O) = m(O) + 1 2 m(Ω) and betP (F ) = m(F ) + 1 2 m(Ω).

Figure 10 :

 10 Figure 10: The chosen trajectory with three different combination rules. Cell-N rule: black, Conjunctive and Dempster rule: green. In yellow, the chosen trajectory with binary grid.

Figure 11 :

 11 Figure 11: Algorithm validation scheme under Scaner Studio and Simulink.

Figure 12 :

 12 Figure 12: Diagram of sensor configurations adopted on SCANeR ™ studio.

Figure 13 :

 13 Figure 13: Example of a binary grid and the corresponding scene. Black represents occupied space and white represents free space. The black box in the middle shows the position of the ego-vehicle on the binary grid.

Figure 14 :

 14 Figure 14: Example of the three occupancy grids from the different sensors as well as the final grid for a SCANeR ™ studio scene.

Figure 15 :

 15 Figure 15: Scenario with a dynamic obstacle ( 16.5 m/s) and a static obstacle. The ego-vehicle has an initial velocity of 25 m/s. The red curve represents the reference trajectory.

  a) Longitudinal velocity of the ego-vehicle b) The blue box and the blue curve represent respectively the position and the trajectory followed by the ego-vehicle.

Figure 16 :

 16 Figure 16: Results using binary grid.

  a) Longitudinal velocity of the ego-vehicle b) The blue curve represents the trajectory followed by the ego-vehicle c) The trajectory of the ego-vehicle over time

Figure 17 :

 17 Figure 17: Results using evidential grid with cells number rule, and m1(Cij ) = [0 0 0.6 0.4]

Figure 19 .

 19 Figure 19.a represents the trajectory followed by the egovehicle as well as the position of the other vehicles at the end of overtaking and Figure 19.b represents the ego-vehicle's lateral position over time.Note that the safety distance has been respected all along the overtaking maneuvers given that the safety distance is already integrated in the tentacle planning approach.We can notice that the vehicle trajectory when m1 = [0 0 0.6 0.4] is closer to the boundary of the road compared to the case when m1 = [0 0 0.5 0.5] . What should be noticed in the comparison between both tests is the longitudinal speed. We see in Figure17.a that the vehicle decelerates from 25 m/s to 5 m/s, when the mass m1 = [0 0 0.6 0.4] . That means that no navigable tentacle was found, that's why after overtaking, the vehicle overlaps laterally at a speed of 5 m/s. Despite the proximity to the border, the trajectory was safe because of the reduced speed. However, in the second case, with m1 = [0 0 0.5 0.5] , the vehicle speed in Figure18.a still approximately unchanged, what means that the planning algorithm arrives to identify navigable tentacle, almost on all the overtaking maneuver, due to the reduced constraint on the road border. Then, the vehicle still far from the border, due to its highest speed (25 m/s). Note that the planning algorithm calculates only feasible safe trajectories with respect to the vehicle speed, at any time.The proposed planning method does not depend on the vehicle dynamics; it only considers some limit constraints with respect to these dynamic aspects. Hence, less amount

  a) Longitudinal velocity of the ego-vehicle b) Lateral acceleration of the ego-vehicle

Figure 18 :

 18 Figure 18: Results using evidential grid with different value mass for road edges, and m1(Cij ) = [0 0 0.5 0.5]

  a) The blue curve represents the trajectory followed by the ego-vehicle b) The trajectory of the ego-vehicle over time

Figure 19 :

 19 Figure 19: Results using evidential grid, andm1(Cij ) = [0 0 0.5 0.5]

Table I :

 I Values of the planning algorithm parameters.

The authors are with[START_REF] Montemerlo | Junior : The Stanford Entry in the Urban Challenge[END_REF] Sorbonne universités, Université de Technologie de Compiègne (UTC), CNRS Heudiasyc UMR 7253, 2 PSA Groupe, Direction scientifique, Centre technique de Vélizy, France. Email: {hafida.mouhagir, reine.talj, veronique.cherfaoui}@hds.utc.fr, {françois.aioun, franck.guillemard}@mpsa.com

ACKNOWLEDGE

This work was carried out within the framework of the Equipex ROBOTEX (Reference ANR-10-EQPX-44-01), which was funded by the French Government, through the program "Investments for the future" managed by the National Agency for Research.

ABOUT THE AUTHORS

Franck Guillemard was born in France in 1968. He received the Ph.D. degree in control engineering from the University of Lille, Lille, France, in 1996. He is currently with the Scientific Department of PSA Peugeot Citroen, where he is in charge of advanced research concerning computing science, electronics, photonics, and control. He is also an expert in the field of modeling, design, and control of mechatronic systems for automotives.