Abstract
We introduce ATLEA, a novel extension of Alternating-time Temporal Logic with explicit actions in the object language. ATLEA allows to reason about abilities of agents under commitments to play certain actions. Pre- and postconditions as well as availability and unavailability of actions can be expressed. We show that the multiagent extension of Reiter’s solution to the frame problem can be encoded into ATLEA. We also consider an epistemic extension of ATLEA. We demonstrate that the resulting logic is sufficiently expressive to reason about uniform choices of actions. Complexity results for the satisfiability problem of ATLEA and its epistemic extension are given in the paper.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ågotnes, T.: Action and knowledge in alternating-time temporal logic. Synthese 149(2), 375–407 (2006)
Alur, R., Henzinger, R., Kupferman, O.: Alternating-time temporal logic. Journal of the ACM 49(5), 672–713 (2002)
Belle, V., Lakemeyer, G.: Reasoning about imperfect information games in the epistemic situation calculus. In: Proceedings of AAAI 2010. AAAI Press (2010)
Borgo, S.: Coalitions in action logic. In: Proceedings of IJCAI 2007, pp. 1822–1827 (2007)
Brihaye, T., Da Costa, A., Laroussinie, F., Markey, N.: ATL with strategy contexts and bounded memory. In: Artemov, S., Nerode, A. (eds.) LFCS 2009. LNCS, vol. 5407, pp. 92–106. Springer, Heidelberg (2008)
Chatterjee, K., Henzinger, T.A., Piterman, N.: Strategy logic. Information and Computation 208(6), 677–693 (2010)
van Ditmarsch, H., Herzig, A., de Lima, T.: From Situation Calculus to Dynamic Logic. Journal of Logic and Computation 21(2), 179–204 (2011)
Emerson, E.A.: Temporal and modal logic. In: Handbook of Theoretical Computer Science. Formal Models and Semantics, vol. B, pp. 995–1072. MIT Press (1990)
Gelfond, M., Lifschitz, V.: Representing action and change by logic programs. The Journal of Logic Programming 17, 301–321 (1993)
Gerbrandy, J.: Logics of propositional control. In: Proceedings of AAMAS 2006, pp. 193–200. ACM (2006)
De Giacomo, G., Lespérance, Y., Pearce, A.R.: Situation calculus based programs for representing and reasoning about game structures. In: Proceedings of KR 2010. AAAI Press (2010)
Goranko, V., van Drimmelen, G.: Complete axiomatization and decidability of alternating-time temporal logic. Theoretical Computer Science 353(1-3), 93–117 (2006)
Herzig, A., Lorini, E.: A dynamic logic of agency I: STIT, capabilities and powers. Journal of Logic, Language and Information 19(1), 89–121 (2010)
Kartha, N., Lifschitz, V.: A simple formalizations of actions using circumscription. In: Proceedings of IJCAI 1995, pp. 1970–1975 (1995)
Lange, M., Latte, M.: A CTL-based logic for program abstractions. In: Dawar, A., de Queiroz, R. (eds.) WoLLIC 2010. LNCS (LNAI), vol. 6188, pp. 19–33. Springer, Heidelberg (2010)
Lorini, E., Troquard, N., Herzig, A., Broersen, J.: Grounding power on actions and mental attitudes. Logic Journal of the IGPL 21(3), 311–331 (2013)
Mogavero, F., Murano, A., Vardi, M.Y.: Reasoning about strategies. In: Proceedings of FSTTCS 2010, pp. 133–144 (2010)
Reiter, R.: Natural actions, concurrency and continuous time in the situation calculus. In: Proceedings of KR 1996, pp. 2–13. Morgan Kaufmann (1996)
Reiter, R.: Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems. MIT Press (2001)
Shanahan, M.: Solving the frame problem: a mathematical investigation of the common sense law of inertia. MIT Press (1997)
Thielscher, M.: Representing the knowledge of a robot. In: Proceedings of KR 2000, pp. 109–120. Morgan Kaufmann (2000)
Thielscher, M.: Reasoning Robots - The Art and Science of Programming Robotic Agents. Applied Logic, vol. (33). Springer, Dordrecht (2005)
Troquard, N., Walther, D.: On satisfiability in ATL with strategy contexts. In: del Cerro, L.F., Herzig, A., Mengin, J. (eds.) JELIA 2012. LNCS, vol. 7519, pp. 398–410. Springer, Heidelberg (2012)
van der Hoek, W., Jamroga, W., Wooldridge, M.: A logic for strategic reasoning. In: Proceedings of AAMAS 2005, pp. 157–164. ACM Press (2005)
van der Hoek, W., Wooldridge, M.: Cooperation, knowledge, and time: Alternating-time temporal epistemic logic and its applications. Studia Logica 75, 125–157 (2003)
van der Hoek, W., Wooldridge, M.: On the logic of cooperation and propositional control. Artificial Intelligence 164(1-2), 81–119 (2005)
Walther, D.: ATEL with common and distributed knowledge is exptime-complete. In: Proceedings of M4M-4 (2005)
Walther, D., van der Hoek, W., Wooldridge, M.: Alternating-time Temporal Logic with Explicit Strategies. In: Proceedings of TARK 2007, pp. 269–278. ACM (2007)
Walther, D., Lutz, C., Wolter, F., Wooldridge, M.: ATL satisfiability is indeed Exptime-complete. Journal of Logic and Computation 16(6), 765–787 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Herzig, A., Lorini, E., Walther, D. (2013). Reasoning about Actions Meets Strategic Logics. In: Grossi, D., Roy, O., Huang, H. (eds) Logic, Rationality, and Interaction. LORI 2013. Lecture Notes in Computer Science, vol 8196. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40948-6_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-40948-6_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40947-9
Online ISBN: 978-3-642-40948-6
eBook Packages: Computer ScienceComputer Science (R0)