Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-26T04:59:41.141Z Has data issue: false hasContentIssue false
  • English
  • Français

Planning as tabled logic programming

Published online by Cambridge University Press:  03 September 2015

NENG-FA ZHOU ,
ROMAN BARTÁK  and
AGOSTINO DOVIER
NENG-FA ZHOU
Affiliation:
CUNY Brooklyn College and Graduate Center
ROMAN BARTÁK
Affiliation:
Charles University
AGOSTINO DOVIER
Affiliation:
Univ. di Udine
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper describes Picat's planner, its implementation, and planning models for several domains used in International Planning Competition (IPC) 2014. Picat's planner is implemented by use of tabling. During search, every state encountered is tabled, and tabled states are used to effectively perform resource-bounded search. In Picat, structured data can be used to avoid enumerating all possible permutations of objects, and term sharing is used to avoid duplication of common state data. This paper presents several modeling techniques through the example models, ranging from designing state representations to facilitate data sharing and symmetry breaking, encoding actions with operations for efficient precondition checking and state updating, to incorporating domain knowledge and heuristics. Broadly, this paper demonstrates the effectiveness of tabled logic programming for planning, and argues the importance of modeling despite recent significant progress in domain-independent PDDL planners.

Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 15 , Special Issue 4-5: 31st International Conference on Logic Programming , July 2015 , pp. 543 - 558
Copyright
Copyright © Cambridge University Press 2015 

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

Alford, R., Kuter, U. and Nau, D. S. 2009. Translating HTNs to PDDL: A small amount of domain knowledge can go a long way. In IJCAI. 1629–1634.Google Scholar
Bacchus, F. and Kabanza, F. 2000. Using temporal logics to express search control knowledge for planning. Artif. Intell. 116, 1–2, 123–191.Google Scholar
Baier, J. A., Fritz, C. and McIlraith, S. A. 2011. Golog-style search control for planning. In Knowing, Reasoning, and Acting: Essays in Honour of Hector J. Levesque, Lakemeyer, G. and McIlraith, S. A., Eds. College Publications.Google Scholar
Barták, R., Dovier, A. and Zhou, N.-F. 2015. On modeling planning problems in tabled logic programming. In Proceedings of the 17th International Symposium on Principles and Practice of Declarative Programming. PPDP '15. 31–42.Google Scholar
Bartak, R. and Zhou, N. 2014. Using tabled logic programming to solve the Petrobras planning problem. Theory and Practice of Logic Programming 14, 4–5, 697–710.Google Scholar
Brewka, G., Eiter, T. and Truszczyński, M. 2011. Answer set programming at a glance. Commun. ACM 54, 12, 92–103.Google Scholar
Chrpa, L., Vallati, M. and McCluskey, L. 2014. International planning competition.Google Scholar
Dawson, S., Ramakrishnan, C. R. and Warren, D. S. 1996. Practical program analysis using general purpose logic programming systems –- A case study. ACM SIG-PLAN Notices 31, 5, 117–126.Google Scholar
Dovier, A., Formisano, A. and Pontelli, E. 2011. Perspectives on logic-based approaches for reasoning about actions and change. In LNCS. Vol. 6565. 259–279.Google Scholar
Eiter, T., Faber, W., Leone, N., Pfeifer, G. and Polleres, A. 2004. A logic programming approach to knowledge-state planning: Semantics and complexity. ACM Trans. Comput. Log. 5, 2, 206–263.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B. and Schaub, T. 2012. Answer Set Solving in Practice. Morgan and Claypool Publishers.Google Scholar
Gelfond, M. and Lifschitz, V. 1998. Action languages. Electron. Trans. Artif. Intell. 2, 193–210.Google Scholar
Guo, H.-F. and Gupta, G. 2008. Simplifying dynamic programming via mode-directed tabling. Softw., Pract. Exper. 38, 1, 75–94.Google Scholar
Haslum, P. and Scholz, U. 2003. Domain knowledge in planning: Representation and use. In ICAPS Workshop on PDDL.Google Scholar
Hewitt, C. 1969. Planner: A language for proving theorems in robots. In IJCAI. 295–302.Google Scholar
Kautz, H. and Selman, B. 1998. The role of domain-specific knowledge in the planning as satisfiability framework. In AIPS98. 181–189.Google Scholar
Korf, R. E. 1985. Depth-first iterative-deepening: An optimal admissible tree search. Artif. Intell. 27, 1, 97–109.CrossRefGoogle Scholar
Kowalski, R. 1979. Logic for Problem Solving. North Holland, Elsevier.Google Scholar
Levesque, H. J., Reiter, R., Lespérance, Y., Lin, F. and Scherl, R. B. 1997. GOLOG: A logic programming language for dynamic domains. J. Log. Program. 31, 1–3, 59–83.Google Scholar
Lifschitz, V. 2002. Answer set programming and plan generation. Artif. Intell. 138, 1–2, 39–54.Google Scholar
McDermott, D. 1998. The planning domain definition language manual. CVC Report 98-003, Yale Computer Science Report 1165.Google Scholar
Michie, D. 1968. “memo” functions and machine learning. Nature, 19–22.Google Scholar
Nielson, F., Nielson, H. R., Sun, H., Buchholtz, M., Hansen, R. R., Pilegaard, H. and Seidl, H. 2004. The succinct solver suite. In Proc. Tools and Algorithms for the Construction and Analysis of Systems: 10th International Conference (TACAS), LNCS 2988. 251–265.Google Scholar
Pientka, B. December 2003. Tabled higher-order logic programming. Ph.D. thesis, Technical Report CMU-CS-03-185.Google Scholar
Ramakrishna, Y. S., Ramakrishnan, C. R., Ramakrishnan, I. V., Smolka, S. A., Swift, T. and Warren, D. S. 1997. Efficient model checking using tabled resolution. In Computer Aided Verification. 143–154.Google Scholar
Tamaki, H. and Sato, T. 1986. OLD resolution with tabulation. In ICLP. 84–98.CrossRefGoogle Scholar
Torralba, A., Alcazar, V. and Borrajo, D. 2014. Symba: A symbolic bidirectional a planner. In The 2014 International Planning Competition. 105–109.Google Scholar
Warren, D. H. D. 1974. WARPLAN: A system for generating plans. Tech. Rep. DCL Memo 76, University of Edinburgh.Google Scholar
Warren, D. S. 1992. Memoing for logic programs. Comm. of the ACM, Special Section on Logic Programming 35, 93–111.Google Scholar
Zhou, N.-F. 2014. Combinatorial search with Picat. ICLP, invited talk, http://arxiv.org/abs/1405.2538.Google Scholar
Zhou, N.-F. and Dovier, A. 2013. A tabled Prolog program for solving Sokoban. Fundam. Inform. 124, 4, 561–575.Google Scholar
Zhou, N.-F. and Have, C. T. 2012. Efficient tabling of structured data with enhanced hash-consing. Theory and Practice of Logic Programming 12, 4–5, 547–563.Google Scholar
Zhou, N.-F., Kameya, Y. and Sato, T. 2010. Mode-directed tabling for dynamic programming, machine learning, and constraint solving. In ICTAI. 213–218.Google Scholar
Zhou, N.-F., Sato, T. and Shen, Y.-D. 2008. Linear tabling strategies and optimizations. Theory and Practice of Logic Programming 8, 1, 81–109.CrossRefGoogle Scholar
Supplementary material: PDF

Zhou supplementary material

Online Appendix

Download Zhou supplementary material(PDF)
PDF 2 MB