Operator-Counting Heuristics for Domain-Independent Dynamic Programming

Abstract

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.