search

beefsack / go-astar

Go implementation of the A* search algorithm
MIT License
600 stars 80 forks source link

astar.go will not always choose the optimal path #1

Closed pathway closed 9 years ago

pathway commented 10 years ago

The "Found a path to the goal" condition is checked when expanding neighbours. But to be optimal, this condition should be checked for a node freshly popped from the priority queue instead.

Its taking me longer than Id like to produce a failing testcase, but I can show a simple thought experiment that illustrates the problem. It's not as easy to illustrate in the grid world (and Im not even certain I could illustrate it in that world, because it does not use Edge weights), but your algorithm appears to be designed to be more general that just solving the grids.

Consider a world with Nodes and Edges, Edges each having a cost 

      E
    /  |
  /    |
S---- M

S=Start E=End M=Middle

Edges: S-E is a giant chasm, cost: 10000 S-M and M-E are paved roads. cost: 1

Currently, astar.go would do this. -Push S onto the Queue -Pop S -Expand neighbors of S using Edges -Neighbor E found. END.

Resulting solution would be S-E cost 10000. But optimal solution is S-M-E, cost 2.

pathway commented 10 years ago

If you look at code and pseudocode around the web, you see a mix of both approaches.

"AStar Pseduocode" top hits on google include:

Wikipedia http://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode is like my patch. MIT page http://web.mit.edu/eranki/www/tutorials/search/ uses your existing approach. Game gardens: http://wiki.gamegardens.com/Path_Finding_Tutorial#Pseudo-code_A.2A like my patch. Reference to Nils Nilsson book http://www.edenwaith.com/products/pige/tutorials/a-star.php like my patch

I think the thought experiment is more convincing than web pages, though a failing test would be nice for sure (Im working on it).

beefsack commented 10 years ago

Hi @pathway, thanks for your contribution. Have you had any luck in reproducing with an automated test? I'd love to see that, I'll make an attempt if you haven't had luck but won't be able to spend time on this for a few days.

pathway commented 10 years ago

Test is in progress. It may take me a few days too.

And, thank you very much @beefsack for sharing this code.

pathway commented 10 years ago

Found what appears to be the original literature reference:

Hart, P.E, A Formal Basis for the Heuristic Determination of Minimum Cost Paths Systems Science and Cybernetics, IEEE Transactions on (Volume:4 , Issue: 2 ) July 1968 http://ai.stanford.edu/~nilsson/OnlinePubs-Nils/PublishedPapers/astar.pdf

See II A 3) pp 102.

pathway commented 10 years ago

Test and patch in the pull request https://github.com/beefsack/go-astar/pull/2