基于描述邏輯的動作理論研究

劉一松++謝聰銀

摘要：情景演算對于動作理論的描述具有很強的表達能力，但是其推理算法具有不可判定性。在描述邏輯ALCO@的基礎上，構建基于描述邏輯的動作理論系統DL-A。在該系統中，利用描述邏輯語言描述原子動作的表達式以及語義解釋，并在此基礎上利用各種構造符構造出順序、選擇、并發、迭代等復雜動作，同時賦予這些復雜動作的語法和語義。動作的實現會引起周圍世界狀態的改變，描述動作執行所引起的狀態更新算法?；诿枋鲞壿婣LCO@的動作理論不僅具有很強的表達能力，而且其算法具有可判定性，能夠提供多種推理服務，可以應用于Web語義下的動作描述和推理。

關鍵詞：描述邏輯；動作理論；狀態更新；斷言；動作推理；知識表示

DOIDOI：10.11907/rjdk.151392

中圖分類號：TP301

文獻標識碼：A 文章編號文章編號：16727800（2015）008002904

基金項目基金項目：江蘇省科技支撐計劃（社會發展）項目（BE2013696）；江蘇大學高級專業人才科研啟動基金項目（10JDG063）

作者簡介作者簡介：劉一松（1966-），男，湖南長沙人，江蘇大學計算機科學與通信工程學院教授、碩士生導師，研究方向為分布式人工智能、虛擬智能主體、語義網；謝聰銀（1989-），女，江蘇連云港人，江蘇大學計算機科學與通信工程學院碩士研究生，研究方向為描述邏輯。

0 概述

作為用于知識表示的形式化工具，描述邏輯已經被廣泛應用于眾多領域中，如知識表示、信息系統、軟件工程、自然語言處理等。在下一代Web技術的語義Web中，描述邏輯更是扮演著關鍵角色，成為W3C推薦的Web本體語言，是OWL的邏輯基礎。描述邏輯的主要特點在于具有較強的描述能力，同時保證了相關推理問題的可判定性，有較強的推理算法作支撐。

動作的刻畫和推理是知識表示和推理中重要的研究課題，是當前研究熱點語義Web服務和智能主體的理論基礎。目前，比較成熟的動作理論是基于一階謂詞邏輯的動作理論。以情景演算[1]、流演算[2]和STRIPS系統[3]為代表，它們的共同特點是采用一階謂詞邏輯或高階謂詞邏輯中的公式來表達世界狀態、動作的前提條件和動作執行后產生的影響，具有很強的表達能力，但是相關推理問題卻是不可判定的，限制了動作的推理能力。而基于命題動態邏輯的動作理論[4]采用命題公式刻畫世界狀態和動作，雖然具有可判定的推理，但是描述能力卻大大降低。Baader等[5]提出了一種基于描述邏輯的形式系統，使用描述邏輯中的TBox和ABox來描述領域知識和動作，但該形式系統中的復雜動作僅由原子動作的有限序列構成。Wolter[6]將描述邏輯與命題動態邏輯結合，提出了命題動態邏輯PDLC。Y.Gu等[7]以描述邏輯為參照，改進了情景演算，并在此基礎上研究了動作的相關問題。史忠植等[811]提出了一種動態描述邏輯，將描述邏輯與動態邏輯相結合，給出了動態描述邏輯的Tableau算法。常亮等[12]提出了一種基于動態描述邏輯DDL的動作理論，系統研究了動態描述邏輯的動作表示和推理問題，在此基礎上解決了由于動作執行導致的狀態更新問題。

在上述研究的基礎上，本文系統探討基于描述邏輯ALCO@的動作理論。以描述邏輯中的TBox作為刻畫的知識背景，給出原子動作的語法和語義。以描述邏輯中的TBox和ABox為知識庫，給出執行動作后所引起的ABox的更新算法。

1 ALCO@語法和語義

描述邏輯ALCO@的基本符號有：①大寫字母C，D等表示的概念；②由概念組成的集合NC；③小寫字母a，b等表示個體；④由個體組成的集合NI；⑤用大寫字母R1，R2表示描述邏輯中的二元關系；⑥由二元關系組成的集合NR；⑦用希臘字母φ，ψ表示斷言；⑧概念構造符、、、和。

定義1：ALCO@語法。令NC和NR是可數的不相交的原子概念集和原子關系集，ALCO@的概念描述遞歸定義如下：

（1）任意原子A∈NC是ALCO@的概念。

（2）令C和D是 ALCO@的概念，R是 ALCO@的原子關系，即R∈NR，則表達式C（補）、C∪D（并）、C∩D（交）、R.C（存在約束）和R.C（全稱約束）是ALCO@概念。

以下引入描述邏輯中常用的兩個特殊記號：⊥指代空集的底概念，指代論域全集的頂概念。

定義2：ALCO@語義。ALCO@是一個以二元對I = （ΔI，· I），其中ΔI代表論域的非空集合，· I是解釋函數，它將每個A∈Nc映射為ΔI的子集，每個R∈NR映射為ΔI（ΔI的子集，分別稱為原子概念A和原子關系R的解釋，記作AI和RI。

定義3：表達式C≡D稱為概念等價。如果C是一個概念名，該表達式也稱為概念定義式，其中C稱為被定義的概念。

定義4：形如C（a），C（a），R（a，b）和R（a，b）的表達式稱為斷言，其中C∈NC，a，b∈NI，R∈NR。描述邏輯中的ABox是由概念斷言和關系斷言組成的知識庫，TBox是由概念和概念定義式組成的集合，TBox為ABox的表達提供一個規范。定義5：標準否定范式。ALCO@的概念是標準否定范式，當且僅當概念表達式中所有的否定符號（）只出現在原子概念的前面。運用以下規則可以將任意ALCO@概念轉化為相應的標準否定范式：C ≡ C（CD） ≡ C ∪D（CD） ≡ C ∩ D（R.D） ≡ R.D（R.D） ≡ R.D

2 DL-A的語法與語義

DL-A中的基本符號有：①用拉丁語α、β等表示原子動作名；②動作構造符“u”、“，”、“*”和“；”分別表示選擇、順序迭代和并發。

定義6：原子動作α=（pre，con-result，final），其中：

α表示原子動作名；

pre = {φ1，φ2，...φn}是前提條件集，表示動作執行的前提條件；

con-result = {φ1/ψ1，φ2/ψ2，...φn/ψn}是條件結果集，表示當滿足“/”前面的條件時，動作執行就會產生“/”之后的結果；

final= {φ1，φ2，...φn}是直接結果集，表示由于動作的執行所產生的直接結果。

例：一個顧客jack在網上書店訂購了一本關于Java的書。如果要取消這個訂單，那么取消訂單動作的前提條件是訂單是存在的，另外如果顧客Jack已經過款了，那么在取消訂單的同時還要所付款退還給顧客Jack。

該描述中涉及到的概念名稱為：Customer，Book，角色名稱為：hasOrder，hasPaid，取消訂單這個動作可描述為cancelOrder；

則該例子所描述的知識庫可表示為：

ABox = {Customer（jack），Book（java），hasOrder（jack，java），hasPaid（jack，java）}

cancelOrder（jack，java） = {pre，con-result，final}

其中：

pre = {Customer（jack），Book（java），hasOrder（jack，java）}

con-reAult = {hasPaid（jack，java）/hasRefund（jack，java），hasPaid（jack，java）}

final = {hasOrder（jack，，java）}

說明：①關系斷言hasOrder（jack，java）表示顧客Jack訂購了一本關于Java的書；②關系斷言hasPaid（jack，java）表示顧客Jack為名為Java這本書付過款了；③關系斷言hasRefund（jack，java）表示將買Java書的錢退還給Jack；④動作描述cancelOrder（jack，java）表示Jack要取消Java這本書的訂單。

定義7：三元組M=（Δ，W，I）是DL-A的模型，其中Δ是所有個體對象組成的非空集合，即論域；W是所有狀態的集合；I是對W中的每個狀態w賦予一個解釋函數I（w），對個體常元概念和關系進行解釋。

對于DL-A中的某個狀態w∈ W，該狀態的解釋函數I（w）=（ Δ，· I（w）），由論域Δ和解釋函數·I（w）構成，在該狀態下，概念、關系和動作的語義解釋如下：

（1）I（w） = Δ（2）⊥I（w） = ⊥（3） （C）I（w） = ΔCI（w）

（4） （R）I（w） = ΔRI（w）（5） （CD）I（w） = CI（w） ∩DI（w）（6） （CD）I（w） = CI（w） ∪DI（w）（7）（R.D）I（w） = {x|y（（x，y）∈RI（w） ∧y∈CI（w））}（8） （R.C）I（w） = {{x|y（（x，y）∈RI（w） →y∈CI（w））}上述定義中采用了恒定解釋域假設，模型中的所有狀態都采用同一個解釋域。而且個體名都作為剛性命名符來處理，即個體名的解釋不隨狀態的變化而變化。

在狀態w下，概念斷言是用來表示個體與概念之間的關系，其語義解釋如下：

（1）wC（a） 當且僅當a∈CI（w）；

（2） wC（a） 當且僅當aCI（w）。

在狀態w下，關系斷言是用來表示兩個個體之間所具有的某種關系或者是某個個體所具有的某種屬性，表示的是二元關系，其語義解釋如下：

（1） wR（a，b），當且僅當（a，b）∈RI（w）；

（2） wR（a，b），當且僅當（a，b）RI（w）。

對于原子動作α的語義解釋如下：

αI = （pre，con-result，final）I = {（w，w′）|存在個體a，b∈NI使得：

（1）對于任意的斷言φ∈pre，都有wφ；

（2）對于任意的簡單概念名C∈NC都有：

C+={aI（w） | （φ/C（a）∈con-result∧wφ）∪C（a）∈final}

C-={aI（w） | （φ/C（a）∈con-result∧wφ）∪C（a）∈final}

則CI（w′） = （CI（w）∪C+） C-

（3）對于任意的簡單關系名R∈NR，都有：

R+ = {（a，b）I（w） |（φ/R（a，b）∈con-result∧wφ）∪R（a，b）∈final}

R- = {（a，b）I（w） |（φ/R（a，b）∈con-result∧wφ）∪R（a，b）∈final}

則RI（w′） = （RI（w）∪R+）R-}；其中w，w′是W中的兩個狀態。

定義8：γ=α，β表示順序動作，α，β是原子動作。

說明：只有順序動作中的原子動作α和β依次全部完成，順序動作γ才能完成。動作α執行完之后的狀態是動作β執行時的狀態。

順序動作的語義：α，β={（w，w′）|w，w1，w′∈W，wαw1∧w1βw′}

定義9：動作γ=α∪β表示選擇動作 ，其中α和β都是原子動作。

說明：選擇動作中，只執行滿足條件的一個原子動作，即要么執行α要么執行β。

選擇動作的語義：α∪β = {（w，w′）|w，w∈W，wαw′∨wβw′}

定義10：動作γ=α*表示循環動作，其中α是原子動作。

說明：循環動作表示動作α執行零次或多次。

循環動作的語義：（α*）I={（w，w1，w2，…）|w，w1，w2，…∈W，ww∨wαw1∨（wαw1∧w1αw2）∨…}

定義11：動作γ=（α1；α2；...；αn）表示并發動作，其中α1，α2，...，αn都是原子動作。

說明：并發動作γ表示動作中的原子動作同時執行，當且僅當所有的原子動作全部同時執行時，該動作γ才能夠完成，只要其中一個原子動作無法完成，則并發動作就無法完成。

并發動作的語義：γ=（α1；α2；...；αn）={（w，w′）|w，w∈W，wα1；α2；...；αnw′}

3 基于DL-A的行動推理

根據知識庫構成，可將推理問題分為以下幾類：關于狀態的推理、關于動作的推理以及由動作執行所導致的狀態更新問題。

關于動作的推理主要分為兩部分：判斷原子動作定義式的一致性；動作的可執行性問題、投影問題以及規劃問題。

定義12：稱原子動作α=（pre，con-result，final）相對于TBox T和ABox A是一致，當且僅當存在某個模型M=（Δ，W，I），使得M

T，MA以及wαw′，其中w，w′是W中的兩個狀態。

動作的可執行性問題是指判斷動作α在某個狀態下是否可以執行。例如α=（pre，con-result，final）是一個原子動作，A是一個ABox。如果preA，那么該原子動作時可以執行。對于復雜動作的可執行性問題，可以將復雜動作分解成若干個原子動作，然后判斷原子動作是否可執行，據此推出該復雜動作是否可執行。

動作投影問題是指判斷某個狀態下執行動作α后能否使某個斷言成立。例如α=（pre，con-result，final）是一個原子動作，A是一個ABox，D是一個關系斷言或者概念斷言。假設動作α是可以執行的，且執行結果為集合M。如果D∈M，則執行原子動作α后可以使斷言D成立。

動作規劃問題是指可否找到一個動作序列，使得從初始狀態下出發可依次執行該序列中的動作，從而達到目標狀態（或者是給定一個動作序列、初始狀態和目標狀態，驗證該動作序列能否從初始狀態達到目標狀態）。

文獻[6]在動態描述邏輯的基礎上給出了上述推理問題的形式化定義，并且將轉換成動態描述邏輯中公式的可滿足性問題來解決。

由動作執行所引起的ABox更新問題，是本文需要解決的問題之一?；诿枋鲞壿婣LCO@的知識庫ABox對具體的狀態進行了描述；當動作執行導致狀態改變時，需要相應地對ABox進行更新處理，使得更新后的ABox能夠描述更新后的狀態。

ABox更新算法的過程如下：

定義13：Obj（M）表示集合M中個體名的集合，其中M是斷言集合。

例如：M={Woman（marry），hasChild（tom，bob），Male（bob）} Obj（M）={marry，tom，bob}算法1：根據Tableau算法將原知識庫S進行擴展設原知識庫為ABox A，TBox T，擴展的知識庫為A′。

（1） A′= A。

（2） 從A′中取出一個概念斷言D（a），如果該概念斷言是TBox T中所定義的概念，則用概念定義符號“≡”右邊的概念替換D，所得到的新的斷言為C（a），執行A= A∪{C（a）}，A′ = A′∪{C（a）} {D（a）}。

（3） 從A′中取出一個概念斷言D（a），如果該概念斷言是非標準否定范式，則將該概念斷言轉化為標準否定范式，記為C（a），則執行A′ = A′∪{C（a）} {D（a）}，A∪{C（a）}。

（4） 從A′中取出一個概念斷言D（a）。

① 如果D是形如CE的概念，則執行A = A∪{C（a），E（a）}，A′ = A′∪{C（a），E（a）} {D（a）}；

②如果D是形如R.C的概念，則匹配A′中所有滿足R（a.x）的關系斷言，則執行A′ = A′∪{C（x）}，A = A∪{C（x）}。

運行算法1后，可以在不影響原知識庫的表達能力的基礎上對原知識庫進行最大限度擴展。將經過最大限度擴展的知識庫稱為完全知識庫。

算法2：知識庫S的更新算法如下：

將更新集U中的個體集合表示為Obj（U），知識庫ABox A中個體集合表示為Obj（A）；（1）如果更新集U和知識庫A都是完全的，則執行以下步驟；反之，將更新集和知識庫A按照算法1進行擴展，然后再執行以下步驟。

（2） 從Obj（U）中取出一個元素a，如果aObj（A），并且在更新集U中沒有形如R（a，b）（R（a，b））或者R（b，a）（R（b，a））的關系斷言，其中b∈Obj（A），則將更新集U中的所有關于個體a的斷言C（a）加入到A中，即執行A=A∪{C（a）}。

（3） 從Obj（U）中取出一個元素a，如果a∈Obj（A），則執行如下步驟：①從更新集U中取出關于個體a的概念斷言D（a）：如果D（a）∈A，則執行A = A∪{D（a）}{D（a）}。如果D（a）是形如R.C（a）的斷言，如果在A中存在有形如R.E（a）的斷言，并且C =E，則執行A = A{R.E（a）}；將關于a的其他形式的概念斷言C（a）加入到A中，即A = A∪{ C（a）}；②從更新集U中取出關于a的關系斷言φ：如果φ∈A，則執行A=A{φ}。如果φ是形如R（a，b），并且在A中存在形如R.D（a）的斷言，則執行A = A∪{R.（D∪）}。如果φ是形如R（a，b）∈U，并且在A中存在形如R.D（a）的斷言，則執行A = A∪{R.（D∩）∪@bD}（a）。將關于a的其他形式的關系斷言加入到A中，即A = A∪{φ}；③Obj（U） = Obj（U）{a}。

（4） 依次取出Obj（U）中的剩余元素，并且按照步驟（3）執行。

算法3：動作執行引起的狀態更新算法如下：

有ABox A和原子動作α=（pre，con-result，final）令result =Φ（1）首先將A和原子動作α中的所有斷言按照算法1進行擴展，然后執行以下步驟：

（2）如果pre∈A，則表明原子動作α是可以執行的，繼續執行以下步驟；如果preA表明該原子動作是不可以執行的，算法終止；

（3）從con-result中取出一個元素φ/ψ，如果φ∈A，則result = result ∪{ψ}，con-result = con-result{φ/ψ}；

（4）重復執行步驟（2），直到con-result集合中沒有元素可??；

（5） final = final ∪ result；

（6） 將final集合作為更新集，將A作為原知識集，執行算法2；

（7） 最后得到的知識庫A就是執行動作α之后的新的狀態集合。

算法4：考察原子動作執行情況。在ABox執行任意一個動作α后，實際上發生的動作總可以由若干個原子動作組成的某個序列構成。因此，對應于任意一個動作α，可以通過多次應用算法3來構造出在ABox上執行動作α后所得到新的ABox。

4 結語

基于描述邏輯的動作理論系統DL-A具有如下特點：①使用描述邏輯ALCO@語言對世界的知識、狀態、動作的前提條件、條件結果以及直接結果等進行了描述，其表達能力要比命題邏輯的動作理論更強；②它提供了具有可判定性的推理服務。后續研究重點探討算法的可終止性、可靠性以及完備性。

參考文獻：

[1] REITER R.Knowledge in action：logical foundations for describing and implementing dynamical sysems [M].Cambridge，MA：MIT Press，2001.

[2] THIESCHER M.From situation calculus to fluent calculus：state update axioms as a solution to the inferential frame problem[J].Artificial intelligence，1999，111（1/2）：277299.

[3] FIKES R.STRIPS：a retospective[J].Artificial intelligence，1993，59（12）：227232.

[4] GIACOMO G，LENZERINI M.PDLbased framework for reasoning about actions[C].Proceeding of the 4th Congress of the Italian Association for Artifical Intelligence.LNAI 992.Berlin：Springer，1995：103114.

[5] BAADER F，LUTZ C，MILICIC M，et al.Integrating description logics and action formalisms：first results[C].Proceeding of the 12th National Conference on Artifical Intelligence.Menlo Park：AAAI Press，2005：572577.

[6] WOLTER F，ZAKHARYASCHEV M.Temporalizing description logics[M].Frontiers of Combining Systems II，Studies Press/Wiley，2000：379401.

[7] GU YILAN，SOUTCHANSKI M.Decidable reasoning in amodified situation calculus[C].Proceeding of the 20th International Joint Conferecne on Artifical Intelligence.Menlo Park：AAAI Press，2007：18911897.

[8] 常亮，史忠植，邱莉榕，等.動態描述邏輯的Tableau判定算法[J].計算機學報，2008，6（31），896909.

[9] 史忠植，常亮.基于動態描述邏輯的語義Web服務推理[J].計算機學報，2008，31（9）：15991611.

[10] SHI ZHONGZHI，DONG MINGKAI，JIANG YUNCHENG，et al.A logical foundation for the semantic Web[J].Sciience in China，Ser.F，2005.48（2）：161178.

[11] CHANG LIANG，LIN FEN，SHI ZHONGZHI.A dynamic description logic for representation and reasoning about action[C].Proceedings of the 2nd International Conference on Knowledge science，Engineering and Management.Berlin：Springer，2007：115127.

[12] 常亮，陳立民.基于動態描述邏輯DDL的動作理論[J].計算機科學，2011，7（38），203208.

（責任編輯：陳福時）