Potential Heuristics as Real-Valued Multilinear Polynomials

Abstract

Potential functions are a compact and easy way to describe heuristics in classical planning. They are declarative, simple to understand, and clear to explain. Further, they are used as a tool to study the computational complexity of planning problems, and have connections to other concepts such as novelty measures and generalized planning. In this work, we cast potential functions as real-valued multilinear polynomials over the Booleans. While this might seem as a simple syntactic game at first glance, this automatically brings insights to the theory of potential heuristics. For example, we show that the multilinear polynomial representation can be computed using Fourier expansions. This immediately gives us a unique representation for each heuristic function, which allows us to study concepts such as correlation complexity more directly. Moreover, this also connects potential heuristics to a whole new field of computer science -- analysis of Boolean functions -- leading to consequences ranging from learning theory to performance prediction.