任務(wù)分解的Ｐｅｔｒｉ網(wǎng)方法及有效性研究

方　歡　崔煥慶　王麗麗

摘 要：任務(wù)的分解是實(shí)現(xiàn)多主體系統(tǒng)的關(guān)鍵，運(yùn)用形式化的方法對任務(wù)分解進(jìn)行描述和驗(yàn)證是十分必要的。對于一般的任務(wù)邏輯分解表達(dá)式，利用Petri網(wǎng)對任務(wù)的分解進(jìn)行建模，得到任務(wù)分解Petri網(wǎng)，進(jìn)而通過剔除不合理的任務(wù)分解結(jié)構(gòu)得到任務(wù)有效分解的Petri網(wǎng)系統(tǒng)。通過檢查任務(wù)有效分解的Petri網(wǎng)的存在與否，可以判斷任務(wù)的分解結(jié)構(gòu)是否有效。另外，對于任意一個有限的P/T網(wǎng)系統(tǒng)，給出了判斷是否存在無效任務(wù)分解的充分條件，從而論證了在任務(wù)有效分解的Petri網(wǎng)系統(tǒng)中只存在一級活變遷。將任務(wù)分解的有效性判斷與Petri網(wǎng)活性分析聯(lián)系起來，實(shí)現(xiàn)了多主體系統(tǒng)的一個亟待解決的基礎(chǔ)性問題。

關(guān)鍵詞：Petri網(wǎng)；任務(wù)分解；有效性；多主體

中圖分類號：TP302文獻(xiàn)標(biāo)識碼：A文章編號：1672-1098(2008)01-0085-05

收稿日期：2007-07-06

基金項(xiàng)目：安徽省高等學(xué)校青年教師科研“資助計(jì)劃”項(xiàng)目(2007jq1039)；安徽理工大學(xué)碩士博士基金資助項(xiàng)目

作者簡介：方歡(1982-)，女，安徽池州人，講師，碩士，研究方向?yàn)镻etri網(wǎng)理論及應(yīng)用。

The Petri Net Method of Task Decomposition and

Its Validity Research

FANG Huan1，CUI Huan-qing2，WANG Li-li1

(1. School of Science, Anhui University of Science and Technology, Huainan Anhu ,232001,China;2. School of Information Science and Engineering, Shandong University of Science and Technology, Qingdao Shandong 266510, China)

Abstract: Task decomposition is the key to multi-agent system implementation. It is necessary to describe and validate the task decomposition structure by a formal method. The task decomposition is modeled by Petri Nets for the ordinary logical expressions of task decomposition, and the Petri net of task decomposition is obtained, after deleting unreasonable structure of task decomposition, the Petri net of valid task decomposition is obtained. By checking whether the Petri net of valid task decomposition exists, the task decomposition is valid or not can be judged. Furthermore, for any finite P/T net, the sufficient conditions for judging if invalid task decomposition structure exists, are proposed, and accordingly that only first-level live transitions exist in the valid task decomposition Petri net system is proven. The fundamental problem is solved by combination of task decomposition validation and liveness of Petri net system.

Key words: petri net; task decomposition; validity; multi-agent

由于多主體系統(tǒng)不僅能提供很好的系統(tǒng)魯棒性和效率，能為現(xiàn)存的傳統(tǒng)系統(tǒng)提供互操作性，還能求解那些數(shù)據(jù)、技術(shù)及控制等多種異構(gòu)資源同時存在的問題，因此，多主體系統(tǒng)已越來越受到人們的重視。

