Page 311 - Kỷ yếu hội thảo khoa học lần thứ 12 - Công nghệ thông tin và Ứng dụng trong các lĩnh vực (CITA 2023)

Tran-Viet An and Vu-Anh-Quang Nguyen 295

used in the study, including the simulation environment and performance metrics. Sec-
tion 3 presents the results of the evaluation and discussion, followed by section 6 con-
cludes the paper and discusses potential directions for future research.

2 Background

2.1 A* algorithm

A* algorithm is a heuristic search algorithm used in pathfinding and graph traversal. It
is a combination of Dijkstra's algorithm and a heuristic function that estimates the dis-
tance between the current node and the goal node. A* algorithm uses a priority queue
to store the open list of nodes to be explored. The priority queue is sorted by the sum
of the cost to reach the node from the start node and the estimated cost to reach the goal
node [1].
The algorithm starts at the start node and explores the neighboring nodes. For each
neighbor, the algorithm calculates the cost of moving from the current node to the
neighbor and the estimated cost of moving from the neighbor to the goal node. The sum
of these two costs is used as the priority value to add the neighbor node to the open list.
The algorithm then selects the node with the lowest priority value from the open list
and continues exploring its neighbors. This process is repeated until the goal node is
reached.
A* algorithm guarantees finding the shortest path if the heuristic function satisfies
the admissibility condition, which means the estimated cost to the goal node is always
less than or equal to the actual cost. A* algorithm is commonly used in autonomous
driving vehicles for route planning, collision avoidance, and other pathfinding tasks.

2.2 algorithm

[2] is a popular algorithm for finding the shortest path between
two nodes in a graph. It starts by assigning a tentative distance to all nodes from the
starting node, which is initially set to 0. Then, it selects the node with the smallest
tentative distance and explores its neighboring nodes. For each neighboring node, the
algorithm updates its tentative distance if a shorter path is found from the starting node.
The algorithm continues to select the node with the smallest tentative distance and
explore its neighbors until the destination node is reached, or all nodes have been ex-
plored. The algorithm uses a data structure called a priority queue to store the nodes
with their tentative distances, and it guarantees that the shortest path is found when the
algorithm terminates.
used in various applications, including transportation
networks, computer networks, and social networks. In the context of autonomous driv-

avoidance. It is an efficient algorithm when the graph is sparse, which means there are
few connections between nodes. However, its performance can degrade when the graph
becomes dense, which can happen in large-scale road networks.

ISBN: 978-604-80-8083-9 CITA 2023