License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICLP.2012.37
URN: urn:nbn:de:0030-drops-36080
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3608/
Go to the corresponding LIPIcs Volume Portal

Maratea, Marco ; Pulina, Luca ; Ricca, Francesco

Applying Machine Learning Techniques to ASP Solving

pdf-format:
6.pdf (0.5 MB)

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, given the features of the instances in a training set and the solvers performance on these instances, we apply a classification method to inductively learn algorithm selection strategies to be applied to a test set. We report the results of an experiment considering solvers and training and test sets of instances taken from the ones submitted to the "System Track" of the 3rd ASP 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 higher number of instances compared with any solver that entered the 3rd ASP competition.

BibTeX - Entry

@InProceedings{maratea_et_al:LIPIcs:2012:3608,
  author =	{Marco Maratea and Luca Pulina and Francesco Ricca},
  title =	{{Applying Machine Learning Techniques to ASP Solving}},
  booktitle =	{Technical Communications of the 28th International Conference on Logic Programming (ICLP'12)},
  pages =	{37--48},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-43-9},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{17},
  editor =	{Agostino Dovier and V{\'i}tor Santos Costa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3608},
  URN =		{urn:nbn:de:0030-drops-36080},
  doi =		{10.4230/LIPIcs.ICLP.2012.37},
  annote =	{Keywords: Answer Set Programming, Automated Algorithm Selection, Multi-Engine solvers}
}

Keywords: Answer Set Programming, Automated Algorithm Selection, Multi-Engine solvers
Collection: Technical Communications of the 28th International Conference on Logic Programming (ICLP'12)
Issue Date: 2012
Date of publication: 05.09.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI