# Generation of Optimum Frenet Curves by Genetic Algorithms for AGVs

Eduardo Bayona, J. Enrique Sierra-Garc, Matilde Santos

► To cite this version:

Eduardo Bayona, J. Enrique Sierra-Garc, Matilde Santos. Generation of Optimum Frenet Curves by Genetic Algorithms for AGVs. 19th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI), Jun 2023, León, Spain. pp.454-464, 10.1007/978-3-031-34107-6_36 hal-05498082

HAL Id: hal-05498082

https://inria.hal.science/hal-05498082v1

Submitted on 6 Feb 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
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Generation of Optimum Frenet Curves by Genetic Algorithms for AGVs

Eduardo Bayona<fnref n="1" />,<fnref n="2" />✉, J. Enrique Sierra-Garc<fnref n="1" />✉, and Matilde Santos<fnref n="3" />✉

**Abstract.** This article presents a methodology for the generation of optimized trajectories for Automated Guided Vehicles (AGV) and its implementation. The proposed methodology includes the use of several software tools, such as AutoCAD for defining the occupancy map, MATLAB for mathematical calculations and generating the optimal trajectory, and Unity for visualization. The working process begins with defining the occupancy map using CAD software, selecting waypoints, and generating the optimal trajectory using a genetic algorithm based on the Frenet equations with an optimization parameter. Finally, the generated trajectory is visualized in Unity. The methodology ensures the optimization of the trajectory design process and provides a correct visualization of the results. The proposed approach can be useful in the implementation of AGVs in different fields, such as logistics and manufacturing.

**Keywords:** Soft computing · Automatic Guided Vehicle · Genetic Algorithms · Industry 4.0 · Trajectories

## 1 Introduction

The automation of production processes has led to the development of solutions that allow the internal transfer of raw materials, products, and merchandise. One of the most widely used solutions for automating internal logistics is the use of Automated Guided Vehicles (AGV) [4, 5]. AGVs are mobile robots capable of self-direction within an environment following physical or virtual paths, and they provide a notable improvement in the production processes, reducing costs, increasing production, and optimizing safety during them [9].

Generating optimized trajectories for AGVs is an essential task to maximize their efficiency and productivity. One of the challenges in generating optimized trajectories for AGVs is to find the best path from a starting point to an end point, avoiding obstacles, and minimizing the travel time [8]. Several methods have been proposed to generate optimized trajectories, including the

<footnote n="1">¹ Department of Electromechanical Engineering, University of Burgos, Burgos, Spain
{ebayona,jesierra}@ubu.es</footnote>

<footnote n="2">² Michelin España-Portugal, Aranda de Duero, Spain</footnote>

<footnote n="3">³ Institute of Knowledge Technology, Complutense University of Madrid,
Madrid, Spain
msantos@ucm.es</footnote>
use of numerical methods based on Frenet-Serret formulas [7], and evolutionary
techniques like genetic algorithms [6].

This article presents a methodology for the generation of optimized trajecto-
ries for AGVs and its implementation. The proposed methodology includes the
use of several software tools, such as AutoCAD for defining the occupancy map,
MATLAB for mathematical calculations and generating the optimal trajectory,
and Unity for visualization [6]. The working process begins with defining the
occupancy map using CAD software, selecting waypoints, and generating the
optimal trajectory using a genetic algorithm based on the Frenet equations with
an optimization parameter [3]. Finally, the generated trajectory is visualized in
Unity.

The proposed approach ensures the optimization of the trajectory design
process and provides a correct visualization of the results, making it useful for the
implementation of AGVs in different fields, such as logistics and manufacturing.
This methodology provides a faster, more efficient, and safer way to generate
optimized trajectories for AGVs. By reducing the length of the path, it can
significantly reduce the travel time, directly impacting the production time and
therefore the productivity of the processes where automated transport solutions
are implemented using AGVs.

In conclusion, the use of AGVs has become essential in different business
sectors, and the generation of optimized trajectories is a critical aspect of their
implementation. The proposed methodology using a genetic algorithm based on
the Frenet equations with an optimization parameter and several software tools
ensures the optimization of the trajectory design process and provides a correct
visualization of the results. Therefore, it can be useful for the implementation
of AGVs in different fields, such as logistics and manufacturing.

The paper is structured as follows. Once the motivation of the necessity of
generating optimum trajectories for an AGV is presented, in Sect. 2 the flow of
the steps to reach the objective is described, including the different tools used.
The generation of the occupancy map is developed in Sect. 3. Section 4 explains
how the genetic algorithm is applied and the cost function used. Results are
shown and discussed in Sect. 5 and 6. The paper ends with the conclusions and
future works.

## 2 Work Methodology

With the need to describe optimized trajectories for the performance and imple-
mentation of AGVs, the development of methodologies that automate the tra-
jectory design process and guarantee its optimization and correct visualization
of the obtained results for the user, arises.

In this work, the proposed methodology includes the use of several software
components. As part of the trajectory generation process, a CAD tool must
be used to define an occupancy map. In this work, we will use AutoCAD as
computer-aided design software. Mathematical calculation for trajectory gener-
ation must be performed by a computer, with Matlab being the mathematical
tool used. Finally, Unity is used as a physical engine and visualization tool for
the achieved result. The relationships between the used tools are represented in
the component diagram of Fig. 1.

<figure><img src="image_3.png" /><figcaption>Fig. 1. Component diagram.</figcaption></figure>

The work process begins with the creation of the occupancy map using a CAD tool (AutoCAD in this case) by drawing polylines. Once defined, the points that define each obstacle on the map are exported to a text file, which is then imported into a mathematical tool (Matlab in this case) where they are identified to reconstruct the map geometry.

Within the occupancy map space, minimum waypoints for the trajectory must be selected, including initial and final points as well as intermediate points. Based on these initial conditions, the process of generating the optimal trajectory begins in Matlab. The resulting trajectory is then imported into the simulation tool (Unity) to visualize the AGV's movement on the generated trajectory within the map for discussion (Fig. 2).

## 3 Occupancy Map

The generation of the occupancy map is carried out with CAD software using polylines. Within the map, fixed and mobile obstacles during the operation of the AGVs and the boundaries of the map itself are delimited by layers.

Using a Lisp macro, all the objects that make up the occupancy map are selected. From the selection, each of the points of the polylines of the objects of the map is exported to a text file with the properties of each one: identity code of the object to which they belong, the layer to which they belong, and their coordinates within the limits of the occupancy map.

From the text file, the points are imported into the mathematical tool based on the properties with which they were exported. The occupancy map is
<figure><img src="image_4.png" /><figcaption>Fig. 2. Methodology process diagram.</figcaption></figure>

constructed from these points, based on the geometric shapes defined in the CAD tool, both the limits and the obstacles.

All the space within the geometric shapes that describe the points of each obstacle is considered an occupied zone, and the space between the geometric shapes and the limits of the map will be free zones of occupancy.

## 4 Optimization Through Genetic Algorithm

Once the occupancy map in which the AGVs will operate has been generated, the mathematical tool requires the initial conditions to start working on the optimal trajectory. The initial and final points, as well as the intermediate points of passage that the AGV must pass through, must be defined. Based on these conditions, the tool is capable of finding the optimal trajectory that passes through those points according to an optimization parameter.

The generated trajectory is given by the Frenet equations, which represent a flat curve in $\mathbb{R}^2$ where the tangent vector T and the normal vector N satisfy (1). These equations are known as the Frenet equations of a trajectory [2].

$$ \left. \begin{array}{l} T's = ksNs \\ N's = -ksTs \end{array} \right\} \qquad (1) $$

where s is the distance to the origin of each point, k is the curvature of the trajectory at distance s, T(s) is the tangent vector at distance s, N(s) is the normal vector at distance s, and the symbol 't' denotes the perpendicular vector.
Based on the definition of a Frenet curve, the arc length can be calculated in Cartesian coordinates, where the trajectory will be a flat curve in $\mathbb{R}^2$ with the form $y = f(x)$ where f is a continuous and differentiable function. The length of each of the infinitesimal segments of the curve is expressed in (2).

$$ds = \sqrt{dx^2 + dy^2} = \sqrt{1 + \left(\frac{dy}{dx}\right)^2} dx \quad (2)$$

This leads to the mathematical expression of the arc length of the calculated trajectory (s) based on (2) and expressed in (3).

$$s = \int_{(x_i, y_i)}^{(x_f, y_f)} \sqrt{1 + \left(\frac{dy}{dx}\right)^2} dx \quad (3)$$

To carry out the optimization of the trajectory based on the chosen parameter, a genetic algorithm is used. Genetic algorithms are an evolutionary computational technique used in optimization problems. It is based on the evolution of an initial population of individuals. Its correct coding and the correct choice of genetic operators (mutation and crossover) are key to the algorithm's convergence towards the best solution [1].

The solutions for this optimization problem are defined as a matrix of 3 elements: $[x, y, \theta]$, where x and y are the coordinates of the intermediate points and $\theta$ is the output angle of the trajectory at those intermediate points. Therefore, there will be as many solutions as intermediate points indicated in the tool. The coordinates of the solutions can be any value within the dimensions of the occupancy map and the angles will be any value within the limits of 0 and $2\pi$. These conditions are formally expressed in eqs. (4) to (6).

$$x \in [0, n] \quad (4)$$

$$y \in [0, m] \quad (5)$$

$$\theta \in [0, 2\pi] \quad (6)$$

Being n and m the dimensions on the abscissa and ordinate axis, respectively.

The fitness function of the algorithm will be the inverse of the average of the minimum distances from each point of the trajectory to the occupancy map. Using this fitness function, the genetic algorithm will optimize the generated trajectory in such a way that the points of the trajectory are as far away as possible from the occupancy map on average, ensuring that the selected option is the safest trajectory taking into consideration the distance to obstacles as a parameter.

To calculate the distance from each point to each of the obstacles, the projection of the point onto each of the segments that form each of the obstacles is calculated. If the projection falls on the line on which the segment lies, the minimum distance to the vertices of said segment is used. The value of the distance will be the norm of the vector that joins the point and its projection onto the segment or the nearest vertex. Formally, we can express the projection of a
point P onto a line defined by points A and B that describe the segment of the nearest occupancy map vertex as (7).

$$Q = \operatorname{proj}_{\vec{AB}}(\vec{AP}) = \frac{\vec{AB} \cdot \vec{AP}}{|\vec{AB}|^2} \cdot \vec{AB} \qquad (7)$$

Therefore, the value $D$, as the minimum distance of the points of the trajectory to the occupancy map in case $Q$ will be the norm of $\vec{QP}$ if $Q$ is on $\vec{AB}$ segment as expressed in (8):

$$D = \|\vec{QP}\| = \sqrt{(Q_x - P_x)^2 + (Q_y - P_y)^2} \qquad (8)$$

where $Q_x$ and $Q_y$ are the coordinates of point $Q$ and $P_x$ and $P_y$ are the coordinates of point $P$.

In case $Q$ is outside the $\vec{AB}$ segment, the value of the minimum distance will be the norm to the nearest vertex $A$ or $B$. Assuming $A$ is the nearest one it will be expressed (9):

$$D = \|\vec{AP}\| = \sqrt{(A_x - P_x)^2 + (A_y - P_y)^2} \qquad (9)$$

where $A_x$ and $A_y$ are the coordinates of point $A$ and $P_x$ and $P_y$ are the coordinates of point $P$.

The distance $D$ from the point $i$ of the trajectory to the obstacle $j$ is denoted by $D_{ij}$. Then $D_{ij}$ is computed for all pairs $(i, j) \in N_p \times N_o$, where $N_p$ is the set of points in the trajectory and $N_o$ is the set of obstacles in the occupancy map.

The fitness function is thus expressed as the inverse of the average of the distance from each point of the trajectory to nearest obstacle in the occupancy map. This is formalized by (10):

$$f_F = \frac{n}{\sum_{i=1}^{n} \min_{j \in N_o} D_{ij}} \qquad (10)$$

# 5 Results Visualization

To evaluate the mathematical results within a 3-dimensional environment where the operation of the vehicle can be visualized as expected in the real environment, the optimized trajectory developed in Matlab must be imported into the Unity tool.

The representation of the occupancy map is done using the file created by the CAD tool to generate obstacles in the visualization software. Within the tool, the object representing the AGV vehicle must also be generated based on its real measurements, in order to faithfully represent the expected operation in reality.

From Matlab, the coordinates and output angles of each of the trajectory points are exported to a text file. Within the created occupancy map, the trajectory is reconstructed by importing the coordinates where the vehicle will travel
and its orientation at each of those points. Using its graphics engine, Unity renders the movement of the AGV along the trajectory, allowing the evaluation of the result prior to implementation in the real environment.

# 6 Experiments

In line with the methodology developed previously, two experiments are carried out as a practical demonstration of the methodology. In each experiment, different starting and ending situations are presented, as well as different intermediate points within the same occupancy map, in order to verify the feasibility of the method presented in this work. First, an operating environment for the AGV is generated by simulating an industrial area with various obstacles in the CAD tool used. The different colors correspond to different types of obstacles and the limits of the occupancy map, with yellow representing the fixed obstacle layer, blue representing the mobile obstacle layer, and purple representing the map limits layer. Figure 3a shows the CAD occupancy map.

<figure><img src="image_5.png" /><figcaption>Fig. 3. Occupancy map in CAD and Matlab.</figcaption></figure>

This map is exported through a macro to obtain the points of the polylines that form the map and be able to work with it in the mathematical tool. Once imported, the occupancy map will have the shape shown in Fig. 3b.

Starting from this map, the initial conditions and intermediate points are selected for the genetic algorithm to operate and optimize the trajectory. In experiment 1, the leftmost point is the initial point and the red point on the right is the final point. In experiment 2, the initial point corresponds to the point at the bottom of the image and the final point is the point at the top. Points within the mobile layer can be selected, which means that the trajectory will start from the central point of that obstacle and, during the development of that trajectory, that obstacle in the mobile layer will not be where it was
initially contemplated. Those obstacles where a point has been selected on them
disappear, leaving their profile to indicate their existence on the initial map.
The initial and final points are represented in red and the intermediate points in
blue for each of the experiments. Figure 4a and 4b represent experiment 1 and
2, respectively.

<figure><img src="image_6.png" /><figcaption>Fig. 4. Selection of waypoints.</figcaption></figure>

With these conditions, the algorithm can now start operating with the output
angles of the intermediate points as optimization variables. Figure 5a and 5b
show the results of each of the proposed experiments. The trajectory is shown
in red, and at each point of it, the profile of the AGV vehicle is shown along its
path. The red points on the trajectory are the same points selected earlier as
input parameters of the method, and they are also highlighted in the resulting
trajectories. The yellow lines represent the minimum distance of each of the
points in the optimized trajectory to the occupancy map, so that the average of
these distances is maximized.

In both experiments, it is observed that the trajectory does not follow the
shortest path to its destination. Instead, the algorithm marks a trajectory whose
points remain at the maximum possible average distance from the obstacles in
the occupancy map.

The points that make up this trajectory and their respective exit angles are
exported to a file to be used by the visualization tool (Unity). Once imported,
Unity builds a trajectory from them for the designed vehicle to move within
it, maintaining the same exit angle calculated in the mathematical tool. To
achieve the simulation of the AGV's movement along the optimized trajectory,
an occupancy map analogous to the one used by Matlab must be constructed
that uses the same coordinate reference system, so that the coordinates of the
points on the trajectory are the same in each of the tools.

Figure 6 shows the occupancy map represented in Unity with the same refer-
ence to the origin as the original map. Likewise, it shows the model of the AGV
<figure><img src="image_7.png" /><figcaption>Fig. 5. Optimized trajectories.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 6. Visualization software, occupancy map and results representation</figcaption></figure>

vehicle that represents the profile used in the mathematical tool and the tra-
jectory imported from Matlab by which it will move. Based on the represented
models and trajectory data, the movement of the vehicle along the trajectory can
be visualized as expected to occur in reality, checking for possible situations not
contemplated or safety or technical considerations that may arise during oper-
ation before the vehicles are deployed in their final location. Therefore, using
visualization software allows for a better understanding of the data provided as
a result of the mathematical tool, enabling the detection of patterns or trends
that may otherwise go unnoticed. Similarly, it allows simulating a multitude of
different scenarios and checking how the results affect the operation to help in
decision-making when identifying the best solution.

