An extension of process calculus for asynchronous communications between agents with epistemic states

Abstract

It plays a central role in intelligent agent systems to model agents’ epistemic states and their changes. Asynchrony plays a key role in distributed systems, in which the messages transmitted may not be received instantly by the agents. To characterize asynchronous communications, Asynchronous Announcement Logic (AAL) has been presented, which focuses on the logic laws of the change of epistemic state after receiving information. However AAL does not involve the interactive behaviours between an agent and its environment. Epistemic interactions can change agents’ epistemic states, while the latter will affect the former. Through enriching the well-known \pi-calculus by adding the operators for passing basic facts and applying the well-known action model logic to describe agents’ epistemic states, this paper presents the e-calculus to model epistemic interactions between agents with epistemic states. The e-calculus can be adopted to characterize synchronous and asynchronous communications between agents. To capture the asynchrony, a buffer pool is constructed to store the basic facts announced and each agent reads these facts from this buffer pool in some order. Based on the transmission of link names, the e-calculus is able to realize reading from this buffer pool in different orders. This paper gives two examples: one is to read in the order in which the announced basic facts are sent (First-in-first-out, FIFO), and the other is in an arbitrary order.

Graphical abstract

Keywords

process calculus / epistemic interaction / asynchronous communication

Huili Xing received the BS and ME degrees in computer science respectively from Shandong University, China and Ocean University of China. She is currently pursuing PhD in computer science at Nanjing University of Aeronautics and Astronautics, China. She is also an associate professor at Binzhou Medical University, China. Her research interests include artificial intelligence, logic in computer science and formal methods, which are mainly focused on theoretical research

Zhaohui Zhu received the BS, ME and PhD degrees in computer science and technology from Nanjing University of Aeronautics and Astronautics (NUAA), China in 1992, 1995 and 1998, respectively. He has been a professor of NUAA since 2004. His current research interests include logic in computer science and AI, process algebra and coalgebra

Jinjin Zhang received his PhD degree in computer science and technology from the Institute of Computing Technology, Nanjing University of Aeronautics and Astronautics, China in 2011. He is an assistant professor of Nanjing Audit University, China. His current research interests include software engineering and logic in computer science. He chairs a National Science Fund for Distinguished Young Scholars, a China Postdoctoral Science Foundation, a mathematical talent fund project of the National Natural Science Foundation of China and a major project of Natural Science Fund for Colleges and Universities in Jiangsu Province

References

[1] Pettinati M J, Arkin R C. Push and pull: shepherding multi-agent robot teams in adversarial situations. In: Proceedings of 2019 IEEE International Conference on Advanced Robotics and Its Social Impacts (ARSO). 2019, 665−679

[2] Seuken S, Zilberstein S. Formal models and algorithms for decentralized decision making under uncertainty. Autonomous Agents and Multi-Agent Systems, 2008, 17( 2): 190–250

[3] Harikumar K, Senthilnath J, Sundaram S. Multi-UAV oxyrrhis marina-inspired search and dynamic formation control for forest firefighting. IEEE Transactions on Automation Science and Engineering, 2019, 16( 2): 863–873

[4] Azizi S M, Khorasani K. A hierarchical architecture for cooperative actuator fault estimation and accommodation of formation flying satellites in deep space. IEEE Transactions on Aerospace and Electronic Systems, 2012, 48( 2): 1428–1450

[5] Hu J, Bhowmick P, Lanzon A. Distributed adaptive time-varying group formation tracking for multiagent systems with multiple leaders on directed graphs. IEEE Transactions on Control of Network Systems, 2020, 7( 1): 140–150

[6] van Ditmarsch H. Asynchronous announcements. 2017, arXiv preprint arXiv: 1705.03392v2

[7] Balbiani P, van Ditmarsch H, González S F. Asynchronous announcements. ACM Transactions on Computational Logic, 2022, 23( 2): 10

[8] Knight S, Maubert B, Schwarzentruber F. Reasoning about knowledge and messages in asynchronous multi-agent systems. Mathematical Structures in Computer Science, 2019, 29( Spec.1): 127–168

[9] Baltag A, Moss L S, Solecki S. The logic of public announcements, common knowledge, and private suspicions. In: Proceedings of the 7th Conference on Theoretical Aspects of Rationality and Knowledge. 1998, 43−56

[10] Plaza J. Logics of public communications. Synthese, 2007, 158( 2): 165–179

