This week we implemented 4 search algorithms (DFS, BFS, UCS, and A*) in Python using the pseudocode available in the books. Translating the pseudocode to Python was not particularly difficult. We found that most of our time was spent experimenting with and understanding the structure of the starter code.

The Pacman board will show an overlay of the states explored, and the order in which they were explored (brighter red means earlier exploration). Is the exploration order what you would have expected? Does Pacman actually go to all the explored squares on his way to the goal?

Yes, the order is what we expected because it expands to states that lead to a dead-end. The DFS algorithm continues exploring a path until it can’t anymore. However, Pacman does not traverse all squares explored by the DFS algorithm. This is because Pacman takes the shortest path to the goal state (food) and avoids exploring a path that leads to a dead-end.

Screenshots:

Q1.1:

Q1.2:

Q1.3:

Autograder Q1:

Screenshots:

Q2.1

Q2.2

Q2 Autograder

Screenshots:

Q3.1

Q3.2

Q3.3

Q3 Autograder

Screenshots:

Q4.1

Q4 Autograder

This week we completed questions five and six which required us to implement the four corners problem, and a heuristic to accelerate A* search.

Screenshots:

Q5.1:

Q5.2:

Autograder Q5:

Screenshots:

Q6.1

Q6 Autograder

Q6 Heuristic Formulation

The heuristic is consistent because at any time step, we can move in north, south, east, or west by exactly one unit for cost 1. Therefore, at each step, our path cost increases by 1, but what about the heuristic? Because our heuristic relies on the minimum distance between the current position and any corner, it can decrease by at most one per move. Therefore, the heuristic is consistent.

Because every consistent heuristic is admissible, this implies that our heuristic is also admissible.