Domain-independent cost-optimal planning in ASP. (English) Zbl 1434.68548

Summary: 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, stepless planning, 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.


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


[1] Alviano, M., Dodaro, C., Marques-Silva, J., and Ricca, F.2015. Optimum stable model search: algorithms and implementation. Journal of Logic and Computation.
[2] Baral, C.2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press, New York, NY. · Zbl 1056.68139
[3] Barták, 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.
[4] Blum, A. L. and Furst, M. L.1997. Fast planning through planning graph analysis. Artificial Intelligence 90, 1, 281-300. · Zbl 1017.68533
[5] 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.
[6] 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).
[7] Dimopoulos, Y., Gebser, M., Lühne, P., Romero, J., and Schaub, T.2019. plasp 3: Towards effective ASP planning. Theory and Practice of Logic Programming 19, 3, 477-504. · Zbl 1491.68190
[8] 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-71. · Zbl 1026.68124
[9] 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-208. · Zbl 0234.68036
[10] 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-363. Vancouver, Canada.
[11] 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-301.
[12] Kautz, H.2004. Satplan04: Planning as satisfiability. Working Notes on the Fourth International Planning Competition (IPC-04), 44-45.
[13] 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-3191.
[14] Lifschitz, V.2002. Answer set programming and plan generation. Artificial Intelligence 138, 1-2, 39-54. · Zbl 0995.68020
[15] Maratea, M.2012. Planning as satisfiability with IPC simple preferences and action costs. AI Communications 25, 4, 343-360. · Zbl 1248.68458
[16] Rintanen, J.2011. Heuristics for planning with SAT and expressive action definitions. In Proc. 21st International Conference on Automated Planning and Scheduling, Freiburg, Germany.
[17] Rintanen, J.2012. Planning as satisfiability: Heuristics. Artificial Intelligence 193, 45-86. · Zbl 1270.68276
[18] 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-303.
[19] Robinson, N., Gretton, C., Pham, D.-N., and Sattar, A.2010. Cost-optimal planning using weighted MaxSAT. In Proc. the ICAPS’10 Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems, Toronto, Canada.
[20] Spies, D.2019. Domain-independent cost-optimal planning in ASP. MSc. Thesis, University of Alberta, Edmonton, Canada.
[21] Suda, M.2014. Property directed reachability for automated planning. Journal of Artificial Intelligence Research 50, 265-319. · Zbl 1361.68208
[22] Tange, O.2018. GNU Parallel 2018. Ole Tange.
[23] Vidal, V. and Geffner, H.2006. Branching and pruning: An optimal temporal POCL planner based on constraint programming. Artificial Intelligence 170, 3, 298-335. · Zbl 1131.68528
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.