一種策略沖突的消解方法

李　鑫

(重慶理工大學(xué) 會計學(xué)學(xué)院，重慶 400050)

?

一種策略沖突的消解方法

李鑫

(重慶理工大學(xué) 會計學(xué)學(xué)院，重慶 400050)

摘要：利用非單調(diào)邏輯編程技術(shù)，Chomicki等人提出了一種策略沖突消解方法.雖然該方法具有高效、可靠和良好的封裝性等優(yōu)點，但是它的應(yīng)用域卻受到限制.在Chomicki方法的基礎(chǔ)上，首先定義了組合沖突，它比一般策略沖突涵義更廣.其次，為消解該類沖突引入了一個優(yōu)化解—最大行動接受集，并給出與之互補(bǔ)的最小行動取消集的重要特性.最后，利用基于穩(wěn)定模型語義的權(quán)約束規(guī)則編程技術(shù)，建立消解組合沖突的邏輯程序.由于該程序始終擁有穩(wěn)定模型，所以總是能夠根據(jù)它的模型獲得優(yōu)化解.

關(guān)鍵詞：沖突；權(quán)約束規(guī)則；最大行動接受集；最小行動取消集；穩(wěn)定模型

隨著ECA(event-condition-action)策略在計算機(jī)管理與控制中的廣泛應(yīng)用，如分布式系統(tǒng)管理、數(shù)據(jù)庫系統(tǒng)管理、安全與訪問控制、Web服務(wù)及其組合等，有關(guān)策略沖突的研究也愈來愈受到重視[1-3].

利用基于穩(wěn)定模型語義的非單調(diào)邏輯編程技術(shù)[4-5](也被稱為回答集編程技術(shù)[6])，Chomicki等人[3]提出一種消解PDL(policy description language)[7]策略沖突的方法.該方法具有以下優(yōu)點：

1)易于實現(xiàn)PDL策略及其沖突消解的邏輯編程表示，且邏輯編程技術(shù)能夠確保沖突消解的可靠性和有效性；

2)建立的沖突消解邏輯程序具有良好的層次性和獨立性；

3)根據(jù)沖突消解邏輯程序的穩(wěn)定模型，不但能夠?qū)崿F(xiàn)沖突消解而且還可以獲得極大行動接受集.Chomicki等人選擇PDL策略的原因是它比一般ECA策略更復(fù)雜且描述能力更強(qiáng)[7-8].

Chomicki方法并不能消解本文定義的特殊組合沖突.一方面，該方法的成功依賴于沖突消解邏輯程序語義模型的存在性；另一方面，當(dāng)特殊組合沖突發(fā)生時，按照該方法構(gòu)造的沖突消解邏輯程序不再擁有穩(wěn)定模型.從而導(dǎo)致失敗.其失敗的根本原因是它采用了析取邏輯編程技術(shù)[5,9]，這點將在3.2節(jié)詳細(xì)說明.

下文通過例1的沖突說明特殊組合沖突的普遍性.同時該例也用于闡述本文中的沖突消解方法.

例1在一個簡單的會議室自動預(yù)定系統(tǒng)中，一方面，式(1)的PDL規(guī)則構(gòu)成其策略.該規(guī)則規(guī)定當(dāng)一個用戶User的預(yù)定申請事件requestRes(User)發(fā)生時，為該用戶執(zhí)行預(yù)留會議室的行動procRes(User).另一方面，為消解沖突定義式(2)的行動約束(action constraint,ac)，以防止由于同時執(zhí)行兩個不同用戶的procRes行動而導(dǎo)致的沖突.這里的沖突是由于同時發(fā)生了多個不同用戶的預(yù)定申請事件，而且他們申請的是同一會議室而導(dǎo)致的.另外，假設(shè)會議室的預(yù)留時間重疊.

(1)

(2)

此例也是文獻(xiàn)[3]中的例1.簡潔起見，下文一律假設(shè)預(yù)定申請的是同一會議室，且申請事件同時發(fā)生.該例中，特殊組合沖突指由三個或三個以上不同用戶申請導(dǎo)致的沖突.而由兩個不同用戶申請導(dǎo)致的沖突，也是Chomicki方法能夠消解的，在本文歸為一般組合沖突.

