Page 96 - 2023-Vol19-Issue2
P. 96
92 | Al-Ansarry, Al-Darraji & Honi
path planning process. Algorithm (1) describes these steps
clearly.
Fig. 1. Dijkstra Map Representation • The ShortestPath function takes three inputs: graph,
to the goal by searching the graph structure for the minimum start, and end. Graph is a dictionary of dictionaries
distance between nodes. representing the graph structure, where the keys are the
nodes, and the values are dictionaries of neighbors and
Fig. 2. Path Generation weights. Start and end are the starting and ending nodes,
The goal here is to generate candidate paths from the respectively.
current robot position to the position of the goal. This is ac-
complished by using Dijkstra’s shortest path algorithm, which • The distances dictionary is initialized with the value
finds the optimal path for each two points in a graph. By float(”inf”) for all nodes, representing that the distance
generating and storing the multiple candidate paths, the pro- is unknown. Set the distance equal to 0 between the
posed method provides the robot with multiple options for start node to itself.
reaching the goal position and increases the robustness of the
• The previous dictionary is initialized with None for all
nodes, representing that there is no previous node in
the path yet. The unvisited list is initialized with all the
nodes in the graph.
• The while loop continues until all nodes have been
visited or the end node has been found.
• In each iteration, the node with the minimum distance
is selected as a current node. If it is the end node, the
loop is terminated. The current node is removed from
the unvisited list.
• For each neighbor of the current node, the distance from
the start node to the neighbor is calculated as the sum
of the distance from the start node to the current node
and the edge weight connecting the current one and the
