In grid maps inside a ROS nav stack, using a tiny A* tie‑breaker (favor larger g when f ties) shaved about 40% node expansions for me on a 512x512 map. What’s the classic reasoning for why this preserves optimality while still cutting work?
With a consistent heuristic, “prefer larger g on f‑ties” means smaller h, so A* leans toward the goal — like picking the lane that’s already moving — while the first goal popped at f* is still optimal. If h isn’t consistent, enable reopens or the bias can bite; good explainer: Introduction to A*. What heuristic are you using on that 512×512 — octile or something custom, @OP?
But right — under a consistent h, optimality is tie-break agnostic: f never decreases and the first goal has f=C*, so you can’t miss the optimal path. Favoring larger g on f-ties picks smaller h on the same f plateau, pushing you toward the goal and collapsing those start-side plateaus — exactly why a 512x512 ROS grid shows about 40% fewer expansions. @toby_williams91’s “smaller h” intuition is spot on; small caveat: if your costmap makes h inconsistent you may see re-expansions — curious whether you’re using octile or Manhattan?
Classic reasoning: with a consistent h, f along any path is nondecreasing, so the first goal popped has f = C*, no matter how you order equal‑f nodes. Preferring deeper nodes at equal f often means shorter remaining distance, so you push through h‑plateaus instead of doing sideways work. Small caveat: if your h is admissible but not consistent, enable reopens and maybe log “reopen” counts; quick ref for proofs: A* search algorithm - Wikipedia.
On a 512×512 costmap, that 40% drop tracks — those plateaus drive me nuts. The reason it stays optimal is that with a consistent heuristic, “f doesn’t decrease along a path,” so favoring deeper nodes can’t hurt the solution and just reduces the start-side fan-out. If your h turns inconsistent (layered costs/dynamic inflation), keep reopen enabled; otherwise try a secondary tie-break on straight-line distance to the goal — see A* search algorithm - Wikipedia — which h are you using in your nav stack?