為克服Chomicki方法的局限性，本文提出一種利用基于穩(wěn)定模型語義的權(quán)約束規(guī)則(weight constraint rule, WCR)編程技術(shù)[10-11]消解策略沖突的方法.在Chomicki方法基礎(chǔ)上，首先定義了涵義更為寬泛的組合沖突，它不僅包含了一般組合沖突，更為重要的是，特殊組合沖突也是它的一個子類.然后，為沖突消解提出一個優(yōu)化解概念，即最大行動接受集(largest action-acceptance set, LAAS)，并給出與它互補(bǔ)的最小行動取消集(smallest action-cancellation set,SACS)的重要性質(zhì).最后，在一個極大化處理過程的基礎(chǔ)上，利用WCR編程技術(shù)建立組合沖突消解邏輯程序.由于該程序始終擁有穩(wěn)定模型，所以總是能夠獲得LAASes.

1　背景知識

1.1　WCR編程簡介

任意非單調(diào)邏輯程序是一個由形如式(3)的規(guī)則組成的有限集.其中，li(i∈{0,1，…,n})是一階正(或負(fù))文字，not是 “失敗為否定” (negation-as-failure)操作符.通常稱集合{l0,,l1,…,lk}和{lk+1,,lk+2,…,ln}分別為規(guī)則的頭和體.由于不再象Prolog程序具有唯一的最小海布南模型[12]，所以非單調(diào)邏輯程序通常按照模型語義解釋，即只有在一定的語義模型下，邏輯程序才具有明確的語義解釋.由M.Gelfond和V.Lifschitz開創(chuàng)的穩(wěn)定模型語義是至今為止被廣為接受的一種非單調(diào)邏輯程序模型語義.經(jīng)過二十年的發(fā)展，如今已經(jīng)開發(fā)出多種實用的穩(wěn)定模型語義編程系統(tǒng)，如DLV[13]、AnsProlog[14]等.

(3)

(4)

(5)

(6)

(7)

(8)

WCR編程技術(shù)是對基于穩(wěn)定模型語義的非單調(diào)邏輯編程技術(shù)的一種擴(kuò)展，SMODELS是它的實用編程系統(tǒng).一個WCR的基本形式為“WC0←WC1,…,WCm”，其中，式(4)表示任意權(quán)約束WCi(i∈{0,1,…,m}).WCi的語義定義是，S|=WCi當(dāng)且僅當(dāng)z≤w(S,WCi)≤u，其中，S為任意原子謂詞實例集，權(quán)值函數(shù)w(WCi,S)=∑ai∈Slai+∑bj?Slbj，而且，上界u、下界z以及權(quán)值目前只能為自然數(shù).關(guān)于基于穩(wěn)定模型語義的WCR程序，需要注意以下兩點：①它的模型不但符合穩(wěn)定模型語義解釋，而且還需要滿足權(quán)約束上的權(quán)值約束；②WCR具有靈活多樣的形式，除基本形式外，例如，式(5)的規(guī)則也是可行的.

當(dāng)所有權(quán)值均為1時，WCR被稱為基數(shù)約束規(guī)則(cardinality constraint rule,CCR)，基數(shù)約束可簡化為式(6)的形式.除權(quán)值始終為1外，CCR的語義定義與WCR一樣.WCR編程技術(shù)還提供分別形如式(7)和(8)的minimize和maximize優(yōu)化語句，它們的權(quán)值計算與WCR一樣.以上兩個語句分別完成對程序最小和最大權(quán)值模型的搜索.

1.2　Chomicki方法

1.2.1策略Prolog程序.在文獻(xiàn)[3]中，任意PDL策略P的語義是變換πP:Epochs(P)→ActionSet(P).其中，Epochs(P)是所有段事件集的集合，且一個段事件集是由發(fā)生在一個系統(tǒng)時間段中的所有基本事件實例(primitive event instance)組成的有限集；ActionSet(P)是一個是由所有完成填充的行動構(gòu)成的集合，且它的一個元素被稱為行動集.

(9)

(10)

設(shè)策略P對應(yīng)于一段事件集E的實例為P(E).通過將P(E)中每個PDL規(guī)則實例“e1&…&elcauses a if C”，用式(9)的Horn(或definite)范式捕獲，建立P對應(yīng)于E的Prolog程序∏P.在式(9)中，exec和occ是原子謂詞，條件C=t1θ1t1′，…，tmθ1tm′且任意比較謂詞θi∈{=,≠,≤,≥}(i∈{1,2,…,m}).

