Pathfinding using A-star

In this assignment, we implement A-star algorithm for finding the path in a grid environment.

A brief discussion about the A-star algorithm (From wikipedia)

A* uses a best-first search and finds a least-cost path from a given initial node to one goal node (out of one or more possible goals). As A* traverses the graph, it builds up a tree of partial paths. The leaves of this tree (called the open set or fringe) are stored in a priority queue that orders the leaf nodes by a cost function, which combines a heuristic estimate of the cost to reach a goal and the distance traveled from the initial node. Specifically, the cost function is

.

Here, g(n) is the known cost of getting from the initial node to n; this value is tracked by the algorithm. h(n) is a heuristic estimate of the cost to get from n to any goal node. For the algorithm to find the actual shortest path, the heuristic function must be admissible, meaning that it never overestimates the actual cost to get to the nearest goal node. The heuristic function is problem-specific and must be provided by the user of the algorithm.

We first used two heuristics, namely  Manhattan distance and Euclidean distance as they both are admissible and consistent heuristic.  Then we proceeded to compare the results of weighted heuristics. Following are some video clips demonstrating our results.

Using Eucliedian as heuristic

                                      

                                                       Using Manhattan as heuristic

Next, we checked how different ways of resolving the ties(with same lowest f-value) would imapct the solution

                                      

Tie breaking in favour of smaller 'g'

Tie breaking in favour of larger 'g'

In the final part we dicuss how altering the weight of the heuristic function affects the optimality and speed of the search.  Please refer the follwing table which compares the pathlength/#nodesexpanded against various weights of the heuristic. 

We observe that with the increase in the weight of heuristic function, the number of nodes expanded decreases as evident from the table shown above. However, the path returned is not optimal as the path increases with the increase in weights. This is due the fact the heuristic is now no longer admissible.