无人机集群技术-智能组网与协同 课件 第8章 无人机集群任务分配

国家级虚拟仿真实验教学一流本科课程《无人机集群技术》第八章无人机集群任务分配目录8.1无人机集群的任务8.2无人机集群任务分配求解8.3集中式动态任务分配算法8.4分布式动态任务分配算法8.5本章小结8.1无人机集群的任务无人机集群任务类型8.1无人机集群的任务的定义无人机集群任务是指需要由多架无人机共同完成的任务，该任务拥有足够的时间资源，允许多架无人机顺序工作或者拥有充足的空间资源容纳多架无人机同时配合工作。任务的耦合关系、任务的内容不同，无人机集群任务的类型也有所差别。4无人机集群任务类型根据任务的耦合关系分类：紧耦合任务和松耦合任务两类。根据任务的内容分类：协同控制类、协同工作类和搜索侦查类三类。依据系统协作执行任务时，无人机之间的关系分类：竞争关系与合作关系两类。8.15无人机集群任务分配问题描述结合无人机任务分配的实际情况，可以把UAV任务分配问题定义为：基于一定的环境知识（如任务目标位置、威胁区域位置等），综合考虑无人机性能、到达时间、油耗、威胁及空域管制等约束条件，为集群中的各无人机分配一个或一组有序的任务集，包括目标集合、执行任务的类型以及不同任务的执行顺序和时间等，确保无人机集群在多任务执行过程中的协同性，尽可能完成最多的任务，实现最高的无人机集群执行任务的整体效率。8.16无人机集群任务分配问题描述任务分配问题的具体含义：首先设置了任务集和无人机集：包含四个待执行任务、两架无人机。然后设计具体的路径和任务执行顺序来完成所设定的四个任务。图中每个带箭头直线上方的数字表示无人机在该段航路上所花费的时间，四个圆圈表示四个任务。圆圈斜线左边的数字表示的无人机任务集中任务的序号，斜线右边的数字表示完成这个任务需要的时间。一个典型的任务分配问题示意图8.17无人机集群任务分配问题描述无人机集群任务分配描述方法：8.1一个UAV集群U包含N个无人机U={U1,U2，···，UN}。假设UAV集群在一个二维空间执行任务，在任意时刻t，无人机U的位置为

。设每架UAV为具有恒定速度的质点，无人机的属性可以用一个七元素组来表述：＜＞表示无人机编号、位置、健康状况、价值、任务集合、顺利完成概率和最大完成数量。在任务区域内包含有限数目的待执行任务，组成一个任务集，NT为任务的数量，其属性可以用一个六元素组来表述：＜＞表示目标编号、位置、状态、价值、威胁半径和顺利完成概率，对应水平位置为8无人机集群任务分配问题描述无人机集群任务分配描述方法：UAV任务分配的结果是为集群中的任一无人机Ui分配一条任务执行路线Pi有：其中表示无人机Ui的出发位置，也就是说，对应无人机Ui需要制定一个有序任务集：8.19无人机集群任务分配问题描述8.1无人机集群任务分配的特点：123无人机所需处理的一般为相互耦合的复杂任务系统。复杂性如何保证优先执行目标价值高的任务，如何在短的时间或损耗概率下，尽可能多地执行任务，都是任务分配过程中需要考虑的问题。准确性在任务环境中存在不确定性和无人机预先探测信息的不完备性，会使预先任务分配方案变得不再可行，此时就需要进行动态的在线任务分配，这就要求任务分配算法具有较小的计算复杂度，能够保证实时性要求。实时性10无人机集群任务分配问题描述无人机任务分配的一般原则：（1）无人机的利益最大化，最有利于任务完成的无人机，将优先分配到任务目标；（2）尽量缩短任务的执行时间或者缩短无人机的总航程；（3）目标的优先级，那些具有较高价值的目标应该首先被分配执行；（4）要考虑不同无人机之间的任务均衡性。8.111在无人机集群的任务分配中，通常需要考虑的约束条件：1.最大执行能力无人机只有有限的任务能力，假设无人机Ui的任务执行集合为Pi，则该任务集合的总能力消耗Q(Pi)应小于该无人机的最大任务执行能力

，此约束可表示为：2.最大航程受机载燃油或电源的限制，无人机只能进行有限距离的连续飞行。假设无人机Ui的任务执行集合为，对应的无人机Ui的飞行总距离为Li，应小于无人机的最大航程，此约束可表示为： 3.每个任务都能被分配到所有的任务都需要被分配执行，此约束可表示为：无人机集群任务分配问题描述8.1125.任务时序约束在多无人机多任务分配问题中，任务之间的时序约束通常包括以下两类：①

各个目标上不同类型的任务之间必须满足的时序约束条件②

不同目标的任务之间存在的时序约束如当Ti对Tj具有保护作用时，则对Tj的任务必须在确认了Ti的任务完成之后才能执行，即在无人机集群的任务分配中，通常需要考虑的约束条件：4.同一个任务不能分配给多架无人机同一个任务只能分配给一架无人机，这可以避免任务的重复执行，对于需要多架无人机共同执行的任务，也将其分解为多个子任务，将每个子任务分配给一架无人机。此约束可表示为：无人机集群任务分配问题描述8.113在无人机集群的任务分配中，通常需要考虑的约束条件：6.多机协同约束任务集合中的任何一个任务只能被完成一次，除非在预先的任务需求中对某个特定的目标指定了多次任务或者该任务没能顺利完成。设xi,j∈{0,1}为决策变量，其值满足无人机集群任务分配问题描述则多机协同约束可以表达为：

