What agents can achieve under incomplete information

ABSTRACT

We propose a non-standard semantics for Alternating-time Temporal Logic (ATL) with incomplete information, for which no commonly accepted semantics has been proposed yet. In our semantics, formulae are still interpreted with respect to ATL structures, but are interpreted in sets of states rather than in single states. We also propose a new epistemic operator for "constructive" knowledge, and we show that the new language is strictly more expressive than existing solutions, while retaining the same model checking complexity.

REFERENCES

• 1: Rajeev Alur , Thomas A. Henzinger , Orna Kupferman, Alternating-time temporal logic, Journal of the ACM (JACM), v.49 n.5, p.672-713, September 2002 [doi>10.1145/585265.585270]
• 2: Andreas Herzig , Nicolas Troquard, Knowing how to play: uniform choices in logics of agency, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160666]
• 3: W. Jamroga. Some remarks on alternating temporal epistemic logic. In Proc. of FAMAS, p. 133--140, 2003.
• 4: W. Jamroga and J. Dix. Model checking strategic abilities of agents under incomplete information. In Proceedings of ICTCS 2005, pages 295--308, 2005.
• 5: Wojciech Jamroga , Wiebe van der Hoek, Agents that Know How to Play, Fundamenta Informaticae, v.63 n.2-3, p.185-219, April 2004
• 6: G. Jonker. Feasible strategies in Alternating-time Temporal Epistemic Logic. Master thesis, 2003.
• 7: W. Quine. Quantifiers and propositional attitudes. Journal of Philosophy, 53:177--187, 1956.
• 8: P. Y. Schobbens. Alternating-time logic with imperfect recall. Electronic Notes in Theoretical Computer Science, 85(2), 2004.
• 9: Wiebe van der Hoek , Michael Wooldridge, Tractable multiagent planning for epistemic goals, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 3, July 15-19, 2002, Bologna, Italy [doi>10.1145/545056.545095]
• 10: S. van Otterloo and G. Jonker. On Epistemic Temporal Strategic Logic. In Proc. of LCMAS, 2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Modal logic

General Terms:
Theory

Keywords:
alternating-time temporal logic, epistemic logic, incomplete information, strategic ability