A4: A* and Pathfinding

In this assignment we had to implement an A* algorithm with 2 heuristics: one for Euclidean distance and once for Manhattan distance.

Euclidean differences is basically calculated using something reminiscent of the Pythagorean theorem.

Manhattan distance is basically the sum of absolute values of the differences of the components of vectors.

Part 1:

Here was a bare-bones comparison of Euclidean distance vs. Manhattan Distance in A*

Case 1: Euclidean

Case 2: Euclidean

Case 1: Manhattan

Case 2: Manhattan

Here the videos all pretty much look the same and the paths are the same length, but the real difference is in the number of nodes expanded in each algorithm. Manhattan does significantly better in the number of expanded nodes, having a lower number expanded in both test cases.

Part 2:

Here we tested how to handle ties in f values in computing the best path. We have the choice of tie breaking using g scores. Here we tested what changed when the algorithm chose the node with a higher g score or the lower one.

Higher:

Euclidean

Case 1

https://www.youtube.com/watch?v=-vYfMW0nw_o

Case 2

https://www.youtube.com/watch?v=5UZJ_BXaa3I

Manhattan

Case 1

https://www.youtube.com/watch?v=zfZO6EJ7KDY

Case 2

https://www.youtube.com/watch?v=Lk2t93PB6l0

Lower:

Euclidean

Case 1

https://www.youtube.com/watch?v=pe4LNgLAZp0

Case 2

https://www.youtube.com/watch?v=C2Oa1dUpgQ8

Manhattan

Case 1

https://www.youtube.com/watch?v=EqiE18gcacw

Case 2

https://www.youtube.com/watch?v=BUPeH-fM-1c

Here we also observed a lower node expansion number using the Manhattan heuristic, though the number was a little higher when considering a lower g score.

Part 3:

Here we checked what happened when you increased the weight of a diagonal movement

Euclidean

Diagonal weight = 10

Case 1

https://www.youtube.com/watch?v=O87M_ftU7HI

Case 2

https://www.youtube.com/watch?v=WzMhxJCRI8A

Manhattan

Case 1

https://www.youtube.com/watch?v=8Rw6fImAyI8

Case 2

https://www.youtube.com/watch?v=KjgZCrgod-0

Once again, the case of Manhattan using a lower number of expanded nodes held for this part.

Part 4:

Finally, here we checked what happened when you changed the weight of the heuristic cost, doubling it in each run.

Heuristic Weight: 2

Euclidean

Case 1

https://www.youtube.com/watch?v=NWBZsijrrTU

Case 2

https://www.youtube.com/watch?v=WWZlI1i5hpE

Manhattan

Case 1

https://www.youtube.com/watch?v=9znW3Gtuprc

Case 2

https://www.youtube.com/watch?v=erex6lXe2G4

Heuristic Weight: 4

Euclidean

Case 1

https://www.youtube.com/watch?v=vdRH1PuK8gM

Case 2

https://www.youtube.com/watch?v=ozEIDnPl8Bs

Manhattan

Case 1

https://www.youtube.com/watch?v=yKt6xwyySTo

Case 2

https://www.youtube.com/watch?v=uDpzclYiCuE

Heuristic Weight: 8

Euclidean

Case 1

https://www.youtube.com/watch?v=_KARHtUDekw

Case 2

https://www.youtube.com/watch?v=XkdT0kvJYDw

Manhattan

Case 1

https://www.youtube.com/watch?v=JJizwpD5MK4

Case 2

https://www.youtube.com/watch?v=Ji3Y_7qQDKU

Here what was observed was less clear. The Manhattan heuristic seemed to expand more nodes in some test cases, but not others as the heuristic weight increased