Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2017, Vol. 11 Issue (3) : 499-510    https://doi.org/10.1007/s11704-016-5100-y
RESEARCH ARTICLE
Reasoning about knowledge, belief and certainty in hierarchical multi-agent systems
Lijun WU1,2(), Kaile SU3, Yabiao HAN1, Jingyu CHEN1, Xiangyu LU4
1. School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 610074, China
2. Network Space Security Center, University of Electronic Science and Technology of China, Chengdu 610074, China
3. Institute for Integrated and Intelligent Systems, Griffith University, Brisbane 4000, Australia
4. College of Computer Science and Technology, Huaqiao University, Xiamen 361000, China
 Download: PDF(332 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

Multi-agent systems (MAS) have received extensive studies in the last decade. However, little attention is paid to investigation on reasoning about logics in MAS with hierarchical structures. This paper proposes a complete quantified temporal KBC (knowledge, belief and certainty) logic and corresponding reasoning in hierarchical multi-agent systems (HMAS). The key point is that internal beliefs and certainty, and external belief and certainty are considered in our logic. The internal beliefs and certainty show every agent is autonomous, while the external belief and certainty indicate the mutual influence of mental attitudes between two different agents on different layers in HMAS. To interpret this logic, we propose four classes of corresponding quantified interpreted systems, and define first-order KBC axiomatisations over HMAS, which are sound and complete with respect to the corresponding semantical classes. Finally, we give a case study to show the advantages in terms of expressiveness of our logic.

Keywords hierarchical multi-agent systems      quantified temporal KBC logic      quantified interpreted systems     
Corresponding Author(s): Lijun WU   
Just Accepted Date: 16 June 2016   Online First Date: 23 March 2017    Issue Date: 25 May 2017
 Cite this article:   
Lijun WU,Kaile SU,Yabiao HAN, et al. Reasoning about knowledge, belief and certainty in hierarchical multi-agent systems[J]. Front. Comput. Sci., 2017, 11(3): 499-510.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-016-5100-y
https://academic.hep.com.cn/fcs/EN/Y2017/V11/I3/499
1 LenzenW. Recent work in epistemic logic. Acta Philosophica Fennica, 1978, 30(9): 200–219
2 FaginR, Halpern J, MossY , VardiM. Reasoning About Knowledge. Cambridge: MIT Press, 1995
3 MeyerJ J C, Van der Hoek W. Epistemic logic for AI and Computer Science. Cambridge: Cambridge University Press, 1995
https://doi.org/10.1017/CBO9780511569852
4 AumannR J, Brandenburger A. Epistemic conditions for nash equilibrium. Econometrica, 1995, 63(9): 116–180
https://doi.org/10.2307/2171725
5 FaginR, Halpern J Y, VardiM Y . What can machines know? On the properties of knowledge in distributed systems.Journal of the ACM, 1992, 39(2): 328–378
https://doi.org/10.1145/128749.150945
6 HoekW V D, MeyerJ J, TreurJ. Formal semantics of temporal epistemic reflection Logic. In: Proceedings of the 4th International Workshops on Meta-Programming in Logic. 1994, 332–352
7 Van Der MeydenR. Axioms for knowledge and time in distributed systems with perfect recall. In: Proceedings of the 9th IEEE Symposium on Logic in Computer Science. 1993, 15–22
8 LakemeyerG. Limited reasoning in first-order knowledge bases with full introspection. Artificial Intelligence, 1996, 84(1): 209–255
https://doi.org/10.1016/0004-3702(95)00063-1
9 LomuscioA, Colombetti M. QLB: a quantified logic for belief. In: Proceedings of the 3rd International Workshop on Agent Theories, Architectures, and Languages. 1996
10 RenneB, SackJ, YapA. Logics of temporal-epistemic actions. Synthese, 2016, 193(3): 813–849
https://doi.org/10.1007/s11229-015-0773-6
11 ChenQ L, SuK L, HuY, HuGW. A complete coalition logic of temporal knowledge for multi-agent systems. Frontiers of Computer Science, 2015, 9(1): 75–86
https://doi.org/10.1007/s11704-014-4097-3
12 WuL J, SuK L, SattarA, Chen Q L, SuJ S , WuW. A complete firstorder temporal BDI logic for forest multi-agent systems. Knowledge- Based Systems, 2012, 27(3): 343–351
https://doi.org/10.1016/j.knosys.2011.11.006
13 LamarreP, ShohamY. Knowledge, certainty, belief, and conditionalisation, belief and certainty. In: Proceedings of the International Conference on Knowledge Representation and Reasoning. 1994, 415–424
https://doi.org/10.1016/B978-1-4832-1452-8.50134-2
14 SuK L, SattarA, GovernatoriG , ChenQ L. A computational grounded logic of knowledge, belief and certainty. In: Proceedings of the 4th International Joint Conference on Autonomous Agents and Multi-agent Systems. 2005, 149–156
15 VoorbraakF. The theory of objective knowledge and rational belief. In: Proceedings of Logics in AI, European Workshop. 1990, 499–515
16 FollesdalD. Knowledge, identity, and existence. Theoria, 1967, 23(1): 1–27
17 HintikkaY. Knowledge, identity, and existence. Nous, 1962, 1(1): 33–62
https://doi.org/10.2307/2214711
18 LevesqueH. Knowledge representation and reasoning. Annual Reviews Computer Science, 1986, 30(1): 81–108
https://doi.org/10.1146/annurev.cs.01.060186.001351
19 LiuY M, Levesque H J. Tractable reasoning in first-order knowledge bases with disjunctive information. In: Proceedings of National Conference on Artificial Intelligence. 2005, 639–644
20 KanekoM, Nagashima T. Game logic and its applications 1. Studia Logica, 1996, 57(1): 325–354
https://doi.org/10.1007/BF00370838
21 KanekoM, Nagashima T. Game logic and its applications 2. Studia Logica, 1997, 58(1): 273–303
https://doi.org/10.1023/A:1004975724824
22 BieberP. A Logic of communication in hostile environments. In: Proceedings of the 3rd IEEE Computer Security Foundations Workshop. 1990, 14–22
https://doi.org/10.1109/csfw.1990.128181
23 CohenM, DamsM. A complete axiomatization of knowledge and cryptography. In: Proceedings of IEEE Symposium on Logic in Computer Science. 2007, 77–88
https://doi.org/10.1109/lics.2007.4
24 WooldridgeM. Verifying that agents implement a communication language. In: Proceedings of the 16th National Conference on Artificial Intelligence and the 11th Innovative Applications of Artificial Intelligence Conference Innovative Applications of Artificial Intelligence. 1999, 52–57
25 WooldridgeM, FisherM, HugetM, Parsons S. Model checking multiagent systems with MABLE. In: Proceedings of the 1st International Conference on Autonomous Agents and Multiagent Systems. 2002, 952–959
26 SuK L, SattarA, LuoX Y. Model checking temporal logics of knowledge via OBDDs. Computer Journal, 2007, 50(4): 403–420
https://doi.org/10.1093/comjnl/bxm009
27 BelardinelliF, Lomuscio A. A complete first-order logic of knowledge and time. In: Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning. 2008, 705–714
28 BelardinelliF, Lomuscio A. Quantified epistemic logics for reasoning about knowledge in multi-agent systems. Artificial Intelligence, 2009, 173(9): 982–1013
https://doi.org/10.1016/j.artint.2009.02.003
29 BelardinelliF, Lomuscio A. Interactions between time and knowledge in a first-order logic for multi-agent systems. In: Proceedings of the 12th International Conference on Principles of Knowledge Representation and Reasoning. 2010, 38–48
30 BelardinelliF, Lomuscio A. First-order linear-time epistemic logic with group knowledge: an axiomatisation of the monodic fragment. Fundamenta Informaticae, 2010, 17(9): 175–190
31 WooldridgeM, Jennings N. Intelligent agents: theory and practice. Knowledge Engineering Review, 1995, 10(2): 49–62
https://doi.org/10.1017/S0269888900008122
32 WuL J, SuJ S, SuK L, Luo X Y, YangZ H . A concurrent dynamic logic of knowledge, belief, and certainty for multi-agent systems. Knowledge-Based Systems, 2010, 23(2): 162–168
https://doi.org/10.1016/j.knosys.2009.11.017
33 AdamE, Mandiau R. Roles and hierarchy in multi-agent organizations. In: Proceedings of the 4th International Central and Eastern European Conference on Multi-Agent Systems. 2005, 539–542
https://doi.org/10.1007/11559221_55
34 Emadi AndaniM, Bahrami F, Jabehdar-MaralaniP, IjspeertA J . MODEM: a multiagent hierarchical structure to model the human motor control system. Biological Cybernetics, 2009, 101(5): 361–377
https://doi.org/10.1007/s00422-009-0342-5
35 ChoińskiD, Nocoń W, MetzgerM . Multi-agent system for hierarchical control with self-organising database. In: Proceedings of the 1st KES Symposium on Agent and Multi-Agent Systems: Technologies and Applications. 2007, 655–664
https://doi.org/10.1007/978-3-540-72830-6_68
36 BlackburnP, van Benthem J F A K, WolterF . Handbook of modal logic. Cambridge Tracts in Theoretical Computer Science, 2007, 53(2): 170–180
37 ChagrovA, Zakharyaschev M. Modal Logic. Oxford: Clarendon Press, 1997
38 HughesM J, Cresswell G E. A new introduction to modal logic. New York: Routledge, 1996
https://doi.org/10.4324/9780203290644
39 HalpernJ Y, MeydenR V, VardiM Y. Complete axiomatisations for reasoning about knowledge and time. SIAM Journal on Computing, 2003, 33(3): 674–703
https://doi.org/10.1137/S0097539797320906
[1] FCS-0499-15100-LJW_suppl_1 Download
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed