The problem of finding an admissible heuristic with a low branching factor for common search tasks has been extensively researched in the AI community. A number of common techniques are used:
- Solution costs of sub-problems often serve as useful estimates of the overall solution cost. These are always admissible. For example, a heuristic for a 10-puzzle might be the cost of moving tiles 1-5 into their correct places. A common idea is to use a pattern database that stores the exact solution cost of every subproblem instance.
- The solution of a relaxed problem often serves as a useful admissible estimate of the original. For example manhattan distance is a relaxed version of the n-puzzle problem, because we assume we can move each tile to its position in a single step.
- Given a set of admissible heuristic functions , the function is an admissible heuristic that dominates all of them.
Using these techniques a program called ABSOLVER was written (1993) by A.E. Prieditis for automatically generating heuristics for a given problem. ABSOLVER generated a new heuristic for the 8-puzzle better than any pre-existing heuristic and found the first useful heuristic for solving the Rubik's Cube.