多主體系統(tǒng)主要研究一組自治智能主體之間智能行為的協(xié)調(diào)問題，在實(shí)現(xiàn)具體多主體系統(tǒng)的過程中，首先面臨這樣的一些問題：如何在一組智能主體中形式化地表示、描述問題？如何分解、分配任務(wù)以及綜合各個主體的結(jié)果［1-2］？多主體之間的協(xié)作存在并發(fā)和同步現(xiàn)象，因而可以利用Petri網(wǎng)對多主體的行為進(jìn)行建模［3-5］，通過模型來了解主體之間的相互關(guān)系。另外，多主體系統(tǒng)中的多個主體可能只有一個求解目標(biāo)，也可能有多個目標(biāo)，對于這些給定的各個子目標(biāo)如何在多主體之間協(xié)作實(shí)現(xiàn)，也可以利用Petri網(wǎng)求解這些子目標(biāo)任務(wù)的完成序列及相關(guān)的分配工作［6-8］，為多主體系統(tǒng)的實(shí)現(xiàn)提供正確分析的依據(jù)。

以上這些工作都沒有涉及到任務(wù)的形式化分解，即給定一個大的系統(tǒng)總目標(biāo)，如何將這個大的總目標(biāo)分解成各個子目標(biāo)，在這個基礎(chǔ)上再考慮任務(wù)的分配等問題?？梢?，任務(wù)的分解是多主體系統(tǒng)實(shí)施任務(wù)分配的前提，也是多主體系統(tǒng)實(shí)施協(xié)作的關(guān)鍵，因此借助一種形式化方法對任務(wù)分解進(jìn)行建模并對任務(wù)分解的有效性及正確性加以驗(yàn)證，是十分必要的。

利用Petri網(wǎng)將總目標(biāo)獹 進(jìn)行邏輯分解，使分解得到的子目標(biāo)可以被單個主體完成，然后運(yùn)用Petri 網(wǎng)的形式化分析方法對任務(wù)分解的正確性進(jìn)行分析和驗(yàn)證是本文的主要工作。

記號玁=(S,T;F)表示一個Petri網(wǎng)結(jié)構(gòu)，?x表示x的前集，x?表示x的后集，其中x∈S∪T。

1 基于Petri網(wǎng)的任務(wù)分解

首先，假定給定的總目標(biāo)獹 邏輯上能分解成若干個能被某個工作者主體單獨(dú)完成的子目標(biāo)?？梢詫G進(jìn)行邏輯分解，分解得到若干個子目標(biāo)，每個子目標(biāo)又可以繼續(xù)進(jìn)行邏輯分解，如此進(jìn)行下去，直到得到一系列的不可再分解的小目標(biāo)。

記那些不能繼續(xù)進(jìn)行邏輯分解的目標(biāo)為原子目標(biāo)，而可以進(jìn)行分解的目標(biāo)為中間目標(biāo)。 記號玣1(g1,g2,…,g璵)輌表示中間目標(biāo)g可以分解成子目標(biāo)g1,g2,…,g璵的邏輯關(guān)系組合。

定義1 若謂詞公式獳有如下形式(類合取范式)：獴1∧B2∧…∧B璵,其中B璱(i=1,2,…,m)形如

獿1∨L2∨…∨L璲，其中L璳∈｛L1,L2,…,L璶｝(k=1,2,…j)，并且L1,L2,…,L璶都是文字，則稱A為類合取范式。

定理1 任何一個類似玣1(g1,g2,…,g璵)輌的表達(dá)式，其左部f1(g1,g2,…,g璵)總可以轉(zhuǎn)換為類合取范式的形式。

證 明 根據(jù)謂詞邏輯的知識，任何一個邏輯關(guān)系式都可以化簡成合取范式，而通過定義1可知，類合取范式可以通過添加項(xiàng)得到合取范式，而合取范式通過化簡也可以得到類合取范式，因此可以將任何一個玣1(g1,g2,…,g璵)轉(zhuǎn)換為類合取范式的形式。

類似可以定義類析取范式及其相關(guān)的性質(zhì)。

定義2 若謂詞公式獳有如下形式（類析取范式）：獴1∨B2∨…∨B璵,其中B璱(i=1,2,…,m)形如

獿1∧L2∧…∧L璲，其中L璳∈｛L1,L2,…,L璶｝(k=1,2,…j)，并且L1,L2,…,L璶都是文字，則稱A為類析取范式。

定理2 任何一個類似玣1(g1,g2,…,g璵)輌的表達(dá)式，其左部f1(g1,g2,…,g璵)可以轉(zhuǎn)換為類析取范式的形式。

下面給出基于Petri網(wǎng)的任務(wù)分解的算法。

算法1 總目標(biāo)獹的Petri網(wǎng)分解

輸入：需要進(jìn)行分解的總目標(biāo)獹

輸出：任務(wù)獹分解的Petri網(wǎng)

步驟：

(1) 將獹進(jìn)行邏輯分解，得到一系列的邏輯分解式的集合獸1，其中F1由一系列諸如f1(g1,g2,…,g璵)輌的邏輯表達(dá)式組成；

(2) 使用邏輯表達(dá)式的化簡方法，將獸1中的每個表達(dá)式的左部都化簡成類合取范式或類析取范式的形式，得到的表達(dá)式集合記為獸；

(3) 對于獸中的每個邏輯表達(dá)式，可使用圖1的轉(zhuǎn)換方法將其轉(zhuǎn)化為Petri網(wǎng)結(jié)構(gòu)；

(4) 將轉(zhuǎn)換過程中所有的庫所玸′組成的集合記為S′，所有變遷t′組成的集合記為T′，所有的流關(guān)系f′組成的集合記為F′，得到的Petri網(wǎng)結(jié)構(gòu)為玁′=(S′,T′;F′)；

(5) 算法結(jié)束。

通過算法1，任何一個總目標(biāo)的邏輯分解式就轉(zhuǎn)換成了語義上等價的Petri網(wǎng)結(jié)構(gòu)。a 玤﹊2∨g﹊3∨…∨g﹊m輌﹊1 b 玤﹊2∧g﹊3∧…∧g﹊m輌﹊1

圖1 邏輯表達(dá)式轉(zhuǎn)換為Petri網(wǎng)結(jié)構(gòu)

定義3 設(shè)目標(biāo)玤璱所對應(yīng)的庫所為s璱∈S′)，若(s璱,s璱)∈F′+，則稱目標(biāo)g璱是自包含的任務(wù)。

顯然，若一個任務(wù)是自包含的，則其對應(yīng)的邏輯任務(wù)分解是無效的。

定義4 設(shè)玁′=(S′,T′;F′)是總目標(biāo)G分解得到的Petri網(wǎng)，而Petri網(wǎng)玁=(S,T;F)滿足：

（1） S罶′∧T罷′∧F罠′；

（2） 總目標(biāo)G對應(yīng)的庫所s1,s1∈S；

（3） 衳∈S∪T-｛s1｝:(s1,x)∈F+；

（4） 衳∈S:(x,x)麱+

則稱Petri網(wǎng)玁=(S,T;F)是總目標(biāo)G的任務(wù)有效分解Petri網(wǎng)。

由于Petri網(wǎng)是一種特殊的二分圖，因此根據(jù)圖論的相關(guān)算法可以很容易求出滿足條件：玸璱∈S′∧(s璱,s璱)∈F′+的所有庫所組成的集合。通過算法2刪除玁′=(S′,T′;F′)中所有的自包含任務(wù)，得到任務(wù)有效分解的Petri網(wǎng)玁=(S,T;F)。

算法2 總目標(biāo)獹對應(yīng)的任務(wù)有效分解Petri網(wǎng)的生成算法

輸入：總目標(biāo)獹根據(jù)算法1得到的Petri網(wǎng)

玁′=(S′,T′;F′)

輸出：總目標(biāo)獹對應(yīng)的任務(wù)有效分解的Petri網(wǎng)

玁=(S,T;F)

步驟：

(1) 根據(jù)圖論判斷回路的算法，求出回路cicle中所有滿足條件s璱∈S′∧(s璱,s璱)∈F′+∧(?s璱聯(lián)玞icle∧s?璱聯(lián)玞icle)的庫所s璱組成的集合，記為S″（其中玞icle為任意一條回路）；

(2) 對于И衧∈S″，找出其前集T″=｛t｜t∈T′∧t∈?s｝；

(3) 找出集合F″=｛f｜(鰔∈S″∪T″)∧y∈S′∪T′(x,y)∈F′｝，從N′=(S′,T′;F′)刪除S″，T″和F″е械乃有元素；

(4) 刪除И衳∈S′∪T′:(x,s1)(F′-F″)+及其相關(guān)聯(lián)的有向邊，其中s1為總目標(biāo)G所對應(yīng)的庫所；

(5) 算法結(jié)束。

若通過算法2計(jì)算出總目標(biāo)獹對應(yīng)的任務(wù)有效分解Petri網(wǎng)不存在，即為空網(wǎng)，則表示此時目標(biāo)獹的邏輯分解是錯誤的，必須對獹重新進(jìn)行邏輯分解。從這里可以看出，將任務(wù)分解轉(zhuǎn)換為Petri網(wǎng)結(jié)構(gòu)對于分析任務(wù)分解的有效性起到了很好的監(jiān)督作用。在實(shí)際工程應(yīng)用中，若不對一個總目標(biāo)邏輯分解的有效性做出監(jiān)督，則會造成很大的人力和財(cái)力的浪費(fèi)，同樣在多主體系統(tǒng)中，任務(wù)的有效分解是多主體系統(tǒng)的構(gòu)建的基礎(chǔ)。

定義5 設(shè)玁=(S,T;F)是總目標(biāo)G的任務(wù)有效分解Petri網(wǎng)。

（1） 映射玀0為

M0(s)=0 衧∈S,?s≠

1 衧∈S,?s=聯(lián)

(2)

K(s)=｜｛t｜t∈T∧t∈?s｝｜ 衧∈S,?s≠

1衧∈S,?s=聯(lián)

(3) И衒∈F:W(f)=1

則稱苮=(S,T;E,K,W,M0)為G的任務(wù)有效分解的Petri網(wǎng)系統(tǒng)。

2 系統(tǒng)活性分析

定理3 任務(wù)有效分解的Petri網(wǎng)系統(tǒng)

И苮=(S,T;E,K,W,M0)是一個標(biāo)識自由選擇網(wǎng)。

證 明 由于在∑中，衪1,t2∈T(t1≠t2)滿足

?t1∩?t2≠聯(lián)藎?t1｜=｜?t2｜=1В根據(jù)自由選擇網(wǎng)的定義［2］，可知結(jié)論明顯成立。

定理4 任務(wù)有效分解的Petri網(wǎng)系統(tǒng)

И苮=(S,T;E,K,W,M0)每個變遷都是一級活的。

證 明 根據(jù)定義4，在任務(wù)有效分解的Petri網(wǎng)系統(tǒng)中都有И衪∈T:(s1,t)∈F+，而同時根據(jù)定義5可知M0(s1)=1，則M0［t＞В因此每個變遷都是一級活的。

引理1 設(shè)И苮=(S,T;E,K,W,M0)為任意一個有限的P/T網(wǎng)系統(tǒng)，滿足：

（1） И苮＊是自由標(biāo)識選擇網(wǎng)；

（2） 映射玀0為

M0(s)=0 衧∈S,?s≠

1 衧∈S,?s=聯(lián)

(3)

K(s)=｜｛t｜t∈T∧t∈?s｝｜ 衧∈S,?s≠

1衧∈S,?s=聯(lián)

(4) И衒∈F∶W(f)=1

若 И苮＊е寫嬖諶級活變遷，則必存在玸∈S，使得(s,s)∈T+。

