Domain-Specific Heuristics in Answer Set Programming

Martin Gebser, Benjamin Kaufmann, Javier Romero, Ramón Otero, Torsten Schaub, Philipp WankoAAAI 2013 · DOI

Introduction

Answer Set Programming (ASP) has emerged as a powerful paradigm for solving complex combinatorial search problems. While modern ASP solvers like clasp are highly efficient, they typically rely on general-purpose heuristics, such as VSIDS, which prioritize variables based on their recent involvement in logical conflicts. While robust, these "blind" heuristics often ignore the inherent structural knowledge a human modeler might possess about a specific domain. This paper introduces a declarative framework that allows developers to incorporate domain-specific intuition directly into ASP programs, bridging the gap between high-level modeling and low-level search control.

The Heuristic Framework

The core innovation presented is the extension of the ASP modeling language with a dedicated heuristic predicate: _h(atom, modifier, value, priority). This allows users to write logic rules that influence the solver's decide step—the point where it non-deterministically selects the next variable to assign.

The framework introduces four primary modifiers to guide the search:

  • init: Assigns an initial score to an atom, giving it a priority head start.
  • factor: Dynamically scales an atom's current heuristic score.
  • level: Establishes a decision hierarchy, forcing the solver to resolve higher-level atoms before lower-level ones.
  • sign: Recommends a preferred truth value (True or False) for the solver to attempt first.

Because these heuristics are declarative, they are processed during the grounding phase. This enables the creation of conditional heuristics that can adapt based on the problem state, such as prioritizing specific actions in a planning sequence based on temporal order.

Experimental Evaluation

The authors evaluated the framework across a diverse set of challenging benchmarks, including ASP Competition tasks (Sokoban, Hanoi Tower), abductive reasoning (Circuit Diagnosis, Metabolic Network Expansion), and over 3,000 PDDL planning instances from International Planning Competitions.

Key Results and Efficiency Gains

The empirical results demonstrate that even minimal domain knowledge can lead to significant performance improvements. By biasing conflict-driven scores rather than replacing them, the solver retains its ability to recover from poor guesses while benefiting from structural guidance.

Performance comparison in abductive reasoning tasks, highlighting the dramatic speedup in network repair.

In the "Transcriptional Network Repair" task, the application of domain-specific heuristics reduced average runtimes from 101.3 seconds to just 0.8 seconds—a more than 100-fold improvement. Similarly, the level modifier proved highly effective in planning domains by enforcing a logical decision order.

Comparative performance on PDDL planning benchmarks, showing increased instance coverage and reduced runtimes with domain-specific heuristics.

On PDDL benchmarks, the heuristic-enhanced solver successfully solved 1,652 instances, compared to 1,225 for the base solver, while reducing timeouts by nearly 40%. The total average runtime across these domains dropped from 252.8 seconds to 158.9 seconds.

Conclusion

This framework represents a significant milestone in making ASP more practical for real-world applications. By allowing modelers to "nudge" the solver using domain-specific logic, the approach achieves order-of-magnitude speedups without requiring modifications to the solver's source code. Future work may explore the automated learning of these heuristic rules to further reduce the burden on human experts.

Summary updated

BibTeX
@inproceedings{gebser2013domain,
  author = {Martin Gebser and Benjamin Kaufmann and Javier Romero and Ramón Otero and Torsten Schaub and Philipp Wanko},
  title = {{Domain-Specific Heuristics in Answer Set Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8585},
}
Figure