Skip to main content

2017 | OriginalPaper | Buchkapitel

Blending Lazy-Grounding and CDNL Search for Answer-Set Solving

verfasst von : Antonius Weinzierl

Erschienen in: Logic Programming and Nonmonotonic Reasoning

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

Efficient state-of-the-art answer-set solvers are two-phased: first grounding the input program, then applying search based on conflict-driven nogood learning (CDNL). The latter provides superior search performance but the former causes exponential memory requirements for many ASP programs. Lazy-grounding avoids this grounding bottleneck but exhibits poor search performance. The approach here aims for the best of both worlds: grounding and solving are interleaved, but there is a solving component distinct from the grounding component. The solving component works on (ground) nogoods, employs conflict-driven first-UIP learning and enables heuristics. Guessing is on atoms that represent applicable rules, atoms may be one of true, false, or must-be-true, and nogoods have a distinguished head literal. The lazy-grounding component is loosely coupled to the solver and may yield more ground instances than necessary, which avoids re-grounding whenever the solver moves from one search branch to another. The approach is implemented in the new ASP solver Alpha.

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!

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!

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!

Literatur
1.
Zurück zum Zitat Alviano, M., Dodaro, C., Faber, W., Leone, N., Ricca, F.: WASP: a native ASP solver based on constraint learning. In: Cabalar, P., Son, T.C. (eds.) LPNMR 2013. LNCS (LNAI), vol. 8148, pp. 54–66. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40564-8_6 CrossRef Alviano, M., Dodaro, C., Faber, W., Leone, N., Ricca, F.: WASP: a native ASP solver based on constraint learning. In: Cabalar, P., Son, T.C. (eds.) LPNMR 2013. LNCS (LNAI), vol. 8148, pp. 54–66. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-40564-8_​6 CrossRef
2.
Zurück zum Zitat Balduccini, M., Lierler, Y., Schüller, P.: Prolog and ASP inference under one roof. In: Cabalar, P., Son, T.C. (eds.) LPNMR 2013. LNCS (LNAI), vol. 8148, pp. 148–160. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40564-8_15 CrossRef Balduccini, M., Lierler, Y., Schüller, P.: Prolog and ASP inference under one roof. In: Cabalar, P., Son, T.C. (eds.) LPNMR 2013. LNCS (LNAI), vol. 8148, pp. 148–160. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-40564-8_​15 CrossRef
3.
Zurück zum Zitat Calimeri, F., Fuscà, D., Perri, S., Zangari, J.: I-DLV: the new intelligent grounder of DLV. In: AI*IA, pp. 192–207 (2016) Calimeri, F., Fuscà, D., Perri, S., Zangari, J.: I-DLV: the new intelligent grounder of DLV. In: AI*IA, pp. 192–207 (2016)
4.
Zurück zum Zitat Dao-Tran, M., Eiter, T., Fink, M., Weidinger, G., Weinzierl, A.: OMiGA : an open minded grounding on-the-fly answer set solver. In: Cerro, L.F., Herzig, A., Mengin, J. (eds.) JELIA 2012. LNCS (LNAI), vol. 7519, pp. 480–483. Springer, Heidelberg (2012). doi:10.1007/978-3-642-33353-8_38 CrossRef Dao-Tran, M., Eiter, T., Fink, M., Weidinger, G., Weinzierl, A.: OMiGA : an open minded grounding on-the-fly answer set solver. In: Cerro, L.F., Herzig, A., Mengin, J. (eds.) JELIA 2012. LNCS (LNAI), vol. 7519, pp. 480–483. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-33353-8_​38 CrossRef
5.
Zurück zum Zitat Dovier, A., Formisano, A., Pontelli, E., Vella, F.: A GPU implementation of the ASP computation. In: Gavanelli, M., Reppy, J. (eds.) PADL 2016. LNCS, vol. 9585, pp. 30–47. Springer, Cham (2016). doi:10.1007/978-3-319-28228-2_3 CrossRef Dovier, A., Formisano, A., Pontelli, E., Vella, F.: A GPU implementation of the ASP computation. In: Gavanelli, M., Reppy, J. (eds.) PADL 2016. LNCS, vol. 9585, pp. 30–47. Springer, Cham (2016). doi:10.​1007/​978-3-319-28228-2_​3 CrossRef
6.
Zurück zum Zitat Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T., Thiele, S.: Engineering an incremental ASP solver. In: Garcia de la Banda, M., Pontelli, E. (eds.) ICLP 2008. LNCS, vol. 5366, pp. 190–205. Springer, Heidelberg (2008). doi:10.1007/978-3-540-89982-2_23 CrossRef Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T., Thiele, S.: Engineering an incremental ASP solver. In: Garcia de la Banda, M., Pontelli, E. (eds.) ICLP 2008. LNCS, vol. 5366, pp. 190–205. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-89982-2_​23 CrossRef
7.
Zurück zum Zitat Gebser, M., Kaufmann, B., Neumann, A., Schaub, T.: clasp: a conflict-driven answer set solver. In: Baral, C., Brewka, G., Schlipf, J. (eds.) LPNMR 2007. LNCS, vol. 4483, pp. 260–265. Springer, Heidelberg (2007). doi:10.1007/978-3-540-72200-7_23 CrossRef Gebser, M., Kaufmann, B., Neumann, A., Schaub, T.: clasp: a conflict-driven answer set solver. In: Baral, C., Brewka, G., Schlipf, J. (eds.) LPNMR 2007. LNCS, vol. 4483, pp. 260–265. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-72200-7_​23 CrossRef
8.
Zurück zum Zitat Gebser, M., Kaufmann, B., Neumann, A., Schaub, T.: Conflict-driven answer set enumeration. In: Baral, C., Brewka, G., Schlipf, J. (eds.) LPNMR 2007. LNCS (LNAI), vol. 4483, pp. 136–148. Springer, Heidelberg (2007). doi:10.1007/978-3-540-72200-7_13 CrossRef Gebser, M., Kaufmann, B., Neumann, A., Schaub, T.: Conflict-driven answer set enumeration. In: Baral, C., Brewka, G., Schlipf, J. (eds.) LPNMR 2007. LNCS (LNAI), vol. 4483, pp. 136–148. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-72200-7_​13 CrossRef
9.
Zurück zum Zitat Gebser, M., Kaufmann, B., Schaub, T.: Conflict-driven answer set solving: from theory to practice. Artif. Intell. 187, 52–89 (2012)MathSciNetCrossRefMATH Gebser, M., Kaufmann, B., Schaub, T.: Conflict-driven answer set solving: from theory to practice. Artif. Intell. 187, 52–89 (2012)MathSciNetCrossRefMATH
11.
Zurück zum Zitat Lefèvre, C., Beatrix, C., Stephan, I., Garcia, L.: Asperix, a first-order forward chaining approach for answer set computing. TPLP 17(3), 266–310 (2017)MathSciNet Lefèvre, C., Beatrix, C., Stephan, I., Garcia, L.: Asperix, a first-order forward chaining approach for answer set computing. TPLP 17(3), 266–310 (2017)MathSciNet
12.
Zurück zum Zitat Lefèvre, C., Nicolas, P.: A first order forward chaining approach for answer set computing. In: Erdem, E., Lin, F., Schaub, T. (eds.) LPNMR 2009. LNCS (LNAI), vol. 5753, pp. 196–208. Springer, Heidelberg (2009). doi:10.1007/978-3-642-04238-6_18 CrossRef Lefèvre, C., Nicolas, P.: A first order forward chaining approach for answer set computing. In: Erdem, E., Lin, F., Schaub, T. (eds.) LPNMR 2009. LNCS (LNAI), vol. 5753, pp. 196–208. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-04238-6_​18 CrossRef
13.
Zurück zum Zitat Lefèvre, C., Nicolas, P.: The first version of a new ASP solver : ASPeRiX. In: Erdem, E., Lin, F., Schaub, T. (eds.) LPNMR 2009. LNCS (LNAI), vol. 5753, pp. 522–527. Springer, Heidelberg (2009). doi:10.1007/978-3-642-04238-6_52 CrossRef Lefèvre, C., Nicolas, P.: The first version of a new ASP solver : ASPeRiX. In: Erdem, E., Lin, F., Schaub, T. (eds.) LPNMR 2009. LNCS (LNAI), vol. 5753, pp. 522–527. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-04238-6_​52 CrossRef
14.
Zurück zum Zitat Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., Scarcello, F.: The DLV system for knowledge representation and reasoning. ACM Trans. Comput. Logic 7, 499–562 (2002)MathSciNetCrossRef Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., Scarcello, F.: The DLV system for knowledge representation and reasoning. ACM Trans. Comput. Logic 7, 499–562 (2002)MathSciNetCrossRef
15.
Zurück zum Zitat Palù, A.D., Dovier, A., Pontelli, E., Rossi, G.: Gasp: answer set programming with lazy grounding. Fundam. Inform. 96(3), 297–322 (2009)MathSciNetMATH Palù, A.D., Dovier, A., Pontelli, E., Rossi, G.: Gasp: answer set programming with lazy grounding. Fundam. Inform. 96(3), 297–322 (2009)MathSciNetMATH
16.
Zurück zum Zitat Teppan, E.C., Friedrich, G.: Heuristic constraint answer set programming. In: ECAI. FAIA, vol. 285, pp. 1692–1693. IOS Press (2016) Teppan, E.C., Friedrich, G.: Heuristic constraint answer set programming. In: ECAI. FAIA, vol. 285, pp. 1692–1693. IOS Press (2016)
17.
Zurück zum Zitat Weinzierl, A.: Learning non-ground rules for answer-set solving. In: Grounding and Transformation for Theories with Variables, pp. 25–37 (2013) Weinzierl, A.: Learning non-ground rules for answer-set solving. In: Grounding and Transformation for Theories with Variables, pp. 25–37 (2013)
Metadaten
Titel
Blending Lazy-Grounding and CDNL Search for Answer-Set Solving
verfasst von
Antonius Weinzierl
Copyright-Jahr
2017
DOI
https://doi.org/10.1007/978-3-319-61660-5_17