方　欢　崔焕庆　王丽丽

摘 要：任务的分解是实现多主体系统的关键，运用形式化的方法对任务分解进行描述和验证是十分必要的。对于一般的任务逻辑分解表达式，利用Petri网对任务的分解进行建模，得到任务分解Petri网，进而通过剔除不合理的任务分解结构得到任务有效分解的Petri网系统。通过检查任务有效分解的Petri网的存在与否，可以判断任务的分解结构是否有效。另外，对于任意一个有限的P/T网系统，给出了判断是否存在无效任务分解的充分条件，从而论证了在任务有效分解的Petri网系统中只存在一级活变迁。将任务分解的有效性判断与Petri网活性分析联系起来，实现了多主体系统的一个亟待解决的基础性问题。

关键词：Petri网；任务分解；有效性；多主体

中图分类号：TP302文献标识码：A文章编号：1672-1098(2008)01-0085-05

收稿日期：2007-07-06

基金项目：安徽省高等学校青年教师科研“资助计划”项目(2007jq1039)；安徽理工大学硕士博士基金资助项目

作者简介：方欢(1982-)，女，安徽池州人，讲师，硕士，研究方向为Petri网理论及应用。

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

由于多主体系统不仅能提供很好的系统鲁棒性和效率，能为现存的传统系统提供互操作性，还能求解那些数据、技术及控制等多种异构资源同时存在的问题，因此，多主体系统已越来越受到人们的重视。

多主体系统主要研究一组自治智能主体之间智能行为的协调问题，在实现具体多主体系统的过程中，首先面临这样的一些问题：如何在一组智能主体中形式化地表示、描述问题？如何分解、分配任务以及综合各个主体的结果［1-2］？多主体之间的协作存在并发和同步现象，因而可以利用Petri网对多主体的行为进行建模［3-5］，通过模型来了解主体之间的相互关系。另外，多主体系统中的多个主体可能只有一个求解目标，也可能有多个目标，对于这些给定的各个子目标如何在多主体之间协作实现，也可以利用Petri网求解这些子目标任务的完成序列及相关的分配工作［6-8］，为多主体系统的实现提供正确分析的依据。

以上这些工作都没有涉及到任务的形式化分解，即给定一个大的系统总目标，如何将这个大的总目标分解成各个子目标，在这个基础上再考虑任务的分配等问题。可见，任务的分解是多主体系统实施任务分配的前提，也是多主体系统实施协作的关键，因此借助一种形式化方法对任务分解进行建模并对任务分解的有效性及正确性加以验证，是十分必要的。

利用Petri网将总目标獹 进行逻辑分解，使分解得到的子目标可以被单个主体完成，然后运用Petri 网的形式化分析方法对任务分解的正确性进行分析和验证是本文的主要工作。

记号玁=(S,T;F)表示一个Petri网结构，•x表示x的前集，x•表示x的后集，其中x∈S∪T。

1 基于Petri网的任务分解

首先，假定给定的总目标獹 逻辑上能分解成若干个能被某个工作者主体单独完成的子目标。可以将獹进行逻辑分解，分解得到若干个子目标，每个子目标又可以继续进行逻辑分解，如此进行下去，直到得到一系列的不可再分解的小目标。

记那些不能继续进行逻辑分解的目标为原子目标，而可以进行分解的目标为中间目标。 记号玣1(g1,g2,…,g璵)輌表示中间目标g可以分解成子目标g1,g2,…,g璵的逻辑关系组合。

定义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璵)輌的表达式，其左部f1(g1,g2,…,g璵)总可以转换为类合取范式的形式。

证 明 根据谓词逻辑的知识，任何一个逻辑关系式都可以化简成合取范式，而通过定义1可知，类合取范式可以通过添加项得到合取范式，而合取范式通过化简也可以得到类合取范式，因此可以将任何一个玣1(g1,g2,…,g璵)转换为类合取范式的形式。

类似可以定义类析取范式及其相关的性质。

定义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璵)輌的表达式，其左部f1(g1,g2,…,g璵)可以转换为类析取范式的形式。

下面给出基于Petri网的任务分解的算法。

算法1 总目标獹的Petri网分解

输入：需要进行分解的总目标獹

