Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-16T13:23:47.871Z Has data issue: false hasContentIssue false
  • English
  • Français

Reasoning about actions with Temporal Answer Sets

Published online by Cambridge University Press:  25 January 2012

LAURA GIORDANO ,
ALBERTO MARTELLI  and
DANIELE THESEIDER DUPRÉ
LAURA GIORDANO
Affiliation:
Dipartimento di Informatica, Università del Piemonte Orientale, Italy (e-mail: [email protected])
ALBERTO MARTELLI
Affiliation:
Dipartimento di Informatica, Università di Torino, Italy (e-mail: [email protected])
DANIELE THESEIDER DUPRÉ
Affiliation:
Dipartimento di Informatica, Università del Piemonte Orientale, Italy (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, we combine Answer Set Programming (ASP) with Dynamic Linear Time Temporal Logic (DLTL) to define a temporal logic programming language for reasoning about complex actions and infinite computations. DLTL extends propositional temporal logic of linear time with regular programs of propositional dynamic logic, which are used for indexing temporal modalities. The action language allows general DLTL formulas to be included in domain descriptions to constrain the space of possible extensions. We introduce a notion of Temporal Answer Set for domain descriptions, based on the usual notion of Answer Set. Also, we provide a translation of domain descriptions into standard ASP and use Bounded Model Checking (BMC) techniques for the verification of DLTL constraints.

Keywords

Answer Set ProgrammingTemporal LogicBounded Model Checking
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 13 , Issue 2: 25th Annual GULP Conference , March 2013 , pp. 201 - 225
Copyright
Copyright © Cambridge University Press 2012

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

Bacchus, F. and Kabanza, F. 1998. Planning for temporally extended goals. Annals of Mathematics and Artificial Intelligence 22, 5–27.CrossRefGoogle Scholar
Bacchus, F. and Kabanza, F. 2000. Using temporal logics to express search control knowledge for planning. Artificial Intelligence 116, 1–2, 123–191.CrossRefGoogle Scholar
Balduccini, M. and Gelfond, M. 2003. Diagnostic reasoning with A-prolog. Theory and Practice of Logic Programming 3, 4–5, 425–461.CrossRefGoogle Scholar
Baral, C. and Gelfond, M. 2000. Reasoning agents in dynamic domains. In Logic-Based Artificial Intelligence. Kluwer Academic Publishers, Boston, 257–279.Google Scholar
Baral, C. and Zhao, J. 2007. Non-monotonic temporal logics for goal specification. In Proceedings of IJCAI 2007. AAAI Press/International Joint Conferences on Artificial Intelligence, Menlo Park, USA, 236–242.Google Scholar
Bienvenu, M., Fritz, C. and McIlraith, S. 2006. Planning with qualitative temporal preferences. In Proceedings of KR 2006. AAAI Press, Menlo Park, USA, 134–144.Google Scholar
Biere, A., Cimatti, A., Clarke, E. M., Strichman, O. and Zhu, Y. 2003. Bounded model checking. Advances in Computers 58, 118–149.Google Scholar
Bonatti, P. 2004. Reasoning with infinite stable models. Artificial Intelligence 156, 1, 75–111.Google Scholar
Claßen, J. and Lakemeyer, G. 2008. A logic for non-terminating Golog programs. In Proceedings of KR 2008. AAAI Press, Menlo Park, USA, 589–599.Google Scholar
Dal Lago, U., Pistore, M. and Traverso, P. 2002. Planning with a language for extended goals. In Proceedings of AAAI 2002. AAAI Press, Menlo Park, USA, 447–454.Google Scholar
D'Aprile, D., Giordano, L., Gliozzi, V., Martelli, A., Pozzato, G. and Theseider Dupré, D. 2010. Verifying business process compliance by reasoning about actions. In Proceedings of CLIMA 2010, LNCS 6245. Springer-Verlag, Berlin, 99–116.Google Scholar
Denecker, M., Theseider Dupré, D. and Van Belleghem, K. 1998. An inductive definitions approach to ramifications. Electronic Transactions on Artificial Intelligence 2, 25–97.Google Scholar
Eiter, T., Faber, W., Leone, N., Pfeifer, G. and Polleres, A. 2003. A logic programming approach to knowledge-state planning, II: The DLVk system. Artificial Intelligence 144, 1–2, 157–211.CrossRefGoogle 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 Transactions on Computational Logic 5, 2, 206–263.Google Scholar
Gelfond, M. 2007. Handbook of Knowledge Representation, chapter 7, Answer Sets. Elsevier, Amsterdam.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Logic Programming, Proceedings of the 5th International Conference and Symposium. MIT Press, Boston, USA, 1070–1080.Google Scholar
Gelfond, M. and Lifschitz, V. 1993. Representing action and change by logic programs. Journal of Logic Programming 17, 301–322.CrossRefGoogle Scholar
Gerevini, A. and Long, D. 2005. Plan Constraints and Preferences in PDDL3. Technical Report, Department of Electronics and Automation, University of Brescia, Italy.Google Scholar
Giordano, L. and Martelli, A. 2006. Tableau-based automata construction for dynamic linear time temporal logic. Annals of Mathematics and Artificial Intelligence 46, 3, 289–315.CrossRefGoogle Scholar
Giordano, L., Martelli, A. and Schwind, C. 2001. Reasoning about actions in dynamic linear time temporal logic. The Logic Journal of the IGPL 9, 2, 289–303.CrossRefGoogle Scholar
Giordano, L., Martelli, A. and Schwind, C. 2007. Specifying and verifying interaction protocols in a temporal action logic. Journal of Applied Logic 5, 214–234.CrossRefGoogle Scholar
Giunchiglia, E. 2000. Planning as satisfiability with expressive action languages: Concurrency, constraints and nondeterminism. In Proceedings of KR 2000. Morgan Kaufman, San Francisco, USA, 657–666.Google Scholar
Giunchiglia, E., Lee, J., Lifschitz, V., McCain, N. and Turner, H. 2004. Nonmonotonic causal theories. Artificial Intelligence 153, 1–2, 49–104.Google Scholar
Giunchiglia, E. and Lifschitz, V. 1998. An action language based on causal explanation: Preliminary report. In Proceedings of AAAI/IAAI 1998. AAAI Press, Menlo Park, USA, 623–630.Google Scholar
Giunchiglia, F. and Traverso, P. 1999. Planning as model checking. In Proceedings of 5th European Conference on Planning (ECP'99). Springer-Verlag, Berlin, 1–20.Google Scholar
Heljanko, K. and Niemelä, I. 2003. Bounded LTL model checking with stable models. Theory and Practice of Logic Programming 3, 4–5, 519–550.Google Scholar
Henriksen, J. and Thiagarajan, P. 1999. Dynamic linear time temporal logic. Annals of Pure and Applied logic 96, 1-3, 187–207.Google Scholar
Kabanza, F., Barbeau, M. and St-Denis, R. 1997. Planning control rules for reactive agents. Artificial Intelligence 95, 67–113.Google Scholar
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S. and Scarcello, F. 2006. The DLV system for knowledge representation and reasoning. ACM Transactions on Computational Logic 7, 3, 499–562.Google Scholar
Levesque, H., Reiter, R., Lespérance, Y., Lin, F. and Scherl, R. 1997. Golog: A logic programming language for dynamic domains. Journal of Logic Programming 31, 1–3, 59–83.Google Scholar
Lifschitz, V. 1990. Frames in the space of situations. Artificial Intelligence 46, 365–376.Google Scholar
Panati, A. and Theseider Dupré, D. 2000. State-based vs simulation-based diagnosis of dynamic systems. In Proceedings of ECAI 2000. IOS Press, Amsterdam, 176–180.Google Scholar
Panati, A. and Theseider Dupré, D. 2001. Causal simulation and diagnosis of dynamic systems. In Proceedings of AI*IA 2001: Advances in Artificial Intelligence, LNCS 2175. Springer-Verlag, Berlin, 135–146.Google Scholar
Pistore, M. and Traverso, P. 2001. Planning as model checking for extended goals in non-deterministic domains. In Proceedings of IJCAI 2001. Morgan Kaufman, San Francisco, USA, 479–486.Google Scholar
Pistore, M., Traverso, P. and Bertoli, P. 2005. Automated composition of web services by planning in asynchronous domains. In Proceedings of ICAPS 2005. AAAI Press, Menlo Park, USA, 2–11.Google Scholar
Son, T., Baral, C., Tran, N. and McIlraith, S. 2006. Domain-dependent knowledge in answer set planning. ACM Transactions on Computational Logic 7, 4, 613–657.Google Scholar
Son, T. C. and Pontelli, E. 2006. Planning with preferences using logic programming. Theory and Practice of Logic Programming 6, 5, 559–607.CrossRefGoogle Scholar
Tu, P., Son, T., Gelfond, M. and Morales, R. 2011. Approximation of action theories and its application to conformant planning. Artificial Intelligence 175, 1, 79–119.CrossRefGoogle Scholar
Supplementary material: File

GIORDANO et al. supplementary material

Online Appendix

Download GIORDANO et al. supplementary material(File)
File 258 KB