至此得到，對于一段事件集E而言，任意行動a∈πP(E)當(dāng)且僅當(dāng)∏P∪OCC(E)|=exec(a)，其中，式(10)定義OCC(E).從而完成策略P的等價邏輯編程表示.

1.2.2沖突消解.Chomicki等人定義了形如“Nevera1，a2，…，amifC”的ac以捕獲一類沖突.以上ac規(guī)定在條件C被滿足的情況下，禁止同時執(zhí)行m個行動a1，…，am，否則將導(dǎo)致沖突.AC是管理員定義的ac集合，且對應(yīng)于一個段事件集E的AC實例為AC(E).

(11)

(12)

從以上介紹也可看出，沖突消解邏輯程序具有良好的層次性且各組成部分之間相互獨立.

2　組合沖突

2.1　定義

稱被一個ac(或aci)約束的行動個數(shù)為它的長度.顯然，任意ac(或aci)的長度均大于1.

2)X中所有行動構(gòu)成的集合等于A；

3)X中的任意aci的條件C被滿足.

以上定義中，條件3排除了對aci的條件判斷，這便于沖突組合的研究.而且，由于該類條件易于判斷，所以條件3的要求是合理的.在下文中，用式(13)定義的CAC(E)表示對應(yīng)于一段事件集E的cac集合.

(13)

2.2　Chomicki方法缺陷

在下文中，用EXEC(A)={exec(a)|a∈A}、BLOCK(A)={block(a)|a∈A}分別表示行動集A上的exec和block實例集.同時令U=OCC(E)∪EXEC(πP(E))∪BLOCK(πP(E)).

3　最大行動接受集

對于AC(E)中的單個aci，只需要取消被它約束的一個行動，不但能夠滿足該aci(即實現(xiàn)沖突消解)，而且還確保了行動接受集的極大性.但為滿足AC(E)的一個子集或AC(E)本身，同時又要確保行動接受集的極大性，卻是復(fù)雜的.

定義2對應(yīng)于一段事件集E的行動全集始終是πP(E).設(shè)一個aci集合X?AC(E).如果一個行動集X?πP(E)同時滿足：

1)πP(E)X滿足X中的任意aci；

2)任意X′?X，πP(E)X′至少不能滿足X中的一個aci.

則稱X是X的一個極小行動取消集(minimal action-cancellation set, MACS)，記為ΔX.稱πP(E)ΔX是與ΔX對應(yīng)的 MAAS.顯然，一個ΔX同與之對應(yīng)的MAAS構(gòu)成互補(bǔ)關(guān)系.一個MAAS等價于文獻(xiàn)[3]中定義的繁瑣的“P的極大AC監(jiān)控行動取消(maximal action-cancellation AC-monitor of P)”.

假設(shè)ΔAC(E)∩A<|A|-k+1成立.由以上證明，易得πP(E)ΔAC(E)不能滿足α，所以ΔAC(E)不是AC(E)的一個MACS.

命題1不但適合特殊組合沖突，同樣適合一般組合沖突.

在實際應(yīng)用中，往往要求被接受的行動愈多愈好.但是，由于一個MAAS并不一定是對應(yīng)的AC(E)所有MAASes中基數(shù)最大的集合，所以依靠AC(E)的一個MAAS并不能確保被接受的行動最多.

由命題1可知，此時任意ΔAC(E)至少包含A1(或A2)的2個元素.在AC(E)的所有MAASes中，一方面，由于ΔAC(E)={a1,a2}在AC(E)所有的MACSes中基數(shù)最小，所以對應(yīng)的MAAS(即{a3,a4,a5,a6})基數(shù)最大，從而確保了被接受的行動最多；另一方面，由于ΔAC(E)={a3,a4,a5,a6}的基數(shù)最大，所以對應(yīng)的MAAS(即{a1,a2})擁有最小基數(shù)，從而被接受的行動最少.

定義3設(shè)一個aci集合X?AC(E).在X的所有MACSes中，基數(shù)最小的集合被稱為X的一個SACS，記為ΞX.類似MAAS的定義，稱πP(E)ΞX是與一個ΞX對應(yīng)的LAAS.

