Page 99 - 2023-Vol19-Issue2
P. 99
95 | Al-Ansarry, Al-Darraji & Honi
The method then returns the optimal path, p optimal, which
is the minimum cost path. The cost of each path is calculated
as the sum of the length of the path and the repulsive force
exerted by obstacles on the path. The length of the path can be
calculated using any suitable distance metric, and the repulsive
force can be calculated using the method of Potential Field.
D. Dynamic D-PF Method
We present -in this section- the Dynamic Dijkstra-Potential
Field method (Dynamic D-PF). The goal here is to implement
the selected optimal path as shown in Figure (5) in a real-
time potential field environment and respond to any dynamic
obstacles that may arise during the execution of the path.
This is accomplished by using the connections generated in
the Path Generation phase, which allow the robot to switch
between candidate paths if it encounters a dynamic obstacle
on its current path.
and its associated Potential Field trajectory by summing the
length of the path and the safety of the safe trajectory along
the path. Finally, the path with the lowest cost is chosen as the
optimal path and returned as the result. It is worth mention
that A* and Dijkstra are algorithms to locate the shortest route
between two points within a graph or a network. However,
there are some key differences between them.
Fig. 5. Potential Fields Heat Map with Dynamic Obstacles • Heuristic Function One of the main differences be-
tween A* and Dijkstra is that A* utilizes a heuristic
By combining these two algorithms, the proposed method function to guide the search toward the goal, while Di-
(Dynamic D-PF) as illustrated in Algorithm (3) provides a jkstra does not. The heuristic function estimates the
flexible and efficient way to find an optimal path (short and distance from a node to the goal, which helps A* to
safe) in real-time within a 2D environment. The combination prioritize nodes that are closer to the goal, potentially
of the multiple paths generated by the Dijkstra and the Poten- leading to faster search times.
tial Field method provides robustness and adaptability in the
presence of dynamic obstacles. • Optimality Dijkstra is guaranteed to reach the goal with
the minimum distance between two points, whereas
Algorithm (3), takes as input the robot’s current position, A* is only guaranteed to find an optimal path if the
the target position, and the obstacles in the environment. It heuristic function used is admissible, meaning it never
first generates multiple paths from the robot’s current position overestimates the actual distance to the goal.
to the target one using Dijkstra’s algorithm. Then, for each
path generated by Dijkstra’s algorithm, it applies the Potential • Memory Usage A* typically uses more memory than
Field method to find a safe trajectory along the path, avoiding Dijkstra, as it keeps track of more information about
obstacles along the way. If a safe trajectory is found, the path each node in order to calculate the heuristic function.
and its associated safe trajectory are added to the list of paths. However, this additional memory can often lead to
The EvaluatePath function calculates the cost of each path faster search times.
• Time Complexity In terms of time complexity, the
algorithm of Dijkstra has the worst time complexity:
