Donald Bren School of Information and Computer Sciences

This paper formally defines the idea of transforming one problem representation into another. The power of changing the problem representation is demonstrated in the context of heuristic generation. We prove that each problem transformation induces an admissible and monotonic heuristic on the original problem. Furthermore we show that every admissible and monotonic heuristic is induced by some problem transformation. This result generalizes and unifies several approaches for heuristic formation reported on in the literature. We give four techniques for generating problem transformations and we apply these techniques to generate several heuristics found in the literature. We also show that changing the problem representation can prove (automatically) that some problems are unsolvable.