8.1通过上述描述可知，无人机集群任务分配也是具有诸多约束条件的复杂多目标优化问题。不同约束条件之间还存在着耦合关系，这也增加了无人机任务分配的难度。14无人机集群任务分配问题描述无人机集群的任务过程：1.离线任务预规划：在起飞前，指挥控制中枢根据任务计划和目标环境信息为无人机进行静态环境下的最优载荷配置、目标分配和参考航迹规划。2.巡航飞行：无人机集群以编队的形式进行巡航飞行，指挥控制中枢上的引导操纵员根据参考航迹和无人机集群的状态信息。3.在线任务重规划：在线动态调整无人机集群的任务与航迹，实现多无人机动态协同响应不同的突发事件。4.任务实施：进入目标区域后，按照预先定义的功能角色和协同方案展开任务。5.返航：完成既定任务后，无人机集群计算剩余可用燃油（或剩余可用电量）、选择最佳着陆点并规划返航航迹。8.1158.2无人机集群任务分配求解无人机集群任务分配模型分类在任务分配与协调建模方面，通常采用的方法是对问题进行适当简化后通过经典优化问题进行建模。根据任务分配建模分类，现阶段的模型主要有旅行商问题模型，通用分配问题模型，车辆路径问题模型，混合整数线性规划模型，多无人机协同任务分配问题模型以及随机博弈论任务分配模型。8.217无人机集群任务分配模型分类1.多旅行商问题（MTSP）模型一般来讲，泛化的MTSP问题定义为：给定n个城市集合，让m个旅行商各自从一个城市出发，每位旅行商访问其中一定数量的城市，最后回到其出发城市。要求每个城市至少被一位旅行商访问一次并且只能访问一次，问题的目标是求得访问m条环路的代价最小访问次序，其中代价可以是距离、时间、费用等。8.218无人机集群任务分配模型分类使用MTSP问题模型对无人机任务分配问题建模：假设由a架无人机构成的无人机集群，有b个目标任务的任务集，无人机集群从同一个基地出发，沿着预先设定的飞行航路，完成所有的任务，每个任务只能被完成一次，最后考虑无人机的总航程、无人机完成任务的时间、无人机消耗的能力、完成任务的价值利益等。该模型适用于多无人机单任务分配情形。8.21.多旅行商问题（MTSP）模型192.通用分配问题（GAP）模型通用分配问题属于背包问题的一种，描述为将N个物品分配到M个背包中去。每个背包的容量固定，分配目标是找到一种分配方式，使所有背包整体收益达到最大。使用GAP问题模型对无人机任务分配问题建模：考虑将m个任务分配给n架无人机，每个任务只能给一架无人机执行并且单架无人机的资源，如最大任务数、最大航程受到限制。无人机集群任务分配模型分类8.220无人机集群任务分配模型分类3.车辆路径问题（VRP）模型车辆路径问题是一类具有重要实用价值的组合优化问题，对车辆路径模型进行如下描述：假设有m辆货车，每辆车的负载能力不同，它们从同一个基地出发，为n个目标点输送货物，每个目标点需要送达的货物数量不同，最后，所有货车回到出发点。车辆路径问题模型要考虑送达的时间，货物送达的消耗，完成输送的价值等，并保证所有的货物安全送达。VRP模型分为静态VRP模型和动态VRP模型8.221无人机集群任务分配模型分类4.混合整数线性规划（MILP）模型混合整数线性规划是利用线性化函数建立模型，该模型描述简洁、直接，有助于提高无人机任务执行效率和生存能力。将多无人机对地面目标执行攻击任务问题建模为MILP模型，对每个目标必须要按序执行确认、打击和评估三项任务，并且定义任务之间存在使能约束、时序约束等多种约束条件。从目标优化的角度出发，考虑各种约束条件建立了多无人机协同任务分配的多目标MILP模型。该模型适用于多无人机多任务分配情形。8.222无人机集群任务分配模型分类5.多无人机协同任务分配问题（CMTAP）模型CMTAP模型适用于多无人机多任务分配情形。随着无人机能力的不断增强，无人机执行任务的复杂程度也随之增大，不同任务之间存在着复杂的时序以及时间约束。正是在这种背景下，CMTAP模型被提出。该模型充分考虑一组无人机完成一系列针对地面目标的连贯任务，包括任务目标的识别、攻击、毁伤评估等。8.223无人机集群控制架构1.集中式控制架构在这种控制架构下，集群中的无人机将收集到的外部环境信息和自身状态信息等局部信息发送给中心控制节点，中心控制节点将所有数据进行融合、分类得到全局信息，然后根据全局信息进行分析和决策，将决策结果以控制指令的形式发送给各无人机。其优点是分配算法实现简单且具备产生全局最优解的潜力。该种控制体系结构适用于已知确定的环境，规模较小的系统。8.224无人机集群控制结构集中控制存在的问题：1)实时性差当约束条件较多、信息量较大时，任务分配的计算时间也会拉长，不易满足实时性要求。2）鲁棒性差中心控制节点是整个系统的核心决策单元，负责集群内所有无人机的任务决策。一般情况下，中心控制节点只有一个，一旦该中心控制节点出现故障，则整个集群将失去执行任务的能力，最终不可避免地导致任务失败。8.225无人机集群控制结构区别于集中式控制体系，分布式控制体系中无人机集群中的无人机是具有独自决策能力的智能体，它们具有很强的协同能力和自治性。主要可以分为两种：完全分布式控制体系结构和部分分布式控制体系结构。（1）完全分布式控制体系架构完全分布式控制体系是一种依靠无人机的自主性和相互协作的一种体系结构，在完全分布式控制体系中，把无人机看成具有决策能力的智能体，这样无人机任务分配问题就转化成为各个智能体之间任务的分配和决策问题。8.22.分布式控制架构26无人机集群控制结构（2）部分分布式控制体系架构部分分布式控制体系吸取了无人机任务分配控制体系结构中集中式控制和完全分布式控制体系各自的优势，对于多类型无人机集群任务分配问题的解决方案更为合理。而且部分分布式控制体系对集中式控制体系和分布式控制体系进行取长补短，具有较大的实际应用意义。8.227基于多智能体的分层集散式控制该控制方法借鉴多智能体系统（Multi-AgentSystem,MAS）的思想，将任务控制站中具有人机界面的控制系统和各无人机内部的自主控制系统结合，建立一个分层多智能体系统，用于描述多类型无人机系统的集散式控制体系结构，左图为控制体系的结构图：8.23.基于多智能体的分层集散式控制28无人机集群控制结构在这种结构中，集中式控制体现在任务控制站中，而分布式控制体现在两个方面：一是在预分配阶段，二是在任务执行阶段。从控制体系结构图中可以看出无人机集群包含以下两个部分：（1）集中控制层：该功能实现的是任务控制站中控制系统的集中控制功能。（2）分布式控制层：当外部环境发生变化时，各无人机组通过TSA相互通信，重新分配任务。组内TSA把目标任务分解成若干子任务，然后把子任务分配给组内的各架UAV。同时，UAV也将信息反馈给任务控制站中的指挥员。8.229集中式无人机集群动态任务分配算法8.3集中式无人机集群任务分配算法无人机集群任务分配求解方法无人机集群的任务分配定义:

