search

omron-sinicx / neural-astar

Official implementation of "Path Planning using Neural A* Search" (ICML-21)
https://omron-sinicx.github.io/neural-astar
Other
236 stars 57 forks source link

Is diff a* search admissible? #12

Closed OAHC2022 closed 1 year ago

OAHC2022 commented 1 year ago

Hi,

I am very interested in your work and want to get a good understanding of this code. However, I have a question about how heuristic is implemented here.

I am looking at this line of code in differentiable_astar.py. From my understanding, the heuristic function produces a h value to be greater than 1 while the costmap values are between 0 and 1. If the g_ratio value is set as default (0.5), wouldn't this heuristic value violate the admissible assumption for a*? Yet, when I ran the example code you provided here, the model seemed to be able to train successfully and produce good result. I am not sure why this works. Maybe I am missing something? Could you please help me with this?

Thanks!

yonetaniryo commented 1 year ago

Hi @OAHC2022 , thanks for the question.

That is a good point. As you properly recognized, Neural A* does not satisfy admissibility and as a result, it’s not an optimal solver.

Empirically, Neural A* learns to give costs lower than 1.0 to nodes when the nodes seem to be a part of the shortest paths. So these nodes are more likely to be selected than other nodes, despite the heuristic function is not admissible.

FYI a follow-up work from another group tried to design an admissible version https://arxiv.org/pdf/2105.01480.pdf, which however does not work well yet. I think extending Neural A* to be an optimal solver is an interesting future direction.

OAHC2022 commented 1 year ago

Oh thank you very much! This makes sense :)