方　歡　崔煥慶　王麗麗

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

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

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

收稿日期：2007-07-06

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

作者簡(jiǎn)介：方歡(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)資源同時(shí)存在的問(wèn)題，因此，多主體系統(tǒng)已越來(lái)越受到人們的重視。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

下面給出基于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á)式的化簡(jiǎn)方法，將獸1中的每個(gè)表達(dá)式的左部都化簡(jiǎn)成類(lèi)合取范式或類(lèi)析取范式的形式，得到的表達(dá)式集合記為獸；

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

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

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

通過(guò)算法1，任何一個(gè)總目標(biāo)的邏輯分解式就轉(zhuǎn)換成了語(yǔ)義上等價(jià)的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)玤璱所對(duì)應(yīng)的庫(kù)所為s璱∈S′)，若(s璱,s璱)∈F′+，則稱(chēng)目標(biāo)g璱是自包含的任務(wù)。

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

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

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

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

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

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

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

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

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

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

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

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

玁=(S,T;F)

步驟：

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

(2) 對(duì)于И衧∈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所對(duì)應(yīng)的庫(kù)所；

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

若通過(guò)算法2計(jì)算出總目標(biāo)獹對(duì)應(yīng)的任務(wù)有效分解Petri網(wǎng)不存在，即為空網(wǎng)，則表示此時(shí)目標(biāo)獹的邏輯分解是錯(cuò)誤的，必須對(duì)獹重新進(jìn)行邏輯分解。從這里可以看出，將任務(wù)分解轉(zhuǎn)換為Petri網(wǎng)結(jié)構(gòu)對(duì)于分析任務(wù)分解的有效性起到了很好的監(jiān)督作用。在實(shí)際工程應(yīng)用中，若不對(duì)一個(gè)總目標(biāo)邏輯分解的有效性做出監(jiān)督，則會(huì)造成很大的人力和財(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

則稱(chēng)苮=(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)是一個(gè)標(biāo)識(shí)自由選擇網(wǎng)。

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

?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)每個(gè)變遷都是一級(jí)活的。

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

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

（1） И苮＊是自由標(biāo)識(shí)選擇網(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

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

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

引理1 可以用于任務(wù)自包含的判斷。即對(duì)于一個(gè)給定的有限P/T網(wǎng)系統(tǒng)。可以根據(jù)引理1來(lái)判斷是否存在庫(kù)所玸滿(mǎn)足(s,s)∈F+。

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

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

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

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

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

例：設(shè)有一個(gè)總目標(biāo)獹，在邏輯上可以將其進(jìn)行以下的分解（A軧表示可以通過(guò)A的完成來(lái)實(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)來(lái)實(shí)現(xiàn)，更不能判斷此時(shí)的任務(wù)分解是否是有效的。

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

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

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

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

3 總結(jié)與展望

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

參考文獻(xiàn)：

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

［2］ 姚莉,張維明,汪浩.多主體系統(tǒng)建模方法探索［J］.國(guó)防科技大學(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é)華)