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!