nach oben

Erschienen in:

2022 | OriginalPaper | Buchkapitel

Deep Learning for the Generation of Heuristics in Answer Set Programming: A Case Study of Graph Coloring

verfasst von : Carmine Dodaro, Davide Ilardi, Luca Oneto, Francesco Ricca

Erschienen in: Logic Programming and Nonmonotonic Reasoning

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Answer Set Programming (ASP) is a well-established declarative AI formalism for knowledge representation and reasoning. ASP systems were successfully applied to both industrial and academic problems. Nonetheless, their performance can be improved by embedding domain-specific heuristics into their solving process. However, the development of domain-specific heuristics often requires both a deep knowledge of the domain at hand and a good understanding of the fundamental working principles of the ASP solvers. In this paper, we investigate the use of deep learning techniques to automatically generate domain-specific heuristics for ASP solvers targeting the well-known graph coloring problem. Empirical results show that the idea is promising: the performance of the ASP solver wasp can be improved.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Epistemic Logic Programs: A Study of Some Properties

Nächstes Kapitel A Qualitative Temporal Extension of Here-and-There Logic

Alviano, M., Dodaro, C., Leone, N., Ricca, F.: Advances in WASP. In: Calimeri, F., Ianni, G., Truszczynski, M. (eds.) LPNMR 2015. LNCS (LNAI), vol. 9345, pp. 40–54. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23264-5_5CrossRef

Andres, B., Biewer, A., Romero, J., Haubelt, C., Schaub, T.: Improving coordinated SMT-based system synthesis by utilizing domain-specific heuristics. In: Calimeri, F., Ianni, G., Truszczynski, M. (eds.) LPNMR 2015. LNCS (LNAI), vol. 9345, pp. 55–68. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23264-5_6CrossRef

Balduccini, M.: Learning and using domain-specific heuristics in ASP solvers. AI Commun. 24(2), 147–164 (2011). https://doi.org/10.3233/AIC-2011-0493MathSciNetCrossRefMATH

Bengio, Y., LeCun, Y., Hinton, G.E.: Deep learning for AI. Commun. ACM 64(7), 58–65 (2021). https://doi.org/10.1145/3448250CrossRef

Brewka, G., Eiter, T., Truszczynski, M.: Answer set programming at a glance. Commun. ACM 54(12), 92–103 (2011). https://doi.org/10.1145/2043174.2043195CrossRef

Calimeri, F., Dodaro, C., Fuscà, D., Perri, S., Zangari, J.: Efficiently coupling the I-DLV grounder with ASP solvers. TPLP 20(2), 205–224 (2020). https://doi.org/10.1017/S1471068418000546MathSciNetCrossRefMATH

Calimeri, F., Gebser, M., Maratea, M., Ricca, F.: Design and results of the fifth answer set programming competition. Artif. Intell. 231, 151–181 (2016). https://doi.org/10.1016/j.artint.2015.09.008MathSciNetCrossRefMATH

Dodaro, C., Gasteiger, P., Leone, N., Musitsch, B., Ricca, F., Schekotihin, K.: Combining answer set programming and domain heuristics for solving hard industrial problems (application paper). TPLP 16(5–6), 653–669 (2016). https://doi.org/10.1017/S1471068416000284MathSciNetCrossRefMATH

Eén, N., Sörensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 502–518. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24605-3_37CrossRef

10.

Erdem, E., Gelfond, M., Leone, N.: Applications of answer set programming. AI Mag. 37(3), 53–68 (2016). https://doi.org/10.1609/aimag.v37i3.2678CrossRef

11.

Gebser, M., Kaufmann, B., Romero, J., Otero, R., Schaub, T., Wanko, P.: Domain-specific heuristics in answer set programming. In: Proceedings of AAAI. AAAI Press (2013)

12.

Goodfellow, I., Bengio, Y., Courville, A.: Deep Learning. MIT Press, Cambridge (2016)

13.

Hawkins, D.M.: The problem of overfitting. J. Chem. Inf. Comput. Sci. 44(1), 1–12 (2004)MathSciNetCrossRef

14.

Hoos, H.H., Lindauer, M., Schaub, T.: claspfolio 2: advances in algorithm selection for answer set programming. TPLP 14(4–5), 569–585 (2014)MATH

15.

Hornik, K., Stinchcombe, M.B., White, H.: Multilayer feedforward networks are universal approximators. Neural Netw. 2(5), 359–366 (1989)CrossRefMATH

16.

Kaufmann, B., Leone, N., Perri, S., Schaub, T.: Grounding and solving in answer set programming. AI Mag. 37(3), 25–32 (2016). https://doi.org/10.1609/aimag.v37i3.2672CrossRef

17.

Kingma, D.P., Ba, J.: Adam: a method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)

18.

Liang, J.H., Oh, C., Mathew, M., Thomas, C., Li, C., Ganesh, V.: Machine learning-based restart policy for CDCL SAT solvers. In: Beyersdorff, O., Wintersteiger, C.M. (eds.) SAT 2018. LNCS, vol. 10929, pp. 94–110. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-94144-8_6CrossRef

19.

Maratea, M., Pulina, L., Ricca, F.: A multi-engine approach to answer-set programming. TPLP 14(6), 841–868 (2014). https://doi.org/10.1017/S1471068413000094MathSciNetCrossRef

20.

Oneto, L.: Model Selection and Error Estimation in a Nutshell. MOST, vol. 15. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-24359-3CrossRefMATH

21.

Rumelhart, D., Hinton, G., Williams, R.: Learning representations by back-propagating errors. Nature 323(6088), 533–536 (1986)CrossRefMATH

22.

Selsam, D., Bjørner, N.: Guiding high-performance SAT solvers with Unsat-core predictions. In: Janota, M., Lynce, I. (eds.) SAT 2019. LNCS, vol. 11628, pp. 336–353. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-24258-9_24CrossRefMATH

23.

Shalev-Shwartz, S., Ben-David, S.: Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, Cambridge (2014)

24.

Taupe, R., Friedrich, G., Schekotihin, K., Weinzierl, A.: Solving configuration problems with ASP and declarative domain specific heuristics. In: Proceedings of CWS/ConfWS, vol. 2945, pp. 13–20. CEUR-WS.org (2021)

25.

Wu, H.: Improving sat-solving with machine learning. In: Proceedings of SIGCSE, pp. 787–788. ACM (2017)

26.

Xu, L., Hoos, H.H., Leyton-Brown, K.: Predicting satisfiability at the phase transition. In: Proceedings of AAAI. AAAI Press (2012)

Titel: Deep Learning for the Generation of Heuristics in Answer Set Programming: A Case Study of Graph Coloring
verfasst von: Carmine Dodaro
Davide Ilardi
Luca Oneto
Francesco Ricca
Verlag: Springer International Publishing
Buch: Logic Programming and Nonmonotonic Reasoning
Print ISBN: 978-3-031-15706-6

Electronic ISBN: 978-3-031-15707-3

Copyright-Jahr: 2022
DOI: https://doi.org/10.1007/978-3-031-15707-3_12

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner