Hi,
Thank you for maintaining this library. I am reading the implementation of AStarEpsilon in a_star_epsilon.hpp, and I have a question about how the FOCAL priority is maintained when REBUILD_FOCAL_LIST is not enabled.
From my understanding, each node has both an admissible fScore and a secondary focalHeuristic. The fScore is used to decide whether a node belongs to the FOCAL set, while focalHeuristic is used to order nodes inside the FOCAL set.
In the incremental FOCAL update version, when bestFScore increases, newly eligible OPEN nodes are inserted into the FOCAL set. However, when an already discovered state is reached with a better gScore, the implementation updates the node’s gScore and fScore, and updates its position in the OPEN heap, but it seems that the corresponding focalHeuristic is not recomputed. Also, if the node is already in the FOCAL heap, its position in the FOCAL heap does not seem to be updated.
My question is: is this intentional when REBUILD_FOCAL_LIST is disabled?
For example, if focalHeuristic is path-dependent, such as the accumulated number of conflicts along the path, then the same state may have a different focalHeuristic when reached through a different parent. In that case, after updating cameFrom, gScore, and fScore, it seems that focalHeuristic should also be updated, and if the node is already in the FOCAL set, its position in the FOCAL heap should be updated as well.
Would it be more correct to do something like this when a better path to an existing node is found?
Cost newFocalHeuristic =
current.focalHeuristic
- env.focalStateHeuristic(neighbor.state, tentative_gScore)
- env.focalTransitionHeuristic(current.state, neighbor.state,
current.gScore, tentative_gScore);
(*handle).focalHeuristic = newFocalHeuristic;
Then, when REBUILD_FOCAL_LIST is disabled, if the node is already in the FOCAL heap, should its FOCAL heap handle be updated, or should the node be removed from the FOCAL heap and reinserted?
I am wondering whether the current implementation assumes that focalHeuristic is state-dependent only, or whether the incremental FOCAL version is still expected to work correctly for path-dependent FOCAL values.
Thanks!
Hi,
Thank you for maintaining this library. I am reading the implementation of AStarEpsilon in a_star_epsilon.hpp, and I have a question about how the FOCAL priority is maintained when REBUILD_FOCAL_LIST is not enabled.
From my understanding, each node has both an admissible fScore and a secondary focalHeuristic. The fScore is used to decide whether a node belongs to the FOCAL set, while focalHeuristic is used to order nodes inside the FOCAL set.
In the incremental FOCAL update version, when bestFScore increases, newly eligible OPEN nodes are inserted into the FOCAL set. However, when an already discovered state is reached with a better gScore, the implementation updates the node’s gScore and fScore, and updates its position in the OPEN heap, but it seems that the corresponding focalHeuristic is not recomputed. Also, if the node is already in the FOCAL heap, its position in the FOCAL heap does not seem to be updated.
My question is: is this intentional when REBUILD_FOCAL_LIST is disabled?
For example, if focalHeuristic is path-dependent, such as the accumulated number of conflicts along the path, then the same state may have a different focalHeuristic when reached through a different parent. In that case, after updating cameFrom, gScore, and fScore, it seems that focalHeuristic should also be updated, and if the node is already in the FOCAL set, its position in the FOCAL heap should be updated as well.
Would it be more correct to do something like this when a better path to an existing node is found?
Cost newFocalHeuristic =
current.focalHeuristic
current.gScore, tentative_gScore);
(*handle).focalHeuristic = newFocalHeuristic;
Then, when REBUILD_FOCAL_LIST is disabled, if the node is already in the FOCAL heap, should its FOCAL heap handle be updated, or should the node be removed from the FOCAL heap and reinserted?
I am wondering whether the current implementation assumes that focalHeuristic is state-dependent only, or whether the incremental FOCAL version is still expected to work correctly for path-dependent FOCAL values.
Thanks!