title: Why isn't my heuristic for the A* algorithm admissible?
body: <p>I am going through the CS 188 availible to the public at <a href="https://www.edx.org/course/uc-berkeleyx/uc-berkeleyx-cs188-1x-artificial-579" rel="nofollow noreferrer">edx.org</a>.  Right now I have to develop a heuristic for an A* search to eat all the pellets as shown here:
  <img src="https://i.imgur.com/txRYGzD.png" alt="Pacman"></p>
  
  <p>My heuristic that I was sure would work, (as both admissible and consistent) went like this:</p>
  
  <ul>
  <li>initialize heuristic accumulator called h to be 0</li>
  <li>initialize pos to be the current position of pacman</li>
  <li>while pellets not eaten:  
  
  <ul>
  <li>get nearest pellet from pos using astar search (Manhattan distance as the heuristic)</li>
  <li>add the distance to h</li>
  <li>remove the pellet from pellets</li>
  <li>set pos to be the position of pellet</li>
  </ul></li>
  </ul>
  
  <p>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.</p>
  
  <p>When I use this algorithm in the autograder, it fails the admissibility test. </p>
  
  <p>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.</p>
  
  <p>So if anyone was able to understand this, and has any ideas your input is greatly appreciated! </p>