I am going through the CS 188 available to the public at __edx.org__. Right now I have to develop a heuristic for an A* search to eat all the pellets as shown here:

The heuristic that I was sure would work, (as both admissible and consistent) went like this:

initialize heuristic accumulator called h to be 0

initialize pos to be the current position of Pacman

while pellets not eaten:

get the nearest pellet from pos using astar search (Manhattan distance as the heuristic)

add the distance to h

remove the pellet from pellets

set pos to be the position of pellet

I also cache the previously computed distances so the astar search to find the nearest pellet isn't done if it has already been done before in another computation of a state. It is able to solve the problem very quickly, and the outcome is optimal.

When I use this algorithm in the autograder, it fails the admissibility test.

Don't worry, I am not asking for a solution to the problem, only why my current solution is not admissible? When I go through the example in the picture in my head the heuristic is never overestimating the cost.

So if anyone was able to understand this, and has any ideas your input is greatly appreciated!