基于一定的环境知识（如任务目标位置、威胁区域位置等）和任务要求，为编队中各架无人机分配一个或一组有序的任务集（或目标、空间位置），以便在完成最大任务的同时，使无人机集群的整体效率达到最优。求解无人机任务分配的有效方法是设计出能在合理的计算时间内找到最优或近似最优解的算法。8.331集中式无人机集群任务分配算法典型启发式算法集中式任务分配求解方法可以分为最优化方法和启发式方法。典型的最优化方法穷举法、整数规划法、约束规划法和图论法。典型启发式算法聚类算法、群智能类算法群智能类算法以粒子群优化算法和遗传算法居多。

8.332PSO算法群智能算法的具体特点：昆虫群的群体行动指的是昆虫个体根据一些规律进行个别的运动，从而导致整个群体显现出一种运动规则。在运动中昆虫主要遵循三个准则：第一，实时监测与邻近个体距离，防止产生交叉冲突；第二，采集邻近个体的信息，如速度、位置等；第三，保证和其他昆虫的距离，不能太远，而脱离群体。

8.333PSO算法群智能算法的优点：随机性强；可以对较大规模的实际问题进行求解；逻辑简单，适用于简单的任务判断；在搜索过程中消耗的能力少。8.3群智能算法的缺点：实时性差，很难确定具体时间；理论依据不够充分；得到的解不一定是最优的；对于多类型的无人机不适用。

34PSO算法PSO算法在无人机集群中的应用场景

现假设共有N架无人机和M个地面目标，无人机数量远小于目标数。需要对每个目标执行一次交互任务，因此有M个任务。每个单交互任务只需要一架无人机攻击相应目标；而每个多交互任务需要多架无人机同时与相应的目标交互。无人机完成任务会获得的综合收益由交互的价值、交互时间、完成交互的飞行距离等因素决定。每架无人机的载荷有限。8.335PSO算法该场景下的约束条件：（1）飞行器执行任务时的总航程D。（2）飞行器的载荷上限是Q。（3）飞行器的飞行路程不能超过最大航程Lmax。如何设计适应度函数：（a）飞行器要尽可能避免发生损毁和失联，记为飞行器损耗C。（b）飞行器要尽可能的减少资源消耗，记为航程消耗L。（c）飞行器要尽可能的与价值高的目标进行交互，记为交互收益H。

8.336PSO算法PSO算法求解的基本流程：①初始化一群大小为m的粒子，包括它的位置和速度。②设计适应度函数并评价每个粒子的适应度大小。③对每个粒子将其适应度大小与历史极值P作比较，如果比历史极值好，便将它作为新的P。④根据迭代公式，改变粒子的位置和速度。⑤如达到结束条件（有足够好的适应值或者达到预设的迭代次数），则结束；否则，返回步骤②。⑥算法结束。

8.337遗传算法遗传算法

