search

AtsushiSakai / PythonRobotics

Python sample codes for robotics algorithms.
https://atsushisakai.github.io/PythonRobotics/
Other
23.42k stars 6.56k forks source link

Hybrid A* planner simulation should be added #54

Closed AtsushiSakai closed 5 years ago

jwdinius commented 6 years ago

I'll have a crack at this in the next couple of weeks. I have implemented in the past so it shouldn't be too difficult. Do you still want this @AtsushiSakai?

AtsushiSakai commented 6 years ago

@jwdinius Hi. Thank you for your suggestion. Yes. I still want it!!. Your PR is welcome.

xinbada007 commented 6 years ago

Hey What's the progress now? Anyone adding the Hybrid-A* simulation?

Just wondering if it just misses the simulation implementation but the algorithm is complete?

AtsushiSakai commented 6 years ago

@xinbada007 I'm waiting a someone's PR.

jwdinius commented 6 years ago

I have been unable to complete this work yet. I will try to have a PR by Christmas @xinbada007 @AtsushiSakai

AtsushiSakai commented 6 years ago

@jwdinius Thank you. Take your time : ) .

jwdinius commented 5 years ago

I haven't forgotten about this. I missed the Christmas timeline, but I will be working on it this weekend @AtsushiSakai @xinbada007

AtsushiSakai commented 5 years ago

@jwdinius Thank you for your comment. Take your time and enjoy the end of the year.

AtsushiSakai commented 5 years ago

@jwdinius Hi. Are you working this issue?

jwdinius commented 5 years ago

I'm sorry @AtsushiSakai, I've been unable to find the time to finish this. If anyone has the time before I can finish, here's a repo I am translating to python https://github.com/informramiz/Hybrid-Astar-search-algorithm.git. I will continue working on it, but I have no estimated time of completion.

zhengzh commented 5 years ago

BFS algorithm in Informaramiz's repo is wrong actually.

jwdinius commented 5 years ago

@zhengzh thanks for the response. The implementation generates reasonable looking paths. What specifically is wrong with the implementation? If you know of something else to use as a starting point, I would be interested to hear about it.

zhengzh commented 5 years ago

@jwdinius , Hi. As we know, in BFS algorithm, we should put every children of a parent node into the queue. He only puts the minimum cost node into the queue (in line), but forgets to put other nodes into the queue. I test the program with the MAZE (not the EMPTY_MAZE) and it gives 60 steps to reach the goal, but in this repo, it uses A algorithm (not hybrid A) and only needs 38 steps to reach the goal, and we know both algorithms should give the same optimal path. I don't know why the file is named as hybrid_breadth_first.cpp, I think BFS won't help decrease expanded nodes. The best and simplest hybrid A* implementation I have found is in this repo https://github.com/AtsushiSakai/HybridAStarTrailer, which is the just the same as the original paper described, although I never learn julia language before, I can still understand the code :smile_cat:.

jwdinius commented 5 years ago

Ok @zhengzh , your points are well-taken. I have looked at the implementation and I will work to translate it to python 3.6. Do we want a more general hybrid a implementation (like the A implementation)? I will do the translation so that the core search algorithm can be easily imported into possible future hybrid a* implementations.

jwdinius commented 5 years ago

https://github.com/AtsushiSakai/PythonRobotics/pull/180 addresses this, so I'm stopping work

AtsushiSakai commented 5 years ago

@jwdinius @zhengzh I merged #180 . Thank you so much for your help!!