[11] Fagin R, Halpern J Y, Moses Y, Vardi M Y. Reasoning About Knowledge. Cambridge: The MIT Press, 2003

[12] van Ditmarsch H, van der Hoek W, Kooi B. Dynamic Epistemic Logic. Berlin: Springer, 2007, 337

[13] van Benthem J, van Eijck J, Kooi B. Logics of communication and change. Information and Computation, 2006, 204( 11): 1620–1662

[14] Ågotnes T, Balbiani P, van Ditmarsch H, Seban P. Group announcement logic. Journal of Applied Logic, 2010, 8( 1): 62–81

[15] French T, Hales J, Tay E. A composable language for action models. In: Goré R, Kooi B, Kurucz A, eds. Advances in Modal Logic, Volume 10. CSLI Publications, 2014, 197−216

[16] Hales J. Arbitrary action model logic and action model synthesis. In: Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in Computer Science. 2013, 253−262

[17] Renne B, Sack J, Yap A. Logics of temporal-epistemic actions. Synthese, 2016, 193( 3): 813–849

[18] Engesser T, Mattmüller R, Nebel B, Thielscher M. Game description language and dynamic epistemic logic compared. Artificial Intelligence, 2021, 292: 103433

[19] van Ditmarsch H. The logic of knowledge games: showing a card. In: Proceedings of the BNAIC 99. 1999, 35−42

[20] van Ditmarsch H P, van der Hoek W, Kooi B P. Dynamic epistemic logic with assignment. In: Proceedings of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems. 2005, 141−148

[21] Benevides M F, Lima I M S. Dynamic Epistemic Logic with Assignments, Concurrency and Communication Actions. Porto Alegre: Sociedade Brasileira de Computação, 2020

[22] van Ditmarsch H, French T. Simulation and information: quantifying over epistemic events. In: Proceedings of the 1st International Workshop on Knowledge Representation for Agents and Multi-Agent Systems. 2008, 51−65

[23] van Ditmarsch H, French T, Pinchinat S. Future event logic-axioms and complexity. In: Beklemishev L, Goranko V, Shehtman V, eds. Advances in Modal Logic, Volume 8. Moscow: College Publications, 2010, 77−99

[24] Balbiani P, Baltag A, van Ditmarsch H, Herzig A, Hoshi T, de Lima T. ‘knowable’ as ‘known after an announcement’. The Review of Symbolic Logic, 2008, 1( 3): 305–334

[25] Milner R, Parrow J, Walker D. A calculus of mobile processes, parts I and II. Technical Report ECS-LFCS-89-85 and -86. Scotland: University of Edinburgh, 1989

[26] Milner R, Parrow J, Walker D. A calculus of mobile processes, parts I and II. Information and Computation, 1992, 100(1): 1−77

[27] Sangiorgi D, Walker D. The π-Calculus: A Theory of Mobile Processes. New York: Cambridge University Press, 2001

[28] Plotkin G D. A structural approach to operational semantics. Report DAIMI FN-19. Computer Science Department, Aarhus University, 1981, 17−139

[29] Bozzelli L, van Ditmarsch H, French T, Hales J, Pinchinat S. Refinement modal logic. Information and Computation, 2014, 239: 303-339

[30] Knight S. The epistemic view of concurrency theory. In: Logic in Computer Science. Palaiseau: Ecole Polytechnique, 2013 1991, 333−352

[31] Saraswat V A, Rinard M, Panangaden P. Semantic foundations of concurrent constraint programming. In: Proceedings of the 18th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 1991, 333-352

[32] Dubois D, Prade H. Belief revision: belief change and possibility theory. In: Gärdenfors P, ed. Belief Revision. Cambridge: Cambridge University Press, 1992

[33] Jin Y, Thielscher M. Iterated belief revision, revised. Artificial Intelligence, 2007, 171( 1): 1–18

[34] Blackburn P, de Rijke M, Venema Y. Modal Logic. Cambridge: Cambridge University Press, 2002

[35] Xing H, Zhu Z, Zhang J. A calculus for epistemic interactions. 2022, arXiv preprint arXiv: 2206.14506v1

Acknowledgements

This work received financial support of the Natural Science Foundation of Shandong Province (No. ZR2020MF144) and Postgraduate Research and Practice Innovation Program of Jiangsu Province (No. KYCX17_0288).

Competing interests

The authors declare that they have no competing interests or financial conflicts to disclose.

RIGHTS & PERMISSIONS

2025 Higher Education Press