基于改进合同网算法的异构多AUV 协同任务分配

JOURNAL OF UNMANNED UNDERSEA SYSTEMS Dec. 2017

水下无人系统学报

[引用格式] 李娟, 张昆玉. 基于改进合同网算法的异构多AUV协同任务分配[J]. 水下无人系统学报, 2017, 25(5): 418-423.

基于改进合同网算法的异构多AUV协同任务分配

李 娟, 张昆玉

(哈尔滨工程大学 自动化学院, 黑龙江 哈尔滨, 150001)

摘 要: 传统合同网算法应用在异构多自主式水下航行器(AUV)协同任务分配时, 存在招标过程中多

种招标者并存的情况, 不易产生有效招标者; 在投标过程中, 潜在投标者增加了无效投标数量及其招标者对投标结果的评估负担, 极易产生任务不合理的情况。针对以上2种问题, 文中提出了一种基于改进合同网算法的异构多AUV任务分配策略。该方法将任务负载率指标和令牌环网概念结合起来, 有效解决选择招标者及其任务不合理的问题。基于MATLAB的三维任务环境的仿真实验表明, 对于异构型多AUV进行任务分配, 文中提出的改进合同网算法能够有效提高整体效能并进行合理的任务分配。 关键词: 异构多自主式水下航行器; 任务分配; 合同网算法; 任务负载率指标; 令牌环网

中图分类号: TJ630.1; TP242.6; TP393 文献标识码: A 文章编号: 2096-3920(2017)05-0418-06 DOI: 10.11993/j.issn.2096-3920.2017.05.004

Heterogeneous Multi-AUV Cooperative Task Allocation Based on

Improved Contract Net Algorithm LI Juan, ZHANG Kun-yu

(College of Automation, Harbin Engineering University, Harbin 150001, China)

Abstract: When traditional contract net algorithm is applied to heterogeneous multi-AUV collaborative task allocation, co-existence of a variety of bid inviters occurs in bid winning process, leading to difficulty for producing effective inviter, while in bidding process, potential bidders raise the number of invalid bids, and hence increase burden on the inviter for evaluating the bid, which is easy to result in unreasonable tasks. Aiming at the above two problems, this paper proposes a heterogeneous multi-AUV task allocation strategy based on improved contract net algorithm. This strategy combines the task load rate and the token ring network to solve the problems of selecting bid inviter and its unreasonable task. Three-dimensional environment simulation based on MATLAB shows that the improved contract net algorithm can effectively enhance the overall performance and make reasonable task allocation scheme for task allocation of heterogeneous multi-AUV.

Keywords: heterogeneous multi-autonomous undersea vehicle; task allocation; contract net algorithm; task load rate; token ring network

0 引言

hicles, AUV)是一种能携带多种传感器、专用设备的水下智能化装置。它自带能源, 不受脐带缆的自主式水下航行器(autonomous undersea ve-

牵制, 可以在大范围自主完成复杂海洋环境中的

收稿日期: 2017-05-13; 修回日期: 2017-06-08.

基金项目: 国家自然科学基金项目资助(51609046); 中央高校基本科研业务费专项资金资助(HEUCFM170403). 作者简介: 李 娟(1976-), 女, 副教授, 主要研究方向为船舶智能控制.

418 Journal of Unmanned Undersea Systems www.yljszz.cn

.com.cn. All Rights Reserved.2017年12月

李 娟, 等: 基于改进合同网算法的异构多AUV协同任务分配 第5期

高难度、高危险的水下作业任务。现阶段单AUV1 任务分配问题建模

在信息处理、续航时间等方面能力有限, 几乎不首先, 异构多AUV协同任务分配可以描述能满足不断复杂化、多样化的任务执行需求。使为一个五元组 用多AUV系统, 通过各AUV之间的有效协调、合作以弥补单AUV的缺陷与不足显得更为合理。

V,T,F,E,C (1)

多AUV系统应用为人们提出了许多新的有待解式中:

TT1,T2,,Tn代表任务集合, 任务类型

决的关键问题, 包括多AUV系统的组织结构、协是不完全相同的, 每个子任务Tj均由单AUV独调与协作机制、水下通信、数据融合、新型AUV立完成; VV1,V2,,Vm代表AUV集合, 其中, 平台等。

异构AUV是指基础硬件配置或搭载的任务模块任务分配的目的是异构多AUV进行任务分至少一处不同的AUV; C代表约束条件集合; E表配时所付出的代价最小, 效能最高。分配问题属示三维任务环境; F表示目标函数集合。 于NP难度问题, 为了解决任务分配问题, 有关1.1 数学描述

学者提出了各种智能算法, 主要分为集中式任务假设有m艘异构AUV在一块区域中执行不分配和分布式任务分配。集中式任务分配方式有同类型的任务, 共有n个目标需要分配, 则有目线性规划法[1]、目标聚类法[2]以及遗传算法[3]、蚁标分配矩阵

群算法[4]、粒子群算法[5]等群体智能算法[6], 可以在更快的计算速度下实现任务分配过程中的全局Q1 Tj分配给Vi

ij

0 Tj未分配给V (2) i协调。但随着任务分配规模的提高, 计算复杂度、

式中: i1,2,,m;j1,2,,n。

巨大的计算量以及集中式任务分配方式已不适合1.2 收益指标函数

解决大规模任务分配问题。分布式任务分配方法执行任务的收益指标函数

主要集中在生物免疫机制[7]和合同网算法[8-12], n

特别是合同网算法, 由于其并行计算、分布式通RewardTj

信、可扩展性和鲁棒性的特点, 在任务分配方面ValueTj(3)

j1

取得了较好的效果。1980年, Smith 在研究分布式中: ValueTj代表Vi执行任务后的价值函数;

式问题求解过程时提出合同网算法的概念[13]。它表示权重系数。

是一种谈判协调, 通过模仿经济行为的“招标—n

投标—中标”机制来实现任务分配。文献[14]采用ValueTj=1-

1QijPijAij (4)

信息论中熵的变化量表征任务的收益情况, 并最i1

式中: P终建立了协同任务分配问题的优化模型, 并设计ij代表Vi执行任务Tj的效率; Aij代表Vi了基于相邻局部通信的分布式拍卖算法。文献[15]执行任务Tj的剩余能源。 研究了无人机协同目标分配, 引入任务负载系数1.3 代价指标函数

对其进行分配, 存在总体效能低的缺点, 仅考虑执行任务的代价函数

在2D平面。目前为止, 虽然任务分配在移动航行n

Cost器、智能体以及无人机方面已有较多研究, 但在Tj

cotTj (5)

j1

3D环境下对异构多AUV协同任务分配的研究成式中: cotTj代表Vi执行任务后的损耗函数; 果还是很少。

表示权重系数。且

文中针对分配方面存在的总体效能低、分配m

不合理、在中标过程中多种招标者并存的问题, cotTj

引入令牌环网概念和任务负载率指标, 采用基于SiTjQij

(6)

i1

改进合同网算法来对异构多AUV进行任务分配。

式中,SiTj代表Vi执行任务Tj的路径长度代价。

水下无人系统学报 www.yljszz.cn 419 .com.cn. All Rights Reserved.2017年12月

水下无人系统学报 第25卷

1.4 效能指标函数

控制变量进行协商与竞争, 决定任务的分配情对于异构多AUV

协同任务分配问题, 需要一

况。每个AUV都是独立存在的, 在合同网算法模个衡量任务的目标函数值。执行任务的效能指标函型中, 把AUV分为招标者AUV、投标者AUV以数是由收益指标函数和代价指标函数综合所得。 及中标者AUV[16]。招标者是任务的拥有者, 负责

SumTj=RewardTjCostTj (7) 该任务的分配。投标者要能够完成任务。中标者根据分配矩阵会得到一个最优解为

是投标成功的投标者, 被授予了任务。由于AUV

T自身的特性, AUV可以担任多种角色, 即随着时jSum1Summax (8)

1.5 约束条件

间、条件、状态的变化。它们均有独立处理招投在任务分配的过程中

, 异构多AUV协同去

标的能力[17]。

分配不同类型任务, 为了实现最大总体效能, 约针对任务分配过程[18]中, 基于合同网算法的束条件主要体现在

任务协商过程图如图1所示。

m

Q

ij

≤mmax (9)

i1nQ

ij

≤nmax

(10)

j1

seq(Ti,Tj)0

(11) jnimTj

(tT)j1,,n

j1

Vi

(vT),(12)

i1

mn

i,j

1,j1,,n

(13)

1

T

ij1

Ti,j(tE)≤Ui(vE)

(14)

其中: 式(9)中, mmax代表任务分配给AUV的数

图1 基于合同网算法的任务协商过程

量; 式(10)中, nFig. 1 Task negotiation process based on contract net

max代表AUV分配的最大任务量;

式(11)中, 任务Ti和Tj需要按照一定的顺序完成, 1) 招标阶段: 任务宣布。当AUV发现新目标则表示任务之间具有一定的时序约束; 式(12)中, 且无法独立完成当前任务或发现任务需要分配, tT代表任务类型, vT代表AUV类型, 在任务区

招标者AUV通过广播通信机制来通知所有潜在的域中, AUV只能执行类型相匹配的任务; 式(13)投标者AUV来参加投标。通知的信息包括地理位中, 每个任务只能被分配或执行一次, 符合任务置、完成任务需要的能源以及相关约束条件等。

唯一性原则; 式(14)中, tE代表完成任务所需要2) 投标阶段: 当多AUV中的投标者AUV收的能源, vE代表AUV完成任务消耗的能源。

到招标信息后, 根据合同要求和自己的状态, 评估执行合约目标的效能变化, 再把投标信息传送2 合同网算法

给招标者AUV。

分配算法在异构多AUV协同任务分配中担3) 中标阶段: 在招标者AUV接受投标阶段任着重要角色。AUV遵循这些规则来共同协调彼结束后, 会对所有的投标信息进行评估。根据评此的行为, 以达到一致的目标。在异构多AUV系估结果向其满意的投标者AUV进行分配任务, 统中, 由于AUV执行任务的效能不同, 其整体效

这时进行的通信机制是组播通信方式, 可更好地能也会随之而改变。 提高通信的质量。

2.1 传统合同网算法

4) 签约阶段: 中标者AUV和招标者AUV对在多AUV系统中, AUV之间将投标值作为

提出的合同均无意见, 形成承诺监督关系, 执行

420 Journal of Unmanned Undersea Systems www.yljszz.cn

.com.cn. All Rights Reserved.2017年12月

李 娟, 等: 基于改进合同网算法的异构多AUV协同任务分配 第5期

任务, 协商成功。 采用改进合同网算法来对异构多AUV进行2.2 改进合同网算法

任务分配, 有如下假设: AUV是诚实的, 要求

利用上述协商过程虽然可以实现任务的分配, AUV在投标过程中传送给AUV的信息是真实但传统合同网算法存在着多种投标者并存, 任务的。AUV是自利的, 每个AUV都尽可能完成多分配不合理, 整体效能低的缺点。针对这些问题, 的任务或者是总体效能越高的任务, 以局部优化文中提出引入任务负载率指标和令牌环网概念的达到全局优化。AUV是智慧的, 每个AUV在不方法来进行改进。

能超过自身负载的前提下, 完成更多的任务。这

对于选择招标者AUV, 令牌环网解决出现多3条假设是互补的。

种招标者并存的问题, 这种问题要求AUV在任所有AUV会重新计算自己的任务负载率, 务发布之前申请令牌, 即在任务宣布前在几个潜判断是否需要展开拍卖, 进而实现实时任务分在的招标者AUV之间进行比较选择, 需要额外配。整个任务分配过程的流程图见图2。

的通信, 因此对通信质量要求比较高。

对于有效拍卖, 所有满足条件且有能力完成任务的潜在投标者AUV通过比较招标者AUV与自身负载系数来决定是否成为真的投标者AUV, 潜在投标者AUV对投标过程的选择减少了无效投标数量和招标者AUV评估投标结果的负担, 提高了招标效率。

设Vi的工作负载为Li, 则所有AUV的平均工作负载为

m

Li=



Li

m (15)

i1

式中, m为AUV的个数。在此基础上, 定义任务负载率

PLiLiLi

Li (16)

图2 改进合同网算法的任务分配流程图

通过人为设定阈值K≥0, 判断AUV在合Fig. 2 Flow chart of task allocation based on improved

contract net

同网中能够担任的角色。如果|PLi|K, 说明此条AUV的任务负载比多AUV中的平均负载水平3 仿真试验

要高, 需作为招标者进行任务拍卖, 降低自身的文中以异构多AUV协同为仿真对象, 以海任务负载; 反之|PLi|K则表示比多AUV中的洋区域为仿真环境, 在x,y,z[0,2000]的三维空平均负载水平要低。说明AUV能够作为投标者间, x代表海洋区域的长, y代表海洋区域的宽, z参与投标, 为其他AUV分担任务负载。赋予任务代表海洋区域的高(参见图3和图4)。图中, 6艘

负载率超标最大的AUV任务拍卖权, 由其开展AUV均匀分布在x-y轴, 正方形代表AUV搭载新一轮的拍卖。

的是带侦查功能的传感器模块, 五角形代表

为了更好的说明任务负载均衡的情况, 文中AUV搭载的是勘测功能的传感器模块。20个随使用任务负载率的v次方Sp来描述

机分布的目标中, 正方形代表侦查类型, 五角形m

S代表勘测类型, 为了简化AUV和任务, 文中均以p

PLv

i (17) i1质点的形式表现。AUV配置的类型信息, 其中:

式中: v代表1个常量(一般取3), Sp别名为任务负V1, V3和V6表示执行侦查任务的AUV; V2, V4, V5载量。若Sp的值越小, 异构多AUV整体承载的表示执行勘测任务的AUV。加载任务的类型信息, 任务分布就越均匀。

其中: T1, T4, T5, T7, T9, T11, T12, T14, T16表示侦查任

水下无人系统学报 www.yljszz.cn 421 .com.cn. All Rights Reserved.2017年12月

水下无人系统学报 第25卷

务; T2, T3, T6, T8, T10, T13, T15, T17, T18, T19, T20表示通过以上分配情况的图表对比可以看出, 用勘测任务。在实现异构型多AUV协同任务分配传统合同网算法来进行任务分配时, 任务分布不时, 硬件设备和任务模块直接影响执行任务的数均匀, 比如V1承载的任务较少, V6承载的任务较量, AUV只能执行相匹配的任务。

多。对于招标者AUV的选择, 出现多种招标者并存的情况。在引入任务负载率指标和令牌环网后, 改进合同网算法使异构多AUV整体执行的任务均衡, 从而更好的进行合理分配。

为了说明改进合同网算法和传统合同网算法的效果变化情况。在时间允许的条件下, 进行

20次的竞标回合, 每次竞标回合时的位置参数都

是随机的, 得到的分配方案整体效果变化对比图

图3 传统合同网算法任务分配图

(见图5), 底部数字代表竞标回合的次数。可以看Fig. 3 Task allocation map of traditional contract net

出, 在每一轮的竞拍回合中, 改进合同网算法的algorithm

整体效果值比传统合同网算法高, 从而说明, 改进的合同网算法能够很好完成对模型的求解, 提高分配效率。

图4 改进合同网算法任务分配图

Fig. 4 Task allocation map of improved contract net

algorithm

文中分别用传统合同网算法和改进合同网

算法对多AUV协同的任务分配情况进行仿真。

图5 整体效果对比图

由于AUV的数量小于任务的数量, 每个

Fig. 5 Comparison of overall effects changes

AUV承载的任务数量不止一个。表1较好地说明为说明异构多AUV整体的任务负载均衡变了任务分配情况。

化, 如图6所示, 底部数字代表竞标回合的次数。

表1 传统合同网算法与改进合同网算法的任务分配情

况比较表

Table 1 Comparison of task allocation between traditional

and improved contract nets

AUV

传统合同网算法

改进合同网算法

V1 T5 T5, T12 V2 T13, T18, T20 T13, T18, T20 V3 T9, T4, T14 T9, T4, T14 V4 T2, T6, T8 T2, T6, T8, T19

V5 T17, T10, T19, T15, T3T17, T10, T19, T15, T3 图6 任务负载均衡变化对比图

V6

T11, T1, T16, T7, T12

T11, T1, T16, T7

Fig. 6 Comparison of task load balancing changes

422 Journal of Unmanned Undersea Systems www.yljszz.cn

.com.cn. All Rights Reserved.2017年12月

李 娟, 等: 基于改进合同网算法的异构多AUV协同任务分配 第5期

当任务分配不均匀时, 影响任务完成的整体Task Allocation[J]. IEEE Transactions on Systems Man & 效果。在考虑均衡时, 可以提高整体效能。Sp的值Cybernetics Systems, 2010, 43(1): 38-52.

越小, 多AUV整体承载的任务分布就越均匀。

[9] Kim S K, Russell J S. Framework for an Intelligent

Earthwork System: Part II. Task Identification/schedu- 4 结束语

ling and Resource Allocation Methodology[J]. Automa- tion in Construction, 2003, 12(1): 15-27.

文中在传统合同网算法的基础上, 考虑了任[10] Hayano M, Dai H, Sugawara T. Role and Member

务负载率指标和令牌环网概念, 共同影响异构多

Selection in Team Formation Using Resource Estimation AUV协同实现任务分配。在三维环境中, 提出的for Large-scale Multi-agent Systems[J]. Elsevier Science 改进合同网算法可以合理分配任务, 有效地提高Publishers B. V., 2014 , 146(C): 164-172.

异构多AUV的整体效能。改进合同网算法在大[11] Gerkey B P, Mataric M J. Sold!: Auction Methods for

Multi Robot Coordination[J]. IEEE Transactions on 规模水下勘察、水下搜救等领域有实际应用价值。Robotics and Automation, Special Issue on Multi-Robot 未来如何在动态环境中以及AUV是否失效, 在Systems, 2002, 18(5): 758-768.

异构型AUV群体协同进行任务分配时考虑时间[12] 李新亮, 翟江涛, 戴跃伟. 动态环境下基于改进合同网

约束条件是今后的研究重点。

的多Agent任务分配算法[J]. 科学技术与工程, 2013, 13(27): 1671-1815.

参考文献:

Li Xin-liang, Zhai Jiang-tao, Dai Yue-wei. A Task Alloc- ation Algorithm Base on Improved Contract Net Protocol [1] Choudhury B B, Biswal B B. Alternative Methods for

under the Dynamic Environment[J]. Science Technology Multi-robot Task Allocation[J]. Journal of Advanced Man- and Engineering, 2013, 13(27): 1671-1815.

ufacturing Systems, 2011, 8(2): 163-176.

[13] Smith R G. Thecntract Net Protocol High Level Comm-

[2] 赵敏. 分布式多类型无人机协同任务分配研究及仿真unication and Control in Distributed Problem Solver[J]. [D]. 南京: 南京理工大学, 2009.

IEEE Transaction on Computers, 1980, 29(12): 1104- [3] Shima T, Rasmussen S J, Sparks A G, et al. Multiple Task

1113.

Assignments for Cooperating Uninhabited Aerial Vehicles [14] 邸斌, 周锐, 丁全心. 多无人机分布式协同异构任务分

Using Genetic Algorithms[J]. Computers & Operations 配[J]. 控制与决策, 2013, 28(2): 274-278.

Research, 2006, 33(11): 3252-3269.

Di Bin, Zhou Rui, Ding Quan-xin. Distributed Coordin- [4] 寇英信, 王琳, 周中良. 多目标攻击条件下作战任务分

ated Heterogeneous Task Allocation for Unmanned Aerial 配模型研究[J]. 系统仿真学报, 2008, 20(16): 4408- Vehicles[J]. Control and Decision, 2013, 28(2): 274- 278. 4411.

[15] 钱艳平, 夏洁, 刘天宇. 基于合同网的无人机协同目标

Kou Ying-xin, Wang Lin, Zhou Zhong-liang. Study of 分配方法[J]. 系统仿真学报, 2011, 23(8): 1672-1676. Combat Task Allocation Model in Multi-target Attack Qian Yan-ping, Xia Jie, Liu Tian-yu. Task Assignment Condition[J]. Journal of System Simulation, 2008, 20(16) : Scheme Based on Contract Net[J]. Journal of System Sim- 4408-4411.

ulation, 2011, 23(8): 1672-1676.

[5] 李炜, 张伟. 基于粒子群算法的多无人机任务分配方法

[16] Ponda S S, Johnson L B, How J P. Distributed Chance-

[J]. 控制与决策, 2010, 25(9): 1359-1363.

constrained Task Allocation for Autonomous Multi-agent Li Wei, Zhang Wei. Method of Tasks Allocation of Teams[C]//American Control Conference. Piscataway. Multi-UAVs Based on Particles Swarm Optimization[J]. USA: IEEE, 2012.

Co- ntrol and Decision, 2010, 25(9): 1359-1363.

[17] Liang H, Kang F. A Novel Task Optimal Allocation App-

[6] Nedjah N, Mendonc R M D, Mourelle L D M. PSO-based

roach Based on Contract Net Protocol for Agentoriented Distributed Algorithm for Dynamic Task Allocation in a UUV Swarm System Modeling[J]. Optik-International Jo- Robotic Swarm[J]. Procedia Computer Science, 2015, urnal for Light and Electron Optics, 2016, 127(8): 3928- 51(1): 326-335.

3933.

[7] Polat K, Güneş S. A New Method to Forecast of

[18] Valentinis F, Donaire A, Perez T. Energy-based Guidance

Escherichia Coli Promoter Gene Sequences: Integrating of an Underactuated Unmanned Underwater Vehicle on A Feature Selection and Fuzzy-AIRS Classifier System[J]. Helical Trajectory[J]. Control Engineering Practice, 2015, Expert Systems with Applications, 2009, 36(1): 57-64. 44(13): 138-156.

[8] Owliya M, Saadat M, Jules G G, et al. Agent-Based

(责任编辑: 杨力军)

Interaction Protocols and Topologies for Manufacturing

水下无人系统学报 www.yljszz.cn 423 .com.cn. All Rights Reserved.