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

劉一松++謝聰銀

摘要：情景演算對于動作理論的描述具有很強的表達(dá)能力，但是其推理算法具有不可判定性。在描述邏輯ALCO@的基礎(chǔ)上，構(gòu)建基于描述邏輯的動作理論系統(tǒng)DL-A。在該系統(tǒng)中，利用描述邏輯語言描述原子動作的表達(dá)式以及語義解釋，并在此基礎(chǔ)上利用各種構(gòu)造符構(gòu)造出順序、選擇、并發(fā)、迭代等復(fù)雜動作，同時賦予這些復(fù)雜動作的語法和語義。動作的實現(xiàn)會引起周圍世界狀態(tài)的改變，描述動作執(zhí)行所引起的狀態(tài)更新算法。基于描述邏輯ALCO@的動作理論不僅具有很強的表達(dá)能力，而且其算法具有可判定性，能夠提供多種推理服務(wù)，可以應(yīng)用于Web語義下的動作描述和推理。

關(guān)鍵詞：描述邏輯；動作理論；狀態(tài)更新；斷言；動作推理；知識表示

DOIDOI：10.11907/rjdk.151392

中圖分類號：TP301

文獻(xiàn)標(biāo)識碼：A 文章編號文章編號：16727800（2015）008002904

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

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

0 概述

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

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

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

1 ALCO@語法和語義

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

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

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

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

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

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

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

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

2 DL-A的語法與語義

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

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

α表示原子動作名；

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

con-result = {φ1/ψ1，φ2/ψ2，...φn/ψn}是條件結(jié)果集，表示當(dāng)滿足“/”前面的條件時，動作執(zhí)行就會產(chǎn)生“/”之后的結(jié)果；

final= {φ1，φ2，...φn}是直接結(jié)果集，表示由于動作的執(zhí)行所產(chǎn)生的直接結(jié)果。

例：一個顧客jack在網(wǎng)上書店訂購了一本關(guān)于Java的書。如果要取消這個訂單，那么取消訂單動作的前提條件是訂單是存在的，另外如果顧客Jack已經(jīng)過款了，那么在取消訂單的同時還要所付款退還給顧客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）}

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

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

對于DL-A中的某個狀態(tài)w∈ W，該狀態(tài)的解釋函數(shù)I（w）=（ Δ，· I（w）），由論域Δ和解釋函數(shù)·I（w）構(gòu)成，在該狀態(tài)下，概念、關(guān)系和動作的語義解釋如下：

（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））}上述定義中采用了恒定解釋域假設(shè)，模型中的所有狀態(tài)都采用同一個解釋域。而且個體名都作為剛性命名符來處理，即個體名的解釋不隨狀態(tài)的變化而變化。

在狀態(tài)w下，概念斷言是用來表示個體與概念之間的關(guān)系，其語義解釋如下：

（1）wC（a） 當(dāng)且僅當(dāng)a∈CI（w）；

（2） wC（a） 當(dāng)且僅當(dāng)aCI（w）。

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

（1） wR（a，b），當(dāng)且僅當(dāng)（a，b）∈RI（w）；

（2） wR（a，b），當(dāng)且僅當(dāng)（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）對于任意的簡單關(guān)系名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中的兩個狀態(tài)。

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

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

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

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

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

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

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

說明：循環(huán)動作表示動作α執(zhí)行零次或多次。

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

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

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

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

3 基于DL-A的行動推理

根據(jù)知識庫構(gòu)成，可將推理問題分為以下幾類：關(guān)于狀態(tài)的推理、關(guān)于動作的推理以及由動作執(zhí)行所導(dǎo)致的狀態(tài)更新問題。

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

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

T，MA以及wαw′，其中w，w′是W中的兩個狀態(tài)。

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

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

動作規(guī)劃問題是指可否找到一個動作序列，使得從初始狀態(tài)下出發(fā)可依次執(zhí)行該序列中的動作，從而達(dá)到目標(biāo)狀態(tài)（或者是給定一個動作序列、初始狀態(tài)和目標(biāo)狀態(tài)，驗證該動作序列能否從初始狀態(tài)達(dá)到目標(biāo)狀態(tài)）。

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

由動作執(zhí)行所引起的ABox更新問題，是本文需要解決的問題之一?；诿枋鲞壿婣LCO@的知識庫ABox對具體的狀態(tài)進(jìn)行了描述；當(dāng)動作執(zhí)行導(dǎo)致狀態(tài)改變時，需要相應(yīng)地對ABox進(jìn)行更新處理，使得更新后的ABox能夠描述更新后的狀態(tài)。

ABox更新算法的過程如下：

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

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

（1） A′= A。

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

（3） 從A′中取出一個概念斷言D（a），如果該概念斷言是非標(biāo)準(zhǔn)否定范式，則將該概念斷言轉(zhuǎn)化為標(biāo)準(zhǔn)否定范式，記為C（a），則執(zhí)行A′ = A′∪{C（a）} {D（a）}，A∪{C（a）}。

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

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

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

運行算法1后，可以在不影響原知識庫的表達(dá)能力的基礎(chǔ)上對原知識庫進(jìn)行最大限度擴(kuò)展。將經(jīng)過最大限度擴(kuò)展的知識庫稱為完全知識庫。

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

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

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

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

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

算法3：動作執(zhí)行引起的狀態(tài)更新算法如下：

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

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

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

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

（5） final = final ∪ result；

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

（7） 最后得到的知識庫A就是執(zhí)行動作α之后的新的狀態(tài)集合。

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

4 結(jié)語

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

參考文獻(xiàn)：

[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] 常亮，史忠植，邱莉榕，等.動態(tài)描述邏輯的Tableau判定算法[J].計算機學(xué)報，2008，6（31），896909.

[9] 史忠植，常亮.基于動態(tài)描述邏輯的語義Web服務(wù)推理[J].計算機學(xué)報，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] 常亮，陳立民.基于動態(tài)描述邏輯DDL的動作理論[J].計算機科學(xué)，2011，7（38），203208.

（責(zé)任編輯：陳福時）