×

A parallel memory-efficient epistemic logic program solver: harder, better, faster. (English) Zbl 1485.68036

Summary: As the practical use of answer set programming (ASP) has grown with the development of efficient solvers, we expect a growing interest in extensions of ASP as their semantics stabilize and solvers supporting them mature. Epistemic Specifications, which adds modal operators K and M to the language of ASP, is one such extension. We call a program in this language an epistemic logic program (ELP). Solvers have thus far been practical for only the simplest ELPs due to exponential growth of the search space. We describe a solver that, at the time of its development (mid-2016), was able to solve harder problems better (e.g., without exponentially-growing memory needs w.r.t. K and M occurrences) and faster than any other known ELP solver.

MSC:

68N17 Logic programming
03B42 Logics of knowledge and belief (including belief change)
68T27 Logic in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] ASP Standardization Working Group: ASP-Core-2 input language format, version 2.01c. https://www.mat.unical.it/aspcomp2013/ASPStandardization (2013)
[2] Balai, E.: ELPS (2015), Texas Tech University. Software & documentation available for download at https://github.com/iensen/elps/wiki/
[3] Balai, E., Kahl, P.: Epistemic logic programs with sorts. In: Inclezan, D., Maratea, M. (eds.) Proceedings of the 7th Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2014) (2014)
[4] Balduccini, M.: sismodels (2001), Texas Tech University. See http://www.mbal.tk/ for information
[5] Balduccini, M., Son, T.C. (eds.): Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning—Essays Dedicated to Michael Gelfond on the Occasion of His 65th Birthday, Lecture Notes in Computer Science, vol. 6565. Springer, Berlin (2011) · Zbl 1213.68025
[6] Baral, C.: Knowledge Representation, Reasoning, and Declarative Problem Solving. Cambridge University Press, Cambridge (2003) · Zbl 1056.68139
[7] Bichler, M., Morak, M., Woltran, S.: selp (2018) TU Wien. Software & documentation available for download at http://dbai.tuwien.ac.at/proj/selp/
[8] Bichler, M., Morak, M., Woltran, S.: selp: a single-shot epistemic logic program solver. In: Fandinno, J., Fichte, J.K. (eds.) Proceedings of the 11th Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2018) (2018) · Zbl 1472.68022
[9] Brewka, G., Eiter, T., Truszczyński, M.: Answer set programming at a glance. Commun. ACM 54(12), 92-103 (2011)
[10] Cui, R., Zhang, Z., Zhao, K.: ESParser: an epistemic specification grounder. In: Delgrande, J.P., Faber, W. (eds.) CSSS-12, pp 1823-1827. IEEE Computer Society CPS (2012)
[11] Faber, W., Woltran, S.: Manifold answer-set programs and their applications. In: Balduccini and Son [5], pp. 44-63 · Zbl 1326.68055
[12] Fariñas del Cerro, L., Herzig, A., Su, E.I.: Epistemic equilibrium logic. In: Yang, Q., Wooldridge, M. (eds.) Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015). https://doi.org/10.1093/logcom/exv065. AAAI Press/IJCAI (2015) · Zbl 1432.68453
[13] Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Answer set solving in practice. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers (2012) · Zbl 1251.68060
[14] Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Clingo = ASP + control: preliminary report. In: Kowalski, R.A., Bowen, K.A. (eds.) ICLP 2014. arXiv:1405.3694. The MIT Press, Cambridge (2014) · Zbl 1486.68027
[15] Gelfond, M.: Strong introspection. In: Dean, T.L., McKeown, K. (eds.) AAAI-91, vol. 1, pp. 386-391. AAAI Press/The MIT Press (1991)
[16] Gelfond, M.: Logic programming and reasoning with incomplete information. Ann. Math. Artif. Intell. 12(1-2), 89-116 (1994) · Zbl 0858.68013
[17] Gelfond, M.: New semantics for epistemic specifications. In: Delgrande, J.P., Faber, W. (eds.) LPNMR-11. Lecture Notes in Computer Science, vol. 6645, pp. 260-265. Springer (2011) · Zbl 1327.68249
[18] Gelfond, M., Kahl, Y.: Knowledge Representation, Reasoning, and the Design of Intelligent Agents: the Answer-Set Programming Approach. Cambridge University Press, Cambridge (2014)
[19] Hanks, S., McDermott, D.: Nonmonotonic logic and temporal projection. Artif. Intell. 33(3), 379-412 (1987) · Zbl 0654.68107
[20] Kahl, P.: Refining the Semantics for Epistemic Logic Programs. Ph.D. thesis, Texas Tech University, Lubbock (2014)
[21] Kahl, P., Watson, R., Balai, E., Gelfond, M., Zhang, Y.: The language of epistemic specifications (refined) including a prototype solver. J. Log. Comput. https://doi.org/10.1093/logcom/exv065 (2015) · Zbl 1489.68272
[22] Kahl, P.T., Leclerc, A.P.: Epistemic logic programs with world view constraints. In: Palù, A.D., Tarau, P., Saeedloei, N., Fodor, P. (eds.) Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018), vol. 64. OASIcs (2018)
[23] Kelly, M.: Wviews: A Worldview Solver for Epistemic Logic Programs. Honour’s thesis, University of Western Sydney (2007)
[24] Kelly, M.: Wviews (original version) (2007), University of Western Sydney. Software & documentation available for download at http://staff.scm.uws.edu.au/
[25] Kelly, M.: Wviews (new version) (2018), Michael Kelly. Software & documentation available for download at https://github.com/galactose/wviews
[26] Le, T., Son, T.C.: EP-ASP (2017), New Mexico State University. Software & documentation available for download at https://github.com/tiep/EP-ASP
[27] Leclerc, A.P., Kahl, P.T.: A survey of advances in epistemic logic program solvers. In: Fandinno, J., Fichte, J.K. (eds.) Proceedings of the 11th Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2018) (2018)
[28] Lifschitz, V., Tang, L.R., Turner, H.: Nested expressions in logic programs. Ann. Math. Artif. Intell. 25, 369-389 (1999) · Zbl 0940.68075
[29] Potassco: clingo,gringo (2018), University of Potsdam. Software & documentation available for download at http://potassco.sourceforge.net/
[30] Shen, Y.D., Eiter, T.: Evaluating epistemic negation in answer set programming. Artif. Intell. 237, 115-135 (2016) · Zbl 1358.68278
[31] Smith, D.E., Weld, D.S.: Conformant graphplan. In: Proceedings of the 15th National Conference on Artificial Intelligence/10th Conference on Innovative Applications of Artificial Intelligence, pp 889-896. AAAI-98/IAAI-98, AAAI (1998)
[32] Son, T.C., Le, T., Kahl, P.T., Leclerc, A.P.: On computing world views of epistemic logic programs. In: Sierra, C. (ed.) Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI 2017). IJCAI (2017)
[33] Strasser, A.: EHEX (2018), TU Wien. Software & documentation available for download at https://github.com/hexhex/ehex
[34] Su, E.I.: Extensions of Equilibrium Logic by Modal Concepts. Ph.D. thesis, University of Toulouse, Toulouse (2015)
[35] Truszczyński, M.: Revisiting epistemic specifications. In: Balduccini and Son [5], pp. 315-333 · Zbl 1326.68280
[36] van Harmelen, F., Lifschitz, V., Porter, B. (eds.): Handbook of Knowledge Representation. Foundations of Artificial Intelligence. Elsevier, Amsterdam (2008) · Zbl 1183.68611
[37] Watson, R.G.: An Inference Engine for Epistemic Specifications. Master’s thesis, University of Texas at El Paso (1994)
[38] Zhang, Y.: Computational properties of epistemic logic programs. In: Doherty, P., Mylopoulos, J., Welty, C.A. (eds.) KR-06, pp 308-317. AAAI Press (2006)
[39] Zhang, Z., Wang, B., Zhang, S.: GISolver (2015), Southeast University. Software & documentation available for download at http://cse.seu.edu.cn/people/seu_zzz/indexe.htm
[40] Zhang, Z., Wang, B., Zhang, S.: Logic programming with graded introspection. In: Inclezan, D., Maratea, M. (eds.) ASPOCP 2015 (2015) · Zbl 1375.68038
[41] Zhang, Z., Zhang, S.: Logic programming with graded modality. In: Calimeri, F., Ianni, G., Truszczyński, M. (eds.) LPNMR 2015. Lecture Notes in Artificial Intelligence, vol. 9345. Springer (2015) · Zbl 1467.68030
[42] Zhang, Z., Zhao, K.: ESmodels: an epistemic specification solver. CoRR arXiv:1405.3486 (2014)
[43] Zhang, Z., Zhao, K., Cui, R.: ESmodels: an inference engine of epistemic specifications. In: Luo, J. (ed.) ICTAI 2013, pp 769-774. IEEE (2013)
[44] Zhang, Z., Zhao, K., Cui, R.: ESParser, ESmodels (2014), Southeast University. Software & documentation available for download at http://cse.seu.edu.cn/people/seu_zzz/indexe.htm
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.