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

李 娟, 张昆玉

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

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

李 娟, 张昆玉

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

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

异构多自主式水下航行器; 任务分配; 合同网算法; 任务负载率指标; 令牌环网

0 引言

自主式水下航行器(autonomous undersea vehicles, AUV)是一种能携带多种传感器、专用设备的水下智能化装置。它自带能源, 不受脐带缆的牵制, 可以在大范围自主完成复杂海洋环境中的高难度、高危险的水下作业任务。现阶段单AUV在信息处理、续航时间等方面能力有限, 几乎不能满足不断复杂化、多样化的任务执行需求。使用多AUV系统, 通过各AUV之间的有效协调、合作以弥补单AUV的缺陷与不足显得更为合理。多 AUV系统应用为人们提出了许多新的有待解决的关键问题, 包括多AUV系统的组织结构、协调与协作机制、水下通信、数据融合、新型AUV平台等。

任务分配的目的是异构多 AUV进行任务分配时所付出的代价最小, 效能最高。分配问题属于 NP难度问题, 为了解决任务分配问题, 有关学者提出了各种智能算法, 主要分为集中式任务分配和分布式任务分配。集中式任务分配方式有线性规划法[1]、目标聚类法[2]以及遗传算法[3]、蚁群算法[4]、粒子群算法[5]等群体智能算法[6], 可以在更快的计算速度下实现任务分配过程中的全局协调。但随着任务分配规模的提高, 计算复杂度、巨大的计算量以及集中式任务分配方式已不适合解决大规模任务分配问题。分布式任务分配方法主要集中在生物免疫机制[7]和合同网算法[8-12],特别是合同网算法, 由于其并行计算、分布式通信、可扩展性和鲁棒性的特点, 在任务分配方面取得了较好的效果。1980年, Smith 在研究分布式问题求解过程时提出合同网算法的概念[13]。它是一种谈判协调, 通过模仿经济行为的“招标—投标—中标”机制来实现任务分配。文献[14]采用信息论中熵的变化量表征任务的收益情况, 并最终建立了协同任务分配问题的优化模型, 并设计了基于相邻局部通信的分布式拍卖算法。文献[15]研究了无人机协同目标分配, 引入任务负载系数对其进行分配, 存在总体效能低的缺点, 仅考虑在2D平面。目前为止, 虽然任务分配在移动航行器、智能体以及无人机方面已有较多研究, 但在3D环境下对异构多AUV协同任务分配的研究成果还是很少。

文中针对分配方面存在的总体效能低、分配不合理、在中标过程中多种招标者并存的问题,引入令牌环网概念和任务负载率指标, 采用基于改进合同网算法来对异构多AUV进行任务分配。

1 任务分配问题建模

首先, 异构多 AUV协同任务分配可以描述为一个五元组

1.1 数学描述

假设有m艘异构AUV在一块区域中执行不同类型的任务, 共有 n个目标需要分配, 则有目标分配矩阵

式中: i = 1,2,… ,m; j = 1,2,… ,n 。

1.2 收益指标函数

执行任务的收益指标函数

式中: Value （ Tj）代表 Vi执行任务后的价值函数;α表示权重系数。

式中: Pij代表 Vi执行任务 Tj的效率; Aij代表 Vi执行任务 Tj的剩余能源。

1.3 代价指标函数

执行任务的代价函数

式中: c ot（ Tj）代表 Vi执行任务后的损耗函数; μ表示权重系数。且

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

1.4 效能指标函数

对于异构多 AUV协同任务分配问题, 需要一个衡量任务的目标函数值。执行任务的效能指标函数是由收益指标函数和代价指标函数综合所得。

1.5 约束条件

在任务分配的过程中, 异构多 AUV协同去分配不同类型任务, 为了实现最大总体效能, 约束条件主要体现在

2 合同网算法

分配算法在异构多 AUV协同任务分配中担任着重要角色。AUV遵循这些规则来共同协调彼此的行为, 以达到一致的目标。在异构多AUV系统中, 由于AUV执行任务的效能不同, 其整体效能也会随之而改变。

