Aparant Mane
Comparative analysis of algorithms for path optimization
'Comparative Analysis of Algorithms for Path Optimization' was my Final Year Project at Undergraduate Level implemented for completion of Bachler's Degree
Domain: Artificial Intelligence
Sub Domain: Pathfinding
Software Used:
1. Unity 5
2. Visual Studio Community 2013
3. IBM Rational Rose (for SE Diagrams)
-
Total Time to implement: 6 months
-
The project involves:
Simulating 6 pathfinding algorithms:
1. A*
2. Dijkstra's Shortest Path Algorithm
3. Breadth First Search
4. Depth First Search
5. Best First Search and
6. Modified A*
on a common map to compare, analyze and then select the most optimum algorithm on the basis of
1. Total Time taken to reach Destination
2. Total Distance covered to reach Destination
3. Total Nodes in path
4. Total Nodes examined
5. Time Efficiency
6. Memory Efficiency
7. Time to execute.
-
Modified A* v/s A*
A* computes the path using the Heuristic Fi = Gi + Hi (Manhattan) where ‘i’ is the index of the current node. Since node selection is based on the F cost, an overestimate for the H cost will diminish the weight of the G cost and the algorithm will explore nodes that have lower H values over nodes that have lower G values. This pushes node exploration in the direction of the goal node, rather than keeping it roughly centered on the start node.
In order to achieve an overestimate for H cost and an underestimate for G cost, we multiply the H cost and divide the G cost by a constant (k), where the value of the constant is greater than one.
Fi = (Gi / k) + (Hi * k), k > 1
Consider the following example with 2 test cases:
Case 1:
Node 1:
G = 4, H = 4 and k = 4
F = (G / k) + (H* k)
F = (4 / 4) + (4 * 4)
F = 1 + 16 = 17
Node 2:
G = 6, H = 2 and k = 4
F = (G / k) + (H* k)
F = (6 / 4) + (2 * 4)
F = 1.5 + 8 = 9.5
In the above case, we have considered 2 different set of G and H values both having the same F cost. Traditionally, the A* algorithm will consider both the nodes for path optimization. But, our algorithm will consider the node having an overestimate of H value and underestimate of G value.
Case 2:
Node 1:
G = 4, H = 4 and k = 999
F = (G / k) + (H* k)
F = (4 / 999) + (4 * 999)
F = 0.004+3996
F = 3996.004
Node 2:
G = 6, H = 2 and k = 4
F = (G / k) + (H* k)
F = (6 / 999) + (2 * 999)
F = 0.006 + 1998
F = 1998.006
-
Custom Decision System
The most obvious way would be to calculate the most number of Wins by each Algorithm and the one which has the most, will be selected as the most optimum.
BUT, this does not select the most optimal algorithm in ALL PARAMETERS
So instead, we want to select that algorithm which is optimum for all parameters.
The process of selecting the optimum Algorithm is as follows:
Step 1: All the algorithms are compared for each parameter and a priority is assigned
accordingly. Example, in case of 'Total nodes examined' the algorithms having a lower
value are assigned higher priority.
Consider:
A* = 8 nodes examined
Modified A* = 6 nodes examined
BFS = 80 nodes examined
DFS = 124 nodes examined
Best FS = 12 nodes examined
Dijkstra = 76 nodes examied.
Therefore,
Modified A* = 6 priority
A* = 5 priority
Best FS = 4... and so on.
This is done for all parameters.
Step 2: Compute the sum of all the priorities of all parameters for each algorithm
Ex.
A* Priority Sum =
(A*-Total Time taken to reach Destination Priority) +
(A*-Total Distance covered to reach Destination Priority) +
(A*-Total Nodes in path Priority) +
(A*-Total Nodes examined Priority) +
(A*-Time Efficiency Priority) +
(A*-Memory Efficiency Priority) +
(A*-Time to execute Priority).
Step 3: Once the sum is obtained by each algorithm, the algorithm with the highest sum wins and is the most optimum algorithm
Step 3.1: If 2 or more algorithms are having the same sum, then the algorithm having higher priority in more number of parameters is selected.
Ex.
A* Priority Sum = 6 + 4 + 3 + 6 + 5 + 4 + 5 = 34
Modified A* Priority Sum = 6 + 4 + 3 + 6 + 6 + 4 + 5 = 34
Now, the priority sum is same, So in this case, the Decision system will look for the most number of parameter wins. A* has emerged victorious in 2 parameters (double 6s) whereas Modified A* has emerged victorious in 3 parameters (Triple 6s). Thus Modified A* is selected as the optimum Algorithm.
Step 3.1.1: If the algorithms have the same number of parameter wins, then the algorithm having a better Execution Time is selected because CPU cycles are precious.