Autonomous Control of Unmanned Aerial Vehicle Swarms: Task Allocation Based on Coalition Formation Game
-
摘要: 针对复杂多约束条件下异构无人机集群系统的任务分配问题, 提出一种基于联盟形成博弈的分布式任务预分配和重分配方法. 考虑时效性、同时性等耦合约束条件, 引入准确的能耗模型建立任务分配模型, 利用联盟形成博弈将任务分配问题转化为联盟划分问题, 并设计一种无故障条件下的分布式任务预分配方法, 降低任务分配求解的复杂度, 同时提高最终解的平均质量; 进一步, 针对无人机故障问题, 准确分析健康无人机的运动模型, 合理划分重分配范围, 基于任务预分配结果设计重分配算法. 仿真结果表明了所提分布式任务预分配与重分配方法在不同场景下的实时性和有效性.Abstract: This paper presents a distributed task preallocation and reallocation method for heterogeneous UAV swarms system based on coalition formation game to solve the task allocation problem under complex and multi-constraint conditions. Considering multiple coupling constraints such as timeliness and synchronization, a task allocation model is established and an accurate energy consumption model is introduced to it. The task allocation problem is transformed into a coalition partitioning problem based on coalition formation game. Then a distributed task preallocation method under fault-free conditions with low complexity is designed, which can improve the average quality of the final solution. Furthermore, in response to the occurrence of UAV malfunctions, the motion model of healthy drones is accurately analyzed and the reallocation range is reasonably divided. Then a task reallocation algorithm is proposed based on the preallocation results. The simulation results prove the real-time performance and effectiveness of the proposed distributed task preallocation and reallocation method in different scenarios.
-
人工交通系统是利用人工社会的基本理论与方法, 通过抽取交通环境中单个个体或局部交通行为的基本属性或动态规律, 基于Agent建模技术, 通过交通系统个体或局部Agent之间相互作用, "涌现(Emergence)"出复杂的交通现象, 这是一个"自下而上"、基于"简单一致原则"人工"培育"出来的交通系统[1-3].人工交通系统可把"仿真"结果作为现实的一个替代版本, 而把实际系统也作为可能出现的现实中的一种, 与仿真结果等价[4-6].
霍兰指出: "涌现现象是以相互作用为中心的, 它比单个行为的简单累加要复杂得多"[7].对代理、环境及规则上描述的细微差别, 在涌现过程中, 就可能出现"差之毫厘, 谬以千里"的结果, 从而仿真结果失去了对现实的指导意义, 甚至给出完全错误的指导方案.正如社会学家Helmreich所批评的一样:人工社会的模型反映的是其创造者的潜意识中的文化假设和偏见[8].
如何避免这一问题?在人工交通的建模及平行系统的研究中, 需要引入严密的量化评估体系, 建立系统"可信"或"可用"的数学描述, 并从多维度、多粒度的数据层面进行量化评估, 从理论上保证人工交通系统与现实交通系统在统计特性上、在动态演化规律上、在行为特性上的一致性.本文针对人工交通系统, 基于人工交通系统基本体系结构, 将二型模糊集合方法引入人工交通系统可信度评估中, 建立了一种适用于人工交通系统的可信度评估理论体系与具体评估方法.并利用一个"人工公交交通系统"模型, 进行了可信度评估的数据验证.
本文结构安排如下.第1节介绍了可信度研究的意义, 对可信度研究方法和成果进行了综述, 并提出了本文的可信度评估框架.第2节为可信度评估使用的核心算法介绍.第3节仿真验证.最后给出结论.
1. 可信度研究综述及评估体系
可信度定义:对于一个事物或现象为真的相信程度.可信度的量化值一般在[0, 1]之间, 值越大, 表示该事物越"真"[9].评估复杂仿真系统可信度的过程称为复杂仿真系统的可信度评估.通过开展复杂仿真系统的可信度评估研究和应用, 可以提高综合仿真系统的仿真结果的正确性, 降低其应用的风险保证仿真系统的质量.可信度评估在交通仿真、网络管理、信息管理、远程通讯以及导弹系统等各个领域都有广泛的应用[10-13].
文献[12]针对微观交通仿真模型开发者和使用者的不同需求, 研究了交通仿真模型可信度评价内容及其与仿真模型校正、校核、验证和确认的关系; 分析了三种可用于微观交通仿真模型可信度评价的方法:层次分析法、相似度法以及模糊综合评判.文献[14]使用模糊三角函数与层次分析法及网络层次分析法综合评价列车控制仿真系统的可信度, 获取定量的可信度结果.文献[15]在对当前城市交通导航系统的分析中发现, 许多共享交互的弱点会损害系统的可信度.论文提出了改进的交互机制, 以提高导航系统的可信度.在比较用户的研究中评估了所提议的机制, 并给出了确认其可信度的积极影响的结果.
从应用上分类, 可信度评估方法主要有仿真结果评估与VV & A (Verification, validation and accreditation)两种模式[16-18].基于仿真结果验证的方法主要是应用定性或定量评估方法, 并结合统计学的相关知识, 通过仿真结果与实际或预想结果的比较, 得出仿真可信度评价[16], 是交通仿真系统中主要使用的可信度评估模式.人工交通概念提出以来, 关于其建模方法及应用的研究成果较多, 但可可信度评估的研究相对较少[19]. Li等[20]在前期研究中, 建立了基于二型模糊集合方法的人工交通系统可信度评估体系.
因为一般现代综合评估方法存在: 1)因评价专家主观上的随机性和不一致性导致问题描述的混乱; 2)隶属度函数及权重难以精确确定; 3)简单的评价结果无法精确地反映评价结果与评价对象内在因素的多维关系等问题[21-22].同时考虑到人工交通系统不依赖精确数学模型、不确定性因素多、输入输出数据随机性强等特点, 本文应用二型模糊集理论, 利用其较强的处理不确定性及随机性的能力来对人工交通系统的可信度做具体的评估研究.建立了以区间二型模糊集合理论为核心数据处理算法的评估方法, 如图 1所示.评估方法的核心由三部分构成:数据处理、区间二型模糊集、Jaccard算法.
图 1 基于二型模糊集合理论的人工交通系统评估过程Fig. 1 Artificial traffic system assessment process based on type-2 fuzzy set theory该方法应用可信度概念, 描述将人工交通系统视为交通系统的现实版本的真实程度, 通过评估人工交通系统和实际交通系统输出数据的统计一致性程度, 来评估人工交通系统的可信度.即在一致输入条件下, 输出的统计特性一致.具体思路描述如下:
1) 将来自于实际交通场景的大量数据进行前期处理, 考虑到交通系统的非严格重复的周期性、随机性和不确定性, 基于置信区间概念, 将其处理为区间化数据:同理, 将相应的人工交通系统的输出数据也做同样的处理.
2) 区间化数据表达符合对开放复杂系统的输出数据不确定性和波动性的描述, 在剔除了噪声数据的同时, 也完成了二型模糊集建模的输入数据准备.
3) 应用区间二型模糊集合算法, 将处理后的区间输入进行深度加工, 得到更准确刻画系统特性的两个交通系统(实际交通系统和人工交通系统)的数据集合.
4) 基于Jaccard算法对二型模糊集输出数据集合进行一致性比较, 通过一致性结果数据, 评价人工交通系统的可信度.
上述评价方法, 有效地实现了基于Agent建模的复杂系统评估问题.该方法以系统数据为驱动, 不依赖于数学模型, 同时通过数据的波动性描述系统的不确定性特征:应用了二型模糊集处理带有噪声及不确定性数据的优越性能, 保证二次数据的精准性.
2. 核心算法
2.1 区间二型模糊集合
Zadeh[23]在1975年提出了二型模糊集合的概念, 二型模糊集合是传统模糊集合(称为一型模糊集合)的拓展.二型模糊集合由于隶属度本身是不确定的, 可以对不确定的数据进行确定描述, 在处理带有噪声及不确定性数据方面具有优越的性能[24], 这使它用于处理不确定性强、随机性强的交通流数据成为可能. 2017年, 二型模糊集合理论得到了进一步的修正[25].
定义 1. 设${C}(I)$是由单位区间$I$的全体非空闭子集构成的一个集合.论域$X$上的一个二型模糊集合$\omega $定义为
$ \omega = \ \{ {{( {x, u, z} )} |}\forall x\in X, \forall u \in {L_x} \in {C}( {{2^I}}) , \nonumber\\ \ {z = \mu _\omega ^2( {x, u} ) \in I} \} $
(1) 其中, $x$为主变量, $u$为次变量, $z$为第3变量, ${L_x}$为主隶属度, 由一个多值映射定义而得, 表示为
$ \mu _\omega ^1:\Omega \to {C}\left( {{2^I}} \right)\\ $
(2) $ x\mapsto L_x $
(3) 即$\forall x\in X$, 存在${L_x} \in {C}({{2^I}}) $, 使得$\mu _\omega ^1 (x) = L_x$.
称$\mu _\omega ^1 (x)$为主隶属度函数, 设$\mu _\omega ^2 (x)$为次隶属度函数, 定义为
$ \mu _\omega ^2:\bigcup\limits_{x \in X } {x \times {L_x}} \to I\notag \\x\times u \mapsto z $
(4) 次隶属度函数可以看成是一个以$\bigcup_{x \in X } {x \times {L_x}}$为论域上的一型模糊集合的隶属函数, 该定义称为二型模糊集合的二段式定义.
定义 2. 二型模糊集合$\omega$的支集为在$X\times I$中使次隶属度大于0的全体元素构成的集合, 记为$Supp(\omega)$, 即
$ Supp(\omega)=\left\{( {u, x})|\mu _\omega ^2 (x, u) >0 \right\} $
(5) 若$\mu _\omega ^2$为一个连续函数, 则由连续函数的性质, 可记$CoS(\omega)$为支集$Supp(\omega)$的闭包(Closure of support), 表示为
$ CoS(\omega) = \overline{\left\{( {x, u})|\mu _\omega ^2 (x, u) >0 \right\}} $
(6) 如果对$\forall x \in X$, $\forall u \in L_x$, 都有$\mu^2_\omega(x, u)=1$, 则称$\omega$为一个区间二型模糊集合.
2.2 交通数据的区间化方法
城市交通环境因其开放性、不确定性和随机性较强, 导致交通数据具有不确定性和随机性特征, 但同时, 城市交通环境作为一个大惯性系统, 其数据的非严格重复性又使其具有较好的统计特征.
图 2以24小时交通流量数据为例, 刻画了多天交通流量的分布及区间化描述.在某一给定时刻, 区间的最大和最小值表明了该时刻交通流量可能的变化范围.
交通流量的区间化描述方式不仅能够给出交通流量丰富的分布信息, 并可以用构造内嵌一型模糊集合, 以作为二型模糊集的源数据.
本文引入置信区间的概念, 应用中心极限定理, 将交通流数据由点值数据转化为区间描述[26].
置信区间是指由样本统计量所构造的总体参数的估计区间:
设$\theta $是总体的一个参数, 该参数空间为$\Theta $, ${x_1}$, 是来自该总体的样本, $n$为样本量.对于给定的一个$\alpha$ $(0<\alpha<1)$, 若有两个统计量: ${\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{\theta } _L}={\mathord{\buildrel{\lower3pt\hbox{}} \over\theta } _L}({x_1}, {x_2}, \cdots, {x_n})$和, 对任意的$\theta\in\Theta$, 有${P_\theta }({{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{\theta } }_L}\le\theta\le {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{\theta } }_H})\ge 1 - \alpha $.称随机区间为$\theta $的置信水平为$1-\alpha $的置信区间.
构造未知参数$\theta $的置信区间最常用的方法是轴枢量法.考虑到对于非正态分布的随机序列总体, 一般难以求出其总体的轴枢量, 因此利用中心极限定理将其近似分布转化为正态分布, 从而求得参数的置信区间估计[27].
勒维-林德伯格定理如下:
设${x_1}, {x_2}, \cdots, {x_n}$为相互独立同分布的随机序列, 且$E\left({{x_i}} \right) = \mu $, $D\left({{x_i}} \right) = {\sigma ^2} > 0$, $i = 1, 2, 3, \cdots, $则服从正态分布, 即.
针对这样一个正态分布, 可按照式(7)构造轴枢量
$ G = G\left( {{x_1}, {x_2}, \cdots , {x_n}, \mu } \right) = \frac{{\bar x - \mu }}{{\frac{\sigma }{\sqrt n} }} \sim \rm N \left( {0, 1}\right) $
(7) 经过不等式变形, 方差${\sigma ^2}$已知条件下, 期望$\mu $的置信区间为
$ \left( {\bar x - {\mu _{\frac{\alpha }{2}}}\frac{\sigma }{{\sqrt n }}, \bar x + {u_{\frac{\alpha }{2}}}\frac{\sigma }{{\sqrt n }}} \right) $
(8) 这是一个以样本均值$\overline x $为中心, 半径为${\mu _{\frac{\alpha }{2}}}\frac{\sigma }{{\sqrt n }}$的对称区间.之所以取${\mu _{\frac{\alpha }{2}}}$, 是因为$\frac{\alpha }{2}$分位点很好地处理了置信区间区间可靠性和精度的关系.
2.3 基于Jaccard算法的集合相似性计算
Jaccard算法是由Jaccard在1908年提出的, 用于对两个集合的相似度进行比较[28].其中被广泛使用的参数为Jaccard相似系数(Jaccard similarity coefficient), 用于比较有限样本集之间的相似性与差异性, Jaccard相似系数越大, 样本相似度越高.
从20世纪初到现在, Jaccard算法已经在生物学、经济和社会研究领域中被广泛运用并取得了较好的效果. Bell等[29]在评估植物图像分割的子集匹配时采用了Jaccard算法, 对分割图像和地面实际图像这两个像素集合进行相似度的计算. Rinartha等[30]在文章搜索中运用Jaccard相似度对关键词的处理时间和搜索文章的结果精确性进行了比较分析.结果发现Jaccard相似性查询建议将产生更加准确的搜索结果.研究表明, Jaccard相似度的平均绝对误差(Mean absolute error, MAE)相较于皮尔逊相关系数法、对数似然值相似度和余弦相似度等误差较低, 且算法简单, 运算速度快.在通常情况下, Jaccard系数值越大, 样本相似度越高, 本文采用Wu等[31]提出的针对二型模糊集合Jaccard算法, 如式(9)所示.
$ s{m_J} \left( {\tilde A, \tilde B} \right) =\notag\\ {\frac{ \sum\limits_{i = 1}^N {\min ( {{{\bar \mu }_{\tilde A}}( {{x_i}} ), {{\bar \mu }_{\tilde B}}( {{x_i}} )} )}+ \sum\limits_{i = 1}^N {\min ( {{{\underline{\mu } }_{\tilde A}}( {{x_i}} ), {\underline{\mu } }_{\tilde B}( {{x_i}} )} )} }{ \sum\limits_{i = 1}^N {\max ( {{{\bar \mu }_{\tilde A}}( {{x_i}} ), {{\bar \mu }_{\tilde B}}( {{x_i}} )} )} + \sum\limits_{i = 1}^N {\max ( {{{\underline{\mu } }_{\tilde A}}( {{x_i}} ), {\underline{\mu } }_{\tilde B}( {{x_i}} )} )} }} $
(9) 3. 人工交通系统可信度评估实例验证
3.1 系统建模
本文选择北京海淀区某道路为典型建模场景进行可信度实验研究, 该路段双向2车道, 包含三个公交车站、两个定时控制的信号灯路口和3条公交线路, 全长约为1.4公里.
研究者以2015年3月至4月中旬的每周二、周三、周四共计六周18天, 在每一天的上午8点到下午8点进行数据调研, 以调研数据作为人工交通系统的数据来源.包括双方向车流量、车辆类型、多点车辆速度等.因为在该场景中, 有比较繁忙的公交线路, 公交线路的参与者又受到周边环境的影响, 具有复杂系统典型性数据特征.因此本文特别对参与公共交通运输的数据:包括上下车乘客数、公交车到、发站时间等也进行了数据调研, 完成了该典型交通场景的人工交通系统建模的数据准备.并选取随机性较强、对公共交通调度规划具有重要影响的乘客上车人数作为人工交通系统可信度评估参数, 进行可信度验证.该路段上三个公交车站在调研时段的乘客等车调研数据如表 1所示(实际系统).限于篇幅, 关于人工交通建模的研究内容将在另文进行阐述.
表 1 三个公交车站上车人数的实际调研数据和人工交通系统运行数据Table 1 The actual data and simulation data of people get on the three bus stops时段 实际系统第1站 仿真系统第1站 实际系统第2站 仿真系统第2站 仿真系统第3站 实际系统第3站 3:00 $\sim$ 3:05 9 13 8 15 4 5 3:06 $\sim$ 3:10 10 15 10 13 0 1 3:11 $\sim$ 3:15 14 9 5 8 3 3 3:16 $\sim$ 3:20 0 25 6 9 1 2 3:21 $\sim$ 3:25 29 20 16 0 6 3 3:26 $\sim$ 3:30 25 3 11 19 3 5 3:31 $\sim$ 3:35 15 17 5 6 4 8 3:36 $\sim$ 3:40 10 0 7 6 3 2 3:41 $\sim$ 3:45 15 9 8 0 5 1 3:46 $\sim$ 3:50 19 15 6 11 1 0 3:51 $\sim$ 3:55 9 21 10 9 4 4 3:56 $\sim$ 4:00 19 4 16 18 0 2 搭建的人工交通系统运行界面如图 3所示.根据实际调研数据, 在人工交通系统中设置该路段初始计划乘车人数为50人, 系统将这50个人随机分布在路段的不同地方, 然后各自判断自己离哪个公交车站更近, 从而选择自己的前进方向.多次运行人工交通系统, 得到三个车站等车乘客人数的仿真数据, 其均值也列入表 1 (仿真系统).
3.2 数据处理
为了对数据进行统一处理, 把每个参数的输入数据除以一个比例因子进行"归十化"到区间$[0, 1]$.对"归十化"得到的数据进行一型模糊化处理, 由式(8)将交通流数据由点数据转化为区间数据, 表 2展示了区间化数据结果.基于此数据基础, 即可构造内嵌的一型隶属度模糊集.设每一个区间左端点为$b$, 右端点为$c$, 左右端点的中间值为$a$, 本仿真中, 用区间数据构造三角型隶属度函数, 则
表 2 三个公交车站上车人数模糊化以后的实际数据和仿真数据Table 2 The actual data and simulation data after fuzzified of people get on the three bus stops时段 实际系统第1站 仿真系统第1站 实际系统第2站 仿真系统第2站 仿真系统第3站 实际系统第3站 3:00 $\sim$ 3:05 2 4 3 5 3 5 6 8 3 5 4 6 3:06 $\sim$ 3:10 2 4 4 6 4 6 6 8 0 1 0 2 3:11 $\sim$ 3:15 3 5 2 4 1 3 3 5 2 4 2 4 3:16 $\sim$ 3:20 0 1 7 9 2 4 3 5 0 2 1 3 3:21 $\sim$ 3:25 6 8 6 8 7 9 0 1 5 7 2 4 3:26 $\sim$ 3:30 6 8 0 2 4 6 5 7 2 4 4 6 3:31 $\sim$ 3:35 4 6 5 7 1 3 2 4 3 5 7 9 3:36 $\sim$ 3:40 2 4 0 1 3 5 2 4 2 4 1 3 3:41 $\sim$ 3:45 4 6 2 4 3 5 0 1 4 6 0 2 3:46 $\sim$ 3:50 5 7 4 6 2 4 4 6 0 2 0 1 3:51 $\sim$ 3:55 2 4 6 8 4 6 4 6 3 5 3 5 3:56 $\sim$ 4:00 5 7 0 2 7 9 8 9 0 1 1 3 $ {\mu _F}\left( x \right) = \begin{cases} \frac{{x - b}}{{a - b}}, &b \leq x \leq a \\ \frac{{c - x}}{{c - a}}, &a < x \leq c \\ 0, &x < b ~\mbox{或}~ x > c \end{cases} $
(10) 因此, 每一个区间都对应着一个一型模糊集.运用式(10)进行集合并运算:
$ {\mu _C}\left( x \right) = \max \left( {{\mu _A}\left( x \right), {\mu _B}\left( x \right)} \right) = {\mu _A}\left( x \right) \cup {\mu _B}\left( x \right) $
(11) 其中, ${\mu _A}\left(x \right)$和${\mu _B}\left(x \right)$为一型模糊集合$A$和$B$的隶属度函数, ${\mu _C}\left(x \right)$为集合并运算得到的新集合${ C}$的隶属度函数, 即二型模糊集合$CoS$.本文将某5分钟的前两个时段和本时段及后一个时段共四个时段进行了并运算, 得$CoS$如图 4所示.
对实际交通系统和人工交通系统, 研究时间轴为每一天的上午8点到下午8点, 共12个小时.因为按照5分钟进行数据统计, 所以得到144个$CoS$, 限于篇幅, 仅列出一个5分钟数据采样时段, 两个系统的二型模糊集合图例, 结果如图 5所示.
图 5 三个候车站实际候车乘客数据和对应的人工交通系统候车乘客人数数据的二型模糊集合Fig. 5 Two-type fuzzy set of three stations actual data and corresponding simulation data经过解模糊化处理, 可以得到两个系统分别由144个重心组成的上限重心和下限重心值构造出来的144个集合, 根据式(9)可计算出两个系统三个站点各144个集合的相似度值, 记为$Jsm(x)$ $(x=1$, $2$, $3)$.
3.3 模型评估
由式(9)可计算得到人工公共交通系统可信度评估结果:
第1站的评估结果为$Jsm (1) = 1$
第2站的评估结果为$Jsm (2) = 1$
第3站的评估结果为$Jsm (3) = 0.6331$
整个系统的评估结果为
$ Jsm = \frac{1}{3}\sum\limits_{x = 1}^3 {Jsm(x) =0.88} $
针对这一结果, 本文使用克朗巴哈系数(Cronbach$'$s alpha)进行评价, 通常Cronbach系数的值在0和1之间.如果系数不超过0.6, 一般认为内部一致可信度不足:达到0.7 $\sim$ 0.8时表示量表具有相当的可信度, 达到0.8 $\sim$ 0.9时说明量表可信度非常好, 如表 3所示[32].本文所建立的人工交通系统, 以车站候车人数为计算指标, 得到的可信度为0.88, 表明人工交通系统很可信.
表 3 可信度值与Cronbach系数的关系Table 3 The relationship between the value of credibility and Cronbach coefficient系统可信程度 Cronbach系数(可信度） 不可信 $ < 0.3$ 勉强可信 $0.3 \leq\alpha < 0.4$ 可信 $0.4 \leq\alpha < 0.5$ 很可信(最常见) $0.5 \leq\alpha < 0.7$ 很可信(次常见) $0.7 \leq\alpha < 0.9$ 十分可信 $0.9 \leq\alpha$ 4. 结束语
本文进行了人工交通系统模型可信度评估的研究:针对交通数据的不确定性和随机性特性, 在可可信度评估中引入区间二型模糊集理论, 利用基于统计的数据一致性分析思想, 构建了基于区间二型模糊集方法的人工系统可信度评估方法.本文核心思想是对实际系统和人工系统的输出数据进行了二重处理, 一重处理通过置信区间获取数据的统计特征, 同时区间化得到二重处理的输入数据:二重处理通过二型模糊集方法处理不确定性数据、随机性数据以及噪声数据的能力, 获得更细致刻画系统特性的输出数据集, 通过两个数据集的相似性程度评估系统的可信度.
本文使用人工交通系统中候车乘客人数这一类易受周边环境影响的数据进行了计算验证, 结果表明了基于区间二型模糊集合的可信度评估方法的有效性和合理性.
本文的研究过程中还存在着如下一些问题: 1)在建模过程中没有完全提取交通系统的所有参数及特性; 2)在案例研究中, 也只针对公交运行过程中乘客上车人数数据进行评估, 相对单一.后续的研究工作要继续完善人工交通系统模型, 获得更多类型的数据, 通过更多案例研究实现系统的可信度评估.同时, 也将研究如何通过可信度评估过程及结果对人工交通系统建模过程提出优化建议.
-
图 5 任务分配问题基本元素博弈流程图
Fig. 5 Flowchart of game of basic element in task allocation problem
图 7 联盟总收益统计值箱型图
Fig. 7 Box plots of statistical results of total revenue of coalitions
图 8 n = 12, m = 3时的算法典型收敛过程图
Fig. 8 Typical convergence process diagram of algorithm under n = 12, m = 3
图 9 健康情况下的预分配最优结果图
Fig. 9 Graph of optimal preallocation result under healthy conditions
图 10 不同无人机数量下算法收益与最大总收益之比
Fig. 10 The ratio of revenues to maximum total revenues under different numbers of UAVs
图 11 不同无人机数量下算法运行结果标准差
Fig. 11 Standard deviation of running results under different numbers of UAVs
图 12 不同无人机数量下算法平均运行时间及与枚举法运行时间之比
Fig. 12 The average running time and its ratio to the running time of the enumeration method
图 13 不同任务数量下算法收益与最大总收益之比
Fig. 13 The ratio of revenues to maximum total revenues under different numbers of tasks
图 14 $u_{12}$在$t=0\;{\mathrm{s}}$时发生故障后任务重分配示意图
Fig. 14 Graph of task reallocation after $u_{12}$ occurs fault at $t=0\;{\mathrm{s}}$
图 15 $u_{9}$在$t=8\;{\mathrm{s}}$时发生故障后任务重分配示意图
Fig. 15 Graph of task reallocation after $u_{9}$ occurs fault at $t=8\;{\mathrm{s}}$
图 16 $u_{7}$在$t=15\;{\mathrm{s}}$时发生故障后任务重分配示意图
Fig. 16 Graph of task reallocation after $u_{7}$ occurs fault at $t=15\;{\mathrm{s}}$
图 17 不同场景下任务重分配总收益图
Fig. 17 Total revenues of task reallocation in different scenarios
图 18 不同场景下任务重分配算法运行时间示意图
Fig. 18 Diagram of task reallocation running time in different scenarios
表 1 仿真参数符号和数值
Table 1 The notations and values of simulation parameters
符号 数值 符号 数值 $ P_{0} $ 158.76 W W 20 N $ P_{i} $ 88.63 W m 2.04 kg $ U_{tip} $ $ 120 \;{\mathrm{m/s}} $ $ S_{FP} $ $ 0.015\;1\;{\mathrm{m}}^{2} $ $ v_{0} $ 4.03 m/s $ f_{c} $ 2.4 GHz $ d_{0} $ 0.6 c $ 3\times 10^{8}\;{\mathrm{m/s}} $ $ \rho $ $ 1.225\;{\mathrm{kg/m}}^{3} $ $ \sigma^{2} $ −174 dBm/Hz s 0.05 $ \eta _{1} $ 3 dB A $ 0.503\;{\mathrm{m}}^{2} $ $ \eta _{2} $ 23 dB B 1 MHz 
下载: 导出CSV
表 2 任务仿真参数
Table 2 The simulation parameters of tasks
编号 $ T_{1} $ $ T_{2} $ $ T_{3} $ 位置 (798.4,848.3) (442.5,829.7) (585.9,501.6) 消耗型资源需求数量 (22,11,14,22) (19,13,17,27) (26,19,11,18) 数据量(Mbit) (30,90,100) (150,100,40) (60,100,50) 时间窗口 (24,55) (24,55) (24,55) 折扣系数 0.1 0.1 0.1 任务持续时间$ t_{T_{j}}^{con} $ 1.38 s 1.52 s 1.48 s 任务发射功率$ p_{T_{j}} $ 1 W 1 W 1 W
下载: 导出CSV
表 3 $m=3,\;n=12$时的任务预分配方案
Table 3 The optimal task preallocation solution under $m=3,\;n=12$
无人机 任务 无人机 任务 无人机 任务 $ u_{1} $ $ T_{0} $ $ u_{5} $ $ T_{1} $ $ u_{9} $ $ T_{3} $ $ u_{2} $ $ T_{0} $ $ u_{6} $ $ T_{2} $ $ u_{10} $ $ T_{3} $ $ u_{3} $ $ T_{1} $ $ u_{7} $ $ T_{2} $ $ u_{11} $ $ T_{1} $ $ u_{4} $ $ T_{2} $ $ u_{8} $ $ T_{0} $ $ u_{12} $ $ T_{3} $
下载: 导出CSV
表 4 $u_{12}$在$t=0\;{\mathrm{s}}$时发生故障后任务重分配方案
Table 4 The task reallocation solution after $u_{12}$ occurs fault at $t=0\;{\mathrm{s}}$
无人机 任务 无人机 任务 无人机 任务 $ u_{1} $ $ T_{0} $ $ u_{5} $ $ T_{1} $ $ u_{9} $ $ T_{3} $ $ u_{2} $ $ T_{3} $ $ u_{6} $ $ T_{2} $ $ u_{10} $ $ T_{3} $ $ u_{3} $ $ T_{1} $ $ u_{7} $ $ T_{2} $ $ u_{11} $ $ T_{1} $ $ u_{4} $ $ T_{2} $ $ u_{8} $ $ T_{0} $ $ u_{12} $ 故障, 退出
下载: 导出CSV
表 5 $u_{9}$在$t=8\;{\mathrm{s}}$时发生故障后任务重分配方案
Table 5 The task reallocation solution after $u_{9}$ occurs fault at $t=8\;{\mathrm{s}}$
无人机 任务 无人机 任务 无人机 任务 $ u_{1} $ $ T_{0} $ $ u_{5} $ $ T_{1} $ $ u_{9} $ 故障, 退出 $ u_{2} $ $ T_{0} $ $ u_{6} $ $ T_{3} $ $ u_{10} $ $ T_{3} $ $ u_{3} $ $ T_{1} $ $ u_{7} $ $ T_{2} $ $ u_{11} $ $ T_{1} $ $ u_{4} $ $ T_{2} $ $ u_{8} $ $ T_{0} $ $ u_{12} $ $ T_{3} $
下载: 导出CSV
表 6 $u_{7}$在$t=15\;{\mathrm{s}}$时发生故障后任务重分配方案
Table 6 The task reallocation solution after $u_{7}$ occurs fault at $t=15\;{\mathrm{s}}$
无人机 任务 无人机 任务 无人机 任务 $ u_{1} $ $ T_{0} $ $ u_{5} $ $ T_{1} $ $ u_{9} $ $ T_{3} $ $ u_{2} $ $ T_{0} $ $ u_{6} $ $ T_{2} $ $ u_{10} $ $ T_{3} $ $ u_{3} $ $ T_{1} $ $ u_{7} $ 故障, 退出 $ u_{11} $ $ T_{1} $ $ u_{4} $ $ T_{2} $ $ u_{8} $ $ T_{0} $ $ u_{12} $ $ T_{3} $
下载: 导出CSV
-
[1] Hu Z J, Gao X G, Wan K F, Wang Q L, Zhai Y W. Asynchronous curriculum experience replay: A deep reinforcement learning approach for UAV autonomous motion control in unknown dynamic environments. IEEE Transactions on Vehicular Technology, 2023, 72(11): 13985−14001 [2] Liu K, Zheng J. UAV trajectory planning with interference awareness in UAV-enabled time-constrained data collection systems. IEEE Transactions on Vehicular Technology, 2024, 73(2): 2799−2815 doi: 10.1109/TVT.2023.3320676 [3] Zeng Y, Xu X L, Jin S, Zhang R. Simultaneous navigation and radio mapping for cellular-connected UAV with deep reinforcement learning. IEEE Transactions on Wireless Communications, 2021, 20(7): 4205−4220 doi: 10.1109/TWC.2021.3056573 [4] He W J, Yao H P, Mai T L, Wang F, Guizani M. Three-stage stackelberg game enabled clustered federated learning in heterogeneous UAV swarms. IEEE Transactions on Vehicular Technology, 2023, 72(7): 9366−9380 doi: 10.1109/TVT.2023.3246636 [5] 武文亮, 周兴社, 沈博, 赵月. 集群机器人系统特性评价研究综述. 自动化学报, 2022, 48(5): 1153−1172Wu Wen-Liang, Zhou Xing-She, Shen Bo, Zhao Yue. A review of swarm robotic systems property evalu-ation research. Acta Automatica Sinica, 2022, 48(5): 1153−1172 [6] Zhang J, Cui Y N, Ren J. Dynamic mission planning algorithm for UAV formation in battlefield environment. IEEE Transactions on Aerospace and Electronic Systems, 2023, 59(4): 3750−3765 doi: 10.1109/TAES.2022.3231244 [7] 鞠锴, 冒泽慧, 姜斌, 马亚杰. 基于势博弈的异构多智能体系统任务分配和重分配. 自动化学报, 2022, 48(10): 2416−2428Ju Kai, Mao Ze-Hui, Jiang Bin, Ma Ya-Jie. Task allocation and reallocation for heterogeneous multiagent systems based on potential game. Acta Automatica Sinica, 2022, 48(10): 2416−2428 [8] 王峰, 黄子路, 韩孟臣, 邢立宁, 王凌. 基于KnCMPSO算法的异构无人机协同多任务分配. 自动化学报, 2023, 49(02): 399−414Wang Feng, Huang Zi-Lu, Han Meng-Chen, Xing Li-Ning, Wang Ling. A knee point based coevolution multi-objective particle swarm optimization algorithm for heterogeneous UAV cooperative multi-task allocation. Acta Automatica Sinica, 2023, 49(02): 399−414 [9] Xiong F, Zheng H, Ruan L, Wang H, Tang L J, Dong X, et al. Energy-saving data aggregation for multi-UAV system. IEEE Transactions on Vehicular Technology, 2020, 69(8): 9002−9016 doi: 10.1109/TVT.2020.2999374 [10] 杜永浩, 邢立宁, 蔡昭权. 无人飞行器集群智能调度技术综述. 自动化学报, 2020, 46(2): 222−241Du Yong-Hao, Xing Li-Ning, Cai Zhao-Quan. Survey on intelligent scheduling technologies for unmannedflying craft clusters. Acta Automatica Sinica, 2020, 46(2): 222−241 [11] Chen Z, Nian X H, Meng Q. Distributed optimization of multi-integrator agent systems with mixed neighbor interactions. Automatica, 2023, 157(3): 111245 [12] Zhang Z S, Liu H, Wu G H. A dynamic task scheduling method for multiple UAVs based on contract net protocol. Sensors, 2022, 22(12): 4486 doi: 10.3390/s22124486 [13] Garcia A, Hong M Y. Efficient rate allocation in wireless networks under incomplete information. IEEE Transactions on Automatic Control, 2016, 61(5): 1397−1402 doi: 10.1109/TAC.2015.2466836 [14] 吕晔, 周锐, 李兴, 刘志恒, 邸斌. 基于多轮次分布式拍卖的异构多任务分配算法. 北京航空航天大学学报, 2023, DOI: 10.13700/1001-5965.2023.0156Lyu Ye, Zhou Rui, Li Xing, Liu Zhi-Heng, Di Bin. Multi-task assignment algorithm based on multi-round distributed auction. Journal of Beijing University of Aeronautics and Astronautics, 2023, DOI: 10.13700/1001-5965.2023.0156 [15] Liu D, Dou L Q, Zhang R L, Zhang X Y, Zong Q. Multi-agent reinforcement learning-based coordinated dynamic task allocation for heterogenous UAVs. IEEE Transactions on Vehicular Technology, 2023, 72(4): 4372−4383 doi: 10.1109/TVT.2022.3228198 [16] Yuan R P, Dou J T, Li J T, Wang W, Jiang Y F. Multi-robot task allocation in e-commerce RMFS based on deep reinforcement learning. Mathematical Biosciences and Engineering, 2023, 20(2): 1903−1918 [17] Xu Y H, Jiang B, Yang H. Two-level game-based distributed optimal fault-tolerant control for nonlinear interconnected systems. IEEE Transactions on Neural Networks and Learning Systems, 2020, 31(11): 4892−4906 doi: 10.1109/TNNLS.2019.2958948 [18] Jie Y M, Guo C, Choo K-K R, Liu C Z, Li M C. Game-Theoretic Resource Allocation for Fog-Based Industrial Internet of Things Environment. IEEE Internet of Things Journal, 2020, 7(4): 3041−3052 doi: 10.1109/JIOT.2020.2964590 [19] Jang I, Shin H S, Tsourdos A. Anonymous hedonic game for task allocation in a large-scale multiple agent system. IEEE Transactions on Robotics, 2018, 34(6): 1534−1548 doi: 10.1109/TRO.2018.2858292 [20] Wang L X, Qiu T H, Pu Z Q, Yi J Q, Zhu J Y, Yuan W M. Hedonic coalition formation for distributed task allocation in heterogeneous multi-agent system. International Journal of Control Automation and Systems, 2024, 22(4): 1212−1224 doi: 10.1007/s12555-022-1182-5 [21] Chen J X, Wu Q H, Xu Y H, Qi N, Guan X, Zhang Y L, et al. Joint task assignment and spectrum allocation in heterogeneous UAV communication networks: a coalition formation game-theoretic approach. IEEE Transactions on Wireless Communications, 2021, 20(1): 440−452 doi: 10.1109/TWC.2020.3025316 [22] Zhang T X, Wang Y H, Ma Z J, Kong L J. Task assignment in UAV-enabled front jammer swarm: a coalition formation game approach. IEEE Transactions on Aerospace and Electronic Systems, 2023, 59(6): 9562−9575 doi: 10.1109/TAES.2023.3323441 [23] Qi N, Huang Z Q, Zhou F H, Shi Q J, Wu Q H, Xiao M. A task-driven sequential overlapping coalition formation game for resource allocation in heterogeneous UAV networks. IEEE Transactions on Mobile Computing, 2023, 22(8): 4439−4455 doi: 10.1109/TMC.2022.3165965 [24] Huo X, Zhang H, Huang C, Wang Z P, Yan H C. Task allocation with minimum requirements for multiple mobile robot systems: a game-theoretical approach. IEEE Transactions on Network Science and Engineering, 2024, 11(1): 1202−1213 doi: 10.1109/TNSE.2023.3321605 [25] Tang J, Chen X, Zhu X M, Zhu F. Dynamic reallocation model of multiple unmanned aerial vehicle tasks in emergent adjustment scenarios. IEEE Transactions on Aerospace and Electronic Systems, 2023, 59(2): 1139−1155 [26] 周文惠, 齐瑞云, 姜斌. 面向突发故障的分布式多无人机任务重规划方法. 控制与决策, 2023, 38(05): 1373−1385Zhou Wen-Hui, Qi Rui-Yun, Jiang Bin. Mission replanning method of distributed multiple unmanned aerial vehicles for pop-up faults. Control and Decision, 2023, 38(05): 1373−1385 [27] Wang G, Lv X, Cui L, Yan X. The methods of task pre-allocation and reallocation for multi-UAV cooperative reconnaissance mission. IET Collaborative Intelligent Manufacturing, 2023, 5(4): e12090 doi: 10.1049/cim2.12090 [28] Zeng Y, Xu J, Zhang R. Energy minimization for wireless communication with rotary-wing UAV. IEEE Transactions on Wireless Communications, 2019, 18(4): 2329−2345 doi: 10.1109/TWC.2019.2902559 [29] Yang Z H, Xu W, Shikh-Bahaei M. Energy efficient UAV communication with energy harvesting. IEEE Transactions on Vehicular Technology, 2020, 69(2): 1913−1927 doi: 10.1109/TVT.2019.2961993 [30] Mozaffari M, Saad W, Bennis M, Debbah M. Mobile unmanned aerial vehicles(UAVs) for energy-efficient internet of things communications. IEEE Transactions on Wireless Communications, 2017, 16(11): 7574−7589 doi: 10.1109/TWC.2017.2751045 [31] Zeng Y, Zhang R, Lim T J. Throughput maximization for UAV-enabled mobile relaying systems. IEEE Transactions on Communications, 2016, 64(12): 4983−4996 doi: 10.1109/TCOMM.2016.2611512 [32] Huang S J, Lei J L, Hong Y G. A linearly convergent distributed Nash equilibrium seeking algorithm for aggregative games. IEEE Transactions on Automatic Control, 2023, 68(3): 1753−1759 doi: 10.1109/TAC.2022.3154356 [33] Liu J, Ho D W C, Li L L. A generic algorithm framework for distributed optimization over the time-varying network with communication delays. IEEE Transactions on Automatic Control, 2024, 69(1): 371−378 doi: 10.1109/TAC.2023.3264784 期刊类型引用(0)
其他类型引用(3)
-
下载:
计量
- 文章访问数: 380
- HTML全文浏览量: 178
- 被引次数: 3
