多无人机协同工作流建模与分析

徐胜红，曹文静

(海军航空工程学院 控制工程系，山东 烟台　264001)



多无人机协同工作流建模与分析

徐胜红，曹文静

(海军航空工程学院 控制工程系，山东 烟台264001)

摘要：多无人机协同执行任务能够提升无人机的作战效能和生存性，而协同方法是协同的基础；描述了基于工作流的多无人机协同方法；通过分析单个无人机工作流执行过程，建立单个无人机工作流，研究了协同工作过程；引入Petri网理论，使用基本Petri网形式化描述协同工作流，构建了多无人机协同工作流Petri网模型；针对所建立的协同工作流Petri网模型，通过构建和分析相应的可达图，验证了多无人机协同工作流的有效性；结果表明：所建立的多无人机协同工作流是有效的，基于工作流的协同方法是可行的。

关键词：协同；无人机；工作流；Petri网；可达图

本文引用格式：徐胜红，曹文静.多无人机协同工作流建模与分析[J].兵器装备工程学报，2016(1):109-112.

Citation format:XU Sheng-hong，CAO Wen-jing.Modeling and Analysis for Multi-UAV Cooperation Workflow[J].Journal of Ordnance Equipment Engineering,2016(1):109-112.

在复杂多变的信息化战场环境下，单个无人机执行侦察或攻击等任务时面临侦察角度和范围、杀伤半径和摧毁能力等诸方面的限制，制约了作战效能的发挥。多无人机协同作战是根据作战目的，组织多无人机协同实施作战行动，对敌目标进行协同搜索、跟踪、攻击和防御。目前，多无人机协同执行任务过程中所采用的协同方法主要有：基于地面控制站的协同方法[1-2]、基于中心节点的协同方法[3]、基于多无人机间协商的协同方法[4-8]，以及我们提出的基于工作流的多无人机协同方法[9-10]。

1基于工作流的多无人机协同方法

在基于工作流的多无人机协同方法中，所有参与协同的无人机对任务的执行都要遵循同样的工作流进行。

设所有参与协同的无人机集合记为U，协同执行的任务集合记为T，对于∀t∈T，都对应一个工作流w，与T相应的工作流集合记为W，w中的活动包括两类：协同决策活动：协同决策活动包括战场态势同步和决策两个步骤，整个过程中没有新的战场态势产生；单机任务规划和执行活动：无人机根据决策的结果，规划和控制本无人机的相关设备完成任务，任务执行完毕，修改在执行任务中改变了的本无人机相关战场态势。

战场态势通常包括如下信息：所有参与协同的无人机的编号、飞行状态、作战能力状态、当前活动状态、以及相应状态产生的时刻；所有敌方目标的状态、以及检测到该状态的时刻和无人机编号。

设无人机集合U中的所有无人机要协同执行一项任务tm∈T，tm对应的工作流记作wn，wn中的所有决策集合记为D，∀d∈D，d的决策方法记为f，决策方法集合记为F，初始战场态势为x0，则对于∀u∈U，其协同执行任务的方法如下：

开始协同后，u的工作流管理设备执行wn活动的迁移，并判断当前活动的类型；

如果当前活动是协同决策类型，则与其它无人机进行战场态势同步，直至u存储的战场态势与其他无人机存储的战场态势一致，然后依据u存储的战场态势xj进行决策，决策过程可以描述为

其中，fi∈F是与di∈D相对应的决策方法，xj为战场态势，yj为决策结果。由于对于∀u∈U，此刻决策活动di相同，对应的决策方法fi相同，存储的战场态势xj相同，因此，对于所有参与协同的无人机而言，决策产生的决策结果yj是相同的；决策完毕，继续活动迁移；如果当前活动是单机任务规划和执行活动，则依据决策结果和u存储的战场态势对u的任务进行规划，并控制u相关设备执行任务，任务执行完毕，修改和维护u存储的战场态势中由于执行任务而相应变化的状态，继续活动迁移。

任意无人机u的工作流执行过程如图1所示。

图1　单个无人机工作流执行过程

在协同执行任务的过程中，往往在执行单机任务规划和执行活动的过程中，需要根据当前出现的新情况进行重新协同决策，相应的工作流设计如图2(a)所示，图2(b)是对图2(a)活动的进一步分解。

图2　考虑重新协同决策时单个无人机工作流

