计算机科学 ›› 2019, Vol. 46 ›› Issue (7): 195-205.doi: 10.11896/j.issn.1002-137X.2019.07.030

• 人工智能 • 上一篇    下一篇

多智能体模态逻辑系统KD45n中的知识遗忘

文习明1,2,方良达2,3,余泉2,4,常亮2,王驹2   

  1. (广东行政学院信息技术教研部 广州510053)1
    (广西可信软件重点实验室(桂林电子科技大学) 广西 桂林541004)2
    (暨南大学计算机科学系 广州510632)3
    (黔南民族师范学院数学与统计学院 贵州 都匀558000)4
  • 收稿日期:2018-07-09 出版日期:2019-07-15 发布日期:2019-07-15
  • 作者简介:文习明(1979-),男,博士,讲师,主要研究方向为人工智能、知识表示与推理,E-mail:wenxim@mail2.sysu.edu.cn(通信作者);方良达(1985-),男,博士,讲师,CCF会员,主要研究方向为人工智能、知识表示与推理;余 泉(1979-),男,博士,教授,CCF会员,主要研究方向为人工智能、知识表示与推理;常 亮(1980-),男,博士,教授,CCF会员,主要研究方向为知识表示与推理、形式化方法;王 驹(1950-),男,博士,教授,主要研究方向为逻辑、泛代数、知识表示与推理、形式化方法。
  • 基金资助:
    国家自然科学基金项目(61603152,61463044,61363030),广西可信软件重点实验室研究课题(KX201604,KX201606,KX201419),广西自然科学基金项目(2015GXNSFAA139285)资助

Knowledge Forgetting in Multi-agent Modal Logic System KD45n

WEN Xi-ming1,2,FANG Liang-da2,3,YU Quan2,4,CHANG Liang2,WANG Ju2   

  1. (Department of Information Science,Guangdong Institute of Public Administration,Guangzhou 510053,China)1
    (Guangxi Key Laboratory of Trusted Software(Guilin University of Electronic Technology),Guilin,Guangxi 541004,China)2
    (Department of Computer Science,Jinan University,Guangzhou 510632,China)3
    (School of Mathematics and Statistics,Qiannan Normal College for Nationalities,Duyun,Guizhou 558000,China)4
  • Received:2018-07-09 Online:2019-07-15 Published:2019-07-15

摘要: 遗忘在知识表示与推理领域扮演着非常重要的角色。遗忘在多种逻辑语言中都有大量的研究,被广泛应用于诸多领域。模态逻辑适用于智能体的知识表示与推理。随着多智能体系统研究的发展,多智能体模态逻辑中的知识遗忘也开始被关注。现有研究表明,知识遗忘在不同的多智能体模态逻辑系统中具有不同的性质,且大多无法有效计算。为此,多智能体模态逻辑系统KD45n中的知识遗忘值得进一步研究。首先,基于模型理论给出知识遗忘的定义;接着,分析KD45n中知识遗忘的主要性质;最后,提出KD45n中计算知识遗忘的有效算法。该算法利用人工智能领域解决难求解问题的主要方法之一——知识编译技术,将一般公式编译成交替覆盖析取范式,再利用该范式进行知识遗忘的有效计算。研究结果表明,在KD45n中满足一些很重要的知识遗忘性质,其计算时间复杂度是交替覆盖析取范式公式长度的多项式时间(原公式长度的双重指数时间)。与现有的非初等时间复杂度算法相比,所提算法更高效、更实用。

关键词: 多智能体模态逻辑, 知识编译, 知识推理, 知识遗忘

Abstract: Forgetting plays an important role in knowledge representation and reasoning.It has been extensively studied in many logics and been widely applied to various fields.Modal logic is suitable for representing and reasoning about the knowledge of agents.With the development of the research on multi-agent systems,the investigation on knowledge forgetting in multi-agent modal logics begins to attract attention.However,knowledge forgetting has different properties in different multi-agent modal logic systems,and it cannot be effectively computed in most cases.Therefore,it is necessary to make further investigation on the knowledge forgetting in the multi-agent modal logic system KD45n.Firstly,the knowledge forgetting in the multi-agent modal logic was defined based on model theory.Then,the main properties of knowledge forgetting in KD45n were analyzed.Finally,an effective algorithm to compute knowledge forgetting in KD45n was provided.The computing algorithm adopts the idea of knowledge compilation which is an approach for addressing the intractability of a number of artificial intelligence problems.The alternating cover disjunctive formula is introduced.By compiling the general formula into alternating cover disjunctive formula,knowledge forgetting in KD45n can be effectively computed.The time complexity is double-exponential in the length of the original formula,but polynomial in the length of the compiled one.Compared with the current non-elementary one,the algorithm is more effective and more practical.The results of research show that knowledge forgetting in KD45n satisfies many important properties and can be effectively computed.

