Damn, isn't A* fun and intuitive?

I'd be interesting to dive into bounds and good properties for sets of landmarks.

I imagine that if, - Every node is at least X cost/distance away from a landmark - Landmarks are no closer than Y cost/distance from each other

You can start promising a lot about the size of your open set on any execution.

A* on h* (perfect heuristic) takes O(l) where l is the length of the solution (could expand exactly l nodes, but solving/guessing ties incorrectly might bump this to a multiple around the avg edges per vertex). I imagine that having good bounds mean you'll take no longer than a certain amount of expansions/depth before you lock-into the railway that h* provides (and you need some extra work to get off it too).