2.1 传统合同网算法

在多AUV系统中, AUV之间将投标值作为控制变量进行协商与竞争, 决定任务的分配情况。每个AUV都是独立存在的, 在合同网算法模型中, 把AUV分为招标者AUV、投标者AUV以及中标者AUV[16]。招标者是任务的拥有者, 负责该任务的分配。投标者要能够完成任务。中标者是投标成功的投标者, 被授予了任务。由于AUV自身的特性, AUV可以担任多种角色, 即随着时间、条件、状态的变化。它们均有独立处理招投标的能力[17]。

针对任务分配过程[18]中, 基于合同网算法的任务协商过程图如图1所示。

图1 基于合同网算法的任务协商过程Fig. 1 Task negotiation process based on contract net

1) 招标阶段: 任务宣布。当AUV发现新目标且无法独立完成当前任务或发现任务需要分配,招标者AUV通过广播通信机制来通知所有潜在的投标者AUV来参加投标。通知的信息包括地理位置、完成任务需要的能源以及相关约束条件等。

2) 投标阶段: 当多AUV中的投标者AUV收到招标信息后, 根据合同要求和自己的状态, 评估执行合约目标的效能变化, 再把投标信息传送给招标者AUV。

3) 中标阶段: 在招标者 AUV接受投标阶段结束后, 会对所有的投标信息进行评估。根据评估结果向其满意的投标者 AUV进行分配任务,这时进行的通信机制是组播通信方式, 可更好地提高通信的质量。

4) 签约阶段: 中标者AUV和招标者AUV对提出的合同均无意见, 形成承诺监督关系, 执行任务, 协商成功。

2.2 改进合同网算法

利用上述协商过程虽然可以实现任务的分配,但传统合同网算法存在着多种投标者并存, 任务分配不合理, 整体效能低的缺点。针对这些问题,文中提出引入任务负载率指标和令牌环网概念的方法来进行改进。

对于选择招标者AUV, 令牌环网解决出现多种招标者并存的问题, 这种问题要求 AUV在任务发布之前申请令牌, 即在任务宣布前在几个潜在的招标者 AUV之间进行比较选择, 需要额外的通信, 因此对通信质量要求比较高。

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

设iV的工作负载为iL, 则所有 AUV的平均工作负载为

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

通过人为设定阈值 K ≥ 0 , 判断 AUV在合同网中能够担任的角色。如果|P Li|＞K, 说明此条AUV的任务负载比多AUV中的平均负载水平要高, 需作为招标者进行任务拍卖, 降低自身的任务负载; 反之|P Li|＜K则表示比多AUV中的平均负载水平要低。说明 AUV能够作为投标者参与投标, 为其他AUV分担任务负载。赋予任务负载率超标最大的 AUV任务拍卖权, 由其开展新一轮的拍卖。

为了更好的说明任务负载均衡的情况, 文中使用任务负载率的v次方Sp来描述

式中: v代表1个常量(一般取3), Sp别名为任务负载量。若Sp的值越小, 异构多 AUV整体承载的任务分布就越均匀。

采用改进合同网算法来对异构多 AUV进行任务分配, 有如下假设: AUV是诚实的, 要求AUV在投标过程中传送给 AUV的信息是真实的。AUV是自利的, 每个AUV都尽可能完成多的任务或者是总体效能越高的任务, 以局部优化达到全局优化。AUV是智慧的, 每个AUV在不能超过自身负载的前提下, 完成更多的任务。这3条假设是互补的。

所有 AUV会重新计算自己的任务负载率,判断是否需要展开拍卖, 进而实现实时任务分配。整个任务分配过程的流程图见图2。

图2 改进合同网算法的任务分配流程图Fig. 2 Flow chart of task allocation based on improved contract net

3 仿真试验

文中以异构多 AUV协同为仿真对象, 以海洋区域为仿真环境, 在 x , y, z ∈ [ 0,2 000]的三维空间, x代表海洋区域的长, y代表海洋区域的宽, z代表海洋区域的高(参见图3和图4)。图中, 6艘AUV均匀分布在 x-y轴, 正方形代表 AUV搭载的是带侦查功能的传感器模块, 五角形代表AUV搭载的是勘测功能的传感器模块。20个随机分布的目标中, 正方形代表侦查类型, 五角形代表勘测类型, 为了简化AUV和任务, 文中均以质点的形式表现。AUV配置的类型信息, 其中:V1, V3和V6表示执行侦查任务的AUV; V2, V4, V5表示执行勘测任务的AUV。加载任务的类型信息,其中: T1, T4, T5, T7, T9, T11, T12, T14, T16表示侦查任务; T2, T3, T6, T8, T10, T13, T15, T17, T18, T19, T20表示勘测任务。在实现异构型多 AUV协同任务分配时, 硬件设备和任务模块直接影响执行任务的数量, AUV只能执行相匹配的任务。

图3 传统合同网算法任务分配图Fig. 3 Task allocation map of traditional contract net algorithm

图4 改进合同网算法任务分配图Fig. 4 Task allocation map of improved contract net algorithm

文中分别用传统合同网算法和改进合同网算法对多AUV协同的任务分配情况进行仿真。

由于 AUV的数量小于任务的数量, 每个AUV承载的任务数量不止一个。表1较好地说明了任务分配情况。

表1 传统合同网算法与改进合同网算法的任务分配情况比较表Table 1 Comparison of task allocation between traditional and improved contract nets

通过以上分配情况的图表对比可以看出, 用传统合同网算法来进行任务分配时, 任务分布不均匀, 比如V1承载的任务较少, V6承载的任务较多。对于招标者AUV的选择, 出现多种招标者并存的情况。在引入任务负载率指标和令牌环网后,改进合同网算法使异构多 AUV整体执行的任务均衡, 从而更好的进行合理分配。

为了说明改进合同网算法和传统合同网算法的效果变化情况。在时间允许的条件下, 进行20次的竞标回合, 每次竞标回合时的位置参数都是随机的, 得到的分配方案整体效果变化对比图(见图5), 底部数字代表竞标回合的次数。可以看出, 在每一轮的竞拍回合中, 改进合同网算法的整体效果值比传统合同网算法高, 从而说明, 改进的合同网算法能够很好完成对模型的求解, 提高分配效率。

图5 整体效果对比图Fig. 5 Comparison of overall effects changes

为说明异构多 AUV整体的任务负载均衡变化, 如图6所示, 底部数字代表竞标回合的次数。

图6 任务负载均衡变化对比图Fig. 6 Comparison of task load balancing changes

当任务分配不均匀时, 影响任务完成的整体效果。在考虑均衡时, 可以提高整体效能。Sp的值越小, 多AUV整体承载的任务分布就越均匀。

4 结束语

文中在传统合同网算法的基础上, 考虑了任务负载率指标和令牌环网概念, 共同影响异构多AUV协同实现任务分配。在三维环境中, 提出的改进合同网算法可以合理分配任务, 有效地提高异构多 AUV的整体效能。改进合同网算法在大规模水下勘察、水下搜救等领域有实际应用价值。未来如何在动态环境中以及 AUV是否失效, 在异构型 AUV群体协同进行任务分配时考虑时间约束条件是今后的研究重点。

[1] Choudhury B B, Biswal B B. Alternative Methods for Multi-robot Task Allocation[J]. Journal of Advanced Manufacturing Systems, 2011, 8(2): 163-176.

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

[3] Shima T, Rasmussen S J, Sparks A G, et al. Multiple Task Assignments for Cooperating Uninhabited Aerial Vehicles Using Genetic Algorithms[J]. Computers & Operations Research, 2006, 33(11): 3252-3269.

[4] 寇英信, 王琳, 周中良. 多目标攻击条件下作战任务分配模型研究[J]. 系统仿真学报, 2008, 20(16): 4408-4411.Kou Ying-xin, Wang Lin, Zhou Zhong-liang. Study of Combat Task Allocation Model in Multi-target Attack Condition[J]. Journal of System Simulation, 2008, 20(16) :4408-4411.

[5] 李炜, 张伟. 基于粒子群算法的多无人机任务分配方法[J]. 控制与决策, 2010, 25(9): 1359-1363.Li Wei, Zhang Wei. Method of Tasks Allocation of Multi-UAVs Based on Particles Swarm Optimization[J].Co- ntrol and Decision, 2010, 25(9): 1359-1363.

[6] Nedjah N, Mendonc R M D, Mourelle L D M. PSO-based Distributed Algorithm for Dynamic Task Allocation in a Robotic Swarm[J]. Procedia Computer Science, 2015,51(1): 326-335.

[7] Polat K, Güneş S. A New Method to Forecast of Escherichia Coli Promoter Gene Sequences: Integrating Feature Selection and Fuzzy-AIRS Classifier System[J].Expert Systems with Applications, 2009, 36(1): 57-64.

[8] Owliya M, Saadat M, Jules G G, et al. Agent-Based Interaction Protocols and Topologies for Manufacturing Task Allocation[J]. IEEE Transactions on Systems Man &Cybernetics Systems, 2010, 43(1): 38-52.

[9] Kim S K, Russell J S. Framework for an Intelligent Earthwork System: Part II. Task Identification/scheduling and Resource Allocation Methodology[J]. Automation in Construction, 2003, 12(1): 15-27.

[10] Hayano M, Dai H, Sugawara T. Role and Member Selection in Team Formation Using Resource Estimation for Large-scale Multi-agent Systems[J]. Elsevier Science Publishers B. V., 2014 , 146(C): 164-172.

[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 Systems, 2002, 18(5): 758-768.

[12] 李新亮, 翟江涛, 戴跃伟. 动态环境下基于改进合同网的多 Agent任务分配算法[J]. 科学技术与工程, 2013,13(27): 1671-1815.Li Xin-liang, Zhai Jiang-tao, Dai Yue-wei. A Task Allocation Algorithm Base on Improved Contract Net Protocol under the Dynamic Environment[J]. Science Technology and Engineering, 2013, 13(27): 1671-1815.

[13] Smith R G. Thecntract Net Protocol High Level Communication and Control in Distributed Problem Solver[J].IEEE Transaction on Computers, 1980, 29(12): 1104-1113.

[14] 邸斌, 周锐, 丁全心. 多无人机分布式协同异构任务分配[J]. 控制与决策, 2013, 28(2): 274-278.Di Bin, Zhou Rui, Ding Quan-xin. Distributed Coordinated Heterogeneous Task Allocation for Unmanned Aerial Vehicles[J]. Control and Decision, 2013, 28(2): 274- 278.

[15] 钱艳平, 夏洁, 刘天宇. 基于合同网的无人机协同目标分配方法[J]. 系统仿真学报, 2011, 23(8): 1672-1676.Qian Yan-ping, Xia Jie, Liu Tian-yu. Task Assignment Scheme Based on Contract Net[J]. Journal of System Simulation, 2011, 23(8): 1672-1676.

[16] Ponda S S, Johnson L B, How J P. Distributed Chanceconstrained Task Allocation for Autonomous Multi-agent Teams[C]//American Control Conference. Piscataway.USA: IEEE, 2012.

[17] Liang H, Kang F. A Novel Task Optimal Allocation Approach Based on Contract Net Protocol for Agentoriented UUV Swarm System Modeling[J]. Optik-International Journal for Light and Electron Optics, 2016, 127(8): 3928-3933.

[18] Valentinis F, Donaire A, Perez T. Energy-based Guidance of an Underactuated Unmanned Underwater Vehicle on A Helical Trajectory[J]. Control Engineering Practice, 2015,44(13): 138-156.

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)

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.

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

TJ630.1; TP242.6; TP393

A

2096-3920(2017)05-0418-06

10.11993/j.issn.2096-3920.2017.05.004

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

2017-05-13;

2017-06-08.

国家自然科学基金项目资助(51609046); 中央高校基本科研业务费专项资金资助(HEUCFM170403).

李 娟(1976-), 女, 副教授, 主要研究方向为船舶智能控制.

(责任编辑: 杨力军)