顯然，aci集X的一個SACS必然是它的一個MACS，但反之并不成立.這同樣適合X的LAAS和MAAS.所以，SACS/LAAS是對MACS/MAAS的進(jìn)一步優(yōu)化.另外，X的SACS或LAAS并不是唯一的.

證明由命題1直接可得.

4　組合沖突消解

4.1　極大化

在利用WCR編程技術(shù)消解組合沖突之前，有必要剔出CAC(E)中的冗余元素.首先定義一個CAC(E)上的偏序關(guān)系≤.然后在此關(guān)系基礎(chǔ)上，利用一個簡單的極大化過程剔出CAC(E)中的冗余元素.

可獲得如下關(guān)于偏序集〈CAC(E),≤〉的性質(zhì).

命題3設(shè)兩個cacsαi,αj∈CAC(E)、Ξαj是αj的一個SACS.如果αi≤αj，則αi至少存在的一個SACS(Ξαi)，滿足Ξαi?Ξαj.而且，如果αi=αj，則αi的一個SACS必然是αj的一個SACS，反之也成立.

根據(jù)命題2，可得到如下三個結(jié)論：①如果αi=αj，易得任意行動集是αi的一個SACS當(dāng)且僅當(dāng)它是αj的一個SACS；②如果Ai?Aj且kj=ki，假設(shè)Ξαj∩Ai=|Ai|-ki，即Ξαj只包含|Ai|-ki個Ai的元素.然而這是不可能的，因為此時Ξαj∩(AjAi)=|AjAi|+1成立，即Ξαj需要包含|AjAi|+1個AjAi的元素；③如果Ai=Aj且kj

基于偏序集〈CAC(E),≤〉，用于剔出CAC(E)中冗余元素的極大化過程為：

1)初始CACm(E)為?.

2)如果CAC(E)≠?，從〈CAC(E),≤〉中選擇一個極大元素α，將之添加到CACm(E).然后刪除〈CAC(E),≤〉中任何滿足α′≤α的元素α′.

3)循環(huán)執(zhí)行步驟2，直到CAC(E)=?.

下文用CACm(E)取代CAC(E).

4.2　沖突消解邏輯程序

易得A1是AC(E)的一個SACS.

(14)

(15)

(16)

(17)

由于πP(E)=?使得沖突消解沒有必要，所以，下文中均假設(shè)πP(E)≠?.

由以上定理證明也可知，式(14)可簡化為論據(jù)(fact) “n-k+1≤{block(a1)，…，block(an)}≤n←”.需要說明的是，即使一個WCR程序擁有多個優(yōu)化模型，如多個相同最小基數(shù)模型，但是當(dāng)前的SMODELS只為用戶提供其中的一個優(yōu)化模型.

再根據(jù)定理2和定義3，得AM(E)是AC(E)的一個LAAS.

5　結(jié)語

析取邏輯編程技術(shù)使得Chomicki方法在消解組合沖突時并不可靠.而本文利用WCR編程技術(shù)不但完成沖突消解，特別是能夠完成一種特殊沖突的消解，即組合沖突的消解，同時能夠獲得沖突的優(yōu)化解.本文方法成功的根本原因是，WCR編程技術(shù)不僅提供了優(yōu)化機(jī)制，更重要的是，其程序的穩(wěn)定模型能夠包含一個規(guī)則頭中的多個原子謂詞實例.

參考文獻(xiàn):

[1]Lupu E,Sloman M.Conflicts in Policy-Based Distributed Systems Management[J]. IEEE Transaction on Software Engineering，Nov/Dec，1999，25(6)：852-869.

[2]Turner K, Blair L.Policies and Conflicts in Call Control[J]. The International Journal of Computer and Telecommunications Networking，Elsevier，2006，51(2)：496-514.

[3]Chomicki J,Lobo J, Naqvi S. Conflict Resolution Using Logic Programming[J].IEEE Transactions on Knowledge and Data Engineering，Jan/Feb，2003，15(1)：244-249.

[4]Gelfond M, Lifschitz V. The Stable Model Semantics for Logic Programming[M].The MIT Press: R. Kowalski, K. Bowen (eds.), In Proc the 5th International Conference on logic programming,1988：1070-1080.

