Page 95 - 2023-Vol19-Issue2

91 |
be suitable for real-time response, while RRT is not well-
suited for environments with dynamic obstacles. Potential
field obstacle avoidance is a promising solution for dynamic
environments, but it can result in sub-optimal paths that are
not safe or efficient and may also fall in the local minimum
regions.
L. Li-sang et al. describe a smart obstacle avoidance car
for autonomous driving, using Simultaneous Localization and
Mapping (SLAM) technology to generate a map of an in-
door unknown environment. [7] Other researchers focus on
finding the shortest mobile route in a virtual environment us-
ing the Modified Dijkstra’s algorithm. [8] D. S. Nair and P.
Supriya present a new approach for planning besides colli-
sion avoidance within the system of robot navigation using
Modified Temporal Difference Learning (MTDL). [9] On the
other side, another method that presents a solution for the
problem of constrained coverage path planning for Unmanned
Aerial Vehicles (UAVs) is proposed. [10] X. Li, proposes a
relaxed Dijkstra algorithm to plan the path of a robot within a
real time large-scale and obstacle-intensive environment. [11]
Particle Swarm Optimization (PSO) algorithm is applied to
improve the initial path of Dijkstra to get the final shortest
path. [12] Also, an improvement to the Dijkstra algorithm
for optimizing the shortest path for the direct navigation of
ships has been proposed. [13] In 2022, a new method pro-
poses an energy-efficient local path planning algorithm for
Autonomous Ground Vehicles (AGVs) by merging the Poten-
tial Field algorithm with future movement prediction. [14]
The algorithm of Dijkstra to find the optimal path in real-time
for a single unmanned surface vehicle in Portsmouth Harbour
is introduced. [15] B. Kasmi and A. Hassam (2021) proposed
a two-part path planning method for mobile robot navigation,
using cell decomposition for offline computation and a poten-
tial field method for online computation. [16] Finally, an ana-
lytical method for path planning for a UAV to attack multiple
moving targets in a dynamic environment is presented. [17]
W. Yang et al. operate to address the problems of ”local
minimum” and ”unreachable target”. The improved method
modifies the direction and influence range of the gravitational
field, increases the virtual target and evaluation function, and
increases gravity to solve these problems. [18] These studies
offer valuable insights into various path planning and obstacle
avoidance techniques for robotic systems, which can be useful
in a range of applications. [19], [20], [21]
In this research, we present an improved method for path
planning that combines the Dijkstra path planning algorithm
with the Potential Field obstacle avoidance method to address
the aforementioned challenges (dealing with the dynamic ob-
stacles and overtaking the regions of local minima). The
Dijkstra algorithm is used to generate multiple paths from
the source point to the target one, and the potential field algo- and edges represent the connections between the nodes. The
Al-Ansarry, Al-Darraji & Honi
rithm is used to filter the only desirable paths (paths near to
the shortest one and have a responsible cost) to be assigned
as alternative paths in case of the basic path (shortest one)
intersect by any dynamic obstacle, then evaluated the safety
(obstacle-free) of each path that generated by Dijkstra and
select the next optimal one. The proposed method generates
connections between the alternative paths, allowing the robot
to switch between various paths if it faces a dynamic obsta-
cle on its current route in real-time. This allows the robot to
continue toward its target while avoiding obstacles in a safe
and efficient manner. The proposed method also handled the
issue of trapping within the region of local minima which
PF suffered from, making the path suitable for use in a wide
range of mobile robot applications.
The research is distributed as follows: Section II presents
the methodology for the proposed method and the problem
formulation. In section III, experiments are conducted and the
results are illustrated to validate the algorithm. Finally, the
conclusion is made in Section IV.
II. PROPOSED METHOD
The method suggested involves utilizing a combination of the
Dijkstra path planning algorithm and potential field obstacle
avoidance to determine the most efficient path in constantly
changing environments. It consists of two distinct phases:
Path Generation and Path Selection.
A. Path Generation
The algorithm of Dijkstra is considered a common graph
traversal method that is used to locate the path with the short-
est length between two vertices in a graph with non-negative
edge weights. It is known for its efficiency and is commonly
used in various applications, such as finding the optimal route
between two nodes on a map or finding the shortest path in a
computer network.
The algorithm operates as shown in Figure (1) by itera-
tively exploring nodes within a graph, starting from the initial
node and visiting its neighbors. The distance between the
source node and each neighboring node is calculated and then
selects the neighbor with the shortest distance. This strategy
is continued till every single node has been examined, and the
path with the lowest distance has been determined between
the source node and all other nodes in a graph.
In the path generation phase, the Dijkstra algorithm is used to
generate multiple paths as shown in Figure (2) between the
start and goal points, considering the presence of obstacles
in the environment. The algorithm creates a graph structure,
where nodes represent the possible locations of the robot,
algorithm then finds the shortest path from the source point