Experimenting with Heuristics for Answer Set Programming

Abstract

Answer Set Programming (ASP) is a novel programming paradigm, which allows to solve problems in a simple and highly declarative way. The language of ASP (function-free disjunctive logic programming) is very expressive, and allows to represent even problems of high complexity (every problem in the complexity class
  ). As for SAT solvers, the heuristic for the selection of the branching literal (i.e., the criterion determining the literal to be assumed true at a given stage of the computation) dramatically affects the performance of an ASP system. While heuristics for SAT have received a fair deal of research in AI, only little work in heuristics for ASP has been done so far. In this paper, we extend to the ASP framework a number of heuristics which have been successfully employed in existing systems, and we compare them experimentally. To this end, we implement such heuristics in the ASP system DLV, and we evaluate their respective efficiency on a number of benchmark problems taken from various domains. The experiments show interesting results, and evidence a couple of promising heuristic criteria for ASP, which sensibly outperform the heuristic of DLV.