输出：任务獹分解的Petri网

步骤：

(1) 将獹进行逻辑分解，得到一系列的逻辑分解式的集合獸1，其中F1由一系列诸如f1(g1,g2,…,g璵)輌的逻辑表达式组成；

(2) 使用逻辑表达式的化简方法，将獸1中的每个表达式的左部都化简成类合取范式或类析取范式的形式，得到的表达式集合记为獸；

(3) 对于獸中的每个逻辑表达式，可使用图1的转换方法将其转化为Petri网结构；

(4) 将转换过程中所有的库所玸′组成的集合记为S′，所有变迁t′组成的集合记为T′，所有的流关系f′组成的集合记为F′，得到的Petri网结构为玁′=(S′,T′;F′)；

(5) 算法结束。

通过算法1，任何一个总目标的逻辑分解式就转换成了语义上等价的Petri网结构。a 玤﹊2∨g﹊3∨…∨g﹊m輌﹊1 b 玤﹊2∧g﹊3∧…∧g﹊m輌﹊1

图1 逻辑表达式转换为Petri网结构

定义3 设目标玤璱所对应的库所为s璱∈S′)，若(s璱,s璱)∈F′+，则称目标g璱是自包含的任务。

显然，若一个任务是自包含的，则其对应的逻辑任务分解是无效的。

定义4 设玁′=(S′,T′;F′)是总目标G分解得到的Petri网，而Petri网玁=(S,T;F)满足：

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

（2） 总目标G对应的库所s1,s1∈S；

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

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

则称Petri网玁=(S,T;F)是总目标G的任务有效分解Petri网。

由于Petri网是一种特殊的二分图，因此根据图论的相关算法可以很容易求出满足条件：玸璱∈S′∧(s璱,s璱)∈F′+的所有库所组成的集合。通过算法2删除玁′=(S′,T′;F′)中所有的自包含任务，得到任务有效分解的Petri网玁=(S,T;F)。

算法2 总目标獹对应的任务有效分解Petri网的生成算法

输入：总目标獹根据算法1得到的Petri网

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

输出：总目标獹对应的任务有效分解的Petri网

玁=(S,T;F)

步骤：

(1) 根据图论判断回路的算法，求出回路cicle中所有满足条件s璱∈S′∧(s璱,s璱)∈F′+∧(•s璱联玞icle∧s•璱联玞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″)+及其相关联的有向边，其中s1为总目标G所对应的库所；

(5) 算法结束。

若通过算法2计算出总目标獹对应的任务有效分解Petri网不存在，即为空网，则表示此时目标獹的逻辑分解是错误的，必须对獹重新进行逻辑分解。从这里可以看出，将任务分解转换为Petri网结构对于分析任务分解的有效性起到了很好的监督作用。在实际工程应用中，若不对一个总目标逻辑分解的有效性做出监督，则会造成很大的人力和财力的浪费，同样在多主体系统中，任务的有效分解是多主体系统的构建的基础。

定义5 设玁=(S,T;F)是总目标G的任务有效分解Petri网。

（1） 映射玀0为

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

1 衧∈S,•s=联

(2)

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

1衧∈S,•s=联

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

则称苮=(S,T;E,K,W,M0)为G的任务有效分解的Petri网系统。

2 系统活性分析

定理3 任务有效分解的Petri网系统

И苮=(S,T;E,K,W,M0)是一个标识自由选择网。

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

•t1∩•t2≠联荩•t1｜=｜•t2｜=1В根据自由选择网的定义［2］，可知结论明显成立。

定理4 任务有效分解的Petri网系统

И苮=(S,T;E,K,W,M0)每个变迁都是一级活的。

证 明 根据定义4，在任务有效分解的Petri网系统中都有И衪∈T:(s1,t)∈F+，而同时根据定义5可知M0(s1)=1，则M0［t＞В因此每个变迁都是一级活的。

引理1 设И苮=(S,T;E,K,W,M0)为任意一个有限的P/T网系统，满足：

（1） И苮＊是自由标识选择网；

（2） 映射玀0为

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

1 衧∈S,•s=联

(3)

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

1衧∈S,•s=联

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

