No CrossRef data available.
Article contents
Determining Action Reversibility in STRIPS Using Answer Set and Epistemic Logic Programming
Published online by Cambridge University Press: 27 September 2021
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
In the context of planning and reasoning about actions and change, we call an action reversible when its effects can be reverted by applying other actions, returning to the original state. Renewed interest in this area has led to several results in the context of the PDDL language, widely used for describing planning tasks. In this paper, we propose several solutions to the computational problem of deciding the reversibility of an action. In particular, we leverage an existing translation from PDDL to Answer Set Programming (ASP), and then use several different encodings to tackle the problem of action reversibility for the STRIPS fragment of PDDL. For these, we use ASP, as well as Epistemic Logic Programming (ELP), an extension of ASP with epistemic operators, and compare and contrast their strengths and weaknesses.
Keywords
Information
- Type
- Original Article
- Information
- Theory and Practice of Logic Programming , Volume 21 , Issue 5: 37th International Conference on Logic Programming Special Issue I , September 2021 , pp. 646 - 662
- Creative Commons
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.- Copyright
- © The Author(s), 2021. Published by Cambridge University Press
Footnotes
References
Bylander, T. 1994. The computational complexity of propositional STRIPS planning. Artificial Intelligence 69, 1–2, 165–204.CrossRefGoogle Scholar
Camacho, A., Muise, C. J. and McIlraith, S. A. 2016. From FOND to robust probabilistic planning: Computing compact policies that bypass avoidable deadends. In Proc. ICAPS. 65–69.Google Scholar
Chrpa, L., Faber, W., Fišer, D. and Morak, M. 2020. Determining action reversibility in strips using answer set programming. In International Conference on Logic Programming 2020 Workshop Proceedings. CEUR Workshop Proceedings, vol. 2678.Google Scholar
Chrpa, L., Faber, W. and Morak, M. 2021. Universal and uniform action reversibility. In Proc. KR. to appear.CrossRefGoogle Scholar
Chrpa, L., Lipovetzky, N. and Sardiña, S. 2017. Handling non-local dead-ends in agent planning programs. In Proc. IJCAI, 971–978.Google Scholar
Chrpa, L., McCluskey, T. L. and Osborne, H. 2012. Optimizing plans through analysis of action dependencies and independencies. In Proc. ICAPS.Google Scholar
Cserna, B., Doyle, W. J., Ramsdell, J. S. and Ruml, W. 2018. Avoiding dead ends in real-time heuristic search. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), 1306–1313.Google Scholar
Daum, J., Torralba, Á., Hoffmann, J., Haslum, P. and Weber, I. 2016. Practical undoability checking via contingent planning. In Proc. ICAPS, 106–114.Google Scholar
De Giacomo, G., Gerevini, A. E., Patrizi, F., Saetti, A. and Sardiña, S. 2016. Agent planning programs. Artificial Intelligence 231, 64–106.CrossRefGoogle 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., Erdem, E. and Faber, W. 2008. Undoing the effects of action sequences. Journal of Applied Logic 6, 3, 380–415.CrossRefGoogle Scholar
Eiter, T. and Gottlob, G. 1995. On the computational cost of disjunctive logic programming: Propositional case. Annals of Mathematics and Artificial Intelligence 15, 3–4, 289–323.CrossRefGoogle Scholar
Faber, W. and Morak, M. 2020. Determining action reversibility in STRIPS using epistemic logic programs. In International Conference on Logic Programming 2020 Workshop Proceedings. CEUR Workshop Proceedings, vol. 2678.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
Gelfond, M. 1991. Strong introspection. In Proc. AAAI, T. L. Dean and K. R. McKeown, Eds. AAAI Press/The MIT Press, 386–391.Google Scholar
Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 3/4, 365–386.Google Scholar
Ghallab, M., Nau, D. S. and Traverso, P. 2004. Automated Planning - Theory and Practice. Elsevier.Google Scholar
Ghallab, M., Nau, D. S. and Traverso, P. 2016. Automated Planning and Acting. Cambridge University Press.Google Scholar
Lipovetzky, N., Muise, C. J. and Geffner, H. 2016. Traps, invariants, and dead-ends. In Proc. ICAPS. 211–215.Google Scholar
Morak, M., Chrpa, L., Faber, W. and Fišer, D. 2020. On the reversibility of actions in planning. In Proc. KR. 652–661.CrossRefGoogle Scholar
Truszczynski, M. 2011. Revisiting epistemic specifications. In Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning - Essays Dedicated to Michael Gelfond on the Occasion of His 65th Birthday, M. Balduccini and T. C. Son, Eds. Lecture Notes in Computer Science, vol. 6565. Springer, 315–333.Google Scholar
Faber supplementary material
Faber supplementary material
PDF
105.5 KB
You have
Access
Open access
- 4
- Cited by