4 ms·

I feel this is not needed if you tie-break nodes in Open to favour lower h-values. This leads to a node selection bias for deeper paths, which are more likely c

I feel this is not needed if you tie-break nodes in Open to favour lower h-values. This leads to a node selection bias for deeper paths, which are more likely closer to the goal. If you look at runs, this tie breaking makes A* behave like a greedy algorithm in the absence of obstacles and simply follow a straight path if there's one, and act sort of cleverly when there's a small detour.

jvanderbot 2y ago
On a sparse map, you can tune A* all day, but ultimately if your paths involve more than 1) vertices on the obstacles or 2) straight lines from src to (maybe some of) those vertices to goal, you have created suboptimal paths. The idea goes: Best to just search in that space vs iterating over some other space attempting to indirectly coax out the optimal path. The bonus is that VG-based search is very fast b/c it doesn't search over anything but those. It's just everyone already has grids so they probably just would rather use that. That's all I'm claiming. That, and TFA is basically the same as VG-based search. So, yeah, there are infinite ways to find paths, some optimal some not, some doing more work, some doing less. They'll all probably be fine but not all come with books of guarantees. OP has done a good job to intuit an optimal algorithm with fantastic performance guarantees in this setting.
- dietr1ch 2y ago
  > On a sparse map, you can tune A* all day, but ultimately if your paths involve more than 1) vertices on the obstacles or 2) straight lines from src to (maybe some of) those vertices to goal, you have created suboptimal paths. You would still be choosing a node with the best f-value, so you'll get optimal solutions with any admissible heuristic. In a 2D-grid your heuristic should also be consistent, which will result in pretty good behaviour.
  - jvanderbot 2y ago
    I don't think we're disagreeing

jvanderbot 2y ago

On a sparse map, you can tune A* all day, but ultimately if your paths involve more than 1) vertices on the obstacles or 2) straight lines from src to (maybe some of) those vertices to goal, you have created suboptimal paths. The idea goes: Best to just search in that space vs iterating over some other space attempting to indirectly coax out the optimal path. The bonus is that VG-based search is very fast b/c it doesn't search over anything but those. It's just everyone already has grids so they probably just would rather use that. That's all I'm claiming. That, and TFA is basically the same as VG-based search. So, yeah, there are infinite ways to find paths, some optimal some not, some doing more work, some doing less. They'll all probably be fine but not all come with books of guarantees. OP has done a good job to intuit an optimal algorithm with fantastic performance guarantees in this setting.

dietr1ch 2y ago
> On a sparse map, you can tune A* all day, but ultimately if your paths involve more than 1) vertices on the obstacles or 2) straight lines from src to (maybe some of) those vertices to goal, you have created suboptimal paths. You would still be choosing a node with the best f-value, so you'll get optimal solutions with any admissible heuristic. In a 2D-grid your heuristic should also be consistent, which will result in pretty good behaviour.
- jvanderbot 2y ago
  I don't think we're disagreeing