若 И苮＊е写嬖谌级活变迁，则必存在玸∈S，使得(s,s)∈T+。

证 明 因为玹是三级活变迁， 因此存在无限长的变迁序列σ使得t在σ中无限多次出现。 设M0［σ1＞M1［t＞M2，其中#(t,σ1)=0，此时衧∈•t，M2(s)=0。因t是三级活变迁，则M2［t＞必然成立，设M2［σ2＞M3［t＞，其中，#(t,σ2)=0,此时衧∈•t，M3(s)=1，依此循环反复，即可得到无限长的循环序列σ1tσ2t…，使t出现无限多次。由于标识的流动是借助流关系来实现，因此由上面的分析可以很容易得出(s,s)∈F+。

引理1 可以用于任务自包含的判断。即对于一个给定的有限P/T网系统。可以根据引理1来判断是否存在库所玸满足(s,s)∈F+。

定理5 任务有效分解的Petri网系统中不存在三级活变迁。

证 明 根据引理1的证明，很容易得出结论成立。

定理6 任务有效分解的Petri网系统中不存在二级活变迁。

证 明 假设任务有效分解的Petri网系统中存在一个二级活变迁玹，根据类似引理1的证明思路，不难得出存在一个库所s满足(s,s)∈F+，与任务有效分解的Petri网定义相矛盾，故结论成立。

综合引理1，定理5和定理6可以得出：给定一个任务分解的Petri网系统 苮＃若 苮Ｖ写嬖诙级活变迁或三级活变迁，则 苮？隙ú皇侨挝裼行Х纸獾腜etri网系统，其中必定存在库所玸使得(s,s)∈F+，也就是说存在自包含的任务分解。由此，通过活性分析可以判断一个任务分解的Petri网系统中是否存在自包含的任务分解，或者帮助验证当前的任务分解是否是有效的。

例：设有一个总目标獹，在逻辑上可以将其进行以下的分解（A軧表示可以通过A的完成来实现目标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

从上述的逻辑分解式不易看出子目标之间的关系，以及总目标的实现需要借助哪些子目标来实现，更不能判断此时的任务分解是否是有效的。

根据算法1，将上述的8个逻辑分解式转换成任务分解Petri网（见图2）。

图2 逻辑分解式对应的任务分解Petri网然后再根据算法2，可得出任务有效分解的Petri网，并根据定义3得出任务有效分解的Petri网系统（见图3）。

图3 逻辑分解式对应的任务有效分解Petri网系统

可以对图3的任务有效分解的Petri网系统进行验证分析，系统中的每一个变迁都是一级活的，不存在二级活或者三级活的变迁。并且此任务有效分解的Petri网系统是一个自由标识选择网。从而验证了本文的结论。

3 总结与展望

本文利用Petri网对任务分解进行分析，提出了任务有效分解的概念，并在此基础上，利用Petri网的活性分析，对任务分解的有效性进行判定，给出了相关的结论，从而使得任务分解的正确性和有效性在任务在多主体之间进行分配之前能够得到验证，对多主体系统的构建和实现提供了保障。在解决了任务的形式化分解之后，以后将进行进一步深入的研究，考虑以下问题：① 如何利用任务有效分解的Petri网来对任务完成的先后顺序形成计划，组成多主体系统中任务分配的计划库；② 如何利用相关的Petri网理论证明计划实施的正确性，为多主体系统的主体计划的生成以及任务的分配和实施奠定理论基础；③ 如何利用Petri网来实现任务在多主体之间的动态分配。

参考文献：

［1］ 焦文品,史忠植.多主体间的协作过程研究［J］.计算机研究与发展,2000, 37(8)：904-911.

［2］ 姚莉,张维明,汪浩.多主体系统建模方法探索［J］.国防科技大学学报,1999,21(4)：118-121.

［3］ 马炳先,徐颍蕾,吴哲辉.用层次颜色Petri 网模拟主体行为［J］.系统仿真学报,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 网导论［M］.北京：机械工业出版社华章分社,2005.

［10］ 袁崇义.Petri 网原理与应用［M］.北京：电子工业出版社,2005.

［11］ 石纯一,黄昌宁,王家.人工智能原理［M］.北京：清华大学出版社,1993.

(责任编辑：何学华)