进化理论算法的理论依据是仿照自然界中生物种群进化过程，以优胜劣汰的进化原则，将相对优秀的生物个体通过遗传保留下来。遗传算法是这一大类算法中使用最多、最为典型的算法。遗传算法采用三种进化操作：选择操作、交叉操作和变异操作。8.338遗传算法1.遗传算法基本步骤：①

设置演化代数Ngen，种群规模Npop，繁殖池子大小S，交叉概率Pc，变异概率Pm；②

随机生成大小为Npop的种群；③

评价UAV任务分配种群中的每一个个体；④

如果满足终止，转到第⑫步，否则，进入第⑤步；⑤

利用选择轮盘种群中选取S个个体组成繁殖池子；⑥

按交叉概率Pc，采用部分映射交叉PMX方式进行交操作；⑦

按照变异概率Pm，进行变异操作；8.339遗传算法1.遗传算法基本步骤：⑧

将新生成的个体加入种群中；⑨

计算新个体的适应值；⑩将扩展的种群最差的S个个体删除，使其恢复原来种群的大小；⑪

转到第④步；⑫

从种群中选出最好的个体作为所求航迹，进化过程结束。8.340遗传算法2.染色体编码方法：染色体编码方案：用一个长度为L的任务点排列表示每个种群个体，染色体的每个基因座上随机设定一个任务点的序号。同时对于集群中的所有UAVi（i=1，···，NU），此染色体还对应一个随机产生的非负整数Ni的集合，集合中的元素表示该UAV分配到的任务点的数目，并保证 。下图染色体表示：2个UAV组成的飞行编队，其中UAV1按序执行任务2-3，N1

=2；UAV2按序执行任务1-4-5，N2

=3。8.341遗传算法3.无人机集群任务分配问题的进化操作：（1）选择操作具体的执行过程如下：①计算出种群中每一个个体的评价函数的值，得到它们的总和；②分别计算种群子个体评价函数值的相对值，即各个个体被选中作为父代遗传到下一子代的概率；③再使用类似赌博轮盘的操作（即产生0-1之间的随机数），从而分别确定每个个体被选中遗传到下一代的概率。8.342遗传算法3.无人机集群任务分配问题的进化操作：（2）交叉操作由父代染色体Tx，Ty

按照PMX方法产生两个新子代染色体算法步骤：

8.343遗传算法3.无人机集群任务分配问题的进化操作：（3）变异操作在UAV任务分配的混合搜索算法中，将细菌觅食算法中的迁徙操作作为改进进化算法中的变异算子使用，称之为迁徙变异算子。迁徙变异算子首先进行迁徙操作，以概率随机选择种群中评价函数值较差的染色体，作为变异的初始染色体，然后以概率Pm随机抽取初始染色体中的一位进行变异操作。8.344遗传算法遗传算法优点：以评价函数值为依据进行判断，不需引入其他数学方法对数据进行处理；因为有多个基因插入点，所以具有很强的随机性；存在变异概率，可以跳出局部最优。遗传算法缺点：变异的概率很小，所以很难跳出局部最优解而得到全局最优解;遗传算法由于其本质上的随机性，导致其在大规模组合优化问题的求解

效率和精度不高。8.345无人机集群任务动态再分配无人机任务再分配的定义无人机任务再分配是指在无人机执行任务的过程中，出现无人机损毁、环境变化、敌方目标变化以及总体任务变化等情况时，无人机任务规划系统对这些不确定性事件做出应对措施。在具体环境中，环境的动态性和不确定性以及协同控制的复杂性，任务集、无人机集和环境可能随时发生改变，所以在无人机静态任务分配的基础上，必须存在任务动态再分配机制，根据环境变化和集群状态的变化快速调整无人机的任务计划，以适应复杂的任务执行环境。8.346无人机集群的动态环境任务再分配1.任务动态再分配的触发条件

123无人机集群在执行任务过程中，其任务集并不一定是固定不变的。任务改变由于各种不确定因素，队中的各架无人机可能退出任务的执行，而它原先分配到的任务需要分配给其他无人机，这时，需要进行任务再分配。无人机状态改变地面控制站可在任何时刻对正在执行的任务进行干预而触发任务再分配地面控制站8.347无人机集群的动态环境任务再分配2.任务动态再分配采用的策略

