Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-25T14:06:39.938Z Has data issue: false hasContentIssue false
  • English
  • Français

Domain-Independent Cost-Optimal Planning in ASP

Published online by Cambridge University Press:  20 September 2019

DAVID SPIES ,
JIA-HUAI YOU Open the ORCID record for JIA-HUAI YOU [Opens in a new window]  and
RYAN HAYWARD
DAVID SPIES
Affiliation:
University of Alberta, Edmonton, Canada
JIA-HUAI YOU
Affiliation:
University of Alberta, Edmonton, Canada
RYAN HAYWARD
Affiliation:
University of Alberta, Edmonton, Canada
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Keywords

Cost-Optimal PlanningAnswer Set ProgrammingCORE-2 ASP Standard.
Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 19 , Special Issue 5-6: 35th International Conference on Logic Programming , September 2019 , pp. 1124 - 1142
Copyright
© Cambridge University Press 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alviano, M., Dodaro, C., Marques-Silva, J., and Ricca, F. 2015. Optimum stable model search: algorithms and implementation. Journal of Logic and Computation.Google Scholar
Baral, C. 2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press, New York, NY.Google Scholar
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.Google Scholar
Blum, A. L. and Furst, M. L. 1997. Fast planning through planning graph analysis. Artificial Intelligence 90, 1, 281–300.Google Scholar
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.Google Scholar
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).Google Scholar
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.CrossRefGoogle Scholar
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.Google Scholar
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.Google Scholar
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.Google Scholar
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.Google Scholar
Kautz, H. 2004. Satplan04: Planning as satisfiability. Working Notes on the Fourth International Planning Competition (IPC-04), 44–45.Google Scholar
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.Google Scholar
Lifschitz, V. 2002. Answer set programming and plan generation. Artificial Intelligence 138, 1-2, 39–54.Google Scholar
Maratea, M. 2012. Planning as satisfiability with IPC simple preferences and action costs. AI Communications 25, 4, 343–360.Google Scholar
Rintanen, J. 2011. Heuristics for planning with SAT and expressive action definitions. In Proc. 21st International Conference on Automated Planning and Scheduling, Freiburg, Germany.Google Scholar
Rintanen, J. 2012. Planning as satisfiability: Heuristics. Artificial Intelligence 193, 45–86.Google Scholar
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.Google Scholar
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.Google Scholar
Spies, D. 2019. Domain-independent cost-optimal planning in ASP. MSc. Thesis, University of Alberta, Edmonton, Canada.Google Scholar
Suda, M. 2014. Property directed reachability for automated planning. Journal of Artificial Intelligence Research 50, 265–319.Google Scholar
Tange, O. 2018. GNU Parallel 2018. Ole Tange.Google Scholar
Vidal, V. and Geffner, H. 2006. Branching and pruning: An optimal temporal POCL planner based on constraint programming. Artificial Intelligence 170, 3, 298–335.CrossRefGoogle Scholar
Supplementary material: PDF

Spies et al. supplementary material

Online Appendix

Download Spies et al. supplementary material(PDF)
PDF 142.4 KB