I am well aware of informed graph / tree search strategies for optimal solutions when one has an admissible heuristic - i.e. one that never overestimates the minimum cost from a node to any goal state.
However, what about when one only has a heuristic that never underestimates the minimum cost from a node to any goal state? (Also: is there a name for such a heuristic?)
What I am currently doing is as follows. I first find some path to a goal state (luckily in my case this is relatively trivial) and record its cost and path as the best cost and path. Then I do a depth-first search, with two modifications. One, I do not stop when I reach a goal state, instead updating the best cost found so far and record the path to get here. Two, anytime I find myself at a node where the sum of the cost to get here and the heuristic is greater than or equal to the best cost found so far, I backtrack. Then at the end I output the best path found.
(Two nice things about this: 1) it's guaranteed to return an optimal solution, 2) if interrupted it has a solution, albeit a suboptimal one)
I've been calling this "iterative shallowing" (as opposed to iterative deepening), but I have no clue as to the actual name.
So: is there a name for this? If so, what is it? Is there a name for a lower-bound heuristic? Is there a name for informed search algorithms using only a lower-bound heuristic?