證 明 因?yàn)楂t是三級活變遷， 因此存在無限長的變遷序列σ使得t在σ中無限多次出現(xiàn)。 設(shè)M0［σ1＞M1［t＞M2，其中#(t,σ1)=0，此時衧∈?t，M2(s)=0。因t是三級活變遷，則M2［t＞必然成立，設(shè)M2［σ2＞M3［t＞，其中，#(t,σ2)=0,此時衧∈?t，M3(s)=1，依此循環(huán)反復(fù)，即可得到無限長的循環(huán)序列σ1tσ2t…，使t出現(xiàn)無限多次。由于標(biāo)識的流動是借助流關(guān)系來實(shí)現(xiàn)，因此由上面的分析可以很容易得出(s,s)∈F+。

引理1 可以用于任務(wù)自包含的判斷。即對于一個給定的有限P/T網(wǎng)系統(tǒng)?？梢愿鶕?jù)引理1來判斷是否存在庫所玸滿足(s,s)∈F+。

定理5 任務(wù)有效分解的Petri網(wǎng)系統(tǒng)中不存在三級活變遷。

證 明 根據(jù)引理1的證明，很容易得出結(jié)論成立。

定理6 任務(wù)有效分解的Petri網(wǎng)系統(tǒng)中不存在二級活變遷。

證 明 假設(shè)任務(wù)有效分解的Petri網(wǎng)系統(tǒng)中存在一個二級活變遷玹，根據(jù)類似引理1的證明思路，不難得出存在一個庫所s滿足(s,s)∈F+，與任務(wù)有效分解的Petri網(wǎng)定義相矛盾，故結(jié)論成立。

綜合引理1，定理5和定理6可以得出：給定一個任務(wù)分解的Petri網(wǎng)系統(tǒng) 苮＃若 苮Ｖ寫嬖詼級活變遷或三級活變遷，則 苮？隙ú皇僑撾裼行Х紙獾腜etri網(wǎng)系統(tǒng)，其中必定存在庫所玸使得(s,s)∈F+，也就是說存在自包含的任務(wù)分解。由此，通過活性分析可以判斷一個任務(wù)分解的Petri網(wǎng)系統(tǒng)中是否存在自包含的任務(wù)分解，或者幫助驗(yàn)證當(dāng)前的任務(wù)分解是否是有效的。

例：設(shè)有一個總目標(biāo)獹，在邏輯上可以將其進(jìn)行以下的分解（A軧表示可以通過A的完成來實(shí)現(xiàn)目標(biāo)B）。

В1） (g1∧g2)∨(g3∧g4)軬

（2） (g5∧g6)∨g7輌1

（3） g15∧g1輌5

（4） g5∧g16輌7

（5） g8∧g9輌2

（6） g10∨(g11∧g12)輌3

（7） g12∨(g13∧g14)輌4

（8） g17∨g18輌12

從上述的邏輯分解式不易看出子目標(biāo)之間的關(guān)系，以及總目標(biāo)的實(shí)現(xiàn)需要借助哪些子目標(biāo)來實(shí)現(xiàn)，更不能判斷此時的任務(wù)分解是否是有效的。

根據(jù)算法1，將上述的8個邏輯分解式轉(zhuǎn)換成任務(wù)分解Petri網(wǎng)（見圖2）。

圖2 邏輯分解式對應(yīng)的任務(wù)分解Petri網(wǎng)然后再根據(jù)算法2，可得出任務(wù)有效分解的Petri網(wǎng)，并根據(jù)定義3得出任務(wù)有效分解的Petri網(wǎng)系統(tǒng)（見圖3）。

圖3 邏輯分解式對應(yīng)的任務(wù)有效分解Petri網(wǎng)系統(tǒng)

可以對圖3的任務(wù)有效分解的Petri網(wǎng)系統(tǒng)進(jìn)行驗(yàn)證分析，系統(tǒng)中的每一個變遷都是一級活的，不存在二級活或者三級活的變遷。并且此任務(wù)有效分解的Petri網(wǎng)系統(tǒng)是一個自由標(biāo)識選擇網(wǎng)。從而驗(yàn)證了本文的結(jié)論。

