Operator-Counting Heuristics for Domain-Independent Dynamic Programming
Proceedings of the International Conference on Automated Planning and Scheduling · 08.06.2026 · 36 (1) · 294-303
DOI: 10.1609/icaps.v36i1.42839 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the International Conference on Automated Planning and Scheduling, online erschienen am 08.06.2026. Verfasst von Anubhav Singh und 4 weiteren Autor:innen.
Abstract (Originalsprache)
Domain-independent Dynamic Programming (DIDP) recently emerged as a model-and-solve framework. Its performance heavily depends on a user-specified dual bound function. We introduce a way to automatically derive such bounds generalizing operator-counting heuristics from classical planning. The method approximates by how much an operator can change the value of a feature, which we compute using SAT modulo theories (SMT). We tighten the operator-counting LP using invariants derived by Abstract Interpretation. The dual bounds derived this way match well-known domain-specific dual bounds in TSP and Bin Packing. We evaluate our new dual bounds empirically in an established set of benchmarks.
Zitieren
APA
Singh, A., Pommerening, F., Schindler, T., Beck, J. C., & Helmert, M. (2026). Operator-Counting Heuristics for Domain-Independent Dynamic Programming. Proceedings of the International Conference on Automated Planning and Scheduling, 36(1), 294-303. https://doi.org/10.1609/icaps.v36i1.42839
Vancouver
Singh A, Pommerening F, Schindler T, Beck JC, Helmert M. Operator-Counting Heuristics for Domain-Independent Dynamic Programming. Proceedings of the International Conference on Automated Planning and Scheduling. 2026;36(1):294-303. doi:10.1609/icaps.v36i1.42839
BibTeX
@article{Singh2026,
author = {Singh, Anubhav and Pommerening, Florian and Schindler, Tanja and Beck, J. Christopher and Helmert, Malte},
title = {Operator-Counting Heuristics for Domain-Independent Dynamic Programming},
journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
year = {2026},
volume = {36},
number = {1},
pages = {294--303},
doi = {10.1609/icaps.v36i1.42839}
}
EUVIMED