{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,15]],"date-time":"2025-02-15T05:16:00Z","timestamp":1739596560512,"version":"3.37.1"},"reference-count":52,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T00:00:00Z","timestamp":1736467200000},"content-version":"unspecified","delay-in-days":9,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Solving a decision theory problem usually involves finding the actions, among a set of possible ones, which optimize the expected reward, while possibly accounting for the uncertainty of the environment. In this paper, we introduce the possibility to encode decision theory problems with Probabilistic Answer Set Programming under the credal semantics via decision atoms and utility attributes. To solve the task, we propose an algorithm based on three layers of Algebraic Model Counting, that we test on several synthetic datasets against an algorithm that adopts answer set enumeration. Empirical results show that our algorithm can manage non-trivial instances of programs in a reasonable amount of time.<\/jats:p>","DOI":"10.1017\/s1471068424000474","type":"journal-article","created":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T08:20:23Z","timestamp":1736497223000},"page":"33-63","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Solving Decision Theory Problems with Probabilistic Answer Set Programming"],"prefix":"10.1017","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7133-2673","authenticated-orcid":false,"given":"DAMIANO","family":"AZZOLINI","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3717-3779","authenticated-orcid":false,"given":"ELENA","family":"BELLODI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"RAFAEL","family":"KIESEL","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1654-9703","authenticated-orcid":false,"given":"FABRIZIO","family":"RIGUZZI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2025,1,10]]},"reference":[{"key":"S1471068424000474_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15707-3_4"},{"key":"S1471068424000474_ref43","first-page":"515","volume-title":"Mathematical Foundations of Computer Science","author":"Meinel","year":"1994"},{"key":"S1471068424000474_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2020.07.004"},{"key":"S1471068424000474_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068408003645"},{"key":"S1471068424000474_ref21","unstructured":"De Raedt, L. , Kimmig, A. and Toivonen, H. 2007. ProbLog: A probabilistic prolog and its application in link discovery. In IJCAI 2007. AAAI Press, vol. 7, 2462\u20132467."},{"key":"S1471068424000474_ref13","doi-asserted-by":"publisher","DOI":"10.1109\/69.877512"},{"key":"S1471068424000474_ref28","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068418000054"},{"key":"S1471068424000474_ref32","first-page":"1","article-title":"Graph bisection with Pareto optimization","volume":"23","author":"Hamann","year":"2018","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"S1471068424000474_ref46","doi-asserted-by":"publisher","DOI":"10.1201\/9781003338192"},{"key":"S1471068424000474_ref6","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008699807402"},{"key":"S1471068424000474_ref14","unstructured":"Bueno, T. P. , Mau\u00e1, D. D. , Barros, L. N. and Cozman, F. G. 2017. Modeling Markov decision processes with imprecise probabilities using probabilistic logic programming. In Proceedings of Machine Learning Research, Proceedings of the Tenth International Symposium on Imprecise Probability: Theories and Applications. PMLR, vol. 62, 49\u201360."},{"key":"S1471068424000474_ref5","unstructured":"Azzolini, D. and Riguzzi, F. 2024. Inference in probabilistic answer set programs with imprecise probabilities via optimization. In N. Kiyavash and J. M. Mooij, Eds. Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence (Proceedings of Machine Learning Research, vol. 244, 225\u2013234."},{"key":"S1471068424000474_ref12","doi-asserted-by":"publisher","DOI":"10.1145\/2043174.2043195"},{"key":"S1471068424000474_ref10","unstructured":"Brewka, G. 2002. Logic programming with ordered disjunction. In (Eds.) Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, July 28 - August 1, Edmonton, Alberta, Canada. AAAI Press\/The MIT Press, 100\u2013105."},{"key":"S1471068424000474_ref1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1978.1675141"},{"key":"S1471068424000474_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30227-8_19"},{"key":"S1471068424000474_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-19488-6"},{"key":"S1471068424000474_ref35","doi-asserted-by":"publisher","DOI":"10.1017\/S147106842200014X"},{"key":"S1471068424000474_ref37","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CP.2021.8"},{"key":"S1471068424000474_ref38","unstructured":"Lagniez, J.-M. , Lonca, E. and Marquis, P. 2016. Improving model counting by leveraging definability. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI\u201916), York, New York, USA. AAAI Press, 751\u2013757."},{"key":"S1471068424000474_ref40","unstructured":"Lee, J. and Yang, Z. 2017. LPMLN, weak constraints, and P-log. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA. AAAI Press, 1170\u20131177."},{"key":"S1471068424000474_ref47","doi-asserted-by":"publisher","DOI":"10.24963\/kr.2022\/31"},{"key":"S1471068424000474_ref23","doi-asserted-by":"publisher","DOI":"10.3115\/1073083.1073085"},{"key":"S1471068424000474_ref48","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/4298.003.0069"},{"key":"S1471068424000474_ref17","unstructured":"Cozman, F. G. and Mau\u00e1, D. D. 2016. The structure and complexity of credal semantics. In CEUR Workshop Proceedings, PLP 2016. CEUR-WS.org, vol. 1661, 3\u201314."},{"key":"S1471068424000474_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s13218-018-0545-9"},{"key":"S1471068424000474_ref20","doi-asserted-by":"publisher","DOI":"10.1613\/jair.989"},{"key":"S1471068424000474_ref45","unstructured":"Oztok, U. and Darwiche, A. 2015. A top-down compiler for sentential decision diagrams. In 24th International Joint Conference on Artificial Intelligence (IJCAI 2015). AAAI Press\/IJCAI, 3141\u20133148,"},{"key":"S1471068424000474_ref25","doi-asserted-by":"publisher","DOI":"10.5555\/3032027.3032070"},{"key":"S1471068424000474_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30106-6_49"},{"key":"S1471068424000474_ref24","doi-asserted-by":"publisher","DOI":"10.24963\/kr.2021\/26"},{"key":"S1471068424000474_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103651"},{"key":"S1471068424000474_ref51","doi-asserted-by":"crossref","unstructured":"Van den Broeck, G. , Thon, I. , van Otterlo, M. and De Raedt, L. 2010. DTProbLog: A decision-theoretic probabilistic prolog. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence. AAAI Press, 1217\u20131222.","DOI":"10.1609\/aaai.v24i1.7755"},{"key":"S1471068424000474_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/9781118763117"},{"key":"S1471068424000474_ref39","unstructured":"Lee, J. and Wang, Y. 2016. Weighted rules under the stable model semantics. In Proceedings of the Fifteenth International Conference on Principles of Knowledge Representation and Reasoning (Cape Town, South Africa). AAAI Press, 145\u2013154."},{"key":"S1471068424000474_ref7","unstructured":"Balai, E. and Gelfond, M. 2016. On the relationship between P-log and LP {MLN}. In Kambhampati, S. , Ed. Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, 9-15 July 2016, New York, NY, USA. IJCAI\/AAAI Press, 915\u2013921."},{"key":"S1471068424000474_ref44","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10428-7"},{"key":"S1471068424000474_ref11","first-page":"187","article-title":"Answer sets and qualitative decision making","volume":"146","author":"Brewka","year":"2003","journal-title":"Synthese"},{"key":"S1471068424000474_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068419000450"},{"key":"S1471068424000474_ref19","unstructured":"Darwiche, A. 2004. New advances in compiling CNF into decomposable negation normal form. In 16th European Conference on Artificial Intelligence (ECAI 2004). IOS Press, 328\u2013332."},{"key":"S1471068424000474_ref50","first-page":"1","article-title":"smProbLog: Stable model semantics in probLog for probabilistic argumentation","volume":"2023","author":"Totis","year":"2023","journal-title":"Theory and Practice of Logic Programming"},{"key":"S1471068424000474_ref52","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2016.06.009"},{"key":"S1471068424000474_ref49","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23708-4_10"},{"key":"S1471068424000474_ref36","doi-asserted-by":"publisher","DOI":"10.1016\/j.jal.2016.11.031"},{"key":"S1471068424000474_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23461-8_37"},{"key":"S1471068424000474_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22152-1_41"},{"key":"S1471068424000474_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01929-6_7"},{"key":"S1471068424000474_ref27","unstructured":"Fierens, D. , Van den Broeck, G. , Bruynooghe, M. and De Raedt, L. 2012. Constraints for probabilistic logic programming. In Proceedings of the NIPS Probabilistic Programming Workshop."},{"volume-title":"Graphs, Dioids and Semirings: New Models and Algorithms","year":"2008","author":"Gondran","key":"S1471068424000474_ref30"},{"key":"S1471068424000474_ref34","unstructured":"Kern-Isberner, G. and Thimm, M. 2010. Novel semantical approaches to relational probabilistic conditionals. In Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning, Toronto, Ontario, Canada. AAAI Press, 382\u2013392."},{"key":"S1471068424000474_ref41","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15918-3_9"},{"key":"S1471068424000474_ref42","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-83189-8"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068424000474","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,14]],"date-time":"2025-02-14T13:25:21Z","timestamp":1739539521000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068424000474\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["S1471068424000474"],"URL":"https:\/\/doi.org\/10.1017\/s1471068424000474","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2025,1]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}