Why isn't my heuristic for the A* algorithm admissible?

Question

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!

Answer 1

A non-admissible heuristic may overestimate the cost of reaching the goal. It may or may not result in an optimal solution. However, the advantage is that sometimes, a non-admissible heuristic expands much fewer nodes.

A heuristic for A* needs to supply a number that is no more than the best possible cost. Your heuristic is a likely greedy solution that does not guarantee this. Suppose that there is a single line of pellets and the Pacman is slightly off-center on this line. The cheapest solution is working out which end of the line is nearest, eat all the pellets to the end of that line, and then move in the other direction to eat all the other pellets without having to turn in the longer half of the line.

Your greedy heuristic moves first to whichever pellet is nearest the Pacman which might not be the side that has the shortest distance, so in this case, it may not return a cost any greater than the optimal cost - it returns the cost of a possible solution which may not be optimal.

If you wish to learn about AI algorithm then visit this Artificial Intelligence Course.