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

Fix bug for f_new update condition of pq_astar #14

Closed yonetaniryo closed 1 year ago

HareshKarnan commented 1 year ago

Thanks for this PR! could you explain the f_new equation ? I'm finding it hard to understand intuitively.

yonetaniryo commented 1 year ago

Thanks for this PR! could you explain the f_new equation ? I'm finding it hard to understand intuitively.

Sure. Let me explain in the following way.

First of all, open_list in L121 is a priority queue that stores the f value of opened nodes. In L133, v_cost and v_idx are the f value of the selected node and its index, respectively.

You know, f = g + h, and let me describe f_selected = g_selected + h_selected for the selected node and f_neighbor = g_neighbor + h_neighbor for the neighbor nodes of the selected node, where f_selected = v_cost and f_neighbor = f_new in this implementation. Also, g_neighbor = g_selected + c_neighbor, where c_neighbor is a node cost imposed when arriving at the neighbor node and c_neighbor = pred_cost_vct[n_idx].

Now, we can see that f_neighbor = g_selected + c_neighbor + h_neighbor = f_selected - h_selected + c_neighbor + h_neighbor, which is implemented in the following lines. https://github.com/omron-sinicx/neural-astar/blob/fda7e63d9d21031c7985263f22e098cf20a3bcc1/src/neural_astar/planner/pq_astar.py#L138-L143

Maybe renaming v_cost -> f_selected and v_idx -> idx_selected will make it a bit more intuitive?

yonetaniryo commented 1 year ago

Thank you @HareshKarnan for your review and support! Please feel free to raise issues or proposals if you find any.