Autonomous car decision making and trajectory
tracking based on genetic algorithms and fractional
potential fields

Jean-Baptiste Receveur, Stephane Victor, Pierre Melchior

► To cite this version:

Jean-Baptiste Receveur, Stephane Victor, Pierre Melchior. Autonomous car decision making and trajectory tracking based on genetic algorithms and fractional potential fields. Intelligent Service Robotics, 2020, 10.1007/s11370-020-00314-x. http://hal-02502384

HAL Id: hal-02502384

https://hal.science/hal-02502384v1

Submitted on 19 Jan 2026

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

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

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Autonomous car decision making and trajectory
tracking based on genetic algorithms and fractional
potential fields

Jean-Baptiste Receveur · Stéphane

Victor · Pierre Melchior

**Abstract** This article deals with the issue of trajectory optimization of au-
tonomous terrestrial vehicles on a specific range handled by the human driver.
The main contributions of this paper are a genetic algorithm-potential field
combined method for optimized trajectory planning, the definition of the
multi-criteria optimization problem by including a time variable, dynamical
vehicle constraints, obstacle motion for collision avoidance, and improvements
on the attractive and repulsive potential field definitions. The main interests of
the proposed method are its efficiency even in only arc-connected spaces with
holes, trajectory optimality thanks to the genetic algorithm that minimizes
multi-criteria optimization, reactivity thanks to the potential field through
the consideration for nature and motion of obstacles, its orientation towards
situations a human-driver would consider, and finally the inclusion of con-
straints to avoid danger and to take into account vehicle dynamics. The global
trajectory, optimized through genetic algorithm, is used as a reference in a
fractional potential field, which is a reactive local path planning method. The
repulsive potential field is made safer by adding fractional orders to the ob-
stacles, and the attractive potential field is improved by creating a dynamical
optimal target seen from a robust control point of view. This target replaces
the unique attractive potential field point and avoid its drawbacks such as lo-
cal minima. Autonomous car simulation results are given for a crossroad and
an overtaking scenarios.

**Keywords** Autonomous vehicles · Trajectory planning · Potential fields · Optimization · Genetic algorithms · Fractional potentials

<footnote>Jean-Baptiste Receveur, Stéphane Victor, and Pierre Melchior

Université de Bordeaux, CNRS, IMS UMR 5218, Bordeaux INP/ENSEIRB-MATMECA,
351 Cours de la Libération,
33405 Talence CEDEX, France

E-mail: firstname.lastname@ims-bordeaux.fr</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1: Vehicle control level schematics</figcaption></figure>

# 1 Introduction

## 1.1 General introduction

In the past few years, autonomous cars have become a major concern in the automotive world, and car manufacturers are racing to launch the first working full autonomous car on the market. While machines are a thousand times faster than humans in terms of action and reaction times, they still have less abilities to analyze complex situations, to distinguish an obstacle from another, and to accordingly decide. The perfect autonomous car would have the human decision and analysis abilities with the machine precision of execution. A major issue in this race is to get the vehicle to make decisions in a human way. In this article, the perception is considered done, and focus will be set on planning a trajectory.

Very good surveys about car dedicated methods are given by [9] and [33] and some recent methods are briefly described in paragraph 1.2. For a vehicle, trajectory planning means finding a timed path between two or more locations: it is the combined action of finding a spatial path along with its motion. The vehicle is called Ego-Vehicle (EGV) to distinguish it from other vehicles in the environment. Contributions in this article are related to several aspects of the trajectory planning, and each of these aspects will be compared to the literature.

First, the article presents a smart combination of a Genetic Algorithm (GA) method and a Potential Field (PF) method. PF method has been used in the IMS laboratory as a local path planning method in [20], and this method is transformed here into a global trajectory tracking method. Recent works about vehicles [10][32][5][6] based on the PF method, have focused on local aspects, as the immediate environment of the vehicle is preponderant in the decision making. Moreover, studies, such as [4][3][1] have used the GA as a planning method for UAVs: unfortunately, used alone, this method is not reactive. Finally, GA and PF methods have been combined but either for path-planning in a static environment [11], with few criteria so as to consider the non-holonomic constraints of a UAV path [26] or of a mobile robot [28], or to improve the GA method by initializing it with a PF path [15]. Interesting methods present
a virtual obstacle to modify the vehicle's trajectory [34] and the dynamical modification of weighting coefficients for the different forces in a PF [27]. But most of these methods do not consider the motion along the path, and its optimization. Here, the GA creates a dynamical optimal target in the PF instead of a unique final target, optimizing both the vehicle path and its motion in a dynamical environment.

Secondly, five criteria are jointly considered in the optimization, including fuel consumption. In eco-driving strategy [36][19], the energetic aspects have been treated, but only the motion along the path is considered and not the path itself. For cars, in a dynamical environment, the chosen motion will impact the choice of a path. Multi-criteria optimization for unmanned ground vehicles can be found in [35]. This article follows and completes the work of [29] on multi-criteria optimization, with specifications for the automobile context.

Finally, the attractive potential is improved by interpreting it as a controller, identifying the trajectory high-level tracking to a closed-loop system following a reference. The repulsive potential field is also improved by attributing a fractional order to each obstacle. These orders are calculated function of their vulnerability, which is introduced for the first time here. It means the dangerosity of the obstacles determines the order of differentiation of the potential, which enables the repulsion to be adapted to each obstacle. Moreover, the vehicle size is taken into account in the optimization and realistic road scenarios will be tested.

In a nutshell, the main contributions are the GA-PF combination, the definition of the optimization problem, and improvements on the attractive and repulsive PFs. The main interests of the proposed method are its efficiency even in only arc-connected spaces with holes, the use of multi-criteria optimization, its optimality and reactivity through the combination of GA and PF (through the consideration for nature and motion of obstacles), its orientation towards situations a human-driver would consider, and finally the inclusion of constraints to avoid danger.

The main purpose of this article is to provide a multi-criteria trajectory optimization by using a simple mass point model. With this simplified model, the GA can be fast enough to provide an optimized reference path such as described in the Strategic level of Figure 1. In future works, a more complex dynamical model could be handled to tackle the Control level. Some papers handling kinematics and dynamical model can be cited such as [3,31].

## 1.2 About planning method classification

When book [13] was written, the classification of planning methods was easier: on the one hand global (off-line) methods, where path and motions were most often generated and optimized separately, and mostly based on graph theories, and on the other hand local (on-line) methods, where the next best robot position was found without global optimization. The classification has grown more difficult since new methods have appeared, especially optimization methods.
<table><caption>Table 1: Trajectory planning methods sorted by characteristic distance</caption><thead><tr><th>Long range path planning</th><th>Middle range trajectory planning</th><th>Short range trajectory planning</th></tr></thead><tbody><tr><td>Mostly off-line (global) methods, <strong>advantages:</strong> optimizable, <strong>drawbacks:</strong> fixed obstacles (or foreseen motion), longer computation time.</td><td>Need for an hybrid method, handling both global passage points and local avoidance. Too long for method integrating vehicle equations, but short enough to use continuous curves and optimize speed.</td><td>Mostly on-line (local) methods, <strong>advantages:</strong> faster, reactive, adaptive to changing environment, consideration for the vehicle dynamics and constraints <strong>drawbacks:</strong> hard to optimize.</td></tr><tr><td><ul><li>Using a road-map approach, visibility graph, freeway, cell decomposition (Voronoï, [13])</li><li>Optimization algorithms: Dijkstra, A, A* [21], GA [14], Particle Swarm Optimization, ... [2]</li></ul></td><td><ul><li>Few hybrid methods, like the Deterministic Kinodynamic Planning [7]</li><li>Proposed GA-PF combined method</li></ul></td><td><ul><li>Using integration, continuous curve equations: Lagrangian based methods, mixed linear integer programming [32], receding horizon, dynamical programming, tentacles [5], splines, Béziers curves</li><li>Potential Fields based methods [12] [10]</li></ul></td></tr></tbody></table>

