Body: <p>UCBerkley has a great Intro to AI course (CS188) where you can practice coding up search algorithms. One of the exercises (<a href="https://inst.eecs.berkeley.edu/%7Ecs188/sp22/project1/#question-1-3-points-finding-a-fixed-food-dot-using-depth-first-search" rel="nofollow noreferrer">question 6</a>), asks to generate a heuristic that will have Pacman find all 4 corners of the grid.</p>
  <p>My implementation used a <em>greedy</em> approach that found the closest corner by Manhattan distance, moved Pacman to that corner, and then repeated the process. This is a relaxation of the original problem by removing all the walls. Here is my code below:</p>
  <pre><code>def cornersHeuristic(state: Any, problem: CornersProblem):
  
      corners = list(problem.corners) # These are the corner coordinates
      
      position, corners_status = state
      
      bools = [x==0 for x in corners_status]
      unexplored_corners = []
      
      for index, bool_val in enumerate((bools)):
          if bool_val == True:
              unexplored_corners.append(corners[index])
      
      current_sum = 0    
      while unexplored_corners != []:
          
          dists_temp = []
      
          for corner in unexplored_corners:
          
              d = util.manhattanDistance(position, corner)
              dists_temp.append(d)
          
          min_dist = min(dists_temp)
          current_sum = current_sum + min_dist
          position = unexplored_corners.pop(dists_temp.index(min_dist))
  
      return current_sum 
  </code></pre>
  <p>This implementation ended up working correctly and the autograder recognized it as consistent.
  However, upon closer inspection, I think the autograder made a mistake. Here is an example of where my greedy heuristic would find a path longer than the theoretical shortest path available for Pacman:</p>
  <p>The blue line is the path my heuristic would take and the green line is the correct shortest path.</p>
  <p><a href="https://i.sstatic.net/7GbGZ.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/7GbGZ.png" alt="enter image description here" /></a></p>
  <p>What am I missing here? Why is this heuristic consistent? <strong>And why is this greedy heuristic consistent for the corners problem, but not for the &quot;food anywhere&quot; problem?</strong> Any visualization showing a simple scenario where it would fail for the &quot;food anywhere&quot; problem would be greatly appreciated since Im a visual learner.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-10-04T03:46:47.117Z
Comments.Text: Someone asked a very similar question on Stackoverflow just the other day: https://stackoverflow.com/questions/73680177
Comments.UserDisplayName: BlueRaja - Danny Pflughoeft
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-10-04T14:35:23.987Z
Comments.Text: I disagree. My question is asking why this greedy heuristic is consistent and I provided a figure showing how its not a lower bound on the closest manhattan distance
Comments.UserDisplayName: Nova
Tags: <python><search><heuristics><path-finding><goal-based-agents>
Title: Why is the greedy heuristic admissible and consistent for food at corners problem, but not for food anywhere problem?
UserDisplayName: Nova
ThreadText: # Why is the greedy heuristic admissible and consistent for food at corners problem, but not for food anywhere problem?
  
  (Asked by: username_0 on 2022-10-04)
  
  UCBerkley has a great Intro to AI course (CS188) where you can practice coding up search algorithms. One of the exercises ([question 6](https://inst.eecs.berkeley.edu/%7Ecs188/sp22/project1/#question-1-3-points-finding-a-fixed-food-dot-using-depth-first-search)), asks to generate a heuristic that will have Pacman find all 4 corners of the grid.
  
  My implementation used a *greedy* approach that found the closest corner by Manhattan distance, moved Pacman to that corner, and then repeated the process. This is a relaxation of the original problem by removing all the walls. Here is my code below:
  
  ```
  def cornersHeuristic(state: Any, problem: CornersProblem):
  
      corners = list(problem.corners) # These are the corner coordinates
      
      position, corners_status = state
      
      bools = [x==0 for x in corners_status]
      unexplored_corners = []
      
      for index, bool_val in enumerate((bools)):
          if bool_val == True:
              unexplored_corners.append(corners[index])
      
      current_sum = 0    
      while unexplored_corners != []:
          
          dists_temp = []
      
          for corner in unexplored_corners:
          
              d = util.manhattanDistance(position, corner)
              dists_temp.append(d)
          
          min_dist = min(dists_temp)
          current_sum = current_sum + min_dist
          position = unexplored_corners.pop(dists_temp.index(min_dist))
  
      return current_sum 
  
  ```
  
  This implementation ended up working correctly and the autograder recognized it as consistent.
  However, upon closer inspection, I think the autograder made a mistake. Here is an example of where my greedy heuristic would find a path longer than the theoretical shortest path available for Pacman:
  
  The blue line is the path my heuristic would take and the green line is the correct shortest path.
  
  [![enter image description here](https://i.sstatic.net/7GbGZ.png)](https://i.sstatic.net/7GbGZ.png)
  
  What am I missing here? Why is this heuristic consistent? **And why is this greedy heuristic consistent for the corners problem, but not for the "food anywhere" problem?** Any visualization showing a simple scenario where it would fail for the "food anywhere" problem would be greatly appreciated since Im a visual learner.
  
  **Tags:** python, search, heuristics, path-finding, goal-based-agents
  
  > **Comments:**
  > **username_1**: Someone asked a very similar question on Stackoverflow just the other day: https://stackoverflow.com/questions/73680177  
  > **username_0**: I disagree. My question is asking why this greedy heuristic is consistent and I provided a figure showing how its not a lower bound on the closest manhattan distance  
  
  ---
  
  ## 0 answers
  
  