沈陽理工大學(xué)自動(dòng)化與電氣工程學(xué)院 董沖沖

Petri網(wǎng)的任務(wù)分解原理概述

沈陽理工大學(xué)自動(dòng)化與電氣工程學(xué)院 董沖沖

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

人工智能；模糊Petri網(wǎng)；任務(wù)分解

1.模糊Petri網(wǎng)分解原理

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

不同的文獻(xiàn)對(duì)模糊Petri網(wǎng)有不同的定義，下面介紹一種用于模糊推理的模糊Petri網(wǎng)。

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

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

任務(wù)映射為庫所集，邏輯規(guī)則映射為變遷集，元任務(wù)的可信度映射為模糊 Petri 網(wǎng)的初始標(biāo)識(shí)。任務(wù)分解序列采用Petri網(wǎng)建模后，任務(wù)分解規(guī)劃問題將轉(zhuǎn)化為最優(yōu)變遷序列激發(fā)問題，激發(fā)序列的優(yōu)化是在可行激發(fā)序列內(nèi)實(shí)現(xiàn)的。

模糊Petri網(wǎng)推理是一種基于目標(biāo)驅(qū)動(dòng)的推理，即尋找與目標(biāo)任務(wù)相關(guān)的最可能的分解，對(duì)任務(wù)分解的解釋可通過的動(dòng)態(tài)來顯示，是一種有效的分解方法。模糊Petri網(wǎng)反向推理主要用于故障診斷、事故分析，缺陷檢測(cè)等。目前，有關(guān)模糊Petri網(wǎng)反向推理機(jī)制的研究已經(jīng)取得了重要的進(jìn)展，提出來的推理算法從問題的結(jié)果出發(fā)，在知識(shí)庫系統(tǒng)中提取出一個(gè)子系統(tǒng)或者尋找出與結(jié)果命題相關(guān)的前提命題，故是一種反向推理算法。

對(duì)Petri網(wǎng)的分析有兩種方法，一種方法是利用網(wǎng)的圖形模型，基于Petri網(wǎng)可達(dá)關(guān)系的圖搜索算法，這種推理算法直觀，易懂，但數(shù)據(jù)結(jié)構(gòu)和算法實(shí)現(xiàn)復(fù)雜，推理效率偏低。另一種方法是以網(wǎng)的關(guān)聯(lián)矩陣為基礎(chǔ)，運(yùn)用Petri網(wǎng)良好的數(shù)學(xué)基礎(chǔ)實(shí)現(xiàn)的推理方法，從而算法實(shí)現(xiàn)簡(jiǎn)單，易行，效率高，但推理過程不直觀，而且所提出的算法對(duì)規(guī)則前提部分的不同命題對(duì)推出的結(jié)論有重要性沒有加以區(qū)別，算法有一定的使用范圍。

這里運(yùn)用一個(gè)基于圖搜索的模糊網(wǎng)推理常用算法，是由Shyi-Ming Chen等人提出的，為能清楚說明該推理算法，下面給出幾個(gè)重要定義，設(shè)模糊Petri網(wǎng)中， ta為一個(gè)變遷，pi、pj、pk為三個(gè)庫所。

定義2.3：變遷發(fā)生一個(gè)變遷能夠發(fā)生，即對(duì)給定的閾值D，若變遷的輸入庫所的token值M（相對(duì)應(yīng)于任務(wù)的可信度）大于閾值D，則變遷能夠發(fā)生，否則不能發(fā)生。

定義2.4：直接前集庫所x經(jīng)過一次變遷t可到達(dá)pi，x稱為pi的直接前庫所，這些庫所的集合稱作直接前集，用DP(pi)表示。

定義2.5：前集庫所x經(jīng)過變遷t可到達(dá)pi，經(jīng)過變遷的個(gè)數(shù)可以是一個(gè)也可以是多個(gè)，x稱為pi的前庫所，這些庫所的集合稱作前集，用P(pi)表示。

定義2.6：相鄰庫所就是一系列與pi經(jīng)同一個(gè)變遷能立即可達(dá)的庫所組成的集合。

算法是生成所有從起始庫所到目標(biāo)庫所之間的可達(dá)路徑，根據(jù)起始庫所的模糊token值來計(jì)算目標(biāo)庫所的模糊token值。并規(guī)定規(guī)則可信度D，以及起始庫所的初始標(biāo)識(shí)M0。

輸入：目標(biāo)庫所、起始庫所的初始標(biāo)識(shí)M0。

輸出：目標(biāo)庫所的有效分解。

（1）進(jìn)行初始化：首先根據(jù)目標(biāo)庫所的輸入查詢直接前集DP(pi)，再查詢DP(pi)中每個(gè)元素的直接前集，直到直接前集為空，得到所有前集中為起始庫所的集合Q。

（2）根據(jù)集合Q可以得到所有可能到達(dá)目標(biāo)庫所的路徑。

（3）根據(jù)Petri網(wǎng)的變遷規(guī)則，對(duì)所有可能到達(dá)目標(biāo)庫所的路徑進(jìn)行分析。刪除無效的路徑。

（4）分析每條有效路徑，以及產(chǎn)生的目標(biāo)庫所的可信度，得到最可信的分解。

（5）顯示分解結(jié)果。

假設(shè)：FPN子網(wǎng)絡(luò)如圖所示，目標(biāo)任務(wù)P0，變遷的閾值都為0.5P1,P2,P3,P4,P5的token值分別為0.6、0、0.8、0.3、0.4

（1）子網(wǎng)絡(luò)如圖所示

（2）確定初始庫所為P1、P2、P3、P4、P5

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

由于P3的token值小于變遷的閾值所以不能激發(fā)，第3條路徑刪除由于P4的token值小于變遷的閾值多疑不能激發(fā)，第5條路徑刪除（5）最終得到petri網(wǎng)

2.結(jié)論

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