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

plasp 3: Towards Effective ASP Planning

Published online by Cambridge University Press:  18 January 2019

YANNIS DIMOPOULOS ,
MARTIN GEBSER Open the ORCID record for MARTIN GEBSER [Opens in a new window] ,
PATRICK LÜHNE ,
JAVIER ROMERO  and
TORSTEN SCHAUB Open the ORCID record for TORSTEN SCHAUB [Opens in a new window]
YANNIS DIMOPOULOS
Affiliation:
University of Cyprus, Nicosia, Cyprus (e-mail: [email protected])
MARTIN GEBSER
Affiliation:
University of Klagenfurt, Klagenfurt, Austria, Graz University of Technology, Graz, Austria and University of Potsdam, Potsdam, Germany (e-mail: [email protected])
PATRICK LÜHNE
Affiliation:
University of Potsdam, Potsdam, Germany (e-mails: [email protected], [email protected])
JAVIER ROMERO
Affiliation:
University of Potsdam, Potsdam, Germany (e-mails: [email protected], [email protected])
TORSTEN SCHAUB*
Affiliation:
INRIA Rennes, Rennes, France and University of Potsdam, Potsdam, Germany (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We describe the new version of the Planning Domain Definition Language (PDDL)-to-Answer Set Programming (ASP) translator plasp. First, it widens the range of accepted PDDL features. Second, it contains novel planning encodings, some inspired by Satisfiability Testing (SAT) planning and others exploiting ASP features such as well-foundedness. All of them are designed for handling multivalued fluents in order to capture both PDDL as well as SAS planning formats. Third, enabled by multishot ASP solving, it offers advanced planning algorithms also borrowed from SAT planning. As a result, plasp provides us with an ASP-based framework for studying a variety of planning techniques in a uniform setting. Finally, we demonstrate in an empirical analysis that these techniques have a significant impact on the performance of ASP planning.

Keywords

knowledge representation and nonmonotonic reasoningtechnical notes and rapid communicationsanswer set programmingautomated planningaction and change
Type
Rapid Communication
Information
Theory and Practice of Logic Programming , Volume 19 , Issue 3 , May 2019 , pp. 477 - 504
Copyright
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.)

Footnotes

This work was partially funded by DFG grant SCHA 550/9. The second author was supported by KWF project 28472, cms electronics GmbH, FunderMax GmbH, Hirsch Armbänder GmbH, incubed IT GmbH, Infineon Technologies Austria AG, Isovolta AG, Kostwein Holding GmbH, and Privatstiftung Kärntner Sparkasse. We are grateful to the anonymous reviewers for their helpful comments.

References

Alviano, M., Calimeri, F., Charwat, G., Dao-Tran, M., Dodaro, C., Ianni, G., Krennwallner, T., Kronegger, M., Oetsch, J., Pfandler, A., Püijhrer, J., Redl, C., Ricca, F., Schneider, P., Schwengerer, M., Spendier, L., Wallner, J. and Xiao, G. 2013. The fourth answer set programming competition: Preliminary report. In Proceedings of the Twelfth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’13), Cabalar, P. and Son, T., Eds. Lecture Notes in Artificial Intelligence, vol. 8148. Springer-Verlag, 42–53.CrossRefGoogle Scholar
Apt, K., Blair, H. and Walker, A. 1987. Towards a theory of declarative knowledge. In Foundations of Deductive Databases and Logic Programming, Minker, J., Ed. Morgan Kaufmann Publishers, 89–148.Google Scholar
Baral, C. and Gelfond, M. 2000. Reasoning agents in dynamic domains. In Logic-Based Artificial Intelligence, Minker, J., Ed. Kluwer Academic Publishers, 257–279.CrossRefGoogle Scholar
Biere, A., Heule, M., van Maaren, H. and Walsh, T., Eds. 2009. Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185. IOS Press.Google Scholar
Bomanson, J., Gebser, M., Janhunen, T., Kaufmann, B. and Schaub, T. 2016. Answer set programming modulo acyclicity. Fundamenta Informaticae 147, 1, 63–91.CrossRefGoogle Scholar
Calimeri, F., Gebser, M., Maratea, M. and Ricca, F. 2016. Design and results of the fifth answer set programming competition. Artificial Intelligence 231, 151–181.CrossRefGoogle Scholar
Cimatti, A., Pistore, M. and Traverso, P. 2008. Automated planning. See Lifschitz et al. (2008), 841–867.Google Scholar
Dimopoulos, Y., Gebser, M., Lüijhne, P., Romero, J. and Schaub, T. 2017. plasp 3: Towards effective ASP planning. In Proceedings of the Fourteenth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’17), Balduccini, M. and Janhunen, T., Eds. Lecture Notes in Artificial Intelligence, vol. 10377. Springer-Verlag, 286–300.CrossRefGoogle Scholar
Dimopoulos, Y., Nebel, B. and Koehler, J. 1997. Encoding planning problems in nonmonotonic logic programs. In Proceedings of the Fourth European Conference on Planning (ECP’97), Steel, S. and Alami, R., Eds. Lecture Notes in Artificial Intelligence, vol. 1348. Springer-Verlag, 169–181.Google Scholar
Edelkamp, S. and Hoffmann, J. 2004. PDDL2.2: The language for the classical part of the 4th international planning competition. Technical Report 195, Institute of Informatics, University of Freiburg.Google Scholar
Eiter, T. and Polleres, A. 2006. Towards automated integration of guess and check programs in answer set programming: A meta-interpreter and applications. Theory and Practice of Logic Programming 6, 1–2, 23–60.CrossRefGoogle Scholar
Fisher, M. 2008. Temporal representation and reasoning. See Lifschitz et al. (2008), 513–550.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Lindauer, M., Ostrowski, M., Romero, J., Schaub, T. and Thiele, S. 2017a. Potassco User Guide, 2nd ed. University of Potsdam. https://github.com/potassco/guide/releases/tag/v2.1.0.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T. and Wanko, P. 2016. Theory solving made easy with clingo 5. In Technical Communications of the Thirty-Second International Conference on Logic Programming (ICLP’16), Carro, M., King, A., Saeedloei, N. and De Vos, M., Eds. Open Access Series in Informatics, vol. 52. Dagstuhl Publishing, 2:1–2:15.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B. and Schaub, T. 2014. Clingo = ASP + control: Preliminary report. In Technical Communications of the Thirtieth International Conference on Logic Programming (ICLP’14), Leuschel, M. and Schrijvers, T., Eds. Theory and Practice of Logic Programming 14, 4–5, online supplement. https://arxiv.org/abs/1405.3694v1.Google Scholar
Gebser, M., Kaminski, R., Knecht, M. and Schaub, T. 2011a. plasp: A prototype for PDDL-based planning in ASP. In Proceedings of the Eleventh International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’11), Delgrande, J. and Faber, W., Eds. Lecture Notes in Artificial Intelligence, vol. 6645. Springer-Verlag, 358–363.CrossRefGoogle Scholar
Gebser, M., Kaufmann, B., Otero, R., Romero, J., Schaub, T. and Wanko, P. 2013. Domain-specific heuristics in answer set programming. In Proceedings of the Twenty-Seventh National Conference on Artificial Intelligence (AAAI’13), desJardins, M. and Littman, M., Eds. AAAI Press, 350–356.Google Scholar
Gebser, M., Maratea, M. and Ricca, F. 2017b. The sixth answer set programming competition. Journal of Artificial Intelligence Research 60, 41–95.CrossRefGoogle Scholar
Gebser, M., Sabuncu, O. and Schaub, T. 2011b. An incremental answer set programming based system for finite model computation. AI Communications 24, 2, 195–212.Google Scholar
Gelfond, M. and Inclezan, D. 2013. Some properties of system descriptions of $\mathcal{AL}_d$. Journal of Applied Non-Classical Logics 23, 1–2, 259–285.CrossRefGoogle Scholar
Gelfond, M. and Lifschitz, V. 1998. Action languages. Electronic Transactions on Artificial Intelligence 3, 6, 193–210.Google Scholar
Giunchiglia, E., Lee, J., Lifschitz, V., McCain, N. and Turner, H. 2004. Nonmonotonic causal theories. Artificial Intelligence 153, 1–2, 49–104.CrossRefGoogle Scholar
Helmert, M. 2006. The fast downward planning system. Journal of Artificial Intelligence Research 26, 191–246.CrossRefGoogle Scholar
IPC. 2014. Homepage of the eighth international planning competition. https://helios.hud.ac.uk/scommv/IPC-14/.Google Scholar
Kautz, H., McAllester, D. and Selman, B. 1996. Encoding plans in propositional logic. In Proceedings of the Fifth International Conference on Principles of Knowledge Representation and Reasoning (KR’96), Aiello, L., Doyle, J. and Shapiro, S., Eds. Morgan Kaufmann Publishers, 374–384.Google Scholar
Lifschitz, V. 2002. Answer set programming and plan generation. Artificial Intelligence 138, 1–2, 39–54.CrossRefGoogle Scholar
Lifschitz, V., van Harmelen, F. and Porter, B., Eds. 2008. Handbook of Knowledge Representation. Elsevier Science.Google Scholar
Love, N., Hinrichs, T., Haley, D., Schkufza, E. and Genesereth, M. 2008. General game playing: Game description language specification. Technical Report LG-2006-01, Stanford University.Google Scholar
McDermott, D. 1998. PDDL—the planning domain definition language. Tech. Rep. CVC TR-98-003/DCS TR-1165, Yale Center for Computational Vision and Control.Google Scholar
Miura, S. and Fukunaga, A. 2017. Automatic extraction of axioms for planning. In Proceedings of the Twenty-seventh International Conference on Automated Planning and Scheduling (ICAPS’17), Barbulescu, L., Frank, J., Mausam and Smith, S., Eds. AAAI Press, 218–227.Google Scholar
Rintanen, J. 2012. Planning as satisfiability: Heuristics. Artificial Intelligence 193, 45–86.CrossRefGoogle Scholar
Rintanen, J. 2014. Madagascar: Scalable planning with SAT. In Proceedings of the Eighth International Planning Competition (IPC’14), Vallati, M., Chrpa, L. and McCluskey, T., Eds. University of Huddersfield, 66–70.Google Scholar
Rintanen, J., Heljanko, K. and Niemelä, I. 2006. Planning as satisfiability: Parallel plans and algorithms for plan search. Artificial Intelligence 170, 12–13, 1031–1080.CrossRefGoogle Scholar
Son, T., Baral, C., Nam, T. and McIlraith, S. 2006. Domain-dependent knowledge in answer set planning. ACM Transactions on Computational Logic 7, 4, 613–657.CrossRefGoogle Scholar
Thielscher, M. 2009. Answer set programming for single-player games in general game playing. In Proceedings of the Twenty-Fifth International Conference on Logic Programming (ICLP’09), Hill, P. and Warren, D., Eds. Lecture Notes in Computer Science, vol. 5649. Springer-Verlag, 327–341.Google Scholar
Tseitin, G. 1968. On the complexity of derivation in the propositional calculus. Zapiski Nauchnykh Seminarov LOMI 8, 234–259.Google Scholar
Van Gelder, A., Ross, K. and Schlipf, J. 1991. The well-founded semantics for general logic programs. Journal of the ACM 38, 3, 620–650.CrossRefGoogle Scholar
Wehrle, M. and Rintanen, J. 2007. Planning as satisfiability with relaxed ∃-step plans. In Proceedings of the Twentieth Australian Joint Conference on Artificial Intelligence (AI’07), Orgun, M. and Thornton, J., Eds. Lecture Notes in Computer Science, vol. 4830. Springer-Verlag, 244–253.Google Scholar