Path Planing Algorithms - Dijkstras Algorithm - Essay Example

PATH PLANNING ALGORITHMS Student’s name Course code + name Professor’s name University name City, State Date of submission Introduction Dijkstra’s algorithm refers to a graph-search algorithm used in path finding to determine the shortest distance between two points on a graph. The algorithm applies only to graphs having non-negative edges to produce the shortest path tree. On the other hand, A* is a computer algorithm used in graph traversal and path finding. As the algorithm traverses the graph, it follows the lowest known path while maintaining a record of a sorted priority queue comprising of alternative path segments. The paper analyses the two algorithms with respect to their types, running times and efficiency. Dijkstra’s Algorithm It refers to the single-source shortest path (Yan 2014). The other synonym to Dijkstra’s algorithm is the single source shortest path problem. The objective of the algorithm is to compute the shortest path considering the source as the point of origin to the other graph vertices. In the description of the single-source shortest path algorithm, Let G= {V, E} be a weighted graph. V contains the set of vertices. Let s be a special vertex in V. Recall that G is a directed weighted graph. Let s to be the source and e to be the length of the edge for any edge e in E. All the graph weights are non-negative, directed and weighted. The ordered pair, G mentioned above is a directed graph (Reddy 2013). It contains the set V that comprises of elements known as nodes or vertices. It also consists of the set E that also comprises of ordered pairs of vertices. The vertices in set E are known as directed edges, arrows or arcs. The short form of a directed graph is a digraph. In essence, Dijkstra’s algorithm entails finding the shortest path in a directed-weighted graph. Dijkstra’s algorithm is a greedy algorithm that makes of problem-solving approaches with the intention of arriving at a long-term strategy for the operation or action. The greedy approach solves the single-source shortest path problem (Morris 1998). The approach selects vertex v located nearest to the source s repeatedly from the unselected vertices. The declared distance entails the actual shortest distance between s and v. The algorithm then checks the edges of v to determine if it is possible for v to reach their destination by comparing the weights of the outgoing edges. The Working of Dijkstra’s Algorithm The algorithm works by determining the solution of the sub-problem k that determines the shortest distance from the source to the vertices (Morris 1998). In the determination of the shortest path, k considers the vertices located closest to the source. The working of the algorithm necessitates that all the vertices should be non-negative. Moreover, the graph under consideration should be directed and weighted (digraph). In the event that there are negative edges, the algorithm cannot compute the shortest path from the source to the vertices. Following the execution of the kth round, there results a set known as the frontier of k vertices. The set comprises of vertices situated closest to the source. The solution also categorizes the vertices situated outside the frontier into another group of vertices referred to as the New Frontier. The algorithm maintains the obtained shortest distance in the sDist[w] that holds estimates of the distance from the source to w. To find the next closest vertex, the algorithm maintains the vertices of the New Frontier in a priority-min queue (Morris 1998). Dijsktra’s algorithm also keeps the shortest distance of vertex v from the source s in an array known as sDist. The algorithm sets the shortest distance from s to s to be zero implying that the shortest distance from the source to itself is zero (Morris 1998). It then sets the shortest distance to the other vertices to infinity since there are no already computed values for the distances. Following the completion of processing the distances of the vertices from s, the array sDist will contain the shortest distance from s to v. the algorithm maintains both the Frontier and New Frontier sets. The maintained sets are important in the processing of the algorithm. Frontier comprises of k vertices located closest to the source s following the computation of the shortest distances from the source to the vertices for the paths limited to the k vertices. The New Frontier comprises of vertices that lie outside the Frontier. The figure below shows an example of a digraph. Figure 1: An example of a digraph The Pseudo-Code of the Algorithm The general pseudo code of Dijsktra’s algorithm is as follows Dijkstra’s(G) . Weighted graph (with all weights positive) dist[s] 0 .distance to source vertex is Zero for all v 2 V − {s} do dist[v] 1 .set all other distances to infinity end for S ø . S, the set of visited vertices is initially empty Q V . Q,the queue intially contains all vertices while Q 6= ø do . while the queue is not empty u mindistance(Q, dist) . select ele of Q with the min. distance S S [ {u} . add u to list of visited vertices for all v 2 neighbors[u] do if dist[v] > dist[u] + w(u, v) then . if new shortest path found d(v) d(u) + w(u, v) . set new value of shortest path end if end for . if desired, add trace back code end while return dist end procedure (Reddy 2013) Dijsktra’s algorithm provides an illustration of the Best-First-Breadth-First-Search. On the part of the Best-First, the algorithm selects the best vertex in the New Frontier to undergo the next computation exercise. The Breadth-First search used by the algorithm emanates from the fact that the compositions of vertices in the New Frontier are next in computation. Moreover, the vertices are only one edge from the already processed vertices (Morris 1998). The Efficiency of the Algorithm The Big-O notation is useful in expressing the efficiency or complexity of the algorithm. It provides an alternative approach of understanding the effect of the input on the running time of an algorithm. In Dijkstra’s algorithm, the |E| updates for priority queues and the |V| = n DeleteMins affect the efficiency of the algorithm. When using a Fibonacci heap, the complexity is O (|E| + |V| log |V|). This entails the best bound efficiency. The operation executed by DeleteMins is O (log |V|). When using a standard binary heap, the complexity is O (|E| log |E|), where |E| log |E| terms emanate from the |E| updates. For a priority queue set, the complexity is O (|E| + |V|2). The |V| scans of the unordered New Frontier set give rise to the O (|V|2) terms (Reddy 2013). The scanning of the unordered New Frontier results in vertices that have the shortest distance from the source. The fact that Dijkstra’s algorithm runs a blind search on all the vertices implies that it spends a lot of time finding the vertex with the shortest sDist value thereby resulting in more running time and wasting the available resources. Moreover, algorithm is incapable of handling negative edges. Applying the algorithm to weighted graphs that have negative weights leads to acyclic graphs. Such graphs impede the ability of the algorithm to find the shortest path of the vertices from the source. Traffic information systems apply Dijkstra’s algorithm to track the destinations and sources from a particular destination and source. The algorithm also has an application in internet routing with the help of the Open Shortest Path First (OSPF) approach employed by the algorithm (Reddy 2013). The link-state forms the hierarchy in the areas. The use of the algorithm is in the computation of the shortest path tree within the network area. In essence, the greedy approach employed by Dijkstra’s algorithm in path finding follows three main steps. The first step entails maintaining a set S of vertices that have a known shortest path from the source s. At each successive step, the algorithm adds vertex V to the set S from the set V-S. The algorithm is greedy in the selection of the vertex since it chooses a vertex that has the smallest distance from the source. The final step entails updating the estimates of the distances of the vertices that are closest to v (Reddy 2013). The A* Algorithm A* is one of the several search algorithms in path finding. In determining the shortest path from the source, the algorithm uses three fundamental steps. The first step entails taking the input. In the second step, the algorithm evaluates the input to determine the possible paths. Finally, it returns a solution. The A* algorithm has a wide application in computer science following its utility in finding paths and traversing graphs. Graph traversal entails the process of plotting a path between nodes that is efficiently traversable. The algorithm attains its effective computation of optimal solutions by combining the features of the pure heuristic search and the uniform-cost search. The algorithm builds a “closed list” to record the “fringe list” areas and areas adjacent to the fringe list. Finally, the algorithm calculates the distances from the “start point” with respect to the estimate distances of the “goal point”. The fringe list is commonly known as the open list. It comprises all locations that are immediately adjacent to the already explored and evaluated areas (Reddy 2013). The closed list is the list of the already explored and evaluated areas. The Working of the A* Algorithm The algorithm uses a best-first search to find a least-cost path from a predetermined initial node to a target goal node. In the process of traversing the graph, the algorithm follows a path of the lowest possible and known heuristic cost. During the processing, the algorithm also keeps a record of a sorted priority queue comprising of alternative path segments. Comparing A* algorithm to Dijkstra’s algorithm, it is proper to state that the best-first search approach presents in both algorithms. However, the A* algorithm is more accurate than Dijkstra’s algorithm since it maintains a record of the already traversed nodes. In essence, the rationale of the algorithm is to determine the least-cost path to the goal node that qualifies it to become a best first search algorithm. It uses the general formula Where f (x) is the F cost or the distance-plus-cost-heuristic function g (x) is the total distance from the start point to the current position and h (x) is the heuristic function used in the approximation of the distance between the current location and the goal point (Inam et al. 2010). The distinct nature of the function implies that it is an estimate rather than an exact value. As a result, the more the accuracy of the heuristic function, the faster the process of finding the shortest path from the start point to the goal point. A* Algorithm Pseudo-code function A*(start,goal) closed = empty set q = makequeue(path(start)) while q is not empty do p = removefirst(q) x = lastnode(p) if x in closed then end if if x = goal then return p end if add x to closed for y successor(x) do enqueue(q, p, y) end for return Failure end while end function (Reddy 2013). The Different Variations of the Algorithm The objective of the variations of the parallel A* algorithm is to reduce the running time of the algorithms thereby enabling them to work faster on larger areas. There are three variations of the algorithm. They include: Pre-stored Paths In the event that several agents are finding parallel paths on the same search area, the full or partial repetition of some of the paths is common. As a result, the complete calculation of all the paths each time an agent finds it is a waste of time. To get rid of the problem, it is proper to calculate and store the path in advance. Alternatively, it is also appropriate to run the agents simultaneously thereby using the pre-stored paths to find their respective paths. The finding and storing of some of the paths necessitates the computations of a small number of the paths. However, in the event that an agent intends to find a path, the algorithm checks whether the path in question is already in the found and stored record (Inam 2009). If the path is among the already found and stored paths, the search stops and the algorithm copies the already available path. In the event that the path in question is not among the pre-computed paths, the algorithm will search for the partially pre-computed paths already existing in the database. The checking ascertains whether the end point of the pre-stored path is similar to the target point of the computed path. The algorithm then starts calculating the path. In every instance of selecting the current node, the agent checks whether the node also exists in the pre-computed path. If the node exists, then it is apparent that the agent has already calculated the rest of the path. At the instance, the agent stops finding the path and copies the rest of the already computed path (Inam 2009). Therefore, the agent simply computes the first part of the path and appends the already computed second part of the path to the first part to determine the total distance between the start point and the target point. It is apparent that the approach reduces the time taken to compute the path since the agent only computes the first part of the path and copies the second part of the path from its database. The complete computation of the new path occurs if the there are no sections of the required path that the agent has already computed and stored. Multiple Threads per Agent In this type of A* algorithm, the software runs multiple threads concurrently by using multithreading, concurrency controls and shared memory access. The correct algorithm execution also requires thread synchronization since there are instances where all threads are in search of a specific path and are accessing shared memory. For instance, in the implementation of an A* algorithm using eight parallel threads, the threads work simultaneously on the neighbors that are adjacent to the current node rather than a single thread working in a loop. All the threads will use a “temporary list” available on the CUDA shared memory (Inam 2009). The memory comprises of eight places; with each thread having access to one pace. The multiple implementation of threads in this type of A* algorithm necessitated the introduction of certain changes. For instance, one thread is responsible for executing the initial part of the algorithm. The thread continues with the execution process until the selection of the current node. During this time, all the remaining threads are in the waiting state. Accomplishing the objective requires thread synchronization. Following the selection of the current node, the remaining threads work simultaneously and run in parallel on all the neighbors that are adjacent to the current node. The checking of the adjacent nodes results in the calculation of their F cost and G cost values. The working also involves checking and/or changing their statuses followed by their enlistment on the temporary list. At this juncture, thread synchronization comes into action to ensure that all threads complete their execution process before advancing further (Inam 2009). Finally, one thread runs the remaining section of the algorithm and places the values contained in the temporary list to the open list. The Hierarchical Breakdown of A* The hierarchical finding of A* path applies for larger maps to overcome the memory limitation challenges posed by the first two approaches. The approach entails dividing the paths in slices or small parts and finding the total required path by combining the computed paths of the small parts. The path finding process involves two steps: path abstraction and path calculation. Path abstraction is also known as path slicing. It entails the development of the abstract weighted map from the grid map representation. The next step entails storing the graph in the agent’s memory. It is from the weighted graph that the other procedures of path finding take place (Inam 2009). Path calculation involves computing all the actual paths following the path abstraction exercise. Path calculation occurs in three steps. The first step entails adding the start and target nodes to the abstract weighted graph. The second step involves the computation of the complete abstract paths at the higher level of abstraction on the abstract weighted graph. The third step constitutes path refinement. It entails the refinement of all the abstract paths to the low-level paths (Sturtevant & Buro 2005). The agent then patches up the detailed paths to the abstract paths to yield a complete path. Dijkstra’s Algorithm versus A* Algorithm It is important to note that both algorithms find the shortest distance to a target point from an origin or source (Goyal et al. 2009). Moreover, Dijkstra’s algorithm is a special case of A* algorithm when h (n) = 0. The fact that A* uses the Best First Search approach while Dijkstra’s algorithm uses the Greedy Best First Search implies that A* is faster than Dijkstra’s (Santoso et al. 2010). However, in simplicity terms, it is proper to observe that Dijkstra’s outperforms A*. However, regardless of its simplicity, Dijkstra’s is time consuming since it conducts a blind search of the adjacent vertices. Dijkstra’s algorithm is also incapable of handling negative edges. In the attempt to deal with negative weights, the algorithms leads to acyclic graphs that make it difficult to find the shortest path between the source and the target point. Moreover, Dijkstra’s has no heuristic. As a result, it searches blindly by expanding out equally in all directions. On the other hand, A* scans the area situated only in the direction of the goal point. Therefore, Dijkstra’s searches a large area before finding the required path whereas A* focuses directly in the target area thereby using less time (Santoso et al. 2010). Even though Dijkstra’s is useful when the target point is unknown and A* is the most efficient when both the start point and target point are known, it is proper to state that A* algorithm offers the best path finding solution since it is less time consuming and efficient. Conclusion Even though both A* and Dijkstra’s algorithms find the shortest path between two points, A* is more efficient that Dijkstra’s. The efficiency of A* emanates from the fact that it restricts its scan towards the direction of the target point whereas Dijkstra’s scans the entire area before arriving at the required destination. Dijkstra’s algorithm is also time consuming due to the fact that it scans a larger area. The algorithm is also ineffective in the case of negative weights since it leads to acyclic graphs that make it difficult to find the shortest distance between two points. Therefore, A* algorithm is better than Dijkstra’s in the computation of the shortest path. Reference List Goyal, A, Mogha, P, Luthra, R & Sangwan, N 2014, ‘Path Finding: A* or Dijkstra’s’, International Journal in IT and Engineering, vol. 2, no. 1. Inam, R 2009, ‘A* Algorithm for Multicore Graphics Processors’, Chalmers University of Technology. Inam, R, Cederman, D & Tsigas, P 2010’, ‘A* algorithm for graphics processors’, In Third Swedish Workshop on Multi-Core Computing-MCC'10, November 2010, Göteborg, Sweden. Morris, J 1998, ’10.2 Dijkstra’s Algorithm’. Available from: https://www.cs.auckland.ac.nz/software/AlgAnim/dij-op.html Reddy, H 2013, ‘Path Finding: Dijkstra’s and A* Algorithm’. Santoso, L W, Setiawan, A & Prajogo, A K 2010, ‘Performance Analysis of Dijkstra, A* and Ant Algorithm for Finding Optimal Path Case Study: Surabaya City Map (Doctoral dissertation’, Petra Christian University). Sturtevant, N & Buro, M 2005, ‘Partial path-finding using map abstraction and refinement’, In AAAI (Vol. 5, pp. 1392-1397). Yan, M 2014, ‘Dijkstra’s algorithm’. Read More