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

                                                    

Computer Graphics

Group 40 Documentation

A3: Social Forces

                         
Description: In this assignment, we implemented four important function for social forces - calcWallRepulsion, calcAgentRepulsion, calcGoalForce, and calcProximity.

We define social forces as forces that we exert on particles to drive them towards their destination while avoiding agents and obstacles. 

Each of these functions provides the components for the equation: 

social force = collision avoidance + non-penetration + sliding force

We treated walls as obstacles and other agents as agents and solved social force equations for each of these. For agents and walls, the collision avoidance component is considered the proximity force and the non-penetration component as the repulsion force. These are applied back into the social force equation, along with the calcGoalForce which directs the force for the goal destination. 

For each of the following test cases, we applied a scoring script that gave us the overall score for the scene.  

One Way Hallway: 

One Way Hallway Scores: 

total number of agents: 200
avg. number of collisions per agent: 0
    average time spent by one agent: 84.3662
  average energy spent by one agent: 1501.66
 sum of instantaneous accelerations: 9.28161
(alpha, beta, gamma, delta) weights: (50,1,1,1)
                       weighted sum: 50*0 + 1*84.3662 + 1*1501.66 + 1*9.28161 =
1595.31
                        final score: 1595.31

Two Way Hallway: 

Two Way Hallway Scores:

total number of agents: 200
avg. number of collisions per agent: 0
    average time spent by one agent: 73.5943
  average energy spent by one agent: 1213.45
 sum of instantaneous accelerations: 244.974
(alpha, beta, gamma, delta) weights: (50,1,1,1)
                       weighted sum: 50*0 + 1*73.5943 + 1*1213.45 + 1*244.974 = 1532.01
                        final score: 1532.01

Four Way Hallway: 

Four Way Hallway Scores: 

total number of agents: 400
avg. number of collisions per agent: 0.015
    average time spent by one agent: 83.8544
  average energy spent by one agent: 1291.23
 sum of instantaneous accelerations: 487.834
(alpha, beta, gamma, delta) weights: (50,1,1,1)
                       weighted sum: 50*0.015 + 1*83.8544 + 1*1291.23 + 1*487.833 = 1863.67
                        final score: 1863.67

Bottleneck Evacuation:

Bottleneck Evacuation Scores: 

total number of agents: 200
avg. number of collisions per agent: 6.115
    average time spent by one agent: 99.9456
  average energy spent by one agent: 1256.3
 sum of instantaneous accelerations: 2121.33
(alpha, beta, gamma, delta) weights: (50,1,1,1)
                       weighted sum: 50*6.115 + 1*99.9456 + 1*1256.3 + 1*2121.33 = 3783.32
                        final score: 3783.32

Here are some links to view the simulations! 

One Way Hallway: https://www.youtube.com/watch?v=LLyWknD17gk
Two Way Hallway: https://www.youtube.com/watch?v=3zrMY31haKI
Four Way Hallway: https://www.youtube.com/watch?v=JW5SpJrBHBI
Bottleneck Evacuation: https://www.youtube.com/watch?v=cIEwulbXuGU