图2(a)中，“协同决策”是协同决策活动，而“单机任务规划和执行”是单机任务规划和执行活动。协同决策活动的执行内容包括：无人机首先同步战场态势，当所有无人机所存储的战场态势一致后，进入决策，由于战场态势一致，决策方法一致，因此，决策结果也是一致的。各无人机根据决策结果执行单机任务规划和执行活动。单机任务规划和执行活动包括：规划和执行任务，当在任务执行过程中检测到新态势且需要重新协同决策，则发出重新协同决策请求，并修改自身战场态势，重新进入协同决策活动；当在任务执行过程中接收到其他无人机发送过来的重新协同决策请求，则重新进入协同决策活动；当在执行过程中检测到已完成任务，则结束任务。

2基于Petri网的多无人机协同工作流建模

为了验证多无人机协同工作流的有效性和基于工作流的多无人机协同方法的可行性，应用Petri网对多无人机协同工作流进行形式化建模。

定义1Petri网.五元式PN(P,T,F,W,M0)称为一个Petri网，其中：P={p1,p2,…,pm}是有限位置集，用圆圈来标识，用于描述可能的系统局部状态；T={t1,t2,…,tn}是有限变迁集，使用矩形标识，用于描述修改系统状态的事件；F⊆(P×T)∪(T×P)是有向弧集，它代表节点流关系，表示使事件发生的局部状态(因)或事件发生所引起的局部状态的变化(果)，并且：P∩T=Φ，P∪T≠Φ；W:F→{1,2,3,…}是弧的权函数；M0:P→{0,1,2,…}是初始标识。

在Petri网中，系统的动态特性用令牌(token)标识，令牌表示为包含在位置节点中的圆点，它反映了位置节点代表的状态实现的动态情况。若某位置节点中包含一个令牌，则表示位置节点代表的状态的一次实现(条件或结果为真)；若位置节点中无令牌，则表示位置节点代表的状态尚未实现(条件或结果为假)。

定义2前置集.称•x={y|y∈P∪T∧(y,x)∈F}为前置集。

定义3后置集.称x•={y|y∈P∪T∧(x,y)∈F}为后置集。

定义4点火规则.对p∈P，若M(p)=k，表示位置p中有k个标记(Token)：

