<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>

CC BY-SA 4.0
2022-10-04T03:46:47.117Z
Someone asked a very similar question on Stackoverflow just the other day: https://stackoverflow.com/questions/73680177
BlueRaja - Danny Pflughoeft
CC BY-SA 4.0
2022-10-04T14:35:23.987Z
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
Nova
<python><search><heuristics><path-finding><goal-based-agents>
Why is the greedy heuristic admissible and consistent for food at corners problem, but not for food anywhere problem?
Nova
# 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), 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.

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

