A4: Path Finding

A4: Path Finding

Group Members:

1)     Zachary Daniels - zad7

2)     Nilay Chakraborty - nc541

3)     Zooraze Tariq - zt32

4)     Tanvi Borkar - tab251

  

Github: https://github.com/CG-F15-23-Rutgers/SteerLite

Description:

A* is a graph search algorithm. It consists of two parts for each node in the graph: the g-value (the distance from the initial position/ number of steps) and the h-value (a heuristic estimate of the distance from the goal). These are combined to give the f-value (f = g + h). If h is admissible and consistent, a* is guaranteed to produce an optimal path. The closer the heuristic is to the true distance to goal (assuming the heuristic is consistent and admissible), the fewer the number of nodes that need to be expanded. In this project, we apply the A* algorithm to planning paths in the "SteerLite" world. We show the affect of using different heuristics (Euclidean distance and Manhattan distance), different tie-breaking strategies, penalizing different types of movements (should we treat diagonal steps the same as horizontal and vertical steps?), and different weights in the weighted variant of A*. 

Recordings

Playlist: https://www.youtube.com/playlist?list=PLvNi45_IRtsxxxtXYKDSCKkUYJeSQTZ6s

Part 1:

Euclidean/Search 1:

Euclidean/Search 2:

Manhattan/Search 1:

Manhattan/Search 2:

Part 2:

Euclidean/Search 1/Larger g:

Euclidean/Search 1/Smaller g:

Euclidean/Search 2/Larger g:

Euclidean/Search 2/Smaller g:

Manhattan/Search 1/Larger g:

Manhattan /Search 1/Smaller g:

Manhattan /Search 2/Larger g:

Manhattan /Search 2/Smaller g:

Part 3:

Euclidean/Search 1/Higher Diagonal Cost:

Euclidean/Search 2/Higher Diagonal Cost:

Manhattan/Search 1/Higher Diagonal Cost:

Manhattan /Search 2/Higher Diagonal Cost:

Part 4:

Euclidean/Search 1/Weight 2:

Euclidean/Search 2/Weight 2:

Euclidean/Search 1/Weight 4:

Euclidean/Search 2/Weight 4:

Euclidean/Search 1/Weight 8:

Euclidean/Search 2/Weight 8:

Manhattan/Search 1/Weight 2:

Manhattan /Search 2/Weight 2:

Manhattan /Search 1/Weight 4:

Manhattan /Search 2/Weight 4:

Manhattan /Search 1/Weight 8:

Manhattan /Search 2/Weight 8:

Observations for Parts

Part 1:

Testcase	Manhattan		Euclidean
	Solution Length	Nodes Expanded	Solution Length	Nodes Expanded
Search 1	38	398	26	282
Search 2	89	2014	75	2150

As seen from the observations, manhattan distance as a heuristic expands more nodes as compared to the euclidean distance and the optimal path returned by the Manhattan heuristic is longer than the one returned by Euclidean.

Part 2:

Testcase	Manhattan				Euclidean
	Smaller G		Larger G		Smaller G		Larger G
	Solution Length	Nodes Expanded	Solution Length	Nodes Expanded	Solution Length	Nodes Expanded	Solution Length	Nodes Expanded
Search 1	38	398	38	325	26	282	26	282
Search 2	89	2014	89	1817	75	2151	75	2150

In case of the Manhattan heuristic, the smaller G value for tie breaks behaves in the same way as no tie breaks. When larger G values are used for tie breaks, less nodes are expanded but the solution is of the same length.

For Euclidean heuristics, the number of expanded nodes and length of solutions is same for both the smaller and the larger G values. This is also same as the case where no tie breaks are used.

Part 3:

Testcase	Manhattan		Euclidean
	Solution Length	Nodes Expanded	Solution Length	Nodes Expanded
Search 1	38	325	29	302
Search 2	89	1815	82	2278

In case of Manhattan heuristics, the length of the solution is the same as part 1, but the number of nodes expanded is less than part 1.

However for Euclidean distances, the length of the solution and number of expanded nodes is greater than part 1.

Part 4:

Testcase		Manhattan		Euclidean
	Weight	Solution Length	Nodes Expanded	Solution Length	Nodes Expanded
Search 1	2	38	283	26	194
	4	44	201	33	159
	8	44	171	35	110
Search 2	2	89	837	75	996
	4	89	400	76	415
	8	89	269	77	187

For both the Manhattan and the Euclidean heuristics, as the weight increases, the number of nodes expanded decreases. The length of the solution is almost the same for both of these heuristics, with increase in weight.

Quantitative Analysis for Weighted A*

For A* the evaluation function f(n) is given by,

f(n) = g(n) + h(n)

where g(n) → is the actual cost of reaching the node n from the start node,

            h(n) → is the estimated cost of reaching the goal from the node n

A* gives the best or optimal path when the heuristic cost h(n) is admissible and consistent. When h(n) is less than the actual cost of reaching the goal from n, the algorithm will give the optimal path, but in doing so, it will expand more nodes. When h(n) is equal to the actual cost of reaching the goal from node n, the algorithm will always give the best path, making the algorithm faster. But this scenario is not always possible. When h(n) is greater than the actual cost of reaching the goal from node n, our heuristic is no longer admissible. This means that we are not guaranteed to get the optimal path. But in doing so we expand less number of nodes, making the algorithm faster.

In weighted A* we make the evaluation function more dependent on the heuristic function. As the weight increases, the f(n) becomes more and more dependent on h(n). When the weight is increased, the number of nodes expanded decreases, and the paths may become sub-optimal. This behavior is depicted in the readings observed by running weighted A* using two types of heuristics, Manhattan and Euclidean distances. The readings are recorded in the table given below:

Weight	No. of Expanded Nodes	Heuristic Used	Testcase
2	283	Manhattan	search1
2	837	Manhattan	search2
4	201	Manhattan	search1
4	400	Manhattan	search2
8	171	Manhattan	search1
8	269	Manhattan	search2
2	194	Euclidean	search1
2	996	Euclidean	search2
4	159	Euclidean	search1
4	415	Euclidean	search2
8	110	Euclidean	search1
8	187	Euclidean	search2

We will try to explain the above observations with the help of an example. Suppose that we have two types of terrains in a game: flat and mountains. Suppose we can move directly in a straight line through the mountains to reach our goal, but this requires a lot of effort. Alternatively, we also have the option of traversing around the mountain on the terrain which requires much less effort. Let the cost of moving within the flat terrain be 1 and moving through the mountainous terrain be 3. Hence the search along the mountainous terrain is going to be 3 times more expensive than that around the flat terrain. This means we can move three steps in the flat terrain for every one step in the mountainous terrain. Suppose the total effort to move along the terrain path is less than the total effort to traverse the mountains. When finding a path using an admissible heuristic, the algorithm will always try to find a route along the flat terrain even if an alternative “shorter” (but more expensive) path along the mountainous terrain exists. It will spend time trying to avoid mountainous routes and finding alternatives for them. In this case if we increase the weight of the heuristic by some factor, the time spent in finding the alternatives around mountainous parts will decrease, and as the weight increases the mountainous parts will also be considered because we pay less attention to the effort required traverse a path and place more emphasis on our estimated distance to goal. This path will not be the optimal one. But the algorithm will definitely give results faster because it will expand fewer nodes.

By increasing the heuristic we try to bias the search towards the goal. If heuristic is very large, the algorithm behaves like a Greedy Best First search, which expands the nodes that will take it closer to the goal.

Hence weighted A* is faster and expands less nodes as w increases, but it does not (necessarily) give the optimal path.