Answer Set Programming (ASP) is a purely declarative formalism developed in the field of logic programming and nonmonotonic reasoning. With ASP, computational problems are encoded by logic programs whose answer sets, corresponding to solutions, are computed by an ASP system. In general, several semantically equivalent programs might be defined for the same problem; however, performance of ASP systems while evaluating them might significantly vary. We propose an approach for automatically transforming an input logic program into an equivalent one that can be evaluated more efficiently. To this aim, one can make use of existing tree-decomposition techniques for rewriting selected rules into a set of multiple ones. The idea is to guide and adaptively apply them on the basis of proper new heuristics, in order to obtain a smart rewriting algorithm to be integrated into an ASP system. The method is rather general: it can be adapted to the system at hand and implement different preference policies. Furthermore, we define a set of new heuristics explicitly tailored at optimizing one of the main phases of the typical ASP computation, namely the grounding process; we make use of them in order to actually implement the approach into the ASP system DLV, and in particular into its grounding subsystem I-DLV, and carry out an extensive experimental activity aimed at assessing the impact of the proposal.

Optimizing answer set computation via heuristic-based decomposition

Calimeri, Francesco;Fuscà, Davide;Perri, Simona;Zangari, Jessica
2018-01-01

Abstract

Answer Set Programming (ASP) is a purely declarative formalism developed in the field of logic programming and nonmonotonic reasoning. With ASP, computational problems are encoded by logic programs whose answer sets, corresponding to solutions, are computed by an ASP system. In general, several semantically equivalent programs might be defined for the same problem; however, performance of ASP systems while evaluating them might significantly vary. We propose an approach for automatically transforming an input logic program into an equivalent one that can be evaluated more efficiently. To this aim, one can make use of existing tree-decomposition techniques for rewriting selected rules into a set of multiple ones. The idea is to guide and adaptively apply them on the basis of proper new heuristics, in order to obtain a smart rewriting algorithm to be integrated into an ASP system. The method is rather general: it can be adapted to the system at hand and implement different preference policies. Furthermore, we define a set of new heuristics explicitly tailored at optimizing one of the main phases of the typical ASP computation, namely the grounding process; we make use of them in order to actually implement the approach into the ASP system DLV, and in particular into its grounding subsystem I-DLV, and carry out an extensive experimental activity aimed at assessing the impact of the proposal.
2018
9783319733043
Answer set programming; Artificial intelligence; ASP in practice; Theoretical Computer Science; Computer Science (all)
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/274940
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 6
social impact