×

{ASPeRiX}, a first-order forward chaining approach for answer set computing. (English) Zbl 1379.68075

Summary: The natural way to use Answer Set Programming (ASP) to represent knowledge in Artificial Intelligence or to solve a combinatorial problem is to elaborate a first-order logic program with default negation. In a preliminary step, this program with variables is translated in an equivalent propositional one by a first tool: the grounder. Then, the propositional program is given to a second tool: the solver. This last one computes (if they exist) one or many answer sets (stable models) of the program, each answer set encoding one solution of the initial problem. Until today, almost all ASP systems apply this two steps computation. In this article, the project {ASPeRiX} is presented as a first-order forward chaining approach for Answer Set Computing. This project was among the first to introduce an approach of answer set computing that escapes the preliminary phase of rule instantiation by integrating it in the search process. The methodology applies a forward chaining of first-order rules that are grounded on the fly by means of previously produced atoms. Theoretical foundations of the approach are presented, the main algorithms of the ASP solver {ASPeRiX} are detailed and some experiments and comparisons with existing systems are provided.

MSC:

68N17 Logic programming
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68T30 Knowledge representation
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] AlvianoM., CalimeriF., FaberW., IanniG. and LeoneN.2011. Function symbols in ASP: Overview and perspectives. In Nonmonotonic Reasoning, Essays Celebrating its 30th Anniversary, Vol. 31, G.Brewka, V.Marek, and M.Truszczynski, Eds. Studies in Logic, College Publications, 1-24.
[2] AlvianoM., DodaroC., FaberW., LeoneN. and RiccaF.2013. WASP: A native ASP solver based on constraint learning. In Proc. of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’13), P.Cabalar and T. C.Son, Eds. LNCS, vol. 8148. Springer, 55-67.10.1007/978-3-642-40564-8 · Zbl 1272.68012 · doi:10.1007/978-3-642-40564-8
[3] AlvianoM., FaberW. and LeoneN.2010. Disjunctive ASP with functions: Decidable queries and effective computation. Theory and Practice of Logic Programming10(4-6), 497-512.10.1017/S1471068410000244S1471068410000244 · Zbl 1209.68086 · doi:10.1017/S1471068410000244
[4] BalducciniM.2009. Representing constraint satisfaction problems in answer set programming. In Proc. of the Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP’09). W.Faber and J.Lee, Eds. 16-30.
[5] BaralC.2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press. · Zbl 1056.68139
[6] BaseliceS., BonattiP. and GelfondM.2005. Towards an integration of answer set and constraint solving. In Proc. of the 21st International Conference on Logic Programming (ICLP’05), M.Gabbrielli and G.Gupta, Eds. LNCS, vol. 3668. Springer, 52-66. · Zbl 1165.68481
[7] BaseliceS. and BonattiP. A.2010. A decidable subclass of finitary programs. Theory and Practice of Logic Programming10(4-6), 481-496.10.1017/S1471068410000232S1471068410000232 · Zbl 1205.68114 · doi:10.1017/S1471068410000232
[8] BuccafurriF., LeoneN. and RulloP.2000. Enhancing disjunctive datalog by constraints. IEEE Transactions on Knowledge and Data Engineering12(5), 845-860.10.1109/69.877512 · doi:10.1109/69.877512
[9] CalimeriF., CozzaS., IanniG. and LeoneN.2008. Computable functions in ASP: Theory and implementation. In Proc. of the 24th International Conference on Logic Programming (ICLP’08), M. G.de la Banda and E. Pontelli, Eds. LNCS, vol. 5366. Springer, 407-424.
[10] CalimeriF., CozzaS., IanniG. and LeoneN.2011. Finitely recursive programs: Decidability and bottom-up computation. AI Communications24(4), 311-334. · Zbl 1235.68223
[11] CalimeriF., IanniG. and RiccaF.2014. The third open answer set programming competition. Theory and Practice of Logic Programming14(1), 117-135.10.1017/S1471068412000105 · doi:10.1017/S1471068412000105
[12] CalimeriF., PerriS. and RiccaF.2008. Experimenting with parallelism for the instantiation of ASP programs. Journal of Algorithms63(1-3), 34-54.10.1016/j.jalgor.2008.02.003 · Zbl 1151.68356 · doi:10.1016/j.jalgor.2008.02.003
[13] Dal PalùA., DovierA., PontelliE. and RossiG.2009. Gasp: Answer set programming with lazy grounding. Fundamenta Informaticae96(3), 297-322. · Zbl 1207.68118
[14] Dao-TranM., EiterT., FinkM., WeidingerG. and WeinzierlA.2012. OMiGA: An open minded grounding on-the-fly answer set solver. In Proc. of the 13th European Conference on Logics in Artificial Intelligence (JELIA’12), Luis Fariñas del Cerro, Andreas Herzig and Jérôme Mengin, Eds. LNAI, vol. 7519. Springer, 480-483.
[15] EiterT., LuJ. J. and SubrahmanianV. S.1997. Computing non-ground representations of stable models. In Proc. of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’97), J.Dix, U.Furbach, and A.Nerode, Eds. LNCS, vol. 1265. Springer, 198-217.10.1007/3-540-63255-7 · doi:10.1007/3-540-63255-7
[16] FaberW., LeoneN. and PerriS.2012. The intelligent grounder of DLV. In Correct Reasoning - Essays on Logic-Based AI in Honour of Vladimir Lifschitz, E.Erdem, J.Lee, Y.Lierler, and D.Pearce, Eds. LNCS, vol. 7265. Springer, 247-264.
[17] FaberW., LeoneN. and PfeiferG.1999. Pushing goal derivation in dlp computations. In Proc. of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’99), M.Gelfond, N.Leone and G.Pfeifer, Eds. LNCS, vol. 1730. Springer, 177-191.10.1007/3-540-46767-X · doi:10.1007/3-540-46767-X
[18] FerrarisP., LeeJ. and LifschitzV.2007. A new perspective on stable models. In Proc. of the 20th International Joint Conference on Artificial Intelligence (IJCAI’07). R.Sangal, H.Mehta and R. K.Bagga, Eds. Morgan, Kaufmann Publishers Inc., San Francisco, CA, USA, 372-379.
[19] GebserM., KaminskiR., KaufmannB., OstrowskiM., SchaubT. and ThieleS.2008. Engineering an incremental ASP solver. In Proc. of the 24th International Conference on Logic Programming (ICLP’08), M. Garciade la Banda and E.Pontelli, Eds. LNCS, vol. 5366. Springer, 190-205. · Zbl 1185.68159
[20] GebserM., KaminskiR., KönigA. and SchaubT.2011. Advances in gringo Series 3. In Proc. of 11th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’11), J. P.Delgrande and W.Faber, Eds. LNCS, vol. 6645. Springer, 345-351.10.1007/978-3-642-20895-9 · Zbl 1214.68009 · doi:10.1007/978-3-642-20895-9
[21] GebserM., KaufmannB. and SchaubT.2012. Conflict-driven answer set solving: From theory to practice. Artificial Intelligence187, 52-89. · Zbl 1251.68060
[22] GebserM., SchaubT. and ThieleS.2007. GrinGo: A new grounder for answer set programming. In Proc. of the 9th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’07). LNCS, vol. 4483. Springer, 266-271.
[23] GelfondM. and LifschitzV.1988. The stable model semantics for logic programming. In Proc. of the 5th International Conference and Symposium on Logic Programming (ICLP’88), R. A.Kowalski and K.Bowen, Eds. The MIT Press, Cambridge, Massachusetts, 1070-1080.
[24] GelfondM. and LifschitzV.1991. Classical negation in logic programs and disjunctive databases. New Generation Computing9(3/4), 365-386.10.1007/BF03037169 · Zbl 0735.68012 · doi:10.1007/BF03037169
[25] GiunchigliaE., LierlerY. and MarateaM.2006. Answer set programming based on propositional satisfiability. Journal of Automated Reasoning36(4), 345-377. · Zbl 1107.68029
[26] GottlobG., MarcusS., NerodeA., SalzerG. and SubrahmanianV. S.1996. A non-ground realization of the stable and well-founded semantics. Theoretical Computer Science166(1-2), 221-262.10.1016/0304-3975(95)00207-3 · Zbl 0872.68108 · doi:10.1016/0304-3975(95)00207-3
[27] GrecoS., MolinaroC. and TrubitsynaI.2013. Logic programming with function symbols: Checking termination of bottom-up evaluation through program adornments. Theory and Practice of Logic Programming13(4-5), 737-752.10.1017/S147106841300046XS147106841300046X · Zbl 1286.68045 · doi:10.1017/S147106841300046X
[28] KonczakK., LinkeT. and SchaubT.2006. Graphs and colorings for answer set programming. Theory and Practice of Logic Programming6, 61-106.10.1017/S1471068405002528S1471068405002528 · Zbl 1109.68081 · doi:10.1017/S1471068405002528
[29] LefèvreC. and NicolasP.2009a. A first order forward chaining approach for answer set computing. In Proc. of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’09), EsraErdem, FangzhenLin and TorstenSchaub, Eds. LNCS, vol. 5753. Springer, 196-208.10.1007/978-3-642-04238-6 · Zbl 1175.68008 · doi:10.1007/978-3-642-04238-6
[30] LefèvreC. and NicolasP.2009b. The first version of a new ASP solver: ASPeRiX. In Proc. of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’09), EsraErdem, FangzhenLin and TorstenSchaub, Eds. LNCS, vol. 5753. Springer, 522-527.10.1007/978-3-642-04238-6 · Zbl 1175.68008 · doi:10.1007/978-3-642-04238-6
[31] LeoneN., PfeiferG., FaberW., EiterT., GottlobG., PerriS. and ScarcelloF.2006. The DLV system for knowledge representation and reasoning. ACM Transactions on Computational Logic7(3), 499-562.10.1145/1149114.1149117 · Zbl 1367.68308 · doi:10.1145/1149114.1149117
[32] LierlerY. and LifschitzV.2009. One more decidable class of finitely ground programs. In Proc. of the 25th International Conference on Logic Programming (ICLP’09), P. M.Hill and D. S.Warren, Eds. LNCS, vol. 5649. Springer, 489-493. · Zbl 1251.68064
[33] LinF. and ZhaoY.2004. ASSAT: Computing answer sets of a logic program by SAT solvers. Artificial Intelligence157(1-2), 115-137.10.1016/j.artint.2004.04.004 · Zbl 1085.68544 · doi:10.1016/j.artint.2004.04.004
[34] LinF. and ZhouY.2007. From answer set logic programming to circumscription via logic of GK. In Proc. of the 20th International Joint Conference on Artificial Intelligence (IJCAI’07), R.Sangal, H.Mehta and R. K.Bagga, Eds. Morgan, Kaufmann Publishers Inc., San Francisco, CA, USA, 441-446.
[35] LiuL., PontelliE., SonT. C. and TruszczynskiM.2010. Logic programs with abstract constraint atoms: The role of computations. Artificial Intelligence174(3-4), 295-315.10.1016/j.artint.2009.11.016 · Zbl 1207.68119 · doi:10.1016/j.artint.2009.11.016
[36] LiuL. and TruszczynskiM.2005. Pbmodels - software to compute stable models by pseudoboolean solvers. In Proc. of the 8th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’05), C.Baral, G.Greco, N.Leone, and G.Terracina, Eds. LNCS, vol. 3662. Springer, 410-415.10.1007/11546207 · Zbl 1086.68002 · doi:10.1007/11546207
[37] NiemeläI.1999. Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence25(3-4), 241-273.10.1023/A:1018930122475 · Zbl 0940.68018 · doi:10.1023/A:1018930122475
[38] OstrowskiM. and SchaubT.2012. ASP modulo CSP: The clingcon system. Theory and Practice of Logic Programming12(4-5), 485-503.10.1017/S1471068412000142S1471068412000142 · Zbl 1260.68066 · doi:10.1017/S1471068412000142
[39] PerriS., ScarcelloF., CatalanoG. and LeoneN.2007. Enhancing dlv instantiator by backjumping techniques. Annals of Mathematics and Artificial Intelligence51(2-4), 195-228.10.1007/s10472-008-9090-9 · Zbl 1138.68019 · doi:10.1007/s10472-008-9090-9
[40] SimonsP., NiemeläI. and SoininenT.2002. Extending and implementing the stable model semantics. Artificial Intelligence138(1-2), 181-234.10.1016/S0004-3702(02)00187-X · Zbl 0995.68021 · doi:10.1016/S0004-3702(02)00187-X
[41] SyrjänenT.1998. Implementation of Local Grounding for Logic Programs for Stable Model semantics. Technical Report, Helsinki University of Technology.
[42] TruszczynskiM.2012. Connecting first-order ASP and the logic FO(ID) through reducts. In Correct Reasoning - Essays on Logic-Based AI in Honour of Vladimir Lifschitz, E.Erdem, J.Lee, Y.Lierler and D.Pearce, Eds. LNCS, vol. 7265. Springer, 543-559.
[43] UllmanJ. D.1989. Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press.
[44] WeinzierlA.2013. Learning non-ground rules for answer-set solving. In Proc. 2nd Workshop on Grounding and Transformations for Theories With Variables (GTTV’13).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.