1)t∈T称为在标识M下是使能的(Enable)，记为M[t>，当且仅当∀p∈•t:M(p)≥w(p,t)，其中w(p,t)是从p到t的有向弧上的权；

2) 若t∈T在标识M下是使能的，则t可以点火(fire)，从M点火变迁后，演变到新的标识M′，记为：M[t>M′：

定义5死标识.一个标识M∈M0[>称为死标识，当∀t∈T:M[t≯。即，在此标识下任何一个变迁都不能点火。

若所有位置节点容量和弧的权都为1，这样的Petri网就是基本Petri网。基于多无人机协同工作流，构造了多无人机协同工作流的基本Petri网模型，如图3所示。

图3　多无人机协同工作流Petri网模型

在图3中，phk(k∈N，0

3Petri网模型分析

下面基于多无人机协同工作流Petri网模型，构建相应的可达图，研究多无人机协同工作流的有效性。对可达图的分析主要包括：Petri网中所有的事件是否都能点火；可达图中是否有死标识，即端点，并判断该死标识是否是死锁。

可达标识是Petri网所能进入的状态。对于以上多无人机协同Petri网模型，状态节点多，描述Petri网状态的标识太长，为了方便描述，我们使用如下形式来描述图3的可达标识：

其中，〈P1x〉,〈P2y〉,…,〈Pnz〉分别描述了无人机1，2，…，n的令牌当前所处的位置，则初始标识M0=(〈p11〉,〈p21〉,…,〈pi1〉,…,〈pj1〉,…〈pn1〉)。

M0[>表示从初始标识M0开始的所有可达标识的集合。为了减少可达图中的可达标识，同时还能检测出事件发生和死锁的情况，需要简化构造的可达图，不能对每一个事件所产生的标识都描述出来。为此，引入下面的两个定义。

定义6顺序事件序列.设对于多无人机协同Petri网模型中的无人机i，其事件集合记为Ti，i的事件序列〈til1,til2,…,tilm〉称为顺序事件序列，当且仅当对于∀tilx∈Ti，1≤x≤m-1，tilx + 1∈tilx••，且tilx••是唯一的。

定义7可并行执行的顺序事件序列.对于无人机i和j，设i的一个顺序事件序列记为ti=〈til1,til2,…,tilm〉，j的一个顺序事件序列记为tj=〈tjk1,tjk2,…,tjkn〉，如果∀tilx∈ti，∀tjky∈tj，和tjky不存在执行顺序关系，则ti和tj可以并行执行，称为可并行执行的顺序事件序列，记为〈til1,til2,…,tilm〉,〈tjk1,tjk2,…,tjkn〉。

以顺序事件序列并行执行的结果作为可达图的一个标识，对图3构造出的可达图如图4所示。由图4可见，该可达图的状态空间大大缩简，且不影响对事件触发情况和死锁情况的分析。

图4　多无人机协同Petri网模型可达图

从图4可知：

(1)多无人机协同Petri网中，由于各无人机战场态势往往需要多次通信才能达到一致，因此，th3一般都会发生，在图4中，只描述了th3的后继必经事件th4。

(2)图4中有一个死标识，即(〈p17〉,〈p27〉,…,〈pi7〉,…,〈pj7〉,…,〈pn7〉)，该标识代表了所有参与协同的无人机都进入结束任务状态。由于1≤x≤n，px7都没有迁出事件，因此，此标识并不是真正的死锁标识，而是工作流结束标识。

以上可达图表明，本文建立的多无人机协同工作流中，所有事件都能被触发，不存在死锁情况，因此，所建立的多无人机协同工作流是有效的，基于工作流的多无人机协同方法是可行的。

4结束语

多无人机协同执行作战任务能够提升无人机的作战效能和生存能力。本文依据基于工作流的多无人机协同方法，研究了协同工作过程，建立了协同工作流Petri网模型，通过构建和分析相应可达图，验证了多无人机协同工作流的有效性。然而，以上的可达图是通过静态遍历Petri网得到的，因此，其判断工作流有效性的能力有限。

在多无人机协同执行一项具体任务时，需要在多无人机协同工作流的基础上，结合具体协同任务和所采取的决策方法，构建具体的工作流，并采用动态执行的方式，准确地构造可达图，以验证所建立的协同工作流的有效性，并指导建立有效的协同工作流。

参考文献：

[1]曹菊红,高晓光.多架无人机协同作战智能指挥控制系统[J].火力与指挥控制,2003,28(5):22-24.

[2]李建,符小卫,高晓光.通信约束下的多无人机协同航路规划[J].电光与控制,2013，20(6)：29-33.

[3]郭铭,阎昊,韦有平.移动自组网络在无人机通信中的应用研究[J].舰船电子工程,2008,28(6):59-62.

[4]应贲.分布式多Agent 系统的通信与协商策略研究[D].南京：南京邮电大学，2010.

[5]韩健.基于多Agent的无人机协作控制[D].哈尔滨:哈尔滨工业大学，2012.

[6]欧建军,钟麟.基于多智能体的编队协同空战战术规划[J].电光与控制，2010，17(2)：35-38.

[7]MERINO L,CABALLERO F,MARTíNEZ-DE DIOS J R,et al.A cooperative perception system for multiple UAVs:application to automatic detection for forest fires[J].Journal of Field Robotics,2006,23(3/4)：165-184.

[8]MAZS I,KONDAK K,BERNARD M,et al.Multi-UAV cooperation and control for load transportation and deployment[C].the 2nd International Symposium on UAVs,Reno,Nevada,U.S.A：2010:417-449.

[9]曹文静,徐胜红,张毅,基于工作流的多无人飞行器协同方法及系统[P].中国专利:201410154104.8,2014.

[10]徐胜红,曹文静,李文强.一种多无人机协同方法及其性能分析[J].四川兵工学报,2015,36(8)：100-103.

(责任编辑杨继森)

【信息科学与控制工程】

Modeling and Analysis for Multi-UAV Cooperation Workflow

XU Sheng-hong，CAO Wen-jing

(Department of Control Engineering, Naval Aeronautical and Astronautical University, Yantai 264001, China)

Abstract:Cooperation of multi-UAV could improve the combat effectiveness and survivability. Cooperation method is critical to cooperation. Workflow-based multi-UAV cooperation method was described. With the execution process of one UAV’s work flow, we established one UAV’s work flow, and the cooperation process was studied. With the introduce of Petri network, basic Petri net was used to formalize cooperation work flow, and the Petri net model of multi-UAV cooperation work flow was established. For the Petri net model of multi-UAV cooperation work flow, the corresponding reachability graph was established and analyzed to validate the cooperation workflow. Results show that the established cooperation work flow is effective and the workflow-based cooperation method is feasible.

Key words:cooperation; unmanned aerial vehicle(UAV); work flow; Petri network; reachability graph

文章编号：1006-0707(2016)01-0109-04

中图分类号：TP393.4

文献标识码：A

doi:10.11809/scbgxb2016.01.026

作者简介：徐胜红(1974—)，男，副教授，博士，主要从事无人飞行器组网技术研究。

基金项目：国家自然科学基金(61203168)；中国博士后科学基金(2011M500156；2013T60922)

收稿日期：2015-06-21；修回日期：2015-07-10