{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T22:00:49Z","timestamp":1747173649765,"version":"3.40.5"},"reference-count":23,"publisher":"Cambridge University Press (CUP)","issue":"5-6","license":[{"start":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T00:00:00Z","timestamp":1568937600000},"content-version":"unspecified","delay-in-days":19,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2019,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigate the problem of cost-optimal planning in ASP. Current ASP planners can be trivially extended to a cost-optimal one by adding weak constraints, but only for a given makespan (number of steps). It is desirable to have a planner that guarantees global optimality. In this paper, we present two approaches to addressing this problem. First, we show how to engineer a cost-optimal planner composed of two ASP programs running in parallel. Using lessons learned from this, we then develop an entirely new approach to cost-optimal planning,<jats:italic>stepless planning<\/jats:italic>, which is completely free of makespan. Experiments to compare the two approaches with the only known cost-optimal planner in SAT reveal good potentials for stepless planning in ASP.<\/jats:p>","DOI":"10.1017\/s1471068419000395","type":"journal-article","created":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T13:06:21Z","timestamp":1568984781000},"page":"1124-1142","source":"Crossref","is-referenced-by-count":2,"title":["Domain-Independent Cost-Optimal Planning in ASP"],"prefix":"10.1017","volume":"19","author":[{"given":"DAVID","family":"SPIES","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9372-4371","authenticated-orcid":false,"given":"JIA-HUAI","family":"YOU","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"RYAN","family":"HAYWARD","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2019,9,20]]},"reference":[{"unstructured":"Tange, O. 2018. GNU Parallel 2018. Ole Tange.","key":"S1471068419000395_ref22"},{"unstructured":"Suda, M. 2014. Property directed reachability for automated planning. Journal of Artificial Intelligence Research 50, 265\u2013319.","key":"S1471068419000395_ref21"},{"unstructured":"Spies, D. 2019. Domain-independent cost-optimal planning in ASP. MSc. Thesis, University of Alberta, Edmonton, Canada.","key":"S1471068419000395_ref20"},{"unstructured":"Robinson, N. , Gretton, C. , Pham, D. N. , and Sattar, A. 2008. A compact and efficient SAT encoding for planning. In Proc. 18th International Conference on Automated Planning and Scheduling, Sydney, Australia, pp. 296\u2013303.","key":"S1471068419000395_ref18"},{"key":"S1471068419000395_ref15","doi-asserted-by":"crossref","first-page":"343","DOI":"10.3233\/AIC-2012-0540","article-title":"Planning as satisfiability with IPC simple preferences and action costs","volume":"4","author":"Maratea","year":"2012","journal-title":"AI Communications 25"},{"key":"S1471068419000395_ref14","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0004-3702(02)00186-8","article-title":"Answer set programming and plan generation","volume":"1","author":"Lifschitz","year":"2002","journal-title":"Artificial Intelligence 138"},{"unstructured":"Lelis, L. H. S. , Franco, S. , Abisrror, M. , Barley, M. , Zilles, S. , and Holte, R. C. 2016. Heuristic subset selection in classical planning. In Proc. IJCAI-16, New York, USA, pp. 3185\u20133191.","key":"S1471068419000395_ref13"},{"unstructured":"Kautz, H. 2004. Satplan04: Planning as satisfiability. Working Notes on the Fourth International Planning Competition (IPC-04), 44\u201345.","key":"S1471068419000395_ref12"},{"unstructured":"Howey, R. , Long, D. , and Fox, M. 2004. VAL: automatic plan validation, continuous effects and mixed initiative planning using PDDL. In Proc. 16th IEEE International Conference on Tools with Artificial Intelligence, Boca Raton, Florida, USA, pp. 294\u2013301.","key":"S1471068419000395_ref11"},{"doi-asserted-by":"crossref","unstructured":"Gebser, M. , Kaminski, R. , Knecht, M. , and Schaub, T. 2011. plasp: A prototype for PDDL-based planning in ASP. In Proc. LPNMR-11, pp. 358\u2013363. Vancouver, Canada.","key":"S1471068419000395_ref10","DOI":"10.1007\/978-3-642-20895-9_41"},{"unstructured":"Eiter, T. , Faber, W. , Leone, N. , Pfeifer, G. , and Polleres, A. 2003. Answer set planning under action costs. Journal of Artificial Intelligence Research 19, 25\u201371.","key":"S1471068419000395_ref8"},{"unstructured":"Chen, Y. , Lv, Q. , and Huang, R. 2008. Plan-A: A cost-optimal planner based on SAT-constrained optimization. Proc. 6th International Planning Competition (IPC-08).","key":"S1471068419000395_ref6"},{"key":"S1471068419000395_ref4","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/S0004-3702(96)00047-1","article-title":"Fast planning through planning graph analysis","volume":"1","author":"Blum","year":"1997","journal-title":"Artificial Intelligence 90"},{"doi-asserted-by":"crossref","unstructured":"Alviano, M. , Dodaro, C. , Marques-Silva, J. , and Ricca, F. 2015. Optimum stable model search: algorithms and implementation. Journal of Logic and Computation.","key":"S1471068419000395_ref1","DOI":"10.1093\/logcom\/exv061"},{"doi-asserted-by":"publisher","key":"S1471068419000395_ref23","DOI":"10.1016\/j.artint.2005.08.004"},{"doi-asserted-by":"publisher","key":"S1471068419000395_ref7","DOI":"10.1017\/S1471068418000583"},{"unstructured":"Bart\u00e1k, R. , Dvorak, F. , Gemrot, J. , Brom, C. , and Toropila, D. 2012. When planning should be easy: On solving cumulative planning problems. In Proc. 25th International Florida Artificial Intelligence Conference, Florida, USA.","key":"S1471068419000395_ref3"},{"unstructured":"Rintanen, J. 2012. Planning as satisfiability: Heuristics. Artificial Intelligence 193, 45\u201386.","key":"S1471068419000395_ref17"},{"key":"S1471068419000395_ref2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511543357","volume-title":"Knowledge Representation, Reasoning and Declarative Problem Solving","author":"Baral","year":"2003"},{"unstructured":"Fikes, R. and Nilsson, N. J. 1971. STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence 2, 3\/4, 189\u2013208.","key":"S1471068419000395_ref9"},{"doi-asserted-by":"crossref","unstructured":"Rintanen, J. 2011. Heuristics for planning with SAT and expressive action definitions. In Proc. 21st International Conference on Automated Planning and Scheduling, Freiburg, Germany.","key":"S1471068419000395_ref16","DOI":"10.1609\/icaps.v21i1.13478"},{"unstructured":"Robinson, N. , Gretton, C. , Pham, D.-N. , and Sattar, A. 2010. Cost-optimal planning using weighted MaxSAT. In Proc. the ICAPS\u201910 Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems, Toronto, Canada.","key":"S1471068419000395_ref19"},{"unstructured":"Calimeri, F. , Faber, W. , Gebser, M. , Ianni, G. , Kaminski, R. , Krennwallner, T. , Leone, N. , Ricca, F. , and Schaub, T. 2015. ASP-Core-2 input language format. https:\/\/www.mat.unical.it\/aspcomp2013\/files\/ASP-CORE-2.01c.pdf. ASP Standardization Working Group.","key":"S1471068419000395_ref5"}],"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\/S1471068419000395","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T04:41:40Z","timestamp":1664426500000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068419000395\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9]]},"references-count":23,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["S1471068419000395"],"URL":"https:\/\/doi.org\/10.1017\/s1471068419000395","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2019,9]]}}}