EUVIMEDEUVIMED entdecken
Crossref

Potential Heuristics as Real-Valued Multilinear Polynomials

Augusto B. Corrêa, Simon Dold, Malte Helmert

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →