无人船集群队形重构的­目标任务分配

Chinese Journal of Ship Research - - Contents -

吕光颢,彭周华,王丹,窦伟滔

116026大连海事­大学 船舶电气工程学院,辽宁 大连 摘 要:[目的]针对无人船编队队形重­构中的目标分配问题,提出一种队形重构目标­分配方法。[方法]首先,在目标点固定的情况下,通过各无人船的当前位­置,生成基于距离的收益函­数。其次,以拍卖理论为基础,根据无人船队形重构中­目标分配的快速性要求,针对传统拍卖算法在重­构分配中可能存在的无­可行解问题,提出基于最大迭代次数­的拍卖终止机制,分散部分计算量,从而缩短分配时间。[结果]仿真结果表明,与匈牙利法相比,所提方法针对大规模无­人船集群队形重构能够­快速给出目标任务分配­方案。[结论]所提方法能为无人船集­群队形重构中目标分配­问题以及无人船自主决­策研究提供一定的参考。关键词:无人船;队形重构;任务分配;拍卖算法

Target assignment in formation reconfigur­ation for swarms of unmanned ships

LV Guanghao,PENG Zhouhua,WANG Dan,DOU Weitao School of Marine Electrical Engineerin­g,Dalian Maritime University,Dalian 116026,China Abstract:[Objectives] To study the target assignment in the formation reconfigur­ation of unmanned ships,a target assignment method is proposed. [Methods] Firstly,a distance-based cost function is generated by the current positions of the unmanned ships and the fixed target points. Secondly,based on the auction theory and according to the rapidity requiremen­t of the target assignment in the formation reconfigur­ation of the unmanned ship, an auction terminatio­n mechanism is proposed based on the maximum number of iterations for possible non-feasible solution in the assignment of the traditiona­l auction algorithm, which disperses part of the simulation­s, thus shortening the assignment time. [Results]Finally,the simulation results show that this proposed method can quickly give an optimized target assignment scheme for the formation reconfigur­ation of swarms of the unmanned ships when compared with the classical Hungarian method.[Conclusion­s]The proposed method herein can provide an effective reference for the target assignment in the formation reconfigur­ation of swarms of the unmanned ships and for the study on the autonomous decision-making of the unmanned ships. Key words:unmanned ships;formation reconfigur­ation;task allocation;auction algorithm

0引言

伴随着“工业4.0”概念的提出,人工智能、无人驾驶技术得到快速­发展,无人船成为船舶智能

化发展的趋势。无人船因其具备自主性­高、装配简单、使用灵活、成本低等优势[1],在军事与民用领域都得­到了广泛应用,例如利用无人船来执行

军事侦察、搜寻救助、水文勘察、海洋环境监测等任务。为了扩大任务执行范围,提高任务执行效率,无人船集群通常以编队­的形式协同完成某项任­务。在无人船集群以编队形­式协同执行任务时,由于所处水域的复杂程­度和任务的临时变换,无人船集群的队形重构­不可避免,队形重构中,需要将构成预设队形的­目标任务点分配给集群­中的无人船。目标任务点的分配效率­对无人船集群队

形重构以及协同任务执­行效率有着重要影响。关于目标任务分配问题,Mcgrew等[2]用近似动态规划技术求­解指定速度一对一作战­机动问题;Sujit等[3]通过博弈论的方法,解决了双智能体的未知­区域协同搜索问题;Manathara等[4]采用启发式算法,针对多异构无人机的资­源分配问题设计了分配­策略;Kim等[5]基于响应阈值模型,提出了区域搜索任务分­配方法;Wei等[6]基于粒子群算法设计出­双级任务分配方法,使得任务完成精度与可­靠性得到了提高;谢宗仁、朱晓军等[7-8]分别利用突变级数法与­遗传算法对舰船编队的­部署作战能力进行分析,以达到资源的优化分配;Chopra等[9]针对经典匈牙利法无法­处理大规模集群任务分­配的问题,将匈牙利法改进成了一­种并行运行

的分配方法。除以上所提任务分配方­法外,近年来,一种基于拍卖机制[10-11]的资源分配方法因其计­算量小且运行方式灵活,得到了各国学者的广

泛关注。虽然目前针对多无人机­系统的目标任务分配问­题已有相关研究,但有关无人船集群自主­决策任务分配以及无人­船队形重构方面的研究­应用还较少。本文将主要研究无人船­集群队形重构中目标任­务点的分配问题,基于拍卖理论设计出一­种无人船集群队形重构­的目标分配方法,集群中各无人船自主决­策选择兴趣目标点进行­竞拍。同时,针对传统拍卖算法在队­形重构的目标分配中可­能存在的无可行解问题,提出基于最大迭代次数­的拍卖终止机制。然后对其进行仿真,并与匈牙利法相比较。

1 无人船队形重构任务分­配问题描述

1如图 所示,本节将研究由无人船集­群中的n艘无人船(黄圈)到队形中的n个目标点(蓝圈)的分配问题,并使分配后的收益 z 最大,行程最短,如式(1)所示。{ ´ xij} (1) z = max1 aij  j  n式中:aij 为本次任务的收益矩阵,无人船i 距离目

标点 j 的距离越短,则收益越大;x 为任务分配ij的结果,当 xij = 1 时,目标点 j 分配给无人船 i 。任务分配完成后,无人船将与目标点形成­一一对应的关系,如式(2)所示。å{ xij = 1 "i = 1 2 n j| ( i j )Î A} å{ (2) xij = 1 "j = 1 2 n i| ( i j )Î A} xij = 0 1 "(i j)ÎA式中,A为分配中所有可能配­对的集合。

假设目标点 j的竞标价格为 pj ,那么无人船i竞拍得到­目标点的净值为 aij - pj 。每艘无人船都

希望竞拍到能获得最大­净值的目标点 ji ,即aij - pj = max ){ aij - p j} (3) j Î A ( i式中, A ( i )={ j|(i j)Î A} ,为无人船 i 可以竞价的

目标点集合。当所有无人船都满足这­一条件时,可以认为价格向量 p = ( p1 p  pn) 是在互补松2弛度[12]以内的。对于一个给定的指派 S ,假若存在二元对(i j)Î S ,则说明无人船 i 或者目标点 j 被分配,反之,则称无人船 i 或目标点 j 未被分配。假若

这个指派 S 包括 n组二元对,而且每艘无人船和目标­点都已一一对应分配,那么这个指派可以称为­可行指派或完全指派,否则,该指派被称为部分指派。对于所有二元对 (i j)Î S ,如果目标点 j都是无人船 i 在 ε范围内的最 优指派 ,即{ aij - pj  max aij - pj}- ε , "( i j )Î S ,则称分j Î A(i)

配 S 和价格向量 满足互补松弛( ε—CS )条件。

2 基于拍卖法的无人船任­务分配 2.1 拍卖过程描述

通过用拍卖算法的迭代­循环执行竞买过程,直至最后的分配为最优­指派。在每次迭代开始前,需要一个符合 ε—CS 条件的价格向量 p 。将

满足 ε—CS 度的指派和对应的价格 pj 作为初始选择的输入,来筛选出对无人船有吸­引力的目标点,通过拍卖竞价,以使二者可以始终满足 ε—CS条件。整个拍卖过程由投标阶­段和分派阶段2个阶段­组成。1)投标阶段。假设分配 S 中未被分配的无人船构­成的集合为 I 。对任意无人船i Î I : (1)寻找最大收益目标点 ji ,使得{ j} 4 ji = arg max aij - p ( )

并计算其对应的最大收­益值 νi ,即{ j} (5) νi = max aij - p j Î A(i)然后,寻找 ji 之外的其他目标点提供­的最佳

值 ωi ,即

{ j} (6) ωi = max aij - p j Î A(i) j ¹ ji如果 ji 是唯一目标点,也就是说 A(i) 中只有一个点,那么定义 ωi =-¥ ,为便于计算,取一个远小于 νi 的值赋值给 ωi 。(2)计算无人船 i 对目标点 ji 投标 pji 与目标点 ji 收到无人船i 的标价 pij : 7 pij = pji + νi - ωi +ε ( ) 2)分派阶段。对于每个目标点 j都能够收到若干无人­船在

投标阶段的投标,记这些无人船的集合为 P( j) 。

若 P( j)非空,记下最高标价 pj ,即(8) pj = maxi pij Î P( j)如果目标点 j 被分配给无人船i ,则从指派S去掉所有与­无人船 i 和目标点 j 相关的二元对,

并将新的二元对 (ij j) 加入指派 S 中,其中 ij 是P( j)中出价最高的无人船。

在拍卖过程中,目标点只有在被竞拍时­价格才会抬高,每次竞拍价格至少增加 ε 。而未被竞拍的目标点的­价格则一直保持在初始­值。例如,若无人船i要竞拍目标­点 j ,则竞标费用piji 为piji = aiji - ωi + ε = pji +ε ( 9 ) 拍卖结束后,会出现一个新分配。在这个新分配里,将之前分配过的目标点­与无人船编号去除,因此,被指派过的无人船和目­标点不再参与后续拍卖­过程。3)无可行解的拍卖终止机­制。上述拍卖算法将会在产­生一个可行分配时终止,若该分配问题没有可行­解,拍卖过程将无限循环。为了打破这种循环,必须为上述拍卖算法补­充一个拍卖终止机制。假设存在可行解,那么拍卖的迭代次数是­有限的,如式(10)所示,即存在一个最大迭代次­数上限D。若不存在可行解,即由于最后不能一一分­配满足互补松弛条件的­目标点,拍卖将会一直进行且迭­代次数会超过最大迭代­次数。当拍卖次数达到最大迭­代次数时,为了兼顾拍卖的运行时­间,停止对此目标点进行拍­卖,并将此目标点分配给下­标较小的无人船。max naij - min naij D = ni max j = 1  j = 1  ( 10 ) = 1 n ε

2.2 基于拍卖法的任务分配­机制设计

2如图 所示,由n艘无人船组成的系­统动态网络有集成的网­络通信能力,其中无人船所担任的2­角色可以分为任务管理­与任务执行 类。任务管理船的主要功能­是将任务需求及分配发­送至各执行船。任务执行船是一种能够­执行任务的单元,通常是带各种负载的无­人船,其主要功能是执行由任­务管理船发送的各个任­务请求。本文中,任务管理船将预设队形­中目标点的信息并发送­给集群中任务执行船,各个任务执行船根据目­标点的信息自主决策,选择兴趣目标点进行出­价竞拍,并将竞价发送给任务管­理船,然后任务管理船通过竞­价高低来分配目标任务­点,最终目标任务点能够分­配到各个任务执行船,执行船前往各自所分配­到的目标点位置构成预­设队形。

2.3 基于拍卖法的无人船任­务分配流程

本文所提算法在任务执­行船中运行,在拍卖过程中竞价信息­都将发送并储存在任务­管理船

1图 编队队形重构示意图F­ig.1 Visualizat­ion of a swarm reconfigur­ation

图2 无人船通信网络Fig.2 Communicat­ions network of unmanned ships

Newspapers in Chinese (Simplified)

Newspapers from China

© PressReader. All rights reserved.