基于模糊Petri網的任務分解方法

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

?

基于模糊Petri網的任務分解方法

張大權董子威沈林

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

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

任務分解；協同；數據庫；模糊

一、引言

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

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

二、任務分解流程分析

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

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

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

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

(3)根據復雜任務的關鍵詞在規則庫中搜索相關模糊產生式規則。

(4)根據模糊產生式規則映射為相關的Petri網。

(5)根據Petri網的動態性能以及相關算法進行分解。

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

三、模糊Petri網分解原理

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

定義2.1：模糊Petri網是一個五元組

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

(1)(P；T；F)是一個網，滿足條件：(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的運行規則為：(a)對t∈T，如果?s∈·t都有M(p)≥D(t)，則變遷t可以發生，記為M[t>，(b)變遷t的發生產生新的標識M′，記為M[t>M′

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

(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)

通過上述方法，將模糊產生式規則映射為一個模糊Petri網。

定義2.2：任務分解的模糊Petri網定義為5元組FPN=(P，T，F，D，M0)，其中:P為模糊庫所的有限集合；T為模糊變遷的有限集合；D為定義在T上的實函數；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值小于變遷的閾值所以不能激發，第2、4條路徑刪除

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

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

(4)最終得到petri網

五、結論

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

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

[2]劉武.基于對象Petri網的電網調度操作票任務分解方法[J].中國新技術新產品,2010,4-5.

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

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