Effectively, if waypoints with coordinates are chosen as optimization variables, and linked using splines, Bézier's curves, Dubin's curves..., any optimization method can become a trajectory planning method. As all types of methods cannot be summarized here, a non-exhaustive summary will be given in Table 1 and some examples on Figure 2, focusing on the characteristic distances considered for a vehicle, which can be divided into main categories:

- the long range path (from several hundred meters to kilometers long) is mostly handled by the GNSS-receiver; it is globally optimized using an A\*-like (Dijkstra, A, A\*) algorithm, based on graphs theory, and consists of a series of passage points and segments; it corresponds to the guidance level;

- the short range motion (a few centimeters to ten meters) is constrained by the vehicle dynamics, and is often planned using Bézier's curves, splines, tentacles, vehicle dynamics integration; it corresponds to the control level;

- the middle range path represents the navigation level, and is a strategic intermediate category (see example below) handled by this path planner (from ten meters up to several hundred meters). For instance, this type of distance is involved in decisions like crossing crossroads before or after other vehicles, overtaking or waiting behind another vehicle, etc.

Figure 1 represents the three levels handled by a planner. The proposed planner lies between the strategic and tactic levels. More details and a more precise schematics are given in section 3.1.

A trajectory planning problem corresponding to the strategic level distance is developed in section 2. In section 3, two methods are developed in details to be used to respectively optimize (strategic) and control (tactic) the trajectory:
<figure><img src="image_3.png" /><figcaption>Fig. 2: (a) Cell decomposition, long range planning; (b) PF, short range planning; (c) Deterministic Kinodynamic Planning method, hybrid method</figcaption></figure>

GA and PF. Finally, in section 4, illustrating tests and results are given and
a conclusion is drawn in section 5.

## 2 Trajectory planning problem

In the following sections, the EGV evolves in a dynamical environment (see section 2.1), and the corresponding variables, criteria, and constraints are presented respectively in sections 2.2, 2.3 and 2.4.

### 2.1 Path planning environment

As presented in section 1.2, strategic level (or *middle range*) distances are considered which are typically between ten to several hundred meters. This choice makes sense for autonomous vehicles: one hundred meters is close to most sensitive sensor range in the car (infrared sensor range is about 120m). From the sensor information, and the road maps incorporated in the memory, the environment can be partially reconstructed on this distance so as to add anticipation in the optimization.

To illustrate strategy choices involving the considered distances, two scenarios are tested: one crossroad scenario where vehicles are crossing in two directions (see Figure 3 (a)) and a one-way car overtaking scenario (see Figure 3 (b)). In both scenarios, one graduation stands for one meter. In the second scenario, involved speeds are much smaller than real speeds, but so are the distances needed to overtake.

Starting Point (SP) and Final Point (FP) are represented in red. Street sides and cars are rectangular obstacles. Black areas are obstacles and gray (untouched) or red (touched) areas are "danger zones", or security zones around obstacles. Danger zones can be generated by adding the vehicle dimensions to the obstacle, which is often the case in the literature, or by fixing a threshold, representing the acceptable level of danger. An arrow denotes the obstacle motion direction.
<figure><img src="image_4.png" /><figcaption>Fig. 3: Test environments, SP is the starting point and the FP the final point, $V_1$ to $V_4$ are obstacle speeds.</figcaption></figure>

- In the 1st scenario as the EGV wants to cross straightforwardly, the path should be straight. The aspects to be tested here are its reactions to other vehicles, and the moment passes through.

- In the 2nd scenario, both the strategy and trajectory are tested. Effectively, the exit is close, and the EGV has to make a choice between waiting behind or overtaking. Whether it overtakes or not, the shape of the trajectory can be optimized.

In practice the detection of the environment is a very complicated problem, using data fusion from various sensors, cameras, and GNSS-receivers. But as it is a completely different field of research, the detection is assumed to be established.

## 2.2 Optimization variables

In the proposed hybrid method, the idea is to use as few optimization variables as possible, to shape a trajectory to be used as a target in the potential field (see section 3 for more details). $(x_0, y_0)$ and $(x_f, y_f)$ respectively are the *a priori* known position of the starting point and final point, and the initial time $t_0$ is always considered known (here it is equal to zero). The trajectory optimization method is therefore based on the optimization of optimal intermediate points. The number of intermediate points $n_{opt}$ is highly dependent on the environment and its choice is not discussed here. Intermediate optimal points are linked within the optimization through spline functions to make and evaluate “continuous” trajectories. These functions are composed of a higher number of points called interpolation points. In the following sections, the environment is assumed discretized, and the number of interpolation points $n_{interp}$ is chosen as $n_{interp} \ge 2\sqrt{(x_f - x_0)^2 + (y_f - y_0)^2}$. $x_l^{int}$ are the x-values
<figure><img src="image_5.png" /><figcaption>Fig. 4: Illustration of the different trajectory points.</figcaption></figure>

of the interpolation points, $y_l^{int}$ their y-values, and $t_f$ is the final time. $l$ is the index of the considered interpolation point (i.e. $l \in [1, n_{interp}]$).

To resume, the optimization variables are composed of intermediate point positions $(x_n, y_n)$ associated to their transit times $t_n$, with $n \in [1, n_{opt}]$, plus the final time $t_f$ which is also unknown.

The number of optimization variables is then:

$$n_{var} = 3n_{opt} + 1. \qquad (1)$$

Note that one additional intermediate point brings three more variables, which is significant for the optimization. The notations are illustrated in details on Figure 4.

## 2.3 Optimization criteria

Five criteria are to be met: a danger criterion, a trajectory length one, a time one, an energetic one, and a discomfort one. They have been introduced in [29], but further explanation is given here. The driver might have preferences, particularly concerning the importance of the comfort and energetic criteria: he may want the trajectory to be more comfortable than faster, or faster than shorter. In the following formulas, $b_1$ and $b_2$ are two vehicles coefficients, depending on the motor parameters, speed constant or maximum torque $T_{max}$, and on the wheel radius and transmission ratio (see [23]). $v$ and $a$ are its speed and acceleration norms, and $\sigma$ the corresponding jerk. All criteria are presented in details in [29], only their expression is reminded here.

- The *danger criterion* depends on the obstacles in the environment. Two options can be tested: the danger can be calculated either with the following formula

$$J_{danger} = \frac{1}{n_{interp}} \sum_{l} U_{tot}^{rep}(x_{l}^{int}, y_{l}^{int}),$$
where $U_{tot}^{rep}$ is the total repulsive potential field described in section 3.2, or can also be calculated in a binary way, zero if no obstacle is crossed, and a very high value if an obstacle is crossed. On the one hand, the danger is considered as a normal criterion and can be pondered, on the other hand, the criterion is an all or nothing criterion. In this study the first method was used so that a progressive continuous repulsion is provided by an obstacle: as the EGV reconstructs the environment around, every point of its environment has a potential value, which can be used as a good marker of the danger.

- The trajectory length criterion can be expressed as

$$J_{length} = \sum_{l} \sqrt{(x_{l+1}^{int} - x_{l}^{int})^2 + (y_{l+1}^{int} - y_{l}^{int})^2}.$$

It is a precise measurement of the trajectory length.

- The time criterion expression is

$$J_{time} = t_f - t_0.$$

The temporal length of the trajectory is a criterion by itself, as the quickest trajectory is often desired.

- The energetic criterion (or fuel cost criterion) comes from [23] and is expressed as

$$J_{energy} = \int_{0}^{t_f} b_1 u(t)v(t) + b_2 u(t)^2 dt,$$

where $u(t) = \frac{\tau(t)}{T_{max}}$ is the fraction of the maximum torque $T_{max}$ provided by the motor at time t, $\tau$ being the instantaneous torque. The relationship between the torque and the acceleration is unknown as there is no vehicle model here, however its percentage is coherent. As the trajectory is discrete, the acceleration is used instead of the torque and the formula should be discretized such as

$$J_{energy} = \sum_{l} (b_1 \tilde{a}_l v_l + b_2 \tilde{a}_l^2) dt_n,$$

where

$$dt_n = \frac{(n_{opt} + 1)(t_{n+1} - t_n)}{n_{interp}}, \\ \tilde{a} = \frac{a}{a_{max}},$$

