Manhattan distance in A*

Question

I am implementing a NxN puzzle solver using A* search algorithm and using Manhattan distance as a heuristic and I've run into a curious bug (?) which I can't wrap my head around.

Consider these puzzles (0 element being blank space):
(initial)

1 0 2
7 5 4
8 6 3

(goal)

1 2 3
4 5 6
7 8 0

The minumum number of moves to reach solution from initial state is 11. However, my solver, reaches goal in 17 moves.

And therein lies the problem - my puzzle solver mostly solves the solvable puzzles in a correct (minimum) number of moves but for this particular puzzle, my solver overshoots the minimum number of moves and I think I've nailed down the problem to a miscalculation of Manhattan distance in this particular case.

At this link you can see what my solver is doing (on the right) and what a tried-n-tested solver is doing (Brian Borowski's excellent solver, available here).

In the very first move, Brian's solver immediately chooses solution that pushes element 5 up, but my solver has other ideas, and on the stacktrace (given on the link), my solver chooses solution which pushes 2 to the left (since that board's Manhattan distance is lower, the board is on the front of priority queue). I can't see what is the problem and I can't blame my Manhattan distance calculation, since it correctly solves a number of other 3x3 puzzles.

Here is how I calculate the Manhattan distance of a given Board:

/**
 * Calculates sum of Manhattan distances for this board and stores it in private field to promote immutability.
 */
private void calculateManhattanDistance() {
    int manhattanDistanceSum = 0;
    for (int x = 0; x < N; x++) // x-dimension, traversing rows (i)
        for (int y = 0; y < N; y++) { // y-dimension, traversing cols (j)
            int value = tiles[x][y]; // tiles array contains board elements
            if (value != 0) { // we don't compute MD for element 0
                int targetX = (value - 1) / N; // expected x-coordinate (row)
                int targetY = (value - 1) % N; // expected y-coordinate (col)
                int dx = x - targetX; // x-distance to expected coordinate
                int dy = y - targetY; // y-distance to expected coordinate
                manhattanDistanceSum += Math.abs(dx) + Math.abs(dy); 
            } 
        }
    manhattanDistance = manhattanDistanceSum;
}

I would appreciate any insight or idea you may have.

If any additional code is needed, I'll post it right away.

Shied

Are you sure it can't be a bug in your A* implementation, instead of the distance heuristic? – Alexia

Well, I've thought of that, but if you check the stacktrace, I actually think everything works as expected. The solution chosen is the solution with the least cost and that's what we want. The problem is that I calculate the suboptimal move as the best and choose it as path. That's what led me to suspect the distance calculation, but I can't see the error. – Shied

Are you comparing your run against Brian's solver running using only Manhattan distance as the heuristic? Or is Brian's also using linear conflict (see the second reference). It strikes me that MD-wise moving 2 as the first move might indeed make sense, but such a "greedy" approach is often suboptimal. A* is only as good as the heuristic you throw at it – Alexia

That's right - I am using MD-only as the heuristic. I've set the application parameters exactly to match my solver. Can you see any error in given MD calculation. Do you have any suggestion on how to avoid such A* "greediness"? – Shied

Hmm yes, I just tried Brian's solver and indeed, in A* mode with MD only it generates a 11-move solution. So it's not the problem of using MD only. It'd be nice to be able to see the source code of Brian's... – Alexia

Actually, Brian was kind enough to provide the source code (it's on his page) but I didn't want to check it since I'd like to solve this problem without "contamining" my own mental set. So can we conclude that MD-calculation seems ok and the problem is most likely in A* algorithm? – Shied

One more thing - according to this article (en.wikipedia.org/wiki/A*_search_algorithm), I don't see any strategy that would evade greediness - it just consumes the node with the least cost and uses it as the path to solution. – Shied

also the first nodes searched is no indication of what other nodes the algo is going to search (it might abandon that branch), also to test if the heuristic is to blame try halfing it (or simply setting to 0) – Dab

Hmm, true, but then again - we're talking here about the optimum number of moves. It is true there are 8puzzles with more than one optimum path but this puzzle is not such and has only one optimum solution, so any venturing from optimum path results in suboptimal solution (as we have here). Interestingly, when I try to run solver on the same puzzle with Hamming distance, it circulates indefinitely....as I understand it, that should be a clear indication I've botched the A* since both heuristics are by definition complete and admissable, so they should find a solution (if any exists). – Shied

To test your A* you could set heuristic to 0, it will run as if it was Dijkstra algorithm. Dijkstra is guaranteed to return optimal solution unless there are negative weights. – Elaina

Answer 1

I was stuck in the same place sometime back where I was solving this in 17 moves.The problem was that I was only using heuristic h(n) for the A* algorithm and whereas for choosing the next node A* uses manhattan distance(heuristic) + pathcost (cost to reach the node from root called as g(n)) to make the choice. Once you plug in this to the algorithm it works like a charm.

Hope this helps someone who is stuck in the same place.

Eulalia

I can't thank you enough for this! I've been stuck in this for over a day and was about to give up – Amarillo

Answer 2

If your heuristic it's admissible (and it is, check this) than A* always return optimal solution. Can be slower or faster (expand more or less nodes) but it returns the optimal solution.

So, cause your heuristic is admissible the problem must be in A* algorithm implementation.

In addition the fact that its first step it's different from the optimal one is meaningless: the algorithm can correctly performs backtrace to get the correct solution path in the future. All the open nodes are candidates for the next step, not only the child of the current node.

Trailblazer

Thank you for your answer - I would even go so far as to say that while the A* implementation is correct, it seems I am counting something that is neither move count nor path visited count. The algorithm actually now correctly solves all NxN puzzles with good timings and detects infeasible puzzles correctly. I'll be updating my original post soon and provide some code so that we can perhaps spot the bug that's been nagging me for some days now. – Shied