基于描述逻辑的动作理论研究

刘一松++谢聪银

摘要：情景演算对于动作理论的描述具有很强的表达能力，但是其推理算法具有不可判定性。在描述逻辑ALCO@的基础上，构建基于描述逻辑的动作理论系统DL-A。在该系统中，利用描述逻辑语言描述原子动作的表达式以及语义解释，并在此基础上利用各种构造符构造出顺序、选择、并发、迭代等复杂动作，同时赋予这些复杂动作的语法和语义。动作的实现会引起周围世界状态的改变，描述动作执行所引起的状态更新算法。基于描述逻辑ALCO@的动作理论不仅具有很强的表达能力，而且其算法具有可判定性，能够提供多种推理服务，可以应用于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更新问题，是本文需要解决的问题之一。基于描述逻辑ALCO@的知识库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∪{b}）}。如果φ是形如R（a，b）∈U，并且在A中存在形如R.D（a）的断言，则执行A = A∪{R.（D∩{b}）∪@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.

（责任编辑：陈福时）