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

?

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

張大權(quán)董子威沈林

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

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

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

一、引言

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

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

二、任務(wù)分解流程分析

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

任務(wù)分解的具體流程如下：

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

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

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

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

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

(6)輸出復(fù)雜任務(wù)分解得到的相關(guān)元任務(wù)(基礎(chǔ)任務(wù))。

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

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

定義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)生新的標(biāo)識M′，記為M[t>M′

四種類型的模糊產(chǎn)生式規(guī)則可分別表示為下面的四種模糊Petri網(wǎng)的基本類型，如圖1所示。模糊Petri網(wǎng)用圓表示庫所，以矩形表示變遷，變遷與庫所間的帶箭頭的連線表示流關(guān)系。庫所中的實心圓點表示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：任務(wù)分解的模糊Petri網(wǎng)定義為5元組FPN=(P，T，F(xiàn)，D，M0)，其中:P為模糊庫所的有限集合；T為模糊變遷的有限集合；D為定義在T上的實函數(shù)；M0為初始標(biāo)識。

四、算法分析

假設(shè)：目標(biāo)任務(wù)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é)論

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

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

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

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

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