Petri網的任務分解原理概述

沈陽理工大學自動化與電氣工程學院 董沖沖

Petri網的任務分解原理概述

沈陽理工大學自動化與電氣工程學院 董沖沖

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

人工智能；模糊Petri網；任務分解

1.模糊Petri網分解原理

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

不同的文獻對模糊Petri網有不同的定義，下面介紹一種用于模糊推理的模糊Petri網。

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

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

任務映射為庫所集，邏輯規則映射為變遷集，元任務的可信度映射為模糊 Petri 網的初始標識。任務分解序列采用Petri網建模后，任務分解規劃問題將轉化為最優變遷序列激發問題，激發序列的優化是在可行激發序列內實現的。

模糊Petri網推理是一種基于目標驅動的推理，即尋找與目標任務相關的最可能的分解，對任務分解的解釋可通過的動態來顯示，是一種有效的分解方法。模糊Petri網反向推理主要用于故障診斷、事故分析，缺陷檢測等。目前，有關模糊Petri網反向推理機制的研究已經取得了重要的進展，提出來的推理算法從問題的結果出發，在知識庫系統中提取出一個子系統或者尋找出與結果命題相關的前提命題，故是一種反向推理算法。

對Petri網的分析有兩種方法，一種方法是利用網的圖形模型，基于Petri網可達關系的圖搜索算法，這種推理算法直觀，易懂，但數據結構和算法實現復雜，推理效率偏低。另一種方法是以網的關聯矩陣為基礎，運用Petri網良好的數學基礎實現的推理方法，從而算法實現簡單，易行，效率高，但推理過程不直觀，而且所提出的算法對規則前提部分的不同命題對推出的結論有重要性沒有加以區別，算法有一定的使用范圍。

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

定義2.3：變遷發生一個變遷能夠發生，即對給定的閾值D，若變遷的輸入庫所的token值M（相對應于任務的可信度）大于閾值D，則變遷能夠發生，否則不能發生。

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

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

定義2.6：相鄰庫所就是一系列與pi經同一個變遷能立即可達的庫所組成的集合。

算法是生成所有從起始庫所到目標庫所之間的可達路徑，根據起始庫所的模糊token值來計算目標庫所的模糊token值。并規定規則可信度D，以及起始庫所的初始標識M0。

輸入：目標庫所、起始庫所的初始標識M0。

輸出：目標庫所的有效分解。

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

（2）根據集合Q可以得到所有可能到達目標庫所的路徑。

（3）根據Petri網的變遷規則，對所有可能到達目標庫所的路徑進行分析。刪除無效的路徑。

（4）分析每條有效路徑，以及產生的目標庫所的可信度，得到最可信的分解。

（5）顯示分解結果。

假設：FPN子網絡如圖所示，目標任務P0，變遷的閾值都為0.5P1,P2,P3,P4,P5的token值分別為0.6、0、0.8、0.3、0.4

（1）子網絡如圖所示

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

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

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

2.結論

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