Potential Heuristics as Real-Valued Multilinear Polynomials
Proceedings of the International Conference on Automated Planning and Scheduling · 08.06.2026 · 36 (1) · 372-376
DOI: 10.1609/icaps.v36i1.42848 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the International Conference on Automated Planning and Scheduling, online erschienen am 08.06.2026. Verfasst von Augusto B. Corrêa und 2 weiteren Autor:innen.
Abstract (Originalsprache)
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.
Zitieren
APA
Corrêa, A. B., Dold, S., & Helmert, M. (2026). Potential Heuristics as Real-Valued Multilinear Polynomials. Proceedings of the International Conference on Automated Planning and Scheduling, 36(1), 372-376. https://doi.org/10.1609/icaps.v36i1.42848
Vancouver
Corrêa AB, Dold S, Helmert M. Potential Heuristics as Real-Valued Multilinear Polynomials. Proceedings of the International Conference on Automated Planning and Scheduling. 2026;36(1):372-376. doi:10.1609/icaps.v36i1.42848
BibTeX
@article{Corra2026,
author = {Corrêa, Augusto B. and Dold, Simon and Helmert, Malte},
title = {Potential Heuristics as Real-Valued Multilinear Polynomials},
journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
year = {2026},
volume = {36},
number = {1},
pages = {372--376},
doi = {10.1609/icaps.v36i1.42848}
}
EUVIMED