123此种方案如同起飞前的任务静态分配。其优点是保证了全局最优；缺点是问题规模较大时，计算时间长。整个编队的完全再分配此种方案是任务再分配针对每架无人机单独调整，优点是任务再分配快速；缺点是最优性难于保证。局部调整此种方案是上述两种方案的折中，它首先对无人机和任务进行分组，然后进行组内任务再分配。分组基础上的再分配8.348无人机集群的动态环境任务再分配3.任务动态再分配的流程任务分配完成后，当条件发生变化，一些任务需要变更时，将触发任务再分配，之后系统又回到稳定状态，等待整个系统任务完成或下一次再分配。整个再分配过程中系统状态发生变化，同时系统中各执行者的状态也将受到影响。任务重分配流程图8.349无人机集群的动态环境任务再分配4.任务动态再分配需要考虑的因素假设任务动态再分配只在现有无人机集群中进行，即不给现有无人机集群增加新的无人机。这时需要考虑的因素包括以下几点：编队中现有可执行任务的无人机的种类及其数量。

编队中现有可执行任务的无人机的当前位置和续航时间。

待执行的任务目标位置和时间窗口。8.350无人机集群的动态环境任务再分配5.任务改变时的任务动态再分配算法（1）首先确定参加新任务的无人机；（2）被确定参加新任务的无人机停止执行现行任务，原地等待；（3）选择任务动态再分配策略；（4）对所有参加新任务的无人机指派任务和规划航线；（5）如果规划的新航线满足执行新任务的要求，则将任务集发送给对应的无人机，并启动执行；（6）收到任务集后，参加新任务的无人机结束等待，并启动执行。8.351无人机集群的动态环境任务再分配6.无人机状态改变时的任务再分配算法①

安排该架无人机返航并着陆。②

确定该架无人机状态改变使该无人机不能继续执行的任务是哪一个任务。③

判断该编队小组中是否有同类无人机可以替代退出的无人机。若有，转④；

否则，转⑤。④

对该编队小组的无人机进行任务再分配。⑤

判断是否可能从编队中的其他小组抽调一架同类无人机替代退出的无人机。

若有，转下一步；若无，则不能继续按原计划执行该任务。⑥

涉及的两个编队小组进行任务再分配。8.352分布式无人机集群动态任务分配算法8.4分布式无人机集群动态任务分配算法分布式控制体系在分布式控制体系中，无人机集群内部或者无人机集群之间的每一架无人机都是具有独自决策能力的智能体，它们具有很强的协同能力和自治性。无人机之间以数据链技术为支撑，对无人机所处环境信息，任务目标集信息，无人机状态信息进行交互，综合考虑各种因素，提出具体的解决任务分配问题的方案和具体步骤。无人机个体在分布式控制体系下具有实时性较强、抗干扰能力强、计算量小、计算复杂度小等优点，且其主要适用于动态环境，中等至大规模系统中。8.454分布式无人机集群任务分配无人机的任务分配问题与市场机制中的资源分配有一定的相似性。市场中有许多客户，每个客户依据自己的投资能力和预期效益对市场中的项目进行投资，个别客户个体无法改变整个市场的走势，但是把所有的客户看作一个统一的大集合，就可以通过投资对整个市场的走势产生决定性的作用，即市场的发展或者市场的消退。典型的的算法是合同网算法和拍卖算法。8.455基于合同网协议的动态任务分配合同网算法（ContractNetProtocol，CNP）合同网协议(Contractnetprotocol,CNP)是分布式环境下广泛采用的较为成熟的协商机制。其主要思想是：当一个任务可以被执行时，这个任务就被公开招标，等待执行该任务的所有个体则参与投标，最后中标的个体，也就是最适合完成该任务的个体，获得完成这个任务的合同并开始执行。