and n is the index of the intermediate optimal points. It is necessary to divide by $n_{interp}$ so that the fuel cost becomes independent of the interpolation point number. This criterion is based on the work of [23], which considers the integration of the useful and dissipated power of an electric motor. A constant term could be added in the energetic criterion to model the loss due to road and aerodynamical resistance.
<figure><img src="image_6.png" /><figcaption>Fig. 5: Criteria dilemma</figcaption></figure>

– The discomfort criterion expression is:

$$ 
\begin{aligned}
J_{dcomfort} &= J_{long\ dcomf} + J_{lat\ dcomf} \\
&= \frac{1}{n_{interp}} \sum_{l} (\sigma_{l}^{long} + \sigma_{l}^{lat}).
\end{aligned}
$$

$\sigma^{long}$ is the longitudinal jerk, and $\sigma^{lat}$ the transversal (or lateral) jerk. The variation of the car acceleration felt by the passengers is responsible for the discomfort. Therefore $J_{dcomfort}$ is computed by adding all the jerk values of the trajectory. The jerk is often used as a representation of the smoothness of a trajectory [16]. [24] showed that minimum jerk trajectories are the smoothest ones.

Not all those criteria can reach an optimal value with the same trajectory. This will generate compromises to make, with unsolvable dilemma illustrated in Figure 5. An enhanced weight of the energy criterion could increase the trajectory time, but reduce its length or improve its comfort. Influences are multiple and coupled, and therefore the problem is a multi-criteria optimization problem.

Multi-criteria optimization theory is a large field of research, and the most common way to combine those criteria will be used: pondered aggregation. A weight coefficient $\alpha_{criterion}$ will be attributed to each criterion (see Table 7 in the appendix), and the global criterion will be the pondered sum of those criteria:

$$ J_{global} = \alpha_{danger}J_{danger} + \alpha_{length}J_{length} + \alpha_{time}J_{time} + \alpha_{energy}J_{energy} + \alpha_{dcomfort}J_{dcomfort}. \quad (2) $$

The weight coefficient choice is not trivial. Contradictions between the five criteria have been illustrated in Figure 5, but sets of values still need to be chosen depending on the passenger's preference. The idea is to use the GNSS-receiver usual modes, and to ask the passenger whether he prefers the *Shortest* trajectory, the *Fastest* one, the *Eco-friendliest* one, or the most *Comfortable*
<table><caption>Table 2: Weight coefficients for the criteria</caption><thead><tr><th>Mode</th><th>α<sub>danger</sub></th><th>α<sub>length</sub></th><th>α<sub>time</sub></th><th>α<sub>energy</sub></th><th>α<sub>dcomfort</sub></th></tr></thead><tbody><tr><td>Shortest</td><td>0.3</td><td>0.4</td><td>0.1</td><td>0.1</td><td>0.1</td></tr><tr><td>Fastest</td><td>0.3</td><td>0.1</td><td>0.4</td><td>0.1</td><td>0.1</td></tr><tr><td>Eco-friendliest</td><td>0.3</td><td>0.1</td><td>0.1</td><td>0.4</td><td>0.1</td></tr><tr><td>Comfortable</td><td>0.3</td><td>0.1</td><td>0.1</td><td>0.1</td><td>0.4</td></tr><tr><td>Balanced</td><td>0.3</td><td>0.175</td><td>0.175</td><td>0.175</td><td>0.175</td></tr></tbody></table>

one. A *Balanced* mode is added if the driver has no preference. The sum of the weight coefficients $α_{criterion}$ is supposed to be equal to 1, no coefficient can be equal to zero, and $α_{danger} ≥ 0.3$ because the trajectory has to be safe. From these conditions, the coefficients given in Table 2 have been found empirically, so as to stress one aspect of the trajectory or the other. It would be interesting to develop a computation method for these coefficients based on multi-objective optimization theory. These coefficients could be automatically computed considering the traffic, the weather, the tire pressures or age, depending on the configurations implemented by the car manufacturer.

In Figure 6, the influence of the weight coefficients is illustrated in the case of one simple round obstacle crossing the environment in the x-direction, at 2.2m/s. The EGV is considered speed-limited and cannot go over 50km/h. For the purpose of the demonstration, the acceleration has not been limited but can be limited as easily without loss of calculation time, as implicit constraints are used (see next section). In Figure 6, each trajectory is represented in the same color as the position of the obstacle when closest to the trajectory. The modules of the speed and acceleration are given, and therefore always positive. The different modes work as expected:

- the *Shortest* mode gives an almost straight trajectory (—), but is slow (45.6s) as the trajectory has to go behind the obstacle. The speed limit makes it too costly for the trajectory to go straight before the obstacle without crash;

- the *Fastest* mode gives a trajectory (—) that reaches the speed limit, and reaches the final point in 17.5s by moving ahead of the obstacle;

- the *Eco-friendliest* (...) and the most *Comfortable* (—) modes give very close results as the objective is almost the same: a very smooth trajectory, without too much acceleration or acceleration variations;

- the *Balanced* mode gives a more curved trajectory (—), so as to reach the goal faster than with the *Eco-friendliest* mode.

In Table 3, values for the different criteria are given. For every scenario, the corresponding criterion is minimum, except for the *Eco-friendliest* one, which confirms that the energy criterion and the discomfort criterion have a similar effect on the trajectory. In the *Balanced* mode, the length of the trajectory is important, which means that the difference in length considered here is not preponderant in the optimization.
<figure><img src="image_7.png" /><figcaption>Fig. 6: Illustration of the different modes</figcaption></figure>

All modes have to be implemented in the vehicle, each focusing on one particular aspect of the trajectory. Looking at Table 3, the *Balanced* mode presents a good compromise in terms of time and energy. The long distance in this scenario is mostly due to the movement of the obstacle, and would not be that poor in other situations. As all different criteria are equally pondered, for the following tests, the *Balanced* mode is used.
<table><caption>Table 3: Criteria values for the different modes</caption><thead><tr><th>Mode</th><th>J<sub>danger</sub></th><th>J<sub>length</sub></th><th>J<sub>time</sub></th><th>J<sub>energy</sub></th><th>J<sub>comfort</sub></th></tr></thead><tbody><tr><td>Shortest</td><td>0</td><td>171</td><td>45.6</td><td>3.55×<br>10<sup>3</sup></td><td>0.168</td></tr><tr><td>Fastest</td><td>0</td><td>173</td><td>17.5</td><td>2.59×<br>10<sup>4</sup></td><td>1.220</td></tr><tr><td>Eco-friendliest</td><td>0</td><td>183</td><td>36.8</td><td>2.60×<br>10<sup>3</sup></td><td>0.101</td></tr><tr><td>Most comfortable</td><td>0</td><td>180</td><td>38.4</td><td>2.46×<br>10<sup>3</sup></td><td>0.094</td></tr><tr><td>Balanced</td><td>0</td><td>192</td><td>28.4</td><td>8.24×<br>10<sup>3</sup></td><td>0.362</td></tr></tbody></table>

## 2.4 Optimization constraints

In this study, the EGV is represented by a two-dimensional point mass (M) model submitted to different forces. Therefore, it is a holonomic system. The trajectory optimization being done on the strategic level, it is computationally impossible to integrate complex vehicle model equations, which are nonlinear, even with a model as simple as a bicycle one. Therefore, spline functions enable computing the trajectory by including constraints such as maximum steering angles, and penalty functions such as maximum torque. In a first approach, some linear constraints are considered, to ensure the coherence of the trajectory:

$$ 
\begin{array}{l}
t_0 < \dots < t_k < \dots < t_f \\
0 < x, y < 120.
\end{array}
\qquad (3)
$$

Those constraints are called explicit constraints and are compulsory for the algorithm. Other constraints (called implicit constraints) were added in order to have more realistic trajectories. For example, the danger criterion expression has been modified such as:

$$ J_{\text{danger}} = \frac{1}{n_{\text{interp}}} \sum_{l} (U_{\text{tot}}^{\text{rep}}(x_{l}^{\text{int}}, y_{l}^{\text{int}}) + \text{pen}(v_{l}) + \text{pen}(a_{l}) + \text{pen}(\dot{\psi}_{l})), \quad (4) $$

