Why do we return the max distance out of the four corners when finding the heuristic for A*?

user238795 0
Viewed 49

I was trying to solve the cs188 ai project-1 search. In cornersHeuristic() function we need to return a heuristic, so that we use it when traversing the corners. And we want to use the shortest path so we use A-star search. Summary of the code to understand it better: We have the locations of the corners in (x,y) format, and we have our characters current location again as (x, y) format. The heuristic returned is maximum distance of the distances between the location to all the corners. But what is the logic here? Shouldn't we return the minimum distance to the nearest corner? Why do we return the max out of these, how does this help to find the shortest path? The code is as below: Some explanations for the code: The corner1, corner2, corner3, corner4, and location variables are all tuples and store x and y values. Such as (1, 1), (4, 5)

def cornersHeuristic(state, problem):

    A heuristic for the CornersProblem that you defined.

      state:   The current search state
               (a data structure you chose in your search problem)

      problem: The CornersProblem instance for this layout.

    This function should always return a number that is a lower bound on the
    shortest path from the state to a goal of the problem; i.e.  it should be
    admissible (as well as consistent).

    corners = problem.corners # These are the corner coordinates
    walls = problem.walls # These are the walls of the maze, as a Grid (game.py)

    location, corner1, corner2, corner3, corner4 = state
    corners = [corner1, corner2, corner3, corner4]
    heuristic = 0
    for x in corners[1]:
        heuristic = max(heuristic,(abs(location[0]-x[0]) + abs(location[1] - x[1])))
    return max_r
heuristics a-star search artificial-intelligence
1 Answers

The heuristic is a lower-bound on the actual distance. You want this lower-bound to be as large as possible, while still being guaranteed to be a lower-bound.

So you're correct that min would work. But max is better, because it's a larger lower-bound.

We can guarantee it will still be a lower-bound because the problem statement is that we want to visit all of the corners. The path-length required to do that will always be at least the cost of visiting the furthest corner. If the problem were to visit any one corner, then we'd need to use min

BlueRaja - Danny Pflughoeft0
Related