3 總結(jié)與展望

本文利用Petri網(wǎng)對任務(wù)分解進(jìn)行分析，提出了任務(wù)有效分解的概念，并在此基礎(chǔ)上，利用Petri網(wǎng)的活性分析，對任務(wù)分解的有效性進(jìn)行判定，給出了相關(guān)的結(jié)論，從而使得任務(wù)分解的正確性和有效性在任務(wù)在多主體之間進(jìn)行分配之前能夠得到驗(yàn)證，對多主體系統(tǒng)的構(gòu)建和實(shí)現(xiàn)提供了保障。在解決了任務(wù)的形式化分解之后，以后將進(jìn)行進(jìn)一步深入的研究，考慮以下問題：① 如何利用任務(wù)有效分解的Petri網(wǎng)來對任務(wù)完成的先后順序形成計(jì)劃，組成多主體系統(tǒng)中任務(wù)分配的計(jì)劃庫；② 如何利用相關(guān)的Petri網(wǎng)理論證明計(jì)劃實(shí)施的正確性，為多主體系統(tǒng)的主體計(jì)劃的生成以及任務(wù)的分配和實(shí)施奠定理論基礎(chǔ)；③ 如何利用Petri網(wǎng)來實(shí)現(xiàn)任務(wù)在多主體之間的動態(tài)分配。

參考文獻(xiàn)：

［1］ 焦文品,史忠植.多主體間的協(xié)作過程研究［J］.計(jì)算機(jī)研究與發(fā)展,2000, 37(8)：904-911.

［2］ 姚莉,張維明,汪浩.多主體系統(tǒng)建模方法探索［J］.國防科技大學(xué)學(xué)報(bào),1999,21(4)：118-121.

［3］ 馬炳先,徐潁蕾,吳哲輝.用層次顏色Petri 網(wǎng)模擬主體行為［J］.系統(tǒng)仿真學(xué)報(bào),2003,15(S)：114-118.

［4］ D XU, RAVOLZ, TRIOERGER,et al.Modeling and Verifying Multi-Agent Behaviors Using Predicate/Transition Nets［C］//Proceeding of the 14th International Conference on Software Engineering and Knowledge Engineering, Jul. 2002, 193-200.

［5］ DANNY WEYNS, TOM HOLVOET. A Colored

Petri Net for a Multi-Agent Application ［C］//MOCA '02, Aarhus,Denmark, 2002.

［6］ JAMIE KING, RAYMOND K PRETTY, RAYM-

OND G GOSINE.Coordinated Execution of Tasks in a Multiagent Environment［J］.IEEE Transactions on Systems, Man,and Cybernetics-part A: Systems and Humans,2003,33(5):615-620.

［7］ WENBIAO HAN， MOHSEN A. Jafari. Controller

Synthesis via Mapping Task Sequence to Petri Net［J］.Proceedings ortbe 2003 IEEE lotermtiood Conference an Robotics and Automation Taipei, Tairao, 2003, 33(4)：14-19.

［8］ JAMIE KING, RAYMOND K PRETTY, RAYM-

OND G GOSINE. Coordinated Execution of Tasks in a Multiagent Environment［J］.IEEE Transactions on Systems, Man, and Cybernetics-part A: Systems and Humans,2003,33(5):615-620.

［9］ 吳哲輝.Petri 網(wǎng)導(dǎo)論［M］.北京：機(jī)械工業(yè)出版社華章分社,2005.

［10］ 袁崇義.Petri 網(wǎng)原理與應(yīng)用［M］.北京：電子工業(yè)出版社,2005.

［11］ 石純一,黃昌寧,王家.人工智能原理［M］.北京：清華大學(xué)出版社,1993.

(責(zé)任編輯：何學(xué)華)