8.456基于合同网协议的动态任务分配合同网一般有三大类任务执行角色：招标者、投标者、中标者。基于合同网协议的任务分配主要过程：

招标阶段：招标者发送任务信息给投标者，包括任务数量、任务完成期限等；

投标阶段：投标者对招标者发送的任务信息实时监测，并对感兴趣的任务进行投标；

中标阶段：招标者在一定的时间段内对所收集的应标进行评估，根据评估结果向其满意的投标者分配任务；签约阶段：招标者向中标者发送中标信息，中标者确认招标者提出的任务分配合同，形成承诺监督关系。合同网协议的原理8.457基于合同网协议的动态任务分配

8.4

58基于合同网协议的动态任务分配两种经典的应用在多无人机任务分配中的买卖合同：（1）基于买卖合同的任务分配8.4

59基于合同网协议的动态任务分配

8.460基于合同网协议的动态任务分配

8.461基于合同网协议的动态任务分配

8.462基于合同网协议的动态任务分配

8.463基于合同网协议的动态任务分配合同网协议应用无人机集群多任务动态分配中的具体方法（1）当无人机集群中的某架无人机者有任务需要时，则启动一个任务招标。（2）在启动招标前，该无人机首先生成一个带权重的损失向量，然后这个损失向量被广播给所有无人机作为参考，即向潜在投标无人机发布任务请求。（3）其他所有收到任务请求信息的潜在投标无人机检索自己的预定路线，也计算出一个自己的损失函数，作为“投标值”发还给招标者无人机。（4）招标者无人机设定一个时间期限，选出一个最优者作为中标者无人机，并通知其接受任务。如果在给定时间内最优者由于种种原因没有回应，则发给次优者，以此类推。8.464基于合同网协议的动态任务分配合同网协议应用无人机集群多任务动态分配中的具体方法（5）一旦中标的投标者无人机回应了招标者无人机，则该任务的执行权就由招标者交给了中标者无人机，即建立了相应的合同。按合同执行任务的中标者无人机若不能独立完成任务，就需扮演投标者角色，将任务继续分解，并按合同网方式进行分配。8.465基于拍卖算法的实时任务分配拍卖算法的本质是模拟实际的拍卖过程，其中参与拍卖的各个个体都是一个智能体。在拍卖开始前，参与拍卖的各个个体计算每一个任务的收益、消耗的能力和选择函数等。拍卖算法首先随机生成一个竞拍的先后次序，各个个体按照次序去完成自己拍卖得到的任务集，一轮拍卖完成后得到一个整体的任务分配方案。重复多轮拍卖过程，直到时间和资源超出限制，得到当前的最优解。拍卖算法原理8.466基于拍卖算法的实时任务分配拍卖算法首先要解决的是竞拍机制的制订为方便描述，假定无人机完成任务方案可以表示为Pj=(Pj1

，Pj2，···，Pji）为一个有序集，i表示有序集Pj

中元素的个数。竞拍中，主要考虑下面两个函数（1）预期效益函数：

其中，ρi,jk表示无人机Ui完成任务Pjk的概率；σjk表示任务的重要程度。8.467基于拍卖算法的实时任务分配

8.4

68基于拍卖算法的实时任务分配无人机集群分布协同拍卖目标任务分配的流程：（1）拍卖开始前，所有竞拍者构建拍卖任务列表；（2）拍卖主持者生成随机的本轮次竞拍次序；（3）拍卖过程中各竞拍者按照生成的竞拍次序出价，每个竞拍者记录拍卖完成后本轮次任务分配总代价和执行关系；（4）计算拍卖生成的方案目标函数，将最优方案替换为本轮结果方案；8.469基于拍卖算法的实时任务分配无人机集群分布协同拍卖目标任务分配的流程：（5）如果时间和资源约束允许，转到第（2）步，否则转第（6）步；（6）输出拍卖后最低总代价的任务方案和竞拍者与任务的执行关系。8.470基于拍卖算法的实时任务分配市场类算法的主要优点拍卖方法虽然不是确定