时间窗约束下的无人集群分布式任务分配算法_李瑞琳.pdf

第 43 卷第 3 期2023 年 6 月弹箭与制导学报Journal of Projectiles，ockets，Missiles and GuidanceVol.43 No.3Jun.2023DOI:10 15892/j cnki djzdxb 2023 03 003收稿日期:2023 02 04基金项目:科技部 2020 年度科技创新 2030“新一代人工智能”重大项目(2020AAA0108200)资助作者简介:李瑞琳(1999)，女，硕士研究生，研究方向:任务规划。通信作者:杨宜康(1974)，男，教授，博士，研究方向:超大规模互联网星座优化与调度。引用本文:李瑞琳，崔巍，冯彦翔，等 时间窗约束下的无人集群分布式任务分配算法J 弹箭与制导学报，2023，43(3):16-25LI uilin，CUI Wei，FENG Yanxiang，et al Distributed task allocation algorithm for unmanned cluster with time window constraints J Journal of Projec-tiles，ockets，Missiles and Guidance，2023，43(3):16-25时间窗约束下的无人集群分布式任务分配算法李瑞琳，崔巍，冯彦翔，杨宜康(西安交通大学自动化科学与工程学院，陕西 西安710049)摘要:综合考虑任务时间窗以及无人机能力约束，以任务的平均时间成本最小为优化目标，提出一种无人集群分布式协同任务分配算法。首先，定义任务对于无人机的增益和边际增益，用以描述无人机执行任务的时间成本的变化情况。然后，建立包括任务添加、冲突消解和任务再分配三个阶段的分布式分配算法。最后，仿真实验结果表明:第三个阶段将任务完全分配率提高了 13 76%，相比现有算法，所提算法将任务完全分配率提高了 21 94%，任务平均完成时间降低了 24 25 s。关键词:无人集群系统;时间窗约束;任务分配;分布式算法中图分类号:V279+2文献标志码:A文章编码:1673-9728(2023)03-0016-10Distributed Task Allocation Algorithm for Unmanned Cluster withTime Window ConstraintsLI uilin，CUI Wei，FENG Yanxiang，YANG Yikang(School of Automation Science and Engineering，Xi an Jiaotong University，Xi an 710049，Shaanxi，China)Abstract:Considering the constraints of task time window and UAV capability，and taking the minimum average time cost oftasks as the optimization objective，a distributed collaborative task allocation algorithm for unmanned cluster is proposed First，the gain and marginal gain of tasks for UAVs are defined to describe the change of the time cost of UAVs to perform tasksThen，a distributed allocation algorithm is established，which includes three stages:task addition，conflict resolution and taskreallocation Finally，the experimental results show that the third stage increases the task complete allocation rate by 13.76%，the proposed algorithm increases the task complete allocation rate by 21.94%，and the average task completion time decreasesby 24.25 sKeywords:unmanned cluster system;time window constraint;task assignment;distributed algorithm0引言由于具有灵活性强、装配便捷、成本消耗低等优势1，无人机已广泛应用在搜救、交通巡查、遥感测绘等领域2。单架无人机经常无法保证任务的高效执行，因此需要多架无人机组成无人集群联合或协同执行任务。无人集群协同任务分配是指综合考虑任务特点、平台性能和任务环境，以优化目标为牵引，将任务分配给多架无人机，使得整个系统执行任务消耗的成本最低或效率最高3。近年来，无人集群任务分配问题已成为无人集群协同规划领域亟需解决的关键问题4。无人集群任务分配模型一般分为单一任务模型和多任务模型。单一任务模型包括多旅行商问题模型5、车辆路径问题模型6 等;多任务模型有网络流模型和混合整数线性规划模型7 等。单任务模型中各个任务间的模型空间相互独立，而多任务模型中多个任务间的模型空间是共享的，但在实际场景下，可能产生跷跷板现象，即部分任务效果提升，但另一部分任务效果下降。无人集群任务分配方法分为集中式和分布式两种思路。集中式任务分配算法中由中央处理单元整合全局信息做出决策8，常见的集中式方法有最优化方法8-9 和元启发式算法10-17。其中，文献 14 提出一种遗传 蚁群混合算法并对侦察任务分配问题进行求解;文献 15 提出了基于粒子收敛程度的自适应第 3 期李瑞琳等:时间窗约束下的无人集群分布式任务分配算法惯性权重与量子门变异算子，改造了标准量粒子群算法;文献 16 引入二进制矩阵与自适应惯性因子对侦察任务进行分配求解。集中式方法结构简单，但速度较慢，鲁棒性差。分布式任务分配方法通过各无人机之间的交流、协商、决策，协同分配任务，因此分布式方法灵活性强，对单点故障具有一定鲁棒性，能降低安全风险和成本。分布式方法有拍卖算法18-20、合同网算法及其相应的改进算法(extend contract net protocol，ECNP)等21-23。其中，文献 19提出一致性联盟包算法(consensus-based bundle algorithm，CBBA)，采用基于市场的决策策略作为分配任务选择机制，并使用基于局部通信的共识作为冲突消解机制;文献 22 对 CB-BA 算法进行了改进，考虑了异步通信、时间敏感和动态的任务、任务空间中的障碍和干扰等问题。文献 24提出性能影响算法(performance impact algo-rithm，PI)来解决无人集群任务分配问题，优化利益问题的总体目标。相比于 CBBA 算法中每个无人机致力于降低其局部成本，PI 算法旨在优化整个系统的总体成本。同集中式方法相比，分布式任务分配算法依赖智能体之间的交流通信质量，很少考虑真实环境中的一些要素。例如，文献 25 考虑了无人机飞行能力、任务执行时间窗等约束条件，但忽略了任务执行时间长度的约束;文献 26 提出了一种“闭环 CBBA”，考虑任务完成后无人机返回起飞基地，但忽略了任务分配过程中的各项约束;文献 27 基于 CBBA 框架提出了CBBATW 算法，对任务有效时间窗、车辆燃油成本进行了适当的处理，但在任务时间窗约束较严格时，容易出现任务无法完全分配问题;文献 28 对 PI 算法引入动态重调度模块和 Softmax 函数以应对环境的动态变化，但没有考虑到任务的时间窗约束等条件。针对上述问题，文中基于分布式 PI 算法框架，考虑具有时间窗约束的无人集群协同任务分配问题，提出一种以任务平均完成时间最小为优化目标的分布式任务分配算法(distributed allocation with time win-dows，DATW)。文中的时间窗约束属于“硬约束”，即任务必须在时间窗内被执行，否则不予分配。整个算法在所有无人机上并行运行，通过反复执行任务添加、冲突消解和任务再分配三个阶段，得到满足时间窗约束的任务分配结果。最后进行不同规模的仿真实验，验证所提算法的可行性和实用性。研究的主要创新点为:1)将任务的时间窗约束嵌入到 PI 分布式算法架构中，使得被分配的任务均满足时间窗约束。2)同传统 PI 算法相比，针对因不满足时间窗约束而无法分配的任务，提出新的第三个阶段:以无人机局部时间成本最小为优化目标的任务再分配策略。由此任务再分配阶段提高了 13 76%的任务分配成功率。3)与 CBBATW 算法27 相比，提出的 DATW 算法的任务分配成功率平均值提高了 21 94%，任务平均完成时间降低了 24 25 s，所以性能更好。4)相比于 ECNP 算法23，DATW 算法不受无人机通信拓扑变化的影响，在各种拓扑下都能进行充分交流，适应性更强。1问题描述本研究考虑时间窗约束的无人集群协同任务分配问题。给定 m 个任务 Nt=t1，t2，tm 和 n 架无人机 Nu=u1，u2，un，且 n m。任务 tjNt由二元组 loc(tj)，Dj 表示，其中 loc(tj)=(xj，yj，zj)是 tj三维坐标，Dj是执行任务 tj所需时间;无人机uiNu由 loc(ui)，vi 表示，loc(ui)=(xi，yi，zi)是 ui的初始位置坐标，vi表示飞行速度。无人机的动态情况改变会影响其飞行性能。因此，为了简化计算，假设无人机 ui的速度 vi为一个常数。无人机之间通过局部链路进行通信，相应的通信拓扑网络可用n n 维的对称邻接矩阵 G 表示，其元素 Gih=1 表示无人机 ui和 uh互为邻近无人机，彼此可以交换共享信息;Gih=0 表示 ui和 uh不能通信。所有分配给无人机 ui的任务构成了 ui的“执行路径”Pi=t1i，t2i，t|Pi|i。ui从初始位置loc(ui)出发，顺序执行 Pi中的任务，一旦完成当前任务，ui将立刻飞往下一任务位置，不会有等待。所有无人机的执行路径集 P=P1，P2，PnT即为无人集群任务分配的一个“结果”或者“解”。在实际情况下，无人集群任务分配结果会受到来自于无人机和任务两个方面因素的影响。1)无人机因素由于不同无人机具有不同速度，其执行任务的时间成本也不同。令 tjPi，无人机 ui开始执行任务 tj的时间 Tj(Pi)可表示为:Tj(Pi)=dis(loc(ui)，loc(tj)vj，tj=t1iTk(Pi)+Dk+dis(loc(tk)，loc(tj)vi，tjt1i(1)71弹 箭 与 制 导 学 报第 43 卷式中:tk表示路径 Pi中 tj的前一个任务;dis()表示两个坐标之间的欧几里得距离。无人机 ui完成任务 tj所需的“时间成本”Fj(Pi)可表示为:Fj(Pi)=Tj(Pi)+Dj(2)为方便起见，使用(Pi)=tkFkFk(Pi)(Pi)表示Pi中所有任务的完成时间之和，即(Pi)表示无人机 ui的执行路径 Pi的(局部)时间成本。相应的，令uiNuF(Pi)表示系统的全局时间成本。无人机执行任务能力受限影响可表示为24:PiLi，uiNu(3)式中:Pi表示 Pi中的任务数;Li表示无人机 ui的执行任务数上限。2)任务因素任务的开始执行时间必须满足时间窗“硬”约束。令任务 tj必须不早于时间 Tj_start执行，不晚于时间 Tj_end执行，即:Tj(Pi)Tj_start，Tj_end(4)在任务分配问题中，最小化原则可以分为 Mini-Sum 和 MiniMax。MiniSum 准则一般用于最小化所有无人机的资源总消耗或完成每个任务的平均成本，而MiniMax 则是最小化成本最高的无人机的成本。对于无等待分配问题，由于任务时间窗约束的存在，意味着一个无人机的任务分配情况会改变另一个无人机的可用选择，每个无人机的时间成本会受到其他无人机的影响。此时，MiniMax 准则难以反映不同无人机之间的关系，而 MiniSum 准则可以在无等待任务分配上获得更好的效果，因此文中选择 MiniSum 准则。在满足上述无人机和任务约束的前提下，以任务的平均时间成本为优化目标，研究无人集群协同任务分配问题，相应的数学模型为:min1mni=1tjPiFj(Pi)(5)s tPiPj=，ij(6)PiLi，uiNu(7)Tj_startTj(Pi)Tj_end，tjPi，uiNu(8)其中，式(5)为目标函数，表示任务的平均时间成本最小;式(6)规定每个任务只能指派给一个无人机，且不能重复分配24;式(7)规定无人机 ui一次执行任务数不能超过 Li;式(8)引入了一个非凸约束，规定任务的开始执行时间满足时间窗约束。全局优化目标是非凸的，它由无人机的任务列表、任务坐标和每个无人机的飞行速度共同决定。因此所研究的多无人机任务分配问题是 NP-hard 问题29-30，无法通过简单计算直接获得全局最优解。DATW 算法能够保证所研究的优化问题始终存在一个解决方案 P0。令 P0=P1，P2，PnT，其中 Pi=t1i 或 Pi=，即每个无人机只分配一个任务或者不分配任务。也就是说，每个无人机最多执行一个任务后就完成了自身所有任务的执行，因此约束条件式(6)和式(8)很容易被满足。这保证了优化问题至少存在一个可行的分配方案。2无人集群分布式任务分配算法文中提出一种考虑时间窗约束的分布式任务分配算法(DATW)。所提出的 DATW 算法在所有无人机上并行运行。无人机之间通过局部通信拓扑交换信息，记录所有任务的分配结果和任务增益等信息。算法主要包括任务添加、冲突消解和任务再分配三个阶段。算法先循环迭代执行前两个阶段，当所有无人机记录的任务分配对象列表一致且在一段时间内不发改变时，开始执行第三个阶段，继续将一些未分配的任务分给无人机。经过多轮迭代后，最终得到任务平均时间成本最小且满足时间窗约束的无冲突任务分配结果。首先，定义无人机 ui记录的信息列表。1)任务分配对象列表Zi=Zi1，Zi2，ZimT表示无人机 ui记录的所有任务的分配对象，分量 Zij=k 表示 ui认为任务 tj被分配给了 uk。如果 ui认为 tj未分配，则 Zij趋近无穷大，即 Zij。2)任务增益列表Qi=Qi1，Qi2，QimT表示无人机 ui记录的所有任务的增益。当 Zij=k 时，Qij等于将任务 tj从 Pk中删除后，uk的时间成本的减少量。注意，如果 Zij，则令 Qij。3)任务开始执行时间列表Ti=Ti1，Ti2，TimT表示无人机 ui记录的所有任务的开始执行时间。当 Zij=k 时，Tij反映 uk开始执行任务 tj的时间。如果 Zij，则令 Tij。4)时间戳列表si=si1，si2，sinT记录无人机 ui从无人机uh获得最新信息的时刻，分量 sih可表示为19:sih=r，Gih=1max Gia=1sh，Gih1(9)式中 r表示 ui接收 uh信息的时刻。初始时，令 Pi=，Zij，Qij，tj。无人81第 3 期李瑞琳等:时间窗约束下的无人集群分布式任务分配算法机 ui与邻近无人机在通信中互换上述四种信息。2 1任务添加阶段在任务添加阶段，无人机 ui以最小化全局时间成本为目标，在满足时间窗约束的前提下，选择一些任务插入到自身任务路径 Pi。下面首先给出任务对于无人机的“增益”和“边际增益”的概念，分别描述当将一个任务插入 Pi和从 Pi中删除后无人机 ui自身的时间成本(Pi)的变化情况。1)任务增益假设任务 tj位于 Pi中，令 Pitj表示将 tj从 Pi中移除后剩余的任务序列，增益 qij(Pitj)表示将 tj从 Pi删除后无人机 ui时间成本的变化量，按式(10)计算24:qij(Pitj)=(Pi)(Pitj)(10)增益 qij(Pitj)反应了 tj对于 ui当前时间成本的“贡献值”。当 tjPi时，令 qij(Pitj)。2)任务边际增益假设 tjPi，如果把 tj插入 Pi后肯定会引起无人机 ui时间成本的增加，令边际增益 q*ij(Pitj)表示这种增量的最小值，其计算式为:q*ij(Pitj)=minPi+1k=1(Piktj)(Pi)(11)式中 Piktj表示把 tj插入到 Pi的第 k 个位置后得到的任务序列。当 tjPi时，令 q*ij(Pitj)。在任务添加阶段给无人机 ui分配任务时，只有当任务 tj同时满足下面两个条件，它才会被允许插入到 Pi中。条件 1:Ziji 且 q*ij(Pitj)Qij;条件 2:令 p=argq*ij(Pitj)，将 tj插入 Pi的第 p位置后，所得序列 Piptj中所有任务满足时间窗约束。在条件1 中，Ziji 表示 tj未分配给 ui，令 s=Zij。若 sZij，则 Qij记录将 tj从路径 Ps上删除后 us的时间成本的减少量，q*ij(Pitj)表示将 tj插入 Pi后 ui的时间成本的最小增加量，而 q*ij(Pitj)Qij表示要求将 tj插入 Pi后全局时间成本会减小;若 s，则表示 ui认为 tj还未分配，此时 Qij，为提高任务分配成功率，优先将 tj分配给 ui。条件 2 表示将 tj插入Pi合适位置后仍满足时间窗约束。为尽可能的降低全局时间成本或者优先分配还未分配的任务，从集合(Pi)=tjNt|条件 1 和条件 2 对于 tj成立 选择任务插入 Pi的位置 p=argq*ik(Pitk)，则得到:tk=argmaxtj(Pi)(Qij q*ij(Pitj)(12)将 tk分配给 ui后，令 Zik=i，Qik=q*ik(Pitk)，并按照式(1)重新计算 Pi中所有任务的开始执行时间，进而更新列表 Ti。在无人机 ui上执行的任务添加阶段由图1 描述。其中，无人机 ui根据式(12)不断将(Pi)中的任务转移到路径 Pi中，直到(Pi)=或者 ui执行的任务数已达最大承载量。任务添加阶段结束后，重新计算Pi中每个任务 tj对于 ui的增益值 Qij=qij(Pitj)。2 2冲突消解阶段若算法在所有无人机上并行执行，同一项任务可能会同时分配给多个无人机，产生分配冲突。因此，为获得无冲突的任务分配结果，还需执行冲突消解过程。在这个阶段无人机反复迭代执行协商一致和任务删除两步骤，直到消除了所有冲突并且所有无人机的任务分配信息保持一致，达成全局共识，即 Qi=Qh，uiNu，uhNu且 uiuh。图 1ui执行的任务添加过程Fig 1The process of adding tasks performed by ui2 2 1协商一致步骤假设 Gih=1，无人机 ui与邻近无人机 uh通过局部通信拓扑进行信息交换，共享 Zi和 Zh、Qi和 Qh、Ti和 Th、si和 sh，并按照一定的交流规则更新相应信息。实际上，当无人机 ui收到邻近 uh发来的信息后，会根据 Zi和 si来判断接收到的信息是否为任务 tj的最新信息，并以降低自身时间成本为目标，按照表 1 所示的交流规则决定是否更新自身存储的信息 Zi，Qi和Ti。表 1 共包含以下三种操作:1)更新(update):Zij=Zhj，Qij=Qhj，Tij=Thj;91弹 箭 与 制 导 学 报第 43 卷2)保留(leave):不执行任何操作;3)重置(reset):Zij，Qij，Tij。其中，默认操作为保留。此外，储存在无人机 ui上的时间戳 si表示获得信息的最新时间，因此 ui每次接收信息后都需要按照式(9)更新 si。表 1无人机交流规则Table 1UAV communication ruleZhj(uhis sender)Zij(uiis reciever)Action by uihiIf Qhj Qij:updatehUpdate h，iIf sh sior Qhj Qij:updatetjunallocatedUpdateiiLeaveheset h，iIf sh si:resettjunallocatedLeave h，iiIf sh siand Qhj Qij:updatehIf sh si:update;Else:resetIf sh si:update h，i，If sh siand sh si:update;If sh siand Qhj Qij:update;If sh siand si sh:resettjunallocatedIf sh si:updatetjunallocatediLeavehUpdate h，iIf sh si:updatetjunallocatedLeave2 2 2任务删除步骤利用局部通信网进行协商一致步骤后，无人机 ui检查当前任务路径 Pi，从中删除集合 A=tjPi|Ziji 和集合 B=tjPi|Tj(Pi)Tj_start或 Tj(Pi)Tj_end 中的任务。其中，A 表示 Zi和 Pi不匹配的任务集合，B 表示不符合时间窗约束的任务集合。首先，无人机 ui根据式(13)，将能够最大程度减小执行时间成本的任务 tk从 Pi和 A 中同时移除。重复此过程，直到 A 中的所有任务都不再满足(13)或 A为空。tk=argmaxtjA(qij Qij)0(13)其中qij=(Pi)(Pitj)，表示当前时刻任务 tj对于无人机 ui的时间成本的增益。若上述过程结束后 A，将 A 中任务的执行者重置为 ui，即对于所有剩余任务 tjA，令 Zij=i。然后，无人机 ui检查自身序列 Pi，一旦存在任务tjPi不满足时间窗约束，则将 tj从序列 Pi中移除，并重置信息列表 Zij，Qij，Tij。无人机 ui每移除一个任务 tj，都需要重新计算 Pi中各任务的开始执行时间，判断是否出现不符合时间窗约束的新任务。重复迭代执行这个过程，直至 Pi上的所有任务满足时间窗约束。当任务删除操作结束后，重新计算Pi中每个任务 tj的增益 Qij和任务开始时间 Tij。无人机 ui重复执行上述协商一致和任务删除两个步骤，当多轮迭代后任务分配结果不再发生改变，表明已实现无冲突任务分配且满足时间窗约束，完成了冲突消解阶段。可以由图 2 来描述这个阶段。图 2ui执行的冲突消解阶段Fig 2Conflict resolution phase of ui2 3任务再分配阶段一般情况下，执行前两个阶段后得到的任务分配结果能够涵盖所有任务，但在时间窗约束较苛刻的情况下，可能有一些任务没有被分配。令 C 表示前两个阶段后未分配的任务集合。为了使更多的任务在满足时间窗约束的条件下被分配，还需对 C 中的任务执行第三个阶段 任务再分配。再分配阶段包含任务添加和冲突消解两步骤，只将 C 中的任务从无人机上移除或添加，对 C 之外已经分配的任务不再进行操作。2 3 1任务添加步骤为了避免出现任务被同一个无人机重复添加再删除的操作，对无人机 ui定义一个向量 Mi。初始时令 Mi tj=0，tjC。若 tj被 ui添加到 Pi，但因违反时间窗约束而又从 Pi移出后，令 Mi tj=1。任务 tjC 只有满足下述条件 3 和条件 4 才会被允许插入无人机 ui的路径 Pi中的合适位置。条件 3:Ziji，Mi tj=0;条件 4:令 p=argq*ij(Pitj)，将 tj插入 Pi的第 p02第 3 期李瑞琳等:时间窗约束下的无人集群分布式任务分配算法位后，所得序列 Piptj中所有任务满足时间窗约束。令(Pi，C)=tjC|条件 3 和条件 4 对于 tj都成立。以 ui局部时间成本最小化为目标，按照式(14)从(Pi，C)中选择一个任务 tk插入 Pi的位置p=argq*ik(Pitk):tk=argmintj(Pi，C)q*ij(Pitk)(14)不同于式(12)，本轮任务添加仅考虑了任务对于无人机的边际增益，将式(14)中的任务 tk添加到 Pi后，无人机 ui的局部时间成本增加量最小。重复上述任务添加过程，直至式(14)不再满足或者 ui执行的任务数已达最大承载量。2 3 2冲突消解步骤任务再分配冲突消解也分为协商一致和任务删除两部分。1)协商一致因为是针对 C 中任务的再分配过程，所以在此交流过程中，无人机只交换与 C 中任务相关的信息。协商一致的规则如表 1，具体执行操作同 2 2 1 节中的更新、保留和重置操作。2)任务删除无人机 ui需要删除 A=tjPi|Ziji 和 B=tjPi|Tj(Pi)Tj_start或 Tj(Pi)Tj_end 中的任务。其中，ui移除 A中任务的方法与 2 2 2 节相同。而对于任务 tjB，将任务 tj从序列 Pi中移除时，执行操作:Zij，Qij，Tij，Mi tj=1。Mi tj 设置为 1 是为了保证在当前任务再分配阶段中，tj将不会再被添加进 Pi，从而避免无效的任务添加和移除，提高任务分配效率。无人机 ui每移除一个任务 tj，都需要重新计算 Pi中任务的开始执行时间，判断是否出现不符合时间窗约束的新任务。无人机 ui重复迭代地移除 B中任务，直至 B=，即 Pi中的所有任务满足时间窗约束。任务删除过程结束后，计算 Qij和 Tij，tjPi。2 4收敛性分析文中所提出的 DATW 算法包括任务初分配和任务再分配两部分。其中，任务初分配过程对应于 2 1节和 2 2 节描述的任务添加和冲突消解两个阶段。初分配结果可能不会覆盖全部任务，因此需要执行2 3 节中的任务再分配阶段，尽可能的提高任务分配成功率。DATW 算法基于迭代优化原理展开，每一架无人机在每轮迭代中的目标是降低全局时间成本，并尽可能把所有任务分配给无人机。具体来讲，每架无人机计算执行自身任务路径的时间成本，并与其他无人机视角下对应任务的执行成本相比较，递归地选择从自身任务路径中保留或移除任务，以此来降低全局时间成本。同时，通过第三个任务再分配阶段，尽可能地分配任务。最终实现最小化任务平均完成时间的总目标。任务分配过程中，每架无人机的任务增益列表不断更新，反映了当前的分配情况。当所有无人机的任务分配信息保持一致，达成全局共识，即 Qi=Qh，uiNu，uhNu且 uiuh时，算法收敛。DATW 算法在所有无人机上并行执行，流程图如图 3 所示。图 3DATW 算法流程图Fig 3Flow chart of DATW algorithmDATW 算法具体步骤可总结如下:Step 1根据 2 1 节执行任务添加阶段。Step 2根据 2 2 节循环执行冲突消解阶段，直到所有无人机的增益列表不发生改变。Step 3循环执行 Step 1 和 Step 2，直到所有无人机不添加或移除任务，或迭代次数超过 20 轮。计算未分配任务集合 C，若 C=，算法结束。Step 4对 C 中的任务执行再分配阶段任务添加。Step 5执行再分配阶段冲突消解，循环执行再分配协商一致阶段和再分配任务删除阶段，直到所有12弹 箭 与 制 导 学 报第 43 卷无人机的增益列表不发生改变。Step 6循环 Step 4 和 Step 5，直到所有无人机不添加或移除任务，算法结束。3算法仿真分析假设任务分布在 10 000 m 10 000 m 1 000 m的三维区域，无人机初始时分布在10 000 m 10 000 m二维平面，无人机的飞行速度恒为 50 m/s，每架无人机最多执行任务数为 5，任务时间窗口的最晚完成时间不大于 500 s，任务的执行时间均为 30 s。针对无人机数为 n 和任务数为 m 的算例，随机生成所有无人机和任务的坐标和每个任务对应的时间窗约束条件。注意当时间窗约束较为严格时，可能存在无法分配的任务。文中进行了两组实验:第一组验证在不同规模算例中 DATW 算法的任务再分配阶段的有效性;第二组验证不同通信拓扑环境下 DATW 算法的适用性，检验算法能否成功分配所有任务，分析所有任务都分配后的任务的平均完成时间。第二组实验同时与 CBBA-TW27 算法和 ECNP23 算法进行了对比分析，为了能够与 DATW 算法进行对比，对 CBBATW 和 ECNP 依据实验场景进行了必要的调整。为更方便评估任务分配解的质量，首先规定任务分配成功率为 =M/m，其中 M 为分配给集群系统的任务个数。在实验 1 中只对比分析解的成功率，在实验 2 中先比较任务完全分配的概率，再分析对比=100%的场景中所有任务的平均完成时间。实验1在通信拓扑为全联通情况下(如图4(a)所示)，考虑6 种规模的无人集群任务分配问题 n m(3，7)，(6，12)，(9，20)，(12，25)，(15，30)，(30，70)。令 DATW_1 表示不具备任务再分配阶段的 DATW 算法。对于每种算例，随机生成 10 个场景，在每个场景上分别运行 DATW_1 和 DATW 算法，统计每种算例中 的最大值、平均值和最小值。实验结果如表 2 所示。通过仿真可知，在所有算例中，DATW 算法取得比 DATW_1 算法更好的任务分配成功率，平均提高了 13 76%的任务成功分配率。这表明了文中所提出的任务再分配阶段是有效的且高效的，在满足时间窗约束的前提下，能尽可能把任务分配给无人集群系统。实验 2无人集群内部的通信拓扑关系会对信息交流产生较大影响。诸如全联通网(见图 4(a)的密集通信拓扑能促进集群无人机之间的信息交流，而实际上受限于通信链路约束，无人集群系统之间往往以稀疏通信拓扑为主(如链形、星形、环形拓扑，见图4(b)图 4(d)。图 4四种通信拓扑Fig 4Four communication topologies表 2DATW 算法有效性验证Table 2Validation of DATW algorithm%(m，n)Algorithmmaxminave(3，7)DATW100 0071 4387 14DATW_1100 0057 1482 86(6，12)DATW91 6783 3390 00DATW_191 6758 3377 50(9，20)DATW100 0085 0093 00DATW_195 0050 0073 50(12，25)DATW100 0088 0097 20DATW_1100 0068 0083 60(15，30)DATW100 0090 0098 00DATW_193 3363 3382 33(30，70)DATW100 0095 7197 43DATW_190 0070 0080 43为了全面验证文中提出的 DATW 算法在不同通信拓扑下的性能和适应性，本实验分别考虑 3 种规模的算例，即 n m(6，12)，(12，25)，(30，70)。每种规模下随机生成场景数为 30，在每个场景上基于上述四种拓扑分别运行 DATW 算法、CBBATW 算法和 ECNP 算法，分别统计 =100%的概率。同时，统计当 =100%时，任务的平均完成时间的最大值、最小值和平均值，实验结果如表 3 所示。通过仿真可以得出:1)在全联通拓扑下，ECNP 算法性能表现最22第 3 期李瑞琳等:时间窗约束下的无人集群分布式任务分配算法好，DATW 算法稍差一点，但远比 CBBATW 算法表现好，CBBATW 算法在(30，70)的算例中任务完全分配概率仅为 33 33%，相应的任务平均完成时间也明显高于 DATW 和 ECNP 算法;2)ECNP 算法在链形、星形、环形拓扑下，任务完全分配率大幅下降，任务平均完成时间增大，性能变差，这说明 ECNP 算法依赖于通信拓扑。但 DATW 和 CBBATW 在链形、星形、环形拓扑下的实验结果和全联通拓扑下的结果相近，这表明 DATW 和 CBBATW 算法受拓扑关系影响较小，适应性更强;3)CBBATW 算法随实验规模增大，性能大幅降低，成功分配所有任务的概率最低，在所有算例=100%的场景中的任务平均完成时间均值最低，与CBBATW 算法相比，DATW 算法的任务完全分配率平均提升了 21 94%，平均完成时间提升了 24 25 s。因此，DATW 算法能尽可能地成功分配所有的任务，且得到的解质量更好。表 3四种拓扑下三种算法性能表现Table 3Performance of three algorithms under four topologiesCommunicationtopology(n，m)AlgorithmProbability of completeasignment of tasks/%Maximum averagecompletion time/sMinimum averagecompletion time/sMean value of averagecompletion time/sFullconnectivitynetwork(6，12)DATW100 00116 757 270 207 492 317 0CBBATW96 67139 320 798 763 3116 379 6ECNP100 00114 144 869 232 687 228 5(12，25)DATW90 0099 818 462 390 781 920 7CBBATW83 33116 458 385 921 9106 173 4ECNP93 3389 980 056 592 677 158 7(30，70)DATW86 6781 107 964 846 870 777 5CBBATW33 3399 510 890 053 095 808 9ECNP100 0076 379 960 492 066 967 1Chaintopology(6，12)DATW100 00115 855 870 207 492 638 8CBBATW96 67139 320 798 763 3116 379 6ECNP100 00155 450 491 079 5119 713 4(12，25)DATW90 0099 818 462 39082 564 8CBBATW83 33116 461 585 921 9106 244 7ECNP43 33142 958 1106 839 3122 377 3(30，70)DATW83 3381 107 964 846 871 019 1CBBATW26 6798 864 791 778 496 113 5ECNP3 33127 912 9127 912 9127 912 9Startopology(6，12)DATW100 00116 757 270 207 492 575 7CBBATW96 67139 320 798 763 3116 379 6ECNP100 00165 764 389 530 3121 258 5(12，25)DATW90 0099 818 462 390 782 564 8CBBATW83 33116 461 585 921 9106 244 7ECNP43 33142 958 1106 839 3122 377 3(30，70)DATW83 3381 107 964 846 871 019 1CBBATW26 6798 864 791 778 496 113 5ECNP3 33127 912 9127 912 9127 912 9ingtopology(6，12)DATW100 00115 855 870 207 492 638 8CBBATW96 67139 320 798 763 3116 379 6ECNP100 00155 450 491 079 5119 713 4(12，25)DATW90 0099 818 462 390 782 564 8CBBATW83 33116 46