Computer Graphics

Group 40 Documentation

A4: Path Finding 

In this assignment, we implemented the A* Search algorithm with both the Euclidean and Manhattan distances. The A* Search can be thought of as the following equation: f(n) = g(n)+ h(n), where g(n) represents the exact cost of the path from the starting point to any vertex n, and h(n) represents heuristic estimated cost from any vertex n to the goal. A* computes f(n) at every node to find the most optimal path. The Euclidean distance can be defined as a straight line between 2 points. The Manhattan distance between two points is the sum of the (absolute) differences of their coordinates. E.g. it only costs 1 unit for a straight move, but 2 if one wants to take a crossed move.

We ran our A* search algorithm across two test cases - Search 1 and Search 2. 

Search 1

Search 2

As can be seen from the images above, Search 2 is more complex than Search 2, in that it is longer in length and has many more diagonals/turns. 

There were four different parts to our project for this week. For Part 1, we executed the test cases under normal conditions. For Part 2, we implemented tie breakers for a larger g and a smaller g (separately). For Part 3, we implemented a higher cost for diagonals and used a larger g to break ties. And lastly, in Part 4, we weighted the heuristic by 2, 4, and 8. For each of these different parts, we documented our results (number of expanded nodes and the path lengths) for each search. 

Results

Table 1: Number of Expanded Nodes

Part	Description	Euclidean Search 1	Euclidean Search 2	Manhattan Search 1	Manhattan Search 2
1	Normal	2188	12106	2104	11887
2	Smaller g	2188	12107	2104	11887
	Larger g	2188	12107	2104	11887
3	Higher d cost; Bigger g for ties	2284	8952	1696	5406
4	h Weight 2	2165	11931	2157	11921
	h Weight 4	2081	11496	2086	11574
	h Weight 8	1938	10768	2002	11054

For Parts 1, 2, and 4, the path lengths are the following:

Search 1 Path Length = 3507.34

Search 2 Path Length = 10398.9

For Part 3, the path lengths are the following:

Search 1 Path Length = 5191.63

Search 2 Path Length = 12358.9

Discussion 

The Manhattan Distance has a higher cost for diagonals, and since our test cases mostly move up, down, left and right, it’s obvious that the number of expanded nodes in the normal condition is less for the Manhattan distance than the Euclidean. For these test cases, as we choose how to break ties based on smaller or larger g, there seems to be no change in the number of expanded nodes. It is also clear from the table that as the heuristic weight increases, the number of expanded nodes decreases for each search type. What’s interesting to note is that as the heuristic weight increases, the Euclidean distance expands less nodes than the Manhattan distance. Thus, as the heuristic weight increases, the shortest path expands less nodes than the path which moves only horizontally and vertically. This is because as h increases, the algorithm becomes greedier at each node, and looks for the next best node, rather than the best distance to the goal. Consequently, the Euclidian distance will provide equal cost for diagonals and find the next best node at the corners of the obstacles, while the Manhattan will move up and down rather than diagonal and use more nodes at the corners of the obstacles.

Additionally, the table shows that increases in the cost of diagonals drastically decreases the number of expanded nodes while increasing the path lengths. This is because the agent will avoid moving diagonally and thus expand much less nodes. And consequently, will increase the path distance as it prefers moving only vertically and horizontally. This is the only part that changed the path significantly since the path length increased; this can be seen in the videos provided above. ­­­­

Check out some of our videos! 

Part 1

·       Euclidean search 1: https://youtu.be/xVCbFbdH_rQ

·       Euclidean search 2: https://youtu.be/kdkg7oS9Pd4

·       Manhattan search 1: https://youtu.be/49dnRvyF-yY

·       Manhattan search 2: https://youtu.be/9SL1TpkhIYc

Part 2

·       Manhattan, smaller g search 1: https://youtu.be/llcDSHg8i5s

·       Manhattan smaller g search 2: https://youtu.be/4HFVgrteI-g

·       Manhattan larger g search 1: https://youtu.be/ijEQ9sZCz8g

·       Manhattan larger g search 2: https://youtu.be/M40jCsFxuXI

·       Euclidean smaller g search 1: https://youtu.be/UT7Vtf4_3Ag

·       Euclidean smaller g search 2: https://youtu.be/FZ1wxkJxmGs

·       Euclidean larger g search 1: https://youtu.be/5ADcxDi6T4U

·       Euclidean larger g search 2: https://youtu.be/RH9OVLHNSZY

Part 3

·       Euclidean search 1: https://youtu.be/Sa9uoKjolaM

·       Euclidean search 2: https://youtu.be/ffGKh3YtItA

·       Manhattan search 1: https://youtu.be/xdNKSOZvPEE

·       Manhattan search 2: https://youtu.be/BPWrqGuVUjM

 Part 4

·       Manhattan weight 2 search 1: https://youtu.be/ltyMCohuT-s

·       Manhattan weight 2 search 2: https://youtu.be/8GcWHVwrOIo

·       Manhattan weight 4 search 1: https://youtu.be/k_BgeZkeo44

·       Manhattan weight 4 search 2: https://youtu.be/4YU_0kH26JQ

·       Manhattan weight 8 search 1: https://youtu.be/ZCerTgYp4IU

·       Manhattan weight 8 search 2: https://youtu.be/zj1PbMcdlC4

·       Euclidean weight 2 search 1: https://youtu.be/zZseKH5Cc8o

·       Euclidean weight 2 search 2: https://youtu.be/RLjyouXTHQk

·       Euclidean weight 4 search 1: https://youtu.be/ZJ0gcqv3czs

·       Euclidean weight 4 search 2: https://youtu.be/Y0xI0_TK-Ss

·       Euclidean weight 8 search 1: https://youtu.be/VeaOjwvfmPc

·       Euclidean weight 8 search 2: https://youtu.be/e2eV9VTSW0E