It is also shown the appearance of the Unity representation of the results generated by the mathematical tool for experiment 1. In the image, the shape of the occupancy map and the model of the AGV vehicle can be distinguished. Likewise, the optimized trajectory imported into the tool by which the AGV will move can be distinguished, being able to visualize in real-time how the vehicle's operation will be from the initial point to the end.

# 7 Conclusions and Future Works

This paper presents a methodology for designing trajectories for AGVs that auto-
mates the design process and guarantees optimization of the trajectory based
on selected parameters. The methodology combines several software tools such
as AutoCAD, Matlab, and Unity for designing and visualizing the optimal tra-
jectory.

Based on the results of the two experiments presented, it is demonstrated
that this methodology can be useful for generating trajectories in a real working
environment and has been validated through the Unity simulation of the AGV's
movement on the generated trajectory.

The generation of the occupancy map using CAD software, in this case Auto-
CAD, allows for a detailed definition of the obstacles and boundaries of the map,
ensuring high precision in the generation of the trajectory. The process of gen-
erating the optimal trajectory through Frenet equations and supported by the
use of genetic algorithms also ensures high precision in the generated trajectory.

Simulation in Unity allows for visualization and analysis of the generated
trajectory, facilitating validation and adjustment of the trajectory if necessary. In
conclusion, the methodology proposed in this paper is a useful tool for designing
and generating optimal trajectories for AGVs in industrial working environments
and can be adapted and improved for specific applications. The combination of
several software tools allows for automation of the design process, reducing the
time and effort required to generate an optimal trajectory.

As future works, different fitness functions could be implemented, weighting
other factors such as energy saving or the dynamic generations of trajectories in
case of pop-up obstacles.

# References

1. Abajo, M.R., Sierra-García, J.E., Santos, M.: Evolutive tuning optimization of a PID controller for autonomous path-following robot. In: Sanjurjo González, H., Pastor López, I., García Bringas, P., Quintián, H., Corchado, E. (eds.) SOCO 2021. AISC, vol. 1401, pp. 451–460. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-87869-6_43

2. Alencar, H., Santos, W., Neto, G.: Differential Geometry of Plane Curves. American Mathematical Society, Providence (2022)
3. Bayona, E., Sierra-García, J.E., Santos, M.: Optimization of trajectory generation for automatic guided vehicles by genetic algorithms. In: Bringas, P.G., et al. 17th International Conference on Soft Computing Models in Industrial and Environmental Applications (SOCO 2022). SOCO 2022. Lecture Notes in Networks and Systems, vol. 531, pp. 484–492. Springer, Cham (2023)

4. Berman, S., Schechtman, E., Edan, Y.: Evaluation of automatic guided vehicle systems. Robot. Comput.-Integr. Manuf. **25**(3), 522–528 (2009)

5. Espinosa, F., Santos, C., Sierra-García, J.E.: Transporte multi-agv de una carga: estado del arte y propuesta centralizada. Revista Iberoamericana de Automática e Informática industrial **18**(1), 82–91 (2020)

6. Kim, D.H., Kim, S.B.: Path following control of automated guide vehicle using camera sensor. In: Zelinka, I., Brandstetter, P., Trong Dao, T., Hoang Duy, V., Kim, S.B. (eds.) AETA 2018. LNEE, vol. 554, pp. 932–938. Springer, Cham (2020).
https://doi.org/10.1007/978-3-030-14907-9_90

7. Kirsch, C., Künemund, F., Heß, D., Röhrig, C.: Comparison of localization algorithms for AGVs in industrial environments, pp. 183–188 (2012)

8. Yang, Z., Liu, H., Xie, R.: Improved ant colony algorithm based on parameters optimization for AGV path planning. In: 2021 2nd International Symposium on Computer Engineering and Intelligent Communications (ISCEIC), pp. 87–92 (2021)

9. Zamora-Cadenas, L., Velez, I., Sierra-Garcia, J.E.: UWB-based safety system for autonomous guided vehicles without hardware on the infrastructure. IEEE Access **9**, 96430–96443 (2021)