[5]Gelfond M,Lifschitz V.Classical Negation in Logic Programs and Disjunctive Databases[J].New Generation Computing，1991，9(3/4)：365-386.

[6]Gelfond M, Leone N. Logic Programming and Knowledge Representation—The A-Prolog Perspective[J]. Artificial Intelligence，Elsevier，2002，138：3-38.

[7]Lobo J, Bhatia R, Naqvi S. A Policy Description Language[C]// In Proc the 16th National Conference on Artificial Intelligence (AAAI-99), July,1999：291-298.

[8]Son T C, Lobo J. Reasoning about Policies Using Logic Programs[C]//In Proc the AAAI Spring Symposium on Answer Set Programming: Towards Efficient and Scalable Knowledge Representation and Reasoning, March,2001：210-216.

[9]Przymusinski T. Stable Semantics for Disjunctive Programs[J]. New Generation Computing，1991，9(3/4)：401-424.

[10]Niemel? I, Simons P， Soininen T. Stable Model Semantics of Weight Constraint Rules[C]// In Proc. the 5th International Conference on Logic Programming and Nonmonotonic Reasoning, Texas，USA，Dec，1999：317-331.

[11]Simons P, Niemel? I, Soininen T. Extending and Implementing the Stable Model Semantics[J]. Artificial Intelligence，Elsevier，2002，138：181-234.

[12]Emden M, Kowalski R. The Semantics of Predicate Logic as a Programming Language[J]. Journal of ACM，1976，23(4)：733-742.

[13]Leone N, Pfeifer G, Faber W, et al. The DLV System for Knowledge Representation and Reasoning[J]. ACM Transactions on Computational Logic，2006，7(3)：499-562.

[14]Baral C. Knowledge Representation, Reasoning, and Declaring Problem Solving with Answer sets[M].Cambridge University Press，2003.

[15]Leone N, Rullo P, Scarcello F. Disjunctive Stable Models: Unfounded Sets, Fixpoint Semantics, and Computation[J]. Information and Computation，1997，135(2)：69-112.

[16]Lifschitz V, Turner H. Splitting a Logic Program[C] / / In Proc the 11th International Conference on Logic Programming, 1994：23-37.

[17]盧開澄,盧華明.組合數(shù)學(xué)[M].3版.北京：清華大學(xué)出版社，2002.

責(zé)任編輯：時凌

A Method of Policy Conflict Resolution

LI Xin

(School of Accounting,Chongqing University of Technology,Chongqing 400050,China)

Abstract：By using the nonmonotonic logic programming technology, Chomicki et al. proposed an approach to resolve policy conflict. Although the approach is efficient, reliable, and has good encapsulation, its application domain is limited. On the base of Chomicki’s approach, we firstly define combination conflict that is more general than common policy conflict. Then, we introduce an optimal solution for combination conflict resolution, i.e., the largest action-acceptance set, and show the important property of the smallest action-cancellation set as the complement of the solution. Lastly, the logic program for combination conflict resolution is constructed by using weight constraint rule programming technology with the stable model semantics. Because the logic program always has at least one stable mode, it is reliable to obtain an optimal solution according to a stable model of this program.

Key words：conflict；weight constraint rule；largest action-acceptance set；smallest action-cancellation set；stable model

作者簡介：郭黎(1978- )，女，博士，副教授，主要從事視頻圖像處理與識別信息顯示的研究. 何恬(1988- )，女，碩士生，主要從事國土資源調(diào)查、評價與規(guī)劃開發(fā)的研究;*:宋鄂平(1971- )，男，高級實驗師，博士，主要從事林業(yè)、旅游、地質(zhì)學(xué)的研究.

DOI:10.13501/j.cnki.42-1569/n.2015.06.028 10.13501/j.cnki.42-1569/n.2015.06.020

文章編號：1008-8423(2015)02-0230-05 1008-8423(2015)02-0193-04

通信作者

基金項目：教育部人文社會科學(xué)青年基金項目(12YJC630306). 國家自然科學(xué)基金項目(61263030,61463014)；湖北省自然科學(xué)基金資助項目(2014CFB612)；湖北民族學(xué)院博士啟動基金(MY2014B018).

收稿日期：2015-03-31. 2014-12-01.

中圖分類號：TP181；TP182

文獻(xiàn)標(biāo)志碼：A