where pen($v_l$), pen($a_l$), and pen($\dot{\psi}_l$) are penalty functions that depend on the maximum allowed speed $v_{max}$ (legal constraint) at a particular point of the trajectory, on the maximum available acceleration $a_{max}$ (mechanical constraint), and on the maximum yaw rate $\dot{\psi}_{max}$, depending on the maximum turning angle of the wheels and the speed. Thus, those constraints are not compulsory, but they imply a natural reduction of the speed and acceleration below the limits, depending on how strong the penalties are. Ideally, it would be necessary to have explicit saturation constraints, but in terms of computation time, this method is much more efficient. Moreover, these penalties enable the optimization to produce a realistic trajectory for the vehicle, even though a complex dynamical model is not considered.
<figure><img src="image_8.png" /><figcaption>Fig. 7: EGV control loop with attractive and repulsive PF acting as a controller and a perturbation</figcaption></figure>

Once the trajectory planning problem has been described, the method to solve it using both PF and GA is presented.

## 3 Combined “Genetic Algorithm-Potential Fields” (GA-PF) method

### 3.1 Control loop analogy

The objective of the presented method proposed in a control loop manner for the vehicle trajectory is shown in Figure 7. The reference is the GA trajectory, calculated offline, or more exactly it should be calculated periodically, this period depending on how quick the vehicle discovers new environments. The attractive PF has been re-interpreted as a controller, and the repulsive PF as a disturbance. The measured output position $(x^{mes}, y^{mes})$ are then to be provided to the real vehicle and to its internal control loops (see the *control level* shown in Figure 1).

### 3.2 Potential Fields

The PF method has been studied and improved in the CRONE team through several research works [22] [25] [18] [17] inspired from [8]. The concept of the PF method is to fill the robot workspace with potential fields in which the robot is attracted towards its target position and is repulsed away from obstacles [13]. This deterministic method is particularly seductive thanks to its elegant mathematical analysis and simplicity. While the GA only considers the position speed and acceleration of obstacles at $t_0$ for the optimization, the PF can handle the actual speed of obstacles in real-time, including unforeseen motions. Though, it presents some major drawbacks: local minima make the vehicle reach the wrong destination, like most local method, the trajectory is difficult to optimize, as it is fixed by the shape of the potential, and therefore the vehicle only reacts to its environment. To solve both issues, a new way
of managing the attractive potential is presented in the next sections. Many notions have been introduced in [29] and will not be described here.

Two types of potential fields are often separated: the repulsive potential field, representing the danger around obstacles, and the attractive potential, representing the need to reach the target. Both are visions of the same phenomenon: the considered system follows the slope of the gradient. In this study, the repulsive and attractive potentials are generated using two different approaches, described respectively in sections 3.2.1 and 3.2.2.

### 3.2.1 Repulsive Weyl potential field

The repulsive potential field $U_k^{rep}$ of the k-th obstacle is calculated using a potential field defined by [25] from Weyl's definition [37] of the fractional differentiation. Its expression is defined as a function of the distance $r = \|\vec{p}_k^{obst} - \vec{p}\|$ between the obstacle and the EGV:

- if $r \in [r_{min}, r_{max}]$:

$$U_k^{rep}(r) = \frac{r^{n_k-2} - r_{max}^{n_k-2}}{r_{min}^{n_k-2} - r_{max}^{n_k-2}}; \qquad (5)$$

- if $r \notin [r_{min}, r_{max}]$:

$$U_k^{rep}(r) = 0, \qquad (6)$$

