[發明專利]一種一階并行、帶優先級和逐點的限定理論計算方法

在審

• 申請號: 201510097186.1
• 申請日: 2015-03-04
• 公開（公告）號: CN104750974A
• 公開（公告）日: 2015-07-01
• 發明（設計）人: 萬海;蕭展豪;曾娟
• 申請（專利權）人: 中山大學
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 林麗明

技術領域

本發明涉及人工智能領域的非單調邏輯系統計算方法，具體涉及一種一階并行、帶優先級和逐點的限定理論高效計算方法。

背景技術

圖靈獎獲得者、人工智能領域先驅John?McCarthy(1927.9-2011.10)于1959年提出了著名的Advice?Taker計劃，指出常識推理(Commonsense?reasoning)能力是實現人工智能的關鍵，這也是人工智能領域所面臨最困難的問題之一。John?McCarthy在上世紀八十年代初提出了一種叫做限定理論的非單調邏輯理論，然后在1986年擴展了他之前提出的限定概念，將限定理論從限定一個謂詞擴展到同時限定多個謂詞，并稱之為并行限定理論(Parallel?Circumscription)。Vladimir?Lifschitz于1987年用另一種角度去闡釋“限定”這一概念，引入了“逐點”和“優先級”的思想，提出了逐點的限定理論(Pointwise?Circumscription)。1994年，Vladimir?Lifschitz中對John?McCarthy的限定理論進行了改進，引入了謂詞“優先級”的思想，提出了帶優先級的限定理論(Prioritized?Circumscription)的概念，并給出了并行和帶優先級的限定理論精確的數學定義。

自一階限定理論誕生以來，國內外的研究者與學者一直致力于研究如何計算限定理論，以求在計算機中實現這種能夠處理常識知識的邏輯系統。MarcoCadoli等人提出了一個多項式算法，將一個帶可變謂詞的限定理論的推理問題轉化為一個沒有可變謂詞的限定理論的推理問題，簡化了限定理論的推理問題的計算方法。1994年，Vladimir?Lifschitz中總結了限定理論的性質，并利用這些性質提出了簡化限定理論的方法，例如謂詞完備，就能將形如F(x)→P(x)的一階限定理論化簡為與之等價的一階公式以及消去可變常元方法，利用正反公式方法等。Patrick?Doherty等人于1997年提出了一個算法將在限定理論語義下的一類一階理論歸約為一個一階理論，在利用Tablueax方法計算該一階理論，從而實現在固定Herbrand域和帶可變謂詞的限定理論的求解方法。實質上，他們將一個受限的二階邏輯下的計算問題轉化為一個一階邏輯下的計算問題。2004年，ToshikoWakaki和Katsumi?Inoue將帶優先級的限定理論重新編譯成一個邏輯程序，在利用一個回答集求解器實現一個限定理論求解器來求出所有的極小模型。但是，他們的方法不能處理存在量詞，而且必須限制在一個固定的Herbrand域。后來Emilia?Oikarinen和Tomi?Janhunen中利用了析取邏輯程序中的飽和技術，提出了一個線性時間的翻譯算法，將帶優先級的限定理論轉化為一個析取邏輯程序，將求極小模型的問題轉化為求回答集的問題。但是，這個方法的輸入必須是正析取邏輯程序，不允許帶存在量詞，雖然比起Toshiko?Wakaki等人的方法有更好求解效率，但是仍然屬于一種命題限定理論的求解器。Joohyung?Lee等在2009年提出了在限定理論語義下的一類“典型的”一階理論，直接等價于穩定模型語義下的一階理論。2011年，章衡等提出了將任意一個不帶可變謂詞的在限定理論語義下的一階理論在在任意論域轉化為與之等價的穩定模型語義下的一階理論的翻譯算法，將計算限定理論嵌入到計算穩定模型中。

發明內容

為了克服目前僅可以求解命題限定理論、不能處理存在量詞、缺乏有效求解器的不足，本發明提出一種一階并行、帶優先級和逐點的限定理論高效計算方法，解決了一階限定理論缺乏有效的求解器的現狀，并采用該方法可以設計與實現處理能力強、計算高效的一階并行、帶優先級和逐點限定理論的求解器。

為了實現上述目的，本發明的技術方案為：

一種一階并行、帶優先級和逐點的限定理論計算方法，用于將采用并行、帶優先級和逐點的限定理論描述的問題翻譯成穩定模型下的一階理論，在一般結構下消去一階穩定模型理論中的存在量詞，對優化后的一階回答集邏輯程序調用回答集邏輯程序求解器進行計算；具體包括以下步驟：

(1)將任意一個一階限定理論在線性時間內翻譯為另一個與之在任意結構上邏輯等價的在穩定語義下的一階理論，包括四個基于語法層面的主要翻譯：從一階并行限定理論到一階穩定理論、從若干個一階并行限定理論的合取到一階穩定理論、從一階帶優先級的限定理論到一階穩定理論、從一階逐點限定理論到一階穩定理論；