{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T22:01:22Z","timestamp":1747173682111,"version":"3.40.5"},"reference-count":32,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2023,7,21]],"date-time":"2023-07-21T00:00:00Z","timestamp":1689897600000},"content-version":"unspecified","delay-in-days":20,"URL":"http:\/\/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":[[2023,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We establish a novel relation between delete-free planning, an important task for the AI planning community also known as relaxed planning, and logic programming. We show that given a planning problem, all subsets of actions that could be ordered to produce relaxed plans for the problem can be bijectively captured with stable models of a logic program describing the corresponding relaxed planning problem. We also consider the supported model semantics of logic programs, and introduce one causal and one diagnostic encoding of the relaxed planning problem as logic programs, both capturing relaxed plans with their supported models. Our experimental results show that these new encodings can provide major performance gain when computing optimal relaxed plans, with our diagnostic encoding outperforming state-of-the-art approaches to relaxed planning regardless of the given time limit when measured on a wide collection of STRIPS planning benchmarks.<\/jats:p>","DOI":"10.1017\/s1471068423000273","type":"journal-article","created":{"date-parts":[[2023,7,21]],"date-time":"2023-07-21T08:45:50Z","timestamp":1689929150000},"page":"782-796","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Capturing (Optimal) Relaxed Plans with Stable and Supported Models of Logic Programs"],"prefix":"10.1017","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5660-3052","authenticated-orcid":false,"given":"MASOOD FEYZBAKHSH","family":"RANKOOH","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2029-7708","authenticated-orcid":false,"given":"TOMI","family":"JANHUNEN","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2023,7,21]]},"reference":[{"key":"S1471068423000273_ref15","doi-asserted-by":"crossref","unstructured":"Haslum, P. , Slaney, J. K. and Thi\u00e9baux, S. 2012. Minimal landmarks for optimal delete-free planning. In Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling, ICAPS 2012. AAAI Press, 353\u2013357.","DOI":"10.1609\/icaps.v22i1.13534"},{"key":"S1471068423000273_ref27","unstructured":"Robinson, N. , McIlraith, S. A. and Toman, D. 2014. Cost-based query optimization via AI planning. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27\u201331, 2014, Qu\u00e9bec City, Qu\u00e9bec, Canada. AAAI Press, 2344\u20132351."},{"key":"S1471068423000273_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23264-5_31"},{"key":"S1471068423000273_ref16","doi-asserted-by":"publisher","DOI":"10.1609\/icaps.v19i1.13370"},{"key":"S1471068423000273_ref25","doi-asserted-by":"crossref","unstructured":"Rankooh, M. F. and Rintanen, J. 2022b. Efficient encoding of cost optimal delete-free planning as SAT. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Virtual Event, February 22 \u2013 March 1, 2022. AAAI Press, 9910\u20139917.","DOI":"10.1609\/aaai.v36i9.21228"},{"key":"S1471068423000273_ref14","unstructured":"Haslum, P. 2015. Hsp* code and documentation. http:\/\/users.cecs.anu.edu.au\/patrik\/un-hsps.html."},{"key":"S1471068423000273_ref6","doi-asserted-by":"crossref","unstructured":"Corr\u00eaa, A. B. , Franc\u00e8s, G. , Pommerening, F. and Helmert, M. 2021. Delete-relaxation heuristics for lifted classical planning. In Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling, ICAPS 2021, Guangzhou, China (virtual), August 2-13, 2021. AAAI Press, 94\u2013102.","DOI":"10.1609\/icaps.v31i1.15951"},{"key":"S1471068423000273_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/s13218-018-0546-8"},{"key":"S1471068423000273_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00187-X"},{"volume-title":"Automated planning - theory and practice","year":"2004","author":"Ghallab","key":"S1471068423000273_ref12"},{"key":"S1471068423000273_ref20","doi-asserted-by":"crossref","unstructured":"Lifschitz, V. 1999. Answer set planning. In Proceedings of ICLP 1999, 23\u201337.","DOI":"10.1007\/3-540-46767-X_28"},{"key":"S1471068423000273_ref32","doi-asserted-by":"publisher","DOI":"10.1145\/1183278.1183279"},{"key":"S1471068423000273_ref28","doi-asserted-by":"crossref","unstructured":"Rose, D. J. and Tarjan, R. E. 1975. Algorithmic aspects of vertex elimination. In Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 245\u2013254.","DOI":"10.1145\/800116.803775"},{"key":"S1471068423000273_ref13","unstructured":"Haslum, P. 2012. Incremental lower bounds for additive cost planning problems. In Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling, ICAPS 2012, Atibaia, S\u00e3o Paulo, Brazil, June 25-19, 2012. AAAI."},{"key":"S1471068423000273_ref24","doi-asserted-by":"crossref","unstructured":"Rankooh, M. F. and Rintanen, J. 2022a. Efficient computation and informative estimation of h+ by integer and linear programming. In Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling, ICAPS 2022, Singapore (virtual), June 13\u201324, 2022. AAAI Press, 71\u201379.","DOI":"10.1609\/icaps.v32i1.19787"},{"key":"S1471068423000273_ref8","doi-asserted-by":"crossref","unstructured":"Faber, W. , Morak, M. and Chrpa, L. 2022. Determining action reversibility in STRIPS using answer set programming with quantifiers. In Practical Aspects of Declarative Languages - 24th International Symposium, PADL 2022, Philadelphia, PA, USA, January 17-18, 2022, Proceedings. Lecture Notes in Computer Science, vol. 13165. Springer, 42\u201356.","DOI":"10.1007\/978-3-030-94479-7_4"},{"key":"S1471068423000273_ref18","doi-asserted-by":"publisher","DOI":"10.1613\/jair.4936"},{"key":"S1471068423000273_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90019-C"},{"key":"S1471068423000273_ref10","doi-asserted-by":"publisher","DOI":"10.1609\/icaps.v21i1.13485"},{"key":"S1471068423000273_ref7","doi-asserted-by":"crossref","unstructured":"Corr\u00eaa, A. B. , Pommerening, F. , Helmert, M. and Franc\u00e8s, G. 2022. The FF heuristic for lifted classical planning. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Virtual Event, February 22 - March 1, 2022. AAAI Press, 9716\u20139723.","DOI":"10.1609\/aaai.v36i9.21206"},{"key":"S1471068423000273_ref11","unstructured":"Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proceedings of ICLP\u201988. 1070\u20131080."},{"key":"S1471068423000273_ref19","unstructured":"Keyder, E. and Geffner, H. 2008. Heuristics for planning with action costs revisited. In ECAI 2008 - 18th European Conference on Artificial Intelligence, Patras, Greece, July 21\u201325, 2008, Proceedings. Frontiers in Artificial Intelligence and Applications, vol. 178. IOS Press, 588\u2013592."},{"key":"S1471068423000273_ref2","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2016-1398"},{"key":"S1471068423000273_ref1","unstructured":"Betz, C. and Helmert, M. 2009. Planning with h + in theory and practice. In KI 2009: Advances in Artificial Intelligence, 32nd Annual German Conference on AI, Paderborn, Germany, September 15-18, 2009. Lecture Notes in Computer Science, vol. 5803. Springer, 9\u201316."},{"key":"S1471068423000273_ref4","doi-asserted-by":"publisher","DOI":"10.1145\/2043174.2043195"},{"key":"S1471068423000273_ref22","unstructured":"Mirkis, V. and Domshlak, C. 2007. Cost-sharing approximations for h+. In Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling, ICAPS 2007, Providence, Rhode Island, USA, September 22-26, 2007. AAAI, 240\u2013247."},{"key":"S1471068423000273_ref29","unstructured":"Russell, S. and Norvig, P. 2020. Artificial Intelligence: A Modern Approach (4th Edition). Pearson."},{"key":"S1471068423000273_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)90081-7"},{"key":"S1471068423000273_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00108-4"},{"key":"S1471068423000273_ref17","doi-asserted-by":"publisher","DOI":"10.1613\/jair.855"},{"key":"S1471068423000273_ref23","doi-asserted-by":"crossref","unstructured":"Rankooh, M. F. and Janhunen, T. 2022. Efficient computation of answer sets via SAT modulo acyclicity and vertex elimination. In Logic Programming and Nonmonotonic Reasoning \u2013 16th International Conference, LPNMR 2022, Genova, Italy, September 5-9, 2022, Proceedings, G. Gottlob, D. Inclezan, and M. Maratea, Eds. Lecture Notes in Computer Science, vol. 13416. Springer, 203\u2013216.","DOI":"10.1007\/978-3-031-15707-3_16"},{"key":"S1471068423000273_ref26","doi-asserted-by":"crossref","unstructured":"Rankooh, M. F. and Rintanen, J. 2022c. Propositional encodings of acyclicity and reachability by using vertex elimination. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, 2022 Virtual Event, February 22 \u2013 March 1, 2022. AAAI Press, 5861\u20135868.","DOI":"10.1609\/aaai.v36i5.20530"}],"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\/S1471068423000273","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,27]],"date-time":"2024-02-27T09:38:26Z","timestamp":1709026706000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068423000273\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["S1471068423000273"],"URL":"https:\/\/doi.org\/10.1017\/s1471068423000273","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2023,7]]},"assertion":[{"value":"\u00a9 The Author(s), 2023. 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 (http:\/\/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"}]}}