Why allowing diagonal movement would make the A* and Manhattan Distance inadmissible?

Question

I'm slightly confused about diagonal movement in a grid using A* and the Manhattan distance metric. Can someone explain why using diagonal movement makes it inadmissible? Wouldn't going in diagonal movement find a better optimal solution as in take less steps to get to goal state than up down left right or am I missing something?

Answer 1

Much as beaker's comment denotes, Manhattan Distance will over estimate the distance between a state and the states diagonally accessible to it. By definition, a heuristic that over estimates distances is not admissible.

Now, why exactly is this so?

Lets assume your Manhattan Distance procedure looks something like this:

function manhattan_dist(state): 
    y_dist = abs(state.y - goal.y)
    x_dist = abs(state.x - goal.x)
    return (y_dist + x_dist)

Now, consider the case of applying that procedure to the state of (1,1), and assume the goal is at (3,3). This will return the value of 4, which over estimates the actual distance which is 2. Therefore, Manhattan Distance in this situation will not work as an admissible heuristic.

On game boards that allow for diagonal movement Chebyshev Distance is typically used instead. Why?

Consider this new procedure:

function chebyshev dist(state): 
    y_dist = abs(state.y - goal.y)
    x_dist = abs(state.x - goal.x)
    return max(y_dist, x_dist)

Returning to the previous example of (1,1) and (3,3), this procedure will return the value of 2, which is indeed not an overestimation of the actual distance.

Answer 2

While this topic is older I would like to add a different solution that uses the actual fastest free path to the goal if diagonal movement is allowed.

function heuristic(state):
    delta_x = abs(state.x - goal.x)
    delta_y = abs(state.y - goal.y)
    return min(delta_x, delta_y) * sqrt(2) + abs(delta_x - delta_y)

This method returns a heuristic that moves the maximum amount diagonally and the remainder in a straight way to the goal and presents the largest possible heuristic that does not over-estimate the movement costs to the goal.