Epistemic logic and explicit knowledge in distributed programming

ABSTRACT

In this paper we propose an explicit form of knowledge-based programming. Our initial motivation is the distributed implementation of game-theoretical algorithms, but we abstract away from the game-theoretical details and describe a general scenario, where a group of agents each have some initially private bits of information which they can then communicate to each other. We draw on existing literature to give a formal model using modal logic to represent the knowledge of the agents as well as how that knowledge changes as they communicate. We sketch an implementation which enables processes in a distributed system to explicitly evaluate knowledge formulae. Then we prove that the implementation captures the formal model, and therefore correctly reflects the general scenario. Finally we look at how our approach lends itself to generalisations, and discuss application perspectives.

REFERENCES

• 1: Itai Ashlagi , Dov Monderer , Moshe Tennenholtz, Resource selection games with unknown number of players, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160782]
• 2: Alexandru Baltag , L. S. Moss , S. Solecki, The logic of public announcements, common knowledge, and private suspicions, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1999
• 3: M. Bickford, R. C. Constable, J. Y. Halpern, and S. Petride. Knowledge-Based Synthesis of Distributed Systems Using Event Structures, volume 3452 of Lecture Notes in Computer Science, pages 449--465. Springer, 2005.
• 4: Patrick Blackburn , Maarten de Rijke , Yde Venema, Modal logic, Cambridge University Press, New York, NY, 2001
• 5: R, H. Bordini, L. Braubach, M. Dastani, A. E. F. Seghrouchni, J. J. Gomez-Sanz, J. Leite, G. O'Hare, A. Pokahr, and A. Ricci. A survey of programming languages and platforms for multi-agent systems. Informatica, 30:33--44, 2006.
• 6: B. J. Clement, editor. Workshop on Multiagent Planning and Scheduling, The 15th International Conference on Automated Planning and Scheduling (ICAPS-05), June 2005.
• 7: Ronald Fagin , Joseph Y. Halpern , Yoram Moses , Moshe Y. Vardi, Knowledge-based programs, Distributed Computing, v.10 n.4, p.199-225, July 1997 [doi>10.1007/s004460050038]
• 8: Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi , Yoram Moses, Reasoning about knowledge, MIT Press, Cambridge, MA, 1995
• 9: J. Gerbrandy. Communication strategies in games. Journal of Applied Non-Classical Logics, 17:197--211, 2007.
• 10: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 11: M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994.
• 12: Rohit Parikh , Ramaswamy Ramanujam, A Knowledge Based Semantics of Messages, Journal of Logic, Language and Information, v.12 n.4, p.453-467, Fall 2003 [doi>10.1023/A:1025007018583]

INDEX TERMS

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

General Terms:
Algorithms, Economics, Theory, Verification

Keywords:
explicit knowledge programming