Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is A-star guaranteed to give the shortest path in a 2D grid

I am working with A-star algorithm, whereing I have a 2D grid and some obstacles. Now, I have only vertical and horizontal obstacles only, but they could vary densely.

Now, the A-star works well (i.e. shortest path found for most cases), but if I try to reach from the top left corner to the bottom right, then I see sometimes, the path is not shortest, i.e. there is some clumsiness in the path.

The path seem to deviate from the what the shortest should path should be.

Now here is what I am doing with my algorithm. I start from the source, and moving outward while calculating the value of the neighbours, for the distance from source + distance from destination, I keep choosing the minimum cell, and keep repeating until the cell I encounter is the destination, at which point I stop.

My question is, why is A-star not guaranteed to give me the shortest path. Or is it? and I am doing something wrong?

Thanks.

like image 561
Kraken Avatar asked Apr 26 '13 22:04

Kraken


People also ask

Does A * Always return shortest path?

Not necessarily, it depends on your heuristic. See this section in Wikipedia that explains it in detail. To summarize, A* gives an optimal solution if the heuristic is admissable (meaning it never overestimates the cost).

Is a * Search guaranteed to find the optimal route?

With a consistent heuristic, A* is guaranteed to find an optimal path without processing any node more than once and A* is equivalent to running Dijkstra's algorithm with the reduced cost d'(x, y) = d(x, y) + h(y) − h(x).

Is A * always optimal?

A* is complete and optimal on graphs that are locally finite where the heuristics are admissible and monotonic.

WHAT IS A * search used for?

A* Search Algorithm is a simple and efficient search algorithm that can be used to find the optimal path between two nodes in a graph. It will be used for the shortest path finding.


1 Answers

A-star is guaranteed to provide the shortest path according to your metric function (not necessarily 'as the bird flies'), provided that your heuristic is "admissible", meaning that it never over-estimates the remaining distance.

Check this link: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

In order to assist in determining your implementation error, we will need details on both your metric, and your heuristic.

Update:
OP's metric function is 10 for an orthogonal move, and 14 for a diagonal move.

OP's heuristic only considers orthogonal moves, and so is "inadmissible"; it overestimates by ignoring the cheaper diagonal moves.

The only cost to an overly conservative heuristic is that additional nodes are visited before finding the minimum path; the cost of an overly aggressive heuristic is a non-optimal path possibl e being returned. OP should use a heuristic of:

        7 * (deltaX + deltaY)

which is a very slight underestimate on the possibility of a direct diagonal path, and so should also be performant.

Update #2:
To really squeeze out performance, this is close to an optimum while still being very fast:

7 * min(deltaX,deltaY) + 10 * ( max(deltaX,deltaY) - min(deltaX,deltaY) )

Update #3:
The 7 above is derived from 14/2, where 14 is the diagonal cost in the metric.

Only your heuristic changes; the metric is "a business rule" and drives all the rest. If you are interested on A-star for a hexagonal grid, check out my project here: http://hexgridutilities.codeplex.com/

Update #4 (on performance):
My impression of A-star is that it staggers between regions of O(N^2) performance and areas of almost O(N) performance. But this is so dependent on the grid or graph, the obstacle placement, and the start and end points, that it is hard to generalize. For grids and graphs of known particular shapes or flavours there are a variety of more efficient algorithms, but they often get more complicated as well; TANSTAAFL.

like image 169
Pieter Geerkens Avatar answered Sep 18 '22 12:09

Pieter Geerkens