where $r_{min}$ and $r_{max}$ are two chosen values, $r_{min}$ often being the obstacle radius, and $r_{max}$ the maximum obstacle influence radius. $n_k \in [0.1, 2[\cup]2, +\infty[$ denotes the order of the obstacle $k$, depending on the obstacle speed, nature, and vulnerability:

$$n_k = f(Vuln_k, \Delta v_k, v_k) \qquad (7)$$

where $Vuln_k$ is called the vulnerability of the obstacle, $\Delta v_k$ its speed variation potential, and $v_k$ its speed. Function $f$, to be determined, is increasing with all three parameters, and should have a maximum of 3 and a minimum of 0.1. The minimum is arbitrary, so as not to be zero. The maximum is 3 because the slope of the potential i.e. the repulsive force, should always increase when getting closer to the obstacle (see Figure 8 (a)). Vulnerability can be defined as:

$$Vuln_k = Vuln_k^{EGV} + Vuln_k^{obst} \qquad (8)$$

where $Vuln_k$ is chosen to be a number between 0 and 5 depending on $Vuln_k^{EGV}$, $Vuln_k^{obst} \in [0; 2.5]$. Those are, respectively, the vulnerability of the EGV towards the obstacle, and the vulnerability of the obstacle towards the EGV. Both are considered of equal importance in this study, which explains why their influence on the total vulnerability $Vuln_k$ is the same. More details on vulnerability can be found in [30].

For a road scenario, several types of obstacles are gathered in Table 4. From this table, where $v_k^{min}$ and $v_k^{max}$ are respectively the maximum and minimum speed of the obstacle, the potential speed variation is defined as $\Delta v_k = \max(|v_k - v_{min}|, |v_k - v_{max}|)$.
<table><caption>Table 4: Type of obstacles defined from relation (8)</caption><thead><tr><th>Type of obstacle</th><th>[v<sub>k</sub><sup>min</sup>, v<sub>k</sub><sup>max</sup>] (km/h)</th><th>Vuln<sub>k</sub></th></tr></thead><tbody><tr><td>Other motorized vehicle</td><td>[0; v<sub>lim</sub>]</td><td>4 = 2 + 2</td></tr><tr><td>Bike, Rollerblades, ...</td><td>[0; 30]</td><td>3 = 0.5 + 2.5</td></tr><tr><td>Pedestrian</td><td>[0; 10]</td><td>2.5 = 0 + 2.5</td></tr><tr><td>Road side, sidewalk</td><td>0</td><td>0.5 = 0.5 + 0</td></tr><tr><td>Road sign, post, wall</td><td>0</td><td>2 = 2 + 0</td></tr></tbody></table>

Then $f$ is shaped such as:

$$f(Vuln_k, \Delta v_k, v_k) = Vuln_k (A(v_k + \Delta v_k) + B) \quad (9)$$

where $A$ and $B$ are two coefficients to be determined from $f(0.5, 0, 0) = 0.1 \Rightarrow B = 0.2$ and $f(5, v_{lim}, v_{lim}) = 3 \Rightarrow A = \frac{1}{5v_{lim}}$, which means:

$$f(Vuln_k, \Delta v_k, v_k) = Vuln_k \left( \frac{1}{5v_{lim}} (v_k + \Delta v_k) + 0.2 \right). \quad (10)$$

This formula enables the EGV to calculate an order for every obstacle appearing in the environment, depending on their current speed and their type. The direction of the obstacle could also be considered, i.e. the relative speed between the EGV and the obstacle instead of the absolute speed.

The Weyl definition leads to potential values between 0 and 1. Considering the whole environment, and the Cartesian coordinates $x$ and $y$, the total repulsive potential field is:

$$U_{tot}^{rep}(x, y) = \max_k(U_k^{rep}(x, y)). \quad (11)$$

Figure 8 (b) presents an example of repulsive potential corresponding to a round obstacle of order 1, with a threshold of 0.2. From the potential, the corresponding force is calculated using the negative gradient of the potential [8]:

– if $r \in [r_{min}, r_{max}]$:

$$\begin{aligned} \vec{F}_k^{rep}(r) &= -F_k^0 \vec{\nabla} U_k^{rep} = -F_k^0 \left( \frac{\partial U}{\partial r} \vec{e}_r + \frac{\partial U}{r \partial \varphi} \vec{e}_\phi \right) \\ &= -F_k^0 \frac{\partial U}{\partial r} \vec{e}_r = - \frac{F_k^0 (n_k - 2) r^{n_k - 3}}{r^{n_k - 2} - r_{max}^{n_k - 2}} \end{aligned} \quad (12)$$

– if $r \notin [r_{min}, r_{max}]$:

$$\vec{F}_k^{rep}(r) = 0, \quad (13)$$
<figure><img src="image_9.png" /><figcaption>Fig. 8: (a) Repulsive fractional potential field shape, x-value 0 being the center of the obstacle, and $n = 1$ corresponding to the Coulomb potential; (b) Repulsive potential field in which the EGV moves, for a unique round obstacle of order 1</figcaption></figure>

where $F_k^0$ is a scaling factor, $r$ and $\phi$ respectively are the cylindrical coordinates and $\vec{e}_r$ and $\vec{e}_\phi$ are the corresponding unit vectors, with the obstacle as the center of the frame. As $U_k^{rep}$ does not depend on $\phi$, neither does $\vec{F}$. In a nutshell, three parameters are important for the repulsive force, $F_k^0$ enables the attractive and repulsive forces to get comparable magnitudes (even if they were differently generated), $r_{max}$ handles the radius of influence of all the obstacles, and $n_k$ the dangerousness of a particular obstacle, and the way the EGV should approach it.

### 3.2.2 Attractive potential field

The attractive potential $U^{att}$ is defined as a function of the relative position and velocity of the target with respect to the EGV. Accordingly, the virtual force is defined as the negative gradient of the potential in terms of both position and velocity rather than position only. Their expressions are:

$$U^{att}(\vec{p}, \vec{v}) = \alpha_p \|\vec{p}_{\text{target}} - \vec{p}\| + \alpha_v \|\vec{v}_{\text{target}} - \vec{v}\|, \quad (14)$$

where $\vec{p}$ and $\vec{v}$ are, respectively, the EGV position and speed, and $\vec{p}_{\text{target}}$ and $\vec{v}_{\text{target}}$ those of the target. $\alpha_p$ and $\alpha_v$ are weight coefficients. In [18], $\alpha_p$ and $\alpha_v$ have been interpreted as proportional derivative controller coefficients such as described in relation (20). The corresponding force is:

$$\vec{F}^{att}(\vec{p}, \vec{v}) = -\nabla_p U^{att}(\vec{p}, \vec{v}) - \nabla_v U^{att}(\vec{p}, \vec{v}), \quad (15)$$

where

$$\nabla_w U^{att}(\vec{p}, \vec{v}) = \frac{\partial U^{att}(\vec{p}, \vec{v})}{\partial \vec{w}}. \quad (16)$$
In this expression, $w$ can either be the position $p$ or the speed $v$. It gives:

$$ \vec{F}^{att}(\vec{p}, \vec{v}) = \alpha_p(\vec{p}_{target} - \vec{p}) + \alpha_v(\vec{v}_{target} - \vec{v}), \quad (17) $$

which is equivalent to

$$ F_z^{att} = Ma_z = \alpha_p \epsilon_z + \alpha_v \frac{d\epsilon_z}{dt} \quad (18) $$

if $\epsilon_z = z_{target} - z$ where $z$ can be $x$ or $y$.

If $\vec{d}_{target} = \vec{0}$, $s$ being the Laplace variable, this last equation can be re-interpreted as a controller:

$$ F_z^{att}(s) = (\alpha_p + \alpha_v s)E(s). \quad (19) $$

For causality reasons, this proportional derivative controller is transformed into a lead phase controller:

$$ F_z^{att}(s) = \frac{\alpha_p + \alpha_v s}{1 + \frac{s}{\omega_c}} E(s) = H(s)E(s), \quad (20) $$

where $\omega_c$ is the filter cut-off frequency to render this filter causal.

The PF (local) method does not require that the obstacle trajectories a priori are known. Instead, it only needs the online measurements of the obstacle information. Another advantage of this method is its reactivity when an unexpected event occurs, like an obstacle crossing the trajectory. Although this method enables immediate reaction to the environment, the whole trajectory cannot be optimized: the forces are calculated from the negative gradient of the danger, and the acceleration from Newton's second law. Finally acceleration is integrated to get speed and integrated again to get position, with no way to control the whole trajectory apart from the potential shape. Therefore a global planning method is needed to put the attractive target in an optimal way.

### 3.2.3 Attractive-Repulsive scaling

As the attractive and repulsive force are generated using two distinct definitions, they need to be put on the same scale in order to sum them up (see Figure 1). The attractive force is generated using a controller interpretation, and the repulsive force using the differentiation of a Weyl function. The repulsive potential field must, in any case, be superior to the attractive potential field, so that the EGV cannot run into an obstacle. Though, the attractive and repulsive forces are added, and must then be of comparable magnitude, which is a real challenge. Moreover, considering the target as a fixed point in $(T_x, T_y)$ $(T_x$ and $T_y$ being the dimensions of the field of view) and the EGV as starting at $(0, 0)$, the attractive force is maximal at $t = 0$ when the target
is the furthest from the obstacle. In this case, the target reference input is a step defined as $E(s) = \frac{120}{s}$, and:

$$ 
\begin{aligned}
\max(F^{att}) &= \lim_{t \to 0} F^{att}(t) = \lim_{s \to \infty} sF^{att}(s) \\
&= \lim_{s \to \infty} s\left(\frac{\alpha_p + \alpha_v s}{1 + \frac{s}{\omega_c}}\right)\frac{120}{s} = 120\alpha_v\omega_c.
\end{aligned} 
\quad (21) $$

On the other hand:

$$ \max(F^{rep}) = \frac{F_k^0(n_k - 2)r_{min}^{n_k - 3}}{r_{min}^{n_k - 2} - r_{max}^{n_k - 2}}. \quad (22) $$

Finally, $F_k^0$ is defined to ensure that $\max(F^{att}) \le \max(F^{rep})$, or by equalling relation (21) and (22), it then gives:

$$ F_k^0 = \frac{120\alpha_v\omega_c(r_{min}^{n_k-2} - r_{max}^{n_k-2})}{(n_k - 2)r_{min}^{n_k-3}}. \quad (23) $$

## 3.3 Genetic algorithm

A genetic algorithm solves optimization problems, based on the natural selection principle. It iteratively modifies a population of individuals which are potential solutions. At each iteration, the algorithm picks the best individuals in the population to be “parents” for the next generation. For complex optimization space, over two variables, classic deterministic algorithms can easily fall into local minima or get computationally too complicated. For instance, if the cost function is not continuous, nor differentiable, or with integer variables, deterministic methods might be utterly inefficient.

GA uses some specific terminology already defined in [29], along with the steps of the algorithm. Focus is therefore set on defining the role of the GA.

As was said in section 3.2, the EGV is attracted towards the target according to Newton's second law, under the influence of the attractive force. The EGV cannot move but within the potential field, which means that, to generate a trajectory close to an optimal one, the potential field needs to be optimal. The potential field cannot be optimal by itself when moving obstacles are present. Therefore, an optimal moving target reference needs to be determined, i.e. an optimal attractive point moving so as to permanently attract the EGV to where it should be. The genetic algorithm tests intermediate points (one set of intermediate points constitutes an individual, given in Table 5) and generates a spline trajectory between these points, represented by $(x^{int}, y^{int})$. The final result is an optimal trajectory represented by the variables $(x^{ref}, y^{ref})$.

Without consideration for the fitness function, the GA complexity is known to be $O(n_{pop}n_{gen}n_{var})$ where $n_{pop}$, $n_{gen}$, and $n_{var} = 3n_{opt} + 1$ are respectively the population size, the number of generation and the size of an individual. The fitness function itself has a complexity of $n_{interp}$, without recalculation of
<table><caption>Table 5: Chromosome structure for the trajectory point search. $n_{opt}$ is the number of intermediate points. $x_n$, $y_n$, $t_n$ respectively are the xy-coordinates and the transit time of the n-th intermediate point</caption><tr><td>x<sub>1</sub></td><td>y<sub>1</sub></td><td>t<sub>1</sub></td><td>...</td><td>x<sub>n<sub>opt</sub></sub></td><td>y<sub>n<sub>opt</sub></sub></td><td>t<sub>n<sub>opt</sub></sub></td><td>t<sub>f</sub></td></tr></table>

the PF, but would be of $n_{interp}T_xT_y$, if the whole PF had to be recalculated for every point of the trajectory, which represents a major issue.

The GA is better than any other planification method because its structure enables the optimization of both the positions and transit times of intermediate optimal points. In a nutshell, the GA brings optimality and anticipation, and its output trajectory is inserted in the PF for reactivity and flexibility. The combination of the two is efficient and promising.

### 3.4 Periodic recalculation of the optimal trajectory

The GA computes optimal target points in the vehicle environments. Until now, the environment boundaries were considered fixed, which is a legitimate assumption if the computation time of the algorithm is highly superior to the characteristic time of the computed trajectory. Considering the environment is a 120 m × 120 m square, the minimum trajectory length $L_{min}$ is:

$$L_{min} = 120 \times \sqrt{2} \approx 170 \text{ m.} \qquad (24)$$

An average sedan car moves from 0 to 100 km/h in 10 to 15 seconds, which leads to a maximum acceleration of $a_{max} \approx 2 \text{ m/s}^2$. Let us consider a vehicle going from the starting point to the target point in a straight line, never accelerating more than $a_{max}$, with an intermediate point in the middle, meaning that the speed maximum is in the middle too (all magnitudes are symmetrical). In this situation, the time needed to complete the trajectory is:

$$t_f \approx 20 \text{ s.} \qquad (25)$$

In the work of [25], the target point acts as a reference, the EGV follows this reference, and the whole system acts as a second order regulation. To avoid overshoots, the damping factor should be greater or equal to 1. According to the classic abacus of second order linear systems, for a time response of $tr_{5\%} \approx 20 \text{ s}$, and a damping factor of 1, the value of $\omega_0 \cdot tr_{5\%}$ is 5 and then the natural frequency is:

$$\omega_0 = \frac{\omega_0 tr_{5\%}}{tr_{5\%}} \approx \frac{5}{20} \approx 0.25 \text{ rad/s.} \qquad (26)$$

From that, the characteristic time $t_{car}$ of the system can be defined as:

$$t_{car} = 1/\omega_0 = 4 \text{ s.} \qquad (27)$$
Finally, the computation time $t_{comp}$ has to be very low compared to $t_{car}$. In a real situation, the vehicle will be moving forward and discovering new environment. Moreover, some obstacles might move in an unforeseen manner, and new obstacles might appear in the environment such as pedestrians, vehicles, animals. Those two events, namely new obstacles and new environment discovery, can make the trajectory suboptimal at best, and not feasible at worst, meaning that the optimal trajectory needs to be recalculated.

Two kinds of recalculation can be considered: periodic and triggered. In both, initial conditions will be the actual speed and position of the vehicle, and final conditions will be a new target point at the far end of its field of view.

- The periodic recalculation mainly addresses the first issue: as the vehicle is moving, it discovers new environments and needs to recalculate its trajectory to the new target point. The period of recalculation question has not been addressed yet, but the period should be as small as possible, as long as it is not shorter than $t_{comp}$.

- The triggered recalculation mainly addresses the second issue: unforeseen events might happen and trigger a recalculation of the optimal trajectory. Triggered recalculation should be a priority.

Unfortunately, the issue is not as simple. As the vehicle is moving forward, new environment is discovered, and so are new obstacles, which might trigger a recalculation. Both recalculations are linked, and a priority on the triggered recalculation might just mean that the periodic recalculation will never happen. This is why the genetic algorithm cannot be used alone as a control method. It is an optimization method, however the potential field completes it by handling unforeseen events. If, in a planned trajectory, an unforeseen obstacle crosses it, the potential field is able to handle it.

## 4 Simulation example and results

As was said in section 3, the GA is not meant to replace the potential field method and its advantages, it rather comes as an improvement of the existing method by adding an optimal dynamical target in the PF (see the control loop of Figure 7). Periodically, this optimal trajectory is recalculated (see section 3.4). Trajectories are generated for the two scenarios presented in section 2.1. In the following tests, two methods will be compared:

- method 1: Potential fields (PF) used alone as a control method, with a target directly set at the end of the potential field as an attractive point;

- method 2: Potential fields (GA-PF) with genetic algorithm optimization, following an optimal dynamical target along the polynomial reference trajectory.

It should be noted that the first method cannot be evaluated in terms of trajectory time as there is no time notion in the potential field alone. No
<figure><img src="image_10.png" /><figcaption>Fig. 9: Comparison between three trajectories of the EGV avoiding a squared obstacle, giving three different orders $n_1$ of the obstacle</figcaption></figure>

comparison will be done in terms of computation time as the potential field method is a real-time method. For both methods, the real-time trajectory will be compared with the theoretical GA optimal trajectory (thick blue). Note that this GA optimization trajectory cannot be used alone because it is generated periodically and not continuously, and it cannot adapt in real-time.

## 4.1 Impact of the obstacle order $n_k$

In section 3.2, an order for each obstacle was described. So as to illustrate the influence of this order, three trajectories have been generated for three different orders 1, 1.5 and 1.8, in the case of one squared obstacle in the middle of the environment. These trajectories are illustrated in Figure 9. For all the chosen values, the obstacle is avoided correctly. Though, as shown in the black ellipse, the higher $n_1$, the earlier the influence of the obstacle, i.e. the more secure for both the obstacle and the EGV.

For these tests, $F_0$ has been set to $10^5$, whereas the value given in (23) is close to $10^7$. If $F_0$ is set to the calculated value, the repulsive force is too strong and the vehicle is stopped very close from the starting point. This calibration was made so that the target is similar to a step reference, with the target being at 120 m from the EGV. On the contrary, in this simulation, the target is dynamical, and though much closer to the EGV, which makes the attractive force weaker. Though, the calibration is to be explored in further studies.

## 4.2 Scenario 1: crossroad scenario

With this crossroad scenario, two points are highlighted:
<figure><img src="image_11.png" /><figcaption>Fig. 10: Scenario 1: comparison between the classic PF method (a) and the GA-PF method (b); (c) impact of an unforeseen obstacle motion on the trajectory ($V_3$ accelerates); (d) position curves for the three trajectories; (e) speed curves for the three trajectories; (f) acceleration curves for the three trajectories</figcaption></figure>

- the interest of the GA-PF used as a global trajectory tracking method with a dynamical optimal target, compared to the local path planning PF method;

- the reactivity of the EGV when an obstacle moves in an unexpected way.

As the different vehicles are moving, a stop-motion like technique is used, by representing the trajectory on six different figures (see Figure 10).

In Figure 10, the red point is the target to follow, and the green point the center of the vehicle. On Figure 10 (a), the classic PF method is used. It can be seen that it is not fit for a road scenario, as it is local and obstacles are moving. Without anticipation, the EGV ends up in the middle of the crossroad, trying to reach the final goal, and bumping from one vehicle to another. On Figure 10 (e) the classic PF acceleration (in red) is clearly problematic for a real vehicle. On Figure 10 (b), the GA-PF trajectory is represented. If the obstacle motions are correctly anticipated, it is quite efficient in enabling the EGV to cross the crossroad the best way possible. In Figures 10 (a) and (b), all the vehicles keep their initial speed $V_1$, $V_2$ and $V_3$, but on Figure 10 (c), the
vehicle number 3 accelerates in an unexpected way, which leads the EGV to be unable to cross. Thanks to the PF, and to lateral saturations on the speed to keep it in the lane, it stops in time, even if the optimal target (red point) keeps going forward. The EGV waits for vehicle number 3 to cross. Therefore, the PF method is used as a backup reactive method in case an obstacle acts in an unexpected way. As the scenario does not go as expected (Vehicle 3 accelerates), the trajectory is not optimal in this case, which can be seen on Figure 10 (d) where the yellow speed differs from the optimal green speed from $t = 5$ s approximately. Fortunately, thanks to the PF reactivity, the trajectory is safe, which is the main point, and coherent.

In Figure 10 (f), it can be seen that sharp variations occur on the acceleration, due to the effect of obstacles in the potential field. In these simulations, these variations are very fast and thus, do not impact much the EGV position. Moreover, the measured position of the EGV model going out of the control loop shown in Figure 7 is provided to the real vehicle internal loops, according to Figure 1. If these acceleration variations are too sharp, they will be filtered by the actuators due to their high time constants. Nevertheless, the impact of these variations should be studied, so as to filter them, because actuators could be damaged.

## 4.3 Scenario 2: overtaking scenario

In this scenario, two elements are highlighted:

- the interest of the GA-PF used as a global trajectory tracking method with a dynamical optimal target, compared to the PF used as a local path planning method, in terms of strategy and trajectory, which was not really the case for the previous scenario as the path was straight;

- the differences in terms of strategy considering the speed of the vehicle in front.

In Figure 11 (a), it can be seen that the classic PF method is not fit for an overtaking scenario. Indeed, the EGV goes straight till the end, as the attractive force is too strong because of the distance between the target and the EGV. On Figures 11 (b) and (c), if the other vehicle motion is correctly anticipated, the GA-PF method is efficient by enabling the EGV to choose between overtaking (see Figure 11 (b)) or staying behind (see Figure 11 (c)) when the front vehicle moves faster. In any case, the PF method is still used as a backup reactive method in case an obstacle acts in an unexpected way. As can be seen on Figure 11 (a), the potential field method could still be improved as the attractive force provided by the target is too strong as compared to the repulsive force, consequently the EGV completely ignores the repulsion. With the GA-PF method, the weighting of the attractive and repulsive forces is easier to manage, as the distance between the target and the EGV can be adapted, in the case of an unexpected event. The target could be paying attention to the EGV, and awaits if being delayed by an unforeseen obstacle
<figure><img src="image_12.png" /><figcaption>Fig. 11: Scenario 2: comparison between the classic PF method (a) and the GA-PF method (b); (c) case where the EGV waits that the front vehicle passes before going out (the front vehicle moves faster); (d) position curves for the three trajectories; (e) speed curves for the three trajectories; (f) acceleration curves for the three trajectories</figcaption></figure>

motion. Moreover, as can be seen on Figures 11 (b) and (c), the trajectory could be even smoother, and take into consideration safety distance by using $r_{max}$.

Table 6 compares the two methods, the PF used alone and the PF combined with the GA, or GA-PF. The proposed GA-PF method works better compared to the PF used alone as the global trajectory stemming from GA is obtained after optimization. Moreover, if an unforeseen event occurs such as a speed variation of a mobile obstacle, the combined GA-PF handles this uncertainty. The proposed GA-PF method handles both global and local trajectory of the EGV contrary to purely global methods which cannot handle unforeseen events or local methods which are indeed completely reactive but not optimized (in terms of energy, length or time criteria). Consequently, a hybrid method such as our proposed algorithm is necessary to handle both global and local issues.

Just like Fig. 10 (f), the accelerations curves (see Fig. 11 (f)) has also acceleration variations due to the proximity of the obstacle. If these acceleration variations are too sharp, they will also be filtered by the actuators due to
<table><caption>Table 6: Qualitative comparison of the two methods.</caption><thead><tr><th></th><th>Potential Fields with final target (classic PF method)</th><th>Potential fields with dynamical optimal target (GA-PF method)</th></tr></thead><tbody><tr><td>Real-time method</td><td>yes</td><td>yes</td></tr><tr><td>Unforeseen obstacle avoidance</td><td>yes</td><td>yes</td></tr><tr><td>Mobile obstacle avoidance</td><td>yes</td><td>yes</td></tr><tr><td>Path Optimization</td><td>no</td><td>yes</td></tr><tr><td>Motion Optimization</td><td>no</td><td>yes</td></tr></tbody></table>

their high time constants. Nevertheless, the impact of these variations should be studied, so as to filter them, because actuators could be damaged.

## 5 Conclusion

In this article, a new method is proposed as a genetic algorithm-potential field combined method, which is designed to plan a strategy for a specific distance. In fact, a global optimal trajectory is obtained through multi-criteria optimization by including vehicle constraints and obstacle motion for collision avoidance, and local reactivity is carried out thanks to attractive and repulsive potential fields.

The main contributions are a new definition of the potentials: repulsive potential is defined according to the nature of the obstacles, and attractive potential is made smoother with the addition of a dynamical optimal target in the potential field. Anticipation is added in the trajectory planning, because the environment is always partially known thanks to the sensors and the embedded maps. Therefore, an optimal global path can be planned in advance so as to avoid pure reaction as it is the case in the potential field method used alone, and also to avoid deadlocks.

For this purpose, optimization multi-criteria are defined, and aggregated in a user-friendly way. In addition, test scenarios are created so as to explore different aspects of the method. Moreover, the genetic algorithm enables the joint optimization of the trajectory and the speed and acceleration curves by adding time variables in the optimization, which was not possible before as the speed was not considered. This is necessary in a dynamical environment.

The method is efficient in giving optimal and road-compatible trajectories, that respect constraints such as maximum accelerations and maximum speeds, and by providing much smoother path as compared to the classic PF trajectories. In further studies, the optimal trajectory needs to be periodically recalculated and the calculation time must be very inferior to the recalculation period. Plus, dynamical, non-holonomic vehicle model constraints need to be taken into consideration to ensure the trajectory is admissible for the EGV.
<table><caption>Table 7: Parameter values for simulations</caption><thead><tr><th>Parameter name</th><th>Parameter value</th></tr></thead><tbody><tr><td>V<sub>1</sub>, V<sub>2</sub>, V<sub>3</sub>, V<sub>4</sub></td><td>-2.2, 5, 1.5, 4 - 6 m/s</td></tr><tr><td>b<sub>1</sub>, b<sub>2</sub></td><td>1000</td></tr><tr><td>n<sub>interp</sub></td><td>200</td></tr><tr><td>M</td><td>750 kg</td></tr><tr><td>n<sub>k</sub></td><td>[1, 3]</td></tr><tr><td>α<sub>p</sub>, α<sub>v</sub></td><td>168750, 22500</td></tr><tr><td>T<sub>x</sub>, T<sub>y</sub></td><td>120 m</td></tr></tbody></table>

## Appendix

The genetic algorithm has to be parameterized, and the different parameters are summed up in Table 7 along with standard values. Speed values are small because of the scale considered for the figures, for visibility purpose, which does not change the result. Effectively, for higher speeds, the distance needed to overtake would be longer, and therefore the cars would be smaller on the figures.

## References

1. Ahmadi, S., Kebriaei, H., Moradi, H.: Constrained coverage path planning: evolutionary and classical approaches. Robotica 36(6), 904–924 (2018). DOI 10.1017/S0263574718000139

2. Besada-Portas, E., de la Torre, L., Moreno, A., Risco-Martín, J.: On the performance comparison of multi-objective evolutionary uav path planners. Information Sciences 238, 111 – 125 (2013). DOI 10.1016/j.ins.2013.02.022

3. Cáceres Flórez, C., Rosário, J., Amaya, D.: Control structure for a car-like robot using artificial neural networks and genetic algorithms. Neural Computing and Applications (2018). DOI 10.1007/s00521-018-3514-1

4. Capello, E., Guglieri, G., Quagliotti, F., Speciale, G.: Trajectory optimisation for autonomous vehicles: A miniUAV application. In: The 26th International Congress of the International Council of the Aeronautical Sciences. Anchorage, Alaska, USA (2008)

5. Chebly, A., Tagne, G., Talj, R., Charara, A.: Local trajectory planning and tracking of autonomous vehicles, using clothoid tentacles method. In: 2015 IEEE Intelligent Vehicles Symposium (IV), pp. 674–679 (2015). DOI 10.1109/IVS.2015.7225762

6. Chiang, H., Malone, N., Lesser, K., Oishi, M., Tapia, L.: Path-guided artificial potential fields with stochastic reachable sets for motion planning in highly dynamic environments. In: 2015 IEEE International Conference on Robotics and Automation (ICRA), pp. 2347–2354 (2015). DOI 10.1109/ICRA.2015.7139511

7. Gaillard, F., Soulignac, M., Dinont, C., Mathieu, P.: Deterministic kinodynamic planning with hardware demonstrations. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3519–3525 (2011). DOI 10.1109/IROS.2011.6094769

8. Ge, S., Cui, Y.: Dynamic motion planning for mobile robots using potential field method. Autonomous Robots 13(3), 207–222 (2002). DOI 10.1023/A:1020564024509

9. González, D., Pérez, J., Milanés, V., Nashashibi, F.: A review of motion planning techniques for automated vehicles. IEEE Transactions on Intelligent Transportation Systems 17(4), 1135–1145 (2016). DOI 10.1109/TITS.2015.2498841
10. Ji, J., Khajepour, A., Melek, W., Huang, Y.: Path planning and tracking for vehicle collision avoidance based on model predictive control with multiconstraints. IEEE Transactions on Vehicular Technology 66(2), 952–964 (2017). DOI 10.1109/TVT.2016.2555853

11. Jiang, Z., Zeng, Z.: Robot path planning based on a hybrid approach. In: D. Liu, S. Xie, Y. Li, D. Zhao, E. El-Alfy (eds.) Neural Information Processing, pp. 288–295. Springer International Publishing, Cham (2017). DOI 10.1007/978-3-319-70093-9_30

12. Khatib, O.: Real-time obstacle avoidance for manipulators and mobile robots. Int. J. Rob. Res. 5(1), 90–98 (1986). DOI 10.1177/027836498600500106

13. Latombe, J.C.: Robot motion planning, vol. 124. Springer Science & Business Media, New York, USA (2012)

14. Lei, L., Wang, H., Wu, Q.: Improved genetic algorithms based path planning of mobile robot under dynamic unknown environment. In: 2006 International Conference on Mechatronics and Automation, pp. 1728–1732 (2006). DOI 10.1109/ICMA.2006.257475

15. Lei, W., Ming, L.: Application of improved adaptive genetic algorithm in mobile robot path planning. Journal of Nanjing University of Science and Technology 5, 015 (2017)

16. Macfarlane, S., Croft, E.: Jerk-bounded manipulator trajectory planning: design for real-time applications. IEEE Transactions on Robotics and Automation 19(1), 42–52 (2003). DOI 10.1109/TRA.2002.807548

17. Melchior, P., Metoui, B., Najar, S., Abdelkrim, M., Oustaloup, A.: Robust path planning for mobile robot based on fractional attractive force. In: 2009 American Control Conference, pp. 1424–1429 (2009). DOI 10.1109/ACC.2009.5160599

18. Melchior, P., Metoui, B., Poty, A., Najar, S., Oustaloup, A., Abdelkrim, M.: Attractive force based on fractional potential in dynamic motion planning for mobile robot. In: International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, Volume 5: 6th International Conference on Multibody Systems, Nonlinear Dynamics, and Control, Parts A, B, and C, pp. 1423–1430 (2007). DOI 10.1115/DETC2007-35495

19. Mensing, F., Trigui, R., Bideaux, E.: Vehicle trajectory optimization for hybrid vehicles taking into account battery state-of-charge. In: 2012 IEEE Vehicle Power and Propulsion Conference, pp. 950–955 (2012). DOI 10.1109/VPPC.2012.6422774

20. Metoui, B., Melchior, P., Najar, S., Abdelkrim, M.N., Oustaloup, A.: Robust path planning for dynamic environment based on fractional attractive force. In: 2009 6th International Multi-Conference on Systems, Signals and Devices, pp. 1–8 (2009). DOI 10.1109/SSD.2009.4956793

21. Nilsson, N.J.: A mobius automation: An application of artificial intelligence techniques. In: Proceedings of the 1st International Joint Conference on Artificial Intelligence, IJCAI’69, pp. 509–520. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1969)

22. Oustaloup, A., Orsoni, B., Melchior, P., Linarès, H.: Path planning by fractional differentiation. Robotica 21(1), 59–69 (2003). DOI 10.1017/S0263574702004319

23. Petit, N., Sciarretta, A.: Optimal drive of electric vehicles using an inversion-based trajectory generation approach. In: 18th IFAC World Congress, pp. 14519–14526. Milan, Italy (2011). DOI 10.3182/20110828-6-IT-1002.01986

24. Pham, Q., Hicheur, H., Arechavaleta, G., Laumond, J., Berthoz, A.: The formation of trajectories during goal-oriented locomotion in humans. ii. a maximum smoothness model. European Journal of Neuroscience 26(8), 2391–2403 (2007). DOI 10.1111/j.1460-9568.2007.05835.x

25. Poty, A., Melchior, P., Oustaloup, A.: Dynamic path planning for mobile robots using fractional potential field. In: First International Symposium on Control, Communications and Signal Processing, 2004., pp. 557–561 (2004). DOI 10.1109/ISCCSP.2004.1296443

26. Qu, Y., Zhang, Y., Zhang, Y.: A global path planning algorithm for fixed-wing UAVs. Journal of Intelligent & Robotic Systems 91(3), 691–707 (2018). DOI 10.1007/s10846-017-0729-9

27. Raja, R., Dutta, A., Venkatesh, K.: New potential field method for rough terrain path planning using genetic algorithm for a 6-wheel rover. Robotics and Autonomous Systems 72, 295–306 (2015). DOI https://doi.org/10.1016/j.robot.2015.06.002
28. Rao, A.M., Ramji, K., Sundara Siva Rao, B.S.K., Vasu, V., Puneeth, C.: Navigation of non-holonomic mobile robot using neuro-fuzzy logic with integrated safe boundary algorithm. International Journal of Automation and Computing **14**(3), 285–294 (2017). DOI 10.1007/s11633-016-1042-y

29. Receveur, J., Victor, S., Melchior, P.: Multi-criteria trajectory optimization for autonomous vehicles. In: 20th IFAC World Congress (IFAC WC 2017), vol. 50, pp. 12520–12525. Toulouse, France (2017). DOI 10.1016/j.ifacol.2017.08.2063

30. Receveur, J., Victor, S., Melchior, P.: New interpretation of fractional potential fields for robust path planning. Fractional Calculus & applied analysis **22**(1), 113–127 (2019). DOI 10.1515/fca-2019-0007

31. Receveur, J.B., Victor, S., Melchior, P.: Robust longitudinal motion planning using vehicle model inversion. IFAC-PapersOnLine **52**(5), 103 – 108 (2019). DOI 10.1016/j.ifacol.2019.09.017. 9th IFAC Symposium on Advances in Automotive Control AAC 2019

32. Schouwenaars, T., De Moor, B., Feron, E., How, J.: Mixed integer programming for multi-vehicle path planning. In: 2001 European Control Conference (ECC), pp. 2603–2608 (2001). DOI 10.23919/ECC.2001.7076321

33. Schwarting, W., Alonso-Mora, J., Rus, D.: Planning and decision-making for autonomous vehicles. Annual Review of Control, Robotics, and Autonomous Systems **1**(1), 187–210 (2018). DOI 10.1146/annurev-control-060117-105157

34. Shehata, H., Schlattmann, J.: Potential field multi-objective optimization for robot path planning using genetic algorithm. In: K. Kozlowski, M. Tokhi, G. Virk (eds.) Mobile Service Robotics, pp. 149–158. World Scientific Publishing, (2014). DOI 10.1142/9789814623353_0018

35. Vilca, J., Adouane, L., Mezouar, Y.: Optimal multi-criteria waypoint selection for autonomous vehicle navigation in structured environment. Journal of Intelligent & Robotic Systems **82**(2), 301–324 (2016). DOI 10.1007/s10846-015-0223-1

36. Wang, T., Cassandras, C., Pourazarm, S.: Optimal motion control for energy-aware electric vehicles. Control Engineering Practice **38**, 37 – 45 (2015). DOI 10.1016/j.conengprac.2014.12.013

37. Weyl, H.: Bemerkungen zum Begriff des Differentialquotienten gebrochener Ordnung. Naturforsch. Ges. Zürich **62**, 296–302 (1917)