search

simpleai-team / simpleai

simple artificial intelligence utilities
MIT License
968 stars 250 forks source link

AStar algorithm is implemented incorrectly. #74

Closed calee88 closed 3 years ago

calee88 commented 3 years ago

fringe may not contain a node with a state that is in the memory. If a new candidate node has that state, it can not be added to the fringe.

See python-astar project for a correct implementation: https://github.com/jrialland/python-astar.

fisadev commented 3 years ago

That's not correct. There are two variants of the AStar algorithm: the tree search AStar, and the graph search AStar. The graph search one does what you say, while the tree search one doesn't control repeated states. They both have their advantages and disadvantages, and you should choose the correct one depending on the characteristics of your problem. SimpleAI has both variants implemented, you can specify it with the graph_search parameter of the astar function, which by default is set to False. If you set it to True, you activate the variant with repeated states control.

You can read more about the difference between tree and graph search in the Search chapter of the "Artificial Intelligence, a Modern Approach" book (by Norvig and Russell).

calee88 commented 3 years ago

Okay. Thank you for the explanation.

I knew that the algorithm is incorrect, because I got a non-optimal result. And I know that AStar should give an optimal result, when certain conditions are met. (and they are met for my case)

I've tried to find the exact reason why it is failing. And I found that it is because of the BoundedPriorityQueue class. You should heapify the queue after removing an element from it. See this: https://stackoverflow.com/questions/10162679/python-delete-element-from-heap. If you don't do that, the pop method doesn't pop the smallest node.

By the way, simpleai's implementation is fifty times slower than python-astar's implementation for my case.

fisadev commented 3 years ago

Ok, that does sounds like an issue, I'll check the usage of BPQ. Can you provide an example of the problem class and the result vs the expected result? So I have something to debug with.

With regards to speed, yes, simpleai's implementation is intentionally not optimized because of its main usage: as a teaching tool for university AI courses, in which having a simpler version of the code that students can inspect and understand, is valued over having a highly optimized version that would require far more python knowledge to be able to understand it. That's a trade off that we made given our particular needs :)

calee88 commented 3 years ago

Here is a sample problem notebook that shows the issue. I constructed a random paths, and the original AStar algorithm doesn't give you the optimal solution. Uncomment two lines in a _search function to see what is going wrong.

https://colab.research.google.com/drive/1K8ThQyHe4Ka5BTV6p7_ZDOxFStO7_0Wi?usp=sharing

fisadev commented 3 years ago

This issue was finally solved, and a new release has been made with the fix: Version 0.8.3. Sorry for the delay!