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

Question

I am going through the CS 188 availible 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:

My 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 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 heuristic for A* needs to provide a number that is no more than the best possible cost. Your heuristic is a plausible greedy solution that does not guarantee this. Suppose that there is a single line of pellets and the pac-man is slightly off centre on this line. The cheapest solution is work 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 reverse in the longer half of the line.

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

Answer 2

Here is way to set up heuristic which is feasible for your problem. Firstly if your goal is to eat all pellets in minimum distance then your solution is too greedy to achieve a feasible solution for it. Here is way to redesign your heuristic:-

Goal : Eat all pellets in minimum path length.

Heuristic Estimate :

1.> Use A* to calculate all shortest paths from current position to pellets independently.

2.> Cost function: (sum of all unvisited pellets shortest path from current)*2 + total distance from start state.

The Cost function is upper bound .

Note: There can be more efficient way to calculate shortest paths to uneaten pellets at each state. Would need some research.