Key words: Knowledge compilation, Knowledge forgetting, Multi-agent modal logic, Reasoning about knowledge

中图分类号: 

  • TP181
[1]BOOLE G.The laws of thought[M].London:Walton and Maberley,1854.<br /> [2]LIN F Z.On strongest necessary and weakest sufficient conditions [J].Artificial Intelligence,2001,128(1-2):143-159.<br /> [3]DOHERTY P,LUKASZEWICZ W,SZALAS A.Computing strongest necessary and weakest sufficient conditions of first-order formulas[C]∥Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI-2001).Morgan Kaufmann Publishers,2001:145-154.<br /> [4]LIN F Z,REITER R.Forget it! [C]∥Proceedings of AAAI Fall Symposium on Relevance.AAAI Press,1994:141-146.<br /> [5]LANG J,LIBERATORE P,MARQUIS P.Propositional independence:Formula-variable independence and forgetting[J].Journal of Artificial Intelligence Research,2003(18):391-443.<br /> [6]FANG L D,WAN H,LIU X Q,et al.Dependence in propositional logic:Formula-formula dependence an formula forgetting-application to belief update and conservative extension[C]∥Proceedings of the 32th AAAI Conference on Artificial Intelligence (AAAI-2018).AAAI Press,2018:1835-1844.<br /> [7]SU K L,SATTAR A,LV G F,et al.Variable forgetting in reasoning about knowledge [J].Journal of Artificial Intelligence Research,2009(35):677-716.<br /> [8]LANG J,MARQUIS P.Reasoning under inconsistency:A forgetting-based approach [J].Artificial Intelligence,2010,174(12-13):799-823.<br /> [9]ZHANG Y,FOO N.Solving logic program conflict through strong and weak forgettings [J].Artificial Intelligence,2006,170(8/9):739-778.<br /> [10]ZHANG X W.Forgetting for distance-based reasoning and repair in DL-Lite [J].Knowledge-Based Systems,2016(107):246-260.<br /> [11]XIAO P,WANG K W,WANG Z.Inconsistency-tolerant forgetting in DL-lite [C]∥Proceedings of the 16th International Semantic Web Conference.Springer,2017.<br /> [12]CATE B T,CONRADIE W,MARX M,et al.Definitorially complete description logics [C]∥Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR-2006).AAAI Press,2006:79-89.<br /> [13]WANG Z,WANG K W,TOPOR R W,et al.Uniform interpolation for ALC revisited [C]∥Australasian Joint Conference on Advances in Artificial Intelligence (ACAI-2009).Springer,2009:528-537.<br /> [14]WANG Z,WANG K W,TOPOR R W,et al.Tableau-based forgetting in ALC ontologies [C]∥Proceedings of the 19th European Conference on Artificial Intelligence (ECAI-2010).IOS Press,2010:47-52.<br /> [15]WANG K W,WANG Z,TOPOR R W,et al.Eliminating con- cepts and roles from ontologies in expressive descriptive logics [J].Computational Intelligence,2014,30(2):205-232.<br /> [16]KONTCHAKOV R,WOLTER F,ZAKHARYASCHEV M. Logic-based ontology comparison and module extraction,with an application to DL-Lite [J].Artificial Intelligence,2010,174(15):1093-1141.<br /> [17] KONEV B,WALTHER D,WOLTER F.Forgetting and uniform interpolation in large-scale description logic terminologies [C]∥Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI-2009).AAAI Press,2009:830-835.<br /> [18] LUTZ C,SEYLAN I,WOLTER F.An automata-theoretic approach to uniform interpolation and approximation in the description logic EL [C]∥Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR-2012).AAAI Press,2012:286-296.<br /> [19]LUTZ C,WOLTER F.Foundations for uniform interpolation and forgetting in expressive description logics [C]∥Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-2011).AAAI Press,2011:989-995.<br /> [20]LUDWIG M,KONEV B.Practical uniform interpolation and forgetting for ALC TBoxes with applications to logical Diffe-rence[C]∥Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR-2014).AAAI Press,2014:318-327.<br /> [21]KOOPMANN P,SCHMIDT R A.Count and forget:Uniform interpolation of SHQ-ontologies [C]∥Proceedings of the 7th International Joint Conference on Automated Reasoning (IJCAR-2014).Springer,2014:434-448.<br /> [22]ZHAO Y,SCHMIDT R A.Concept forgetting in ALCOI-onto- logies using an Ackermann approach [C]∥Proceedings of the 14th International Semantic Web Conference (ISWC-2015).New York:Springer,2015:587-602.<br /> [23]KOOPMANN P,SCHMIDT R A.Uniform interpolation and forgetting for ALC ontologies with ABoxes[C]∥Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI-2015).AAAI Press,2015:175-181.<br /> [24]WANG Z,WANG K W,TOPOR R W,et al.Forgetting for knowledge bases in DL-Lite [J].Annals of Mathematics and Artificial Intelligence,2010,58(1-2):117-151.<br /> [25]KONTCHAKOV R,WOLTER F,ZAKHARYASCHEV M. Can you tell the difference between DL-Lite ontologies? [C]∥Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR-2008),AAAI Press,2008:285-295.<br /> [26]NAYAK A,CHEN Y,LIN F Z.Forgetting and knowledge update [C]∥Proceedings of 19th Australian Joint Conference on Artificial Intelligence (AI-2006).Springer,2006:131-140.<br /> [27]LIN F Z,REITER R.How to progress a database [J].Artificial Intelligence,1997,92(1-2):131-167.<br /> [28]ZHANG Y,ZHOU Y.Knowledge forgetting:Properties and applications [J].Artificial Intelligence,2009,173(16-17):1525-1537.<br /> [29]LIU Y M,LAKEMEYER G.On first-order definability and computability of progression for local-effect actions and beyond [C]∥Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI-2009).AAAI Press,2009:860-866.<br /> [30]LIU Y M,WEN X M.On the progression of know- ledge in the situation calculus [C]∥Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-2011).AAAI Press,2009:976-982.<br /> [31]FANG L D,LIU Y M,WEN X M.On the progression of know- ledge and belief for nondeterministic actions in the situation calculus [C]∥Proceedings of the 29th International Conference on Artificial Intelligence.AAAI Press,2015:2955-2963.<br /> [32]XU D,LIN Z Q.A prime implicates-based formulae forgetting [C]∥Proceedings of IEEE International Conference on Computer Science and Automation Engineering (CSAE-2011).IEEE,2011:128-132.<br /> [33]NONNENGART A,OHLBACH H J,SZALAS A.Elimination of Predicate Quantifiers[C]∥Proceedings of the 16th International Conference on Automated Deduction (CADE-16).Springer,1999:159-181.<br /> [34]ZHANG Y,ZHOU Y.Forgetting revisited [C]∥Proceedings of the 12th International Conference on the Principles ofKnow-ledge Representation and Reasoning (KR-2010).AAAI Press,2010:602-604.<br /> [35]ZHANG Y,ZHOU Y.Bounded forgetting [C]∥Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI-2011),AAAI Press,2011:280-285.<br /> [36]WANG Y S,WANG K W,WANG Z,et al.Knowledge forgetting in circumscription:A preliminary report [C]∥Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI-2015).AAAI Press,2015:1649-1655.<br /> [37]WANG Y S,WANG K W,ZHANG M Y.Forgetting for answer set programs revisited [C]∥Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI-2013).AAAI Press,2013:1162-1168.<br /> [38]WANG Y S,ZHANG Y,ZHOU Y,et al.Knowledge forgetting in answer set programming [J].Journal of Artificial Intelligence Research,2014,(50):31-70.<br /> [39]DELGRANDE J,WANG K W.A syntax-independent approach to forgetting in disjunctive logic programs [C]∥Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI-2015).AAAI Presss,2015:1482-1488.<br /> [40]JI J M,YOU J H,WANG Y S.On forgetting postulates in answer set programming [C]∥Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI-2015).AAAI Press,2015:3076-3083.<br /> [41]EITER T,WANG K W.Semantic forgetting in answer set programming [J].Artificial Intelligence,2008,172(14):1644-1672.<br /> [42]WANG Z,WANG K W,ZHANG X W.Forgetting and unfolding for existential rules [C]∥Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI-18).AAAI Press,2018:2013-2020.<br /> [43]HALPERN J Y,MOSES Y.A guide to completeness and complexity for modal logics of knowledge and belief [J].Artificial Intelligence,1992,54(3):319-379.<br /> [44]HERZIG A,MENGIN J.Uniform interpolation by resolution in modal logic [C]∥Proceedings of the 11th European Conference on Logics in Artificial Intelligence(JELIA 2008).Springer,2008:219-231.<br /> [45]VISSER A.Uniform interpolation and layered bisimulation[M]∥ G del’96:Logical Foundations of Mathematics,Computer Scien-ce and Physics.Springer,1996:139-164.<br /> [46]B LKOV M.Uniform interpolation and propositional quanti- fiers in modal logics[J].Studia Logica,2007,85(1):1-31.<br /> [47]GHILARDI S,LUTZ C,WOLTER F,et al.Conservative extensions in modal logic [C]∥Advances in Modal Logic 6,Papers From the Sixth Conference on “Advances in Modal Logic”.College Publications,2006:187-207.<br /> [48]GHILARDI S,ZAWADOWSKI M.Undefinability of proposi- tional quantifiers in the modal system S4[J].Studia Logica,1995,55(2):259-271.<br /> [49]FANG L D,LIU Y M,DITMARSCH H V.Forgetting in multi-agent modal logics [C]∥Proceedings of the 25 International Joint Conference on Artificial Intelligence (IJCAI-2016).AAAI Press,2016:1066-1073.<br /> [50]BAADER F,CALVANESE D,MCGUINNESS D L,et al.The description logic handbook:theory,implementation,and applications [M].New York:Cambridge University Press,2003:154-155.<br /> [51]HUANG X,FANG B Q,WAN H,et al.A general multi-agent epistemic planner based on higher-order belief change [C]∥Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-2017).AAAI Press,2017:1093-1101.<br /> [52]KRIPKE S.Semantic analysis of modal logic[J].Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik,1963(9):67-96.<br /> [53]BLACKBURN P,DE RIJKE M,VENEMA Y.Modal Logic [M].Cambridge:Cambridge University Press,2001:55-57.<br /> [54]JANIN D,WALUKIEWICZ I.Automata for the modal μ-calculus and related results [M]∥Mathematical Foundations of Computer Science 1995.Springer,1995:552-562.
[1] 马瑞新, 李泽阳, 陈志奎, 赵亮.
知识图谱推理研究综述
Review of Reasoning on Knowledge Graph
计算机科学, 2022, 49(6A): 74-85. https://doi.org/10.11896/jsjkx.210100122
[2] 杨如涵, 戴毅茹, 王坚, 董津.
基于表示学习的工业领域人机物本体融合
Humans-Cyber-Physical Ontology Fusion of Industry Based on Representation Learning
计算机科学, 2021, 48(5): 190-196. https://doi.org/10.11896/jsjkx.200500023
[3] 杭婷婷, 冯钧, 陆佳民.
知识图谱构建技术:分类、调查和未来方向
Knowledge Graph Construction Techniques:Taxonomy,Survey and Future Directions
计算机科学, 2021, 48(2): 175-189. https://doi.org/10.11896/jsjkx.200700010
[4] 张春霞, 彭成, 罗妹秋, 牛振东.
数学课程知识图谱构建及其推理
Construction of Mathematics Course Knowledge Graph and Its Reasoning
计算机科学, 2020, 47(11A): 573-578. https://doi.org/10.11896/jsjkx.191200141
[5] 李智星, 任诗雅, 王化明, 沈柯.
基于非结构化文本增强关联规则的知识推理方法
Knowledge Reasoning Method Based on Unstructured Text-enhanced Association Rules
计算机科学, 2019, 46(11): 209-215. https://doi.org/10.11896/jsjkx.181001939
[6] 徐凤生,于秀清,史开泉.
动态知识智能发现与属性逻辑动态关系
Intelligent Discovery of Dynamic Knowledges and Logic Dynamic Relation between their Attributes
计算机科学, 2015, 42(4): 160-165. https://doi.org/10.11896/j.issn.1002-137X.2015.04.032
[7] 邹丽,谭雪微,张云霞.
语言真值直觉模糊逻辑的知识推理
Knowledge Reasoning Based on Linguistic Truth-valued Intuitionstic Fuzzy Logic
计算机科学, 2014, 41(1): 134-137.
[8] 张敬谊,童庆,肖筱华.
用于应急指挥的知识推理技术研究
Research on Knowledge Reasoning Technology in Emergency Command System
计算机科学, 2013, 40(2): 261-264.
[9] 倪俊,陈晓苏,刘辉宇,李劲.
网络安全策略求精一致性检测和冲突消解机制的研究
Research on Network Security Policy Refinement Consistency of Detection and Conflict Resolution Mechanisms
计算机科学, 2011, 38(2): 32-37.
[10] 谷文祥,赵晓威,殷明浩.
知识编译研究
Knowledge Compilation Survey
计算机科学, 2010, 37(7): 20-26.
[11] 游福成 苏占东 谢永红 杨炳儒.
多智体在IDSSIM结构设计中的应用

计算机科学, 2004, 31(3): 118-120.
[12] 江莉 刘三阳 王珏 陆爱国.
Vague决策表的知识获取

计算机科学, 2004, 31(2): 111-112.
[13] 王洁 鞠实儿.
概率逻辑程序

计算机科学, 2003, 30(7): 1-3.
[14] 黄智生.
关于知识的推理新进展

计算机科学, 1994, 21(3): 49-52.
[15] 刘逸敏.
知识编译

计算机科学, 1992, 19(5): 47-49.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!