UCBerkley has a great Intro to AI course (CS188) where you can practice coding up search algorithms. One of the exercises (question 6), asks to generate a heuristic that will have Pacman find all 4 corners of the grid.
My implementation used a greedy approach that found the closest corner by Manhattan distance, moved Pacman to that corner, and then repeated the process. This is a relaxation of the original problem by removing all the walls. Here is my code below:
def cornersHeuristic(state: Any, problem: CornersProblem):
corners = list(problem.corners) # These are the corner coordinates
position, corners_status = state
bools = [x==0 for x in corners_status]
unexplored_corners = []
for index, bool_val in enumerate((bools)):
if bool_val == True:
unexplored_corners.append(corners[index])
current_sum = 0
while unexplored_corners != []:
dists_temp = []
for corner in unexplored_corners:
d = util.manhattanDistance(position, corner)
dists_temp.append(d)
min_dist = min(dists_temp)
current_sum = current_sum + min_dist
position = unexplored_corners.pop(dists_temp.index(min_dist))
return current_sum
This implementation ended up working correctly and the autograder recognized it as consistent. However, upon closer inspection, I think the autograder made a mistake. Here is an example of where my greedy heuristic would find a path longer than the theoretical shortest path available for Pacman:
The blue line is the path my heuristic would take and the green line is the correct shortest path.
What am I missing here? Why is this heuristic consistent? And why is this greedy heuristic consistent for the corners problem, but not for the "food anywhere" problem? Any visualization showing a simple scenario where it would fail for the "food anywhere" problem would be greatly appreciated since Im a visual learner.
