基于模糊Petri網(wǎng)的任務分解方法

(沈陽理工大學自動化與電氣工程學院 遼寧 沈陽 110159)

?

基于模糊Petri網(wǎng)的任務分解方法

張大權董子威沈林

(沈陽理工大學自動化與電氣工程學院遼寧沈陽110159)

隨著人工智能的發(fā)展，自主系統(tǒng)對任務分解精度的要求越來越高。為了提高任務分解的準確性，解決協(xié)同作業(yè)過程中時間不確定，工作銜接時機不容易把握等難題，本文提出一種基于模糊petri網(wǎng)的任務分解方法，給出模糊petri網(wǎng)的定義以及將模糊petri網(wǎng)用于任務分解的可行性。該方法是在建立數(shù)據(jù)庫的基礎上結(jié)合模糊petri網(wǎng)模型的推導過程實現(xiàn)的，并在理論的基礎上實現(xiàn)分解可視化。

任務分解；協(xié)同；數(shù)據(jù)庫；模糊

一、引言

近年來隨著人工智能的發(fā)展，任務分解受到越來越多的關注。對于一個不能被任何基礎機構(gòu)單獨完成的復雜任務，為了實現(xiàn)任務目標，必須進行任務分解。任務的分解是實現(xiàn)任務的關鍵，運用形式化的方法對任務分解進行描述和驗證是十分必要的。

Petri網(wǎng)是20世紀60年代由卡爾·A·佩特里發(fā)明的，適合于描述異步的、并發(fā)的計算機系統(tǒng)模型。Petri網(wǎng)既有嚴格的數(shù)學表述方式，也有直觀的圖形表達方式，既有豐富的系統(tǒng)描述手段和系統(tǒng)行為分析技術，又為計算機科學提供堅實的概念基礎。所以Petri網(wǎng)的并發(fā)模型可以滿足任務分解需求。

二、任務分解流程分析

任務分解的主要功能是將提交的任務分解成多個具有盡可能高并行度的子任務，并選取合理的分配調(diào)度策略，決定由哪些機構(gòu)執(zhí)行它們。任務的分解需要考慮任務是如何表示的、分解的方式、完成任務的組織、資源以及子任務之間的聯(lián)系。

任務分解的具體流程如下：

(1)初始：建立一個包含模糊規(guī)則產(chǎn)生式(定義1.1)的規(guī)則庫。

(2)由模糊任務識別得到包含一些關鍵詞的復雜任務(高級任務)。

(3)根據(jù)復雜任務的關鍵詞在規(guī)則庫中搜索相關模糊產(chǎn)生式規(guī)則。

(4)根據(jù)模糊產(chǎn)生式規(guī)則映射為相關的Petri網(wǎng)。

(5)根據(jù)Petri網(wǎng)的動態(tài)性能以及相關算法進行分解。

(6)輸出復雜任務分解得到的相關元任務(基礎任務)。

三、模糊Petri網(wǎng)分解原理

根據(jù)任務分解的規(guī)則產(chǎn)生式的推理過程可以采用模糊Petri網(wǎng)建模的方法進行分析。Petri網(wǎng)是一種形式化系統(tǒng)模型，它有很強的模擬能力和嚴格的數(shù)學定義，同時又具有圖形化的表示，由于它有著異步、并發(fā)的特性，是描述動態(tài)并發(fā)系統(tǒng)的有力工具，也因此在各個領域有著廣泛應用。模糊Petri網(wǎng)是一般網(wǎng)的模糊化，它更能有效地處理含有模糊特性的問題。任務分解是一個復雜困難的過程，有很強的模糊性和不確定性。我們可以通過Petri網(wǎng)相關的分析來判斷任務的分解是否正確，通過Petri網(wǎng)的動態(tài)性能找到完成總?cè)蝿斩扇〉挠媱潱瑸橐院蟮娜蝿談討B(tài)分配打下基礎。

定義2.1：模糊Petri網(wǎng)是一個五元組

∑F=(P,T,F,D,M0)

(1)(P；T；F)是一個網(wǎng)，滿足條件：(a)?x,y∈F:(x,y)∈F+→(y,x)?F+；(b)?t∈T:|·t|≥1∩|t·|≥1；(c)?p∈P:·p=φ∩?p∈P:p·=φ

(2)D:T→(0,1]

(3)M0:P→(0,1]，滿足條件?p∈P:·p≠φ→M0(p)=0

(4)∑F的運行規(guī)則為：(a)對t∈T，如果?s∈·t都有M(p)≥D(t)，則變遷t可以發(fā)生，記為M[t>，(b)變遷t的發(fā)生產(chǎn)生新的標識M′，記為M[t>M′

四種類型的模糊產(chǎn)生式規(guī)則可分別表示為下面的四種模糊Petri網(wǎng)的基本類型，如圖1所示。模糊Petri網(wǎng)用圓表示庫所，以矩形表示變遷，變遷與庫所間的帶箭頭的連線表示流關系。庫所中的實心圓點表示token(可用數(shù)字直接表示)。

(a)If a，Then b.(CF=μ1) (b)If a1 and a2and…an，Then b.(CF=μ2)

(c)If a1 or a2or…an，Then b.(CF=μ3)(d)If a，Then b1 and b2 and…Bn.(CF=μ4)

通過上述方法，將模糊產(chǎn)生式規(guī)則映射為一個模糊Petri網(wǎng)。

定義2.2：任務分解的模糊Petri網(wǎng)定義為5元組FPN=(P，T，F(xiàn)，D，M0)，其中:P為模糊庫所的有限集合；T為模糊變遷的有限集合；D為定義在T上的實函數(shù)；M0為初始標識。

四、算法分析

假設：目標任務P0，變遷的閾值都為0.5

P1,P2,P3,P4,P5的token值分別為0.6、0、0.8、0.3、0.4

(1)確定初始庫所為P1、P2、P3、P4、P5

(2)(P0→P5)and(P2→P6)→P0；

(P1→P5)and(P2→P6)→P0；

(P0→P5)and(P3→P6)→P0；

(P1→P5)and(P3→P6)→P0；

P4→P7→P0五條路徑

(3)由于P1的token值小于變遷的閾值所以不能激發(fā)，第2、4條路徑刪除

由于P3的token值小于變遷的閾值所以不能激發(fā)，第3條路徑刪除

由于P4的token值小于變遷的閾值多疑不能激發(fā)，第5條路徑刪除

(4)最終得到petri網(wǎng)

五、結(jié)論

文本針對任務分解的流程提出一種基于模糊petri網(wǎng)的任務分解方法，模糊petri網(wǎng)通過計算每條路徑分解的估計值給出更合理的路徑，從而完成最優(yōu)分解。針對分解方法給出可視化分析，并軟件實現(xiàn)分解過程。在實際工程應用中分解速率也會是一個重要參數(shù)，這將是面臨的發(fā)展方向。

[1]方歡,崔煥慶,王麗麗.任務分解的Petri網(wǎng)方法及有效性研究[J].安徽理工大學學報,28(1)，2008,85-89.

[2]劉武.基于對象Petri網(wǎng)的電網(wǎng)調(diào)度操作票任務分解方法[J].中國新技術新產(chǎn)品,2010,4-5.

[3]湯新民.基于Petri網(wǎng)的航空發(fā)動機車間維修過程建模及其應用研究[D].哈爾濱工業(yè)大學,2007.

張大權(1990-)，男，漢，河北廊坊人，碩士研究生，沈陽理工大學自動化與電氣工程學院，研究方向：光伏并網(wǎng)發(fā)電控制。