Having in mind the task of improving the solving methods for Answer Set Programming (ASP), there are two usual ways to reach this goal: (i) extending state-of-the-art techniques and ASP solvers, or (ii) designing a new ASP solver from scratch. An alternative to these trends is to build on top of state-of-the-art solvers, and to apply machine learning techniques for choosing automatically the “best” available solver on a per-instance basis.In this paper we pursue this latter direction. We first define a set of cheap-to- compute syntactic features that characterize several aspects of ASP programs. Then, we apply classification methods that, given the features of the instances in a training set and the solvers performance on these instances, inductively learn algorithm selection strategies to be applied to a test set. We report the results of a number of experiments considering solvers and different training and test sets of instances taken from the ones submitted to the “System Track” of the 3rdASP competition. Our analysis shows that, by applying machine learning techniques to ASP solving, it is possible to obtain very robust performance: our approach can solve a significantly higher number of instances compared with any solver that entered the 3rdASP competition.

Applying machine learning techniques to ASP solving / Pulina, Luca; Ricca, Francesco; Maratea, Marco. - CVL 2012/003(2012).

Applying machine learning techniques to ASP solving

Pulina, Luca;
2012

Abstract

Having in mind the task of improving the solving methods for Answer Set Programming (ASP), there are two usual ways to reach this goal: (i) extending state-of-the-art techniques and ASP solvers, or (ii) designing a new ASP solver from scratch. An alternative to these trends is to build on top of state-of-the-art solvers, and to apply machine learning techniques for choosing automatically the “best” available solver on a per-instance basis.In this paper we pursue this latter direction. We first define a set of cheap-to- compute syntactic features that characterize several aspects of ASP programs. Then, we apply classification methods that, given the features of the instances in a training set and the solvers performance on these instances, inductively learn algorithm selection strategies to be applied to a test set. We report the results of a number of experiments considering solvers and different training and test sets of instances taken from the ones submitted to the “System Track” of the 3rdASP competition. Our analysis shows that, by applying machine learning techniques to ASP solving, it is possible to obtain very robust performance: our approach can solve a significantly higher number of instances compared with any solver that entered the 3rdASP competition.
Applying machine learning techniques to ASP solving / Pulina, Luca; Ricca, Francesco; Maratea, Marco. - CVL 2012/003(2012).
File in questo prodotto:
File Dimensione Formato  
Maratea_M_Applying_machine_learning_techniques.pdf

accesso aperto

Tipologia: Versione editoriale (versione finale pubblicata)
Licenza: Non specificato
Dimensione 631.97 kB
Formato Adobe PDF
631.97 kB Adobe PDF Visualizza/Apri

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/11388/263821
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact