How to determine that an heuristic is admissible

Question

An heuristic is admissible if never overestimates the real cost to reach the goal.

In order to prove that an heuristic $h$ is admissible we need to prove that for every state $s$ in the state space we have $h(s)\le h^*(s)$, where $h^*(s)$ is the perfect heuristic.

To prove that a given heuristic is admissible we need to know the perfect heuristic, but if we know the perfect heuristic wouldn't it be useless to search an admissible heuristic?

Are there other ways to prove that an heuristic is admissible?

Answer 1

It is often possible to construct a heuristic which is a provable lower bound on a cost.

For instance, on any path search in a metric space (one with consistent measurements between items), you can calculate the direct distance between two points, and that would be an admissable heuristic for any path-finding search where not all paths are available. This is very easy in grid spaces (Manhatten distance) or Euclidean geometry, which are common settings for path-finding problems.

In general, if your problem is to find a solution to a problem with constraints, you can simplify that problem by removing some or all of the constraints, and use an easy to calculate cost from the simplified problem.