一种基于联盟形成博弈的异构无人机群任务分配方法与流程

1.本发明涉及一种无人机群任务分配方法，特别是一种基于联盟形成博弈的异构无人机群任务分配方法。


背景技术：

2.无人机以其高动态性、动态部署等优点已广泛应用于各个领域中。随着无人机技术、集群控制和人工智能的快速发展，异构无人机群协同任务执行可有效解决单无人机任务执行效率低、鲁棒性差等问题，例如异构无人机群可执行多目标监测任务与评估任务。
3.目前，无人机群任务分配基本可以分为集中式和分布式。集中式方法可以很好解决多约束下的无人机群任务分配问题，其优点在于可给出该问题下的理论最优解。但是，集中式方法计算复杂度高，不适用与大规模无人机群任务分配问题；此外，集中式方法需要全局信息，在无法保证无人机间信息交互的高动态复杂环境很难应用。分布式方法主要包括凸优化中的部分算法以及多智能体强化学习算法，凸优化算法往往受到问题结构特征的限制，而多智能体强化学习算法的收敛性、训练时间与存储约束难以保证。因此，异构无人机群任务分配方法是一项极具挑战性的热点问题。


技术实现要素：

4.发明目的：本发明所要解决的技术问题是针对现有技术的不足，提供特别是一种基于联盟形成博弈的异构无人机群任务分配方法。
5.为了解决上述技术问题，本发明公开了特别是一种基于联盟形成博弈的异构无人机群任务分配方法，包括如下步骤：
6.步骤1：针对无人机的任务类型，分别定义无人机群协同任务执行效能；
7.所述的无人机的任务类型，包括协同监测与协同评估两类任务。
8.所述的分别定义无人机群协同任务执行效能，具体包括：
9.步骤1-1，当无人机群执行协同监测任务类型时，计算无人机群的任务执行效能pr(sm)，具体方法如下：
10.当无人机群sm执行协同任务m，且该任务为协同监测任务类型时，无人机群的任务执行效能pr(sm)定义为：
[0011][0012]
其中，是无人机n对监测任务m的完成概率，n∈sm表示无人机n属于无人机群sm，vm是协同任务m的价值系数，rm是协同任务m的威胁系数。
[0013]
步骤1-2，当无人机群执行协同评估任务类型时，计算无人机群的任务执行效能pc(sm)，具体方法如下：
[0014]
当无人机群sm执行协同任务m，且该任务为协同评估任务类型时，无人机群的任务
执行效能pc(sm)定义为：
[0015][0016]
其中，是无人机n对评估任务m的完成概率。
[0017]
步骤2：将无人机群协同任务执行问题建模为联盟形成博弈模型，其中博弈参与者为机群内各无人机；
[0018]
所述的将无人机群协同任务执行问题建模为联盟形成博弈模型，该博弈模型如下：
[0019][0020]
其中，表示执行任务的无人机群中n个无人机序号，表示执行任务的无人机群中n个无人机序号，表示无人机所需执行的m个任务的集合，为n个无人机的动作集合，其中an为无人机n的动作选择；为n个无人机的效用函数集合，其中un为无人机n的效用函数，为联盟分区，即无人机群形成的联盟状态。
[0021]
所述的无人机效用函数如下：
[0022]
利用平均分配准则，定义无人机n的效用函数un为：
[0023][0024]
其中，|sm|为执行任务m的无人机数目。
[0025]
步骤3：利用基于部分合作的联盟形成算法进行求解，使得各无人机的任务执行效能最大化，得到各无人机的任务选择结果，具体步骤如下：
[0026]
步骤3-1、初始化：各无人机随机选择一个任务，构成初始联盟分区
[0027]
步骤3-2、随机选择一个无人机n，其他无人机保持任务选择不变，计算无人机n当前任务执行效能un，具体方法如下：
[0028][0029]
其中，uj为无人机j的效用函数，为无人机n加入后的联盟，为无人机n未加入前的联盟。其中符号“\”表示将集合元素从该集合中剔除。
[0030]
步骤3-3、无人机n随机选择不同于任务an的任务根据步骤3-2计算改变任务选择后无人机n任务执行效能u
′n；
[0031]
步骤3-4、若un《u
′n，则无人机n将其任务选择从任务an改变至a
′n；若un≥u
′n，则无人机n保持其任务选择an不变；
[0032]
步骤3-5、当收敛到稳定联盟分区时，输出当前各无人机的任务选择与任务执行效
能；否则重复执行步骤3-2，直到收敛到稳定联盟分区。
[0033]
所述的收敛到稳定联盟分区，即所有无人机的任务执行效能总和在迭代中保持不变。
[0034]
步骤4：根据上述任务选择结果，分配无人机群任务，完成基于联盟形成博弈的异构无人机群任务分配。
[0035]
有益效果：
[0036]
本发明通过对联盟博弈的运用，使得各无人机具备自主决策能力，更适用于大规模无人机群任务分配问题；同时，无需全局信息交互，可有效降低计算复杂度。与其他分布式优化方法相比，基于博弈的优化方法时效性高、信息交互少，可有效提高无人机群自主性，发挥机群任务执行效能。
附图说明
[0037]
下面结合附图和具体实施方式对本发明做更进一步的具体说明，本发明的上述和/或其他方面的优点将会变得更加清楚。
[0038]
图1是本发明的任务分配方法整体结构示意图。
[0039]
图2为本发明所提出的基于部分合作的联盟形成算法流程图。
[0040]
图3为本发明所提出的基于部分合作的联盟形成算法收敛仿真结果图。
具体实施方式
[0041]
本发明提供一种基于联盟形成博弈的异构无人机群任务分配方法，从而使异构无人机群通过局部信息交互进行异构任务协同，发挥集群作战效能。
[0042]
技术方案：
[0043]
一种基于联盟形成博弈的异构无人机群任务分配方法，包括以下步骤：
[0044]
步骤1：针对协同监测与协同评估两类任务，分别定义无人机群协同任务执行效能。
[0045]
步骤2：将无人机群协同任务执行问题建模为联盟形成博弈模型，其中博弈参与者为机群内各无人机。
[0046]
步骤3：利用基于部分合作的联盟形成算法进行求解，使得各无人机的任务执行效能最大化。
[0047]
所述步骤1中，当无人机群sm执行协同监测任务m时，其任务执行效能pr(sm)定义为：
[0048][0049]
其中，是无人机n对任务m的监测任务完成概率，n∈sm表示无人机n属于机群sm，vm是任务m的价值系数，rm任务m的威胁系数。同理，当无人机群sm执行协同评估任务m时，其任务执行效能pc(sm)定义为：
[0050][0051]
其中，是无人机n对任务m的评估任务完成概率。
[0052]
所述步骤2中，将无人机群协同任务执行问题建模为联盟形成博弈模型，该博弈模型定义为：
[0053][0054]
其中，表示执行任务的无人机群中n个无人机序号，表示执行任务的无人机群中n个无人机序号，表示无人机所需执行的m个任务的集合，为动作集合，其中an为无人机n的任务选择；为效用函数，其中un为无人机n的效用函数，为联盟分区，即无人机群形成的联盟状态。利用平均分配准则，定义无人机n的效用函数为：
[0055][0056]
其中，|sm|为执行任务m的无人机数目。
[0057]
所述步骤3中，提出一种基于部分合作的联盟形成算法，使得各无人机的任务执行效能最大化，具体算法如下：
[0058]
步骤3-1、初始化：各无人机随机选择一个任务，构成初始联盟分区
[0059]
步骤3-2、随机选择一个无人机n，其他无人机保持任务选择不变，根据如下公式计算无人机n当前任务执行效能un：
[0060][0061]
其中，uj为无人机j的效用函数，为无人机n加入后的联盟，为无人机n未加入前的联盟。其中符号“\”表示将集合元素从该集合中剔除。
[0062]
步骤3-3、无人机n随机选择不同于an的任务根据上述公式计算改变任务选择后无人机n任务执行效能u
′n。
[0063]
步骤3-4、若un《u
′n，则无人机n将其任务选择从an改变至a
′n；若un≥u
′n，则无人机n保持其任务选择an不变。
[0064]
步骤3-5、当收敛到稳定联盟分区时，输出当前各无人机的任务选择与任务执行效能；否则重复执行步骤3-2，直到收敛到稳定联盟分区。
[0065]
其中，收敛到稳定联盟分区表示当前没有无人机愿意改变自身的任务选择，当前联盟结构固定。其判断标准为：所有无人机的任务执行效能总和在多次迭代中保持不变。
[0066]
本发明的原理是：
[0067]
本发明综合考虑任务价值与任务威胁系数，定义了面向不同任务的任务执行效能。采用博弈论的思想，将机群内各无人机作为博弈参与者，用联盟形成博弈解决了无人机群协同任务执行问题，并且提出了一种基于部分合作的联盟形成算法对该博弈模型进行求解，从而实现各无人机的任务执行效能的最大化。
[0068]
实施例：
[0069]
下面结合附图和具体实施例对本发明作进一步详细的说明。
[0070]
本发明提供了一种基于联盟形成博弈的异构无人机群任务分配方法，如图1所示，包括以下步骤：
[0071]
步骤1：针对协同监测任务与协同评估任务两类任务，分别定义无人机群协同任务执行效能。
[0072]
当无人机群sm执行协同监测任务m时，其任务执行效能pr(sm)定义为：
[0073][0074]
其中，是无人机n对任务m的监测任务完成概率，n∈sm表示无人机n属于机群sm，vm是任务m的价值系数，rm任务m的威胁系数。同理，当无人机群sm执行协同评估任务m时，其任务执行效能pc(sm)定义为：
[0075][0076]
其中，是无人机n对任务m的评估任务完成概率。
[0077]
步骤2：将无人机群协同任务执行问题建模为联盟形成博弈模型，其中博弈参与者为机群内各无人机。
[0078]
该博弈模型定义为：
[0079][0080]
其中，表示执行任务的无人机群中n个无人机序号，表示执行任务的无人机群中n个无人机序号，表示无人机所需执行的m个任务的集合，为动作集合，其中an为无人机n的任务选择；为效用函数，其中un为无人机n的效用函数，为联盟分区，即无人机群形成的联盟状态。利用平均分配准则，定义无人机n的效用函数为：
[0081][0082]
其中，|sm|为执行任务m的无人机数目。
[0083]
步骤3：利用基于部分合作的联盟形成算法进行求解，使得各无人机的任务执行效
能最大化。
[0084]
如图2所示，基于部分合作的联盟形成算法步骤如下：
[0085]
步骤3-1、初始化：各无人机随机选择一个任务，构成初始联盟分区
[0086]
步骤3-2、随机选择一个无人机n，其他无人机保持任务选择不变，根据如下公式计算无人机n当前任务执行效能un：
[0087][0088]
其中，uj为无人机j的效用函数，为无人机n加入后的联盟，为无人机n未加入前的联盟。其中符号“\”表示将集合元素从该集合中剔除。
[0089]
步骤3-3、无人机n随机选择不同于an的任务根据上述公式计算改变任务选择后无人机n任务执行效能u
′n。
[0090]
步骤3-4、若un《u
′n，则无人机n将其任务选择从an改变至a
′n；若un≥u
′n，则无人机n保持其任务选择an不变。
[0091]
步骤3-5、当收敛到稳定联盟分区时，输出当前各无人机的任务选择与任务执行效能；否则重复执行步骤3-2，直到收敛到稳定联盟分区。
[0092]
本发明所设计的基于联盟形成博弈的异构无人机群任务分配方法，将其应用到具体实例上，能有效提升无人机群任务执行效能，具体应用如下：
[0093]
考虑一个包含2个监测任务、2个评估任务的场景，由10个能力异构的无人机组成的无人机群对不同任务进行监测或评估。若无人机仅为监测无人机，其评估任务完成概率为0，监测任务完成概率在[0.4，0.8]上服从均匀分布；若无人机仅为评估无人机，其监测任务完成概率为0，评估任务完成概率在[0.4，0.8]上服从均匀分布；若无人机为双任务一体无人机，其监测任务完成概率和评估任务完成概率分别在[0.4，0.8]上服从均匀分布。此外，任务价值系数矩阵为[9.5，8.4，9.1，7.6]，任务威胁系数矩阵为[2.7，2.2，1.2，2.8]。图3为实验运行结果。
[0094]
如图3所示，为所提的基于部分合作的联盟形成算法与传统的基于帕累托准则、自私准则的联盟形成算法应用下的无人机群任务执行效能收敛对比示意图，可以看出，应用本发明所设计方法对应的收敛速度最快，且无人机群任务效能明显高于其他两种传统方法。
[0095]
具体实现中，本技术提供计算机存储介质以及对应的数据处理单元，其中，该计算机存储介质能够存储计算机程序，所述计算机程序通过数据处理单元执行时可运行本发明提供的特别是一种基于联盟形成博弈的异构无人机群任务分配方法的发明内容以及各实施例中的部分或全部步骤。所述的存储介质可为磁碟、光盘、只读存储记忆体(read-only memory，rom)或随机存储记忆体(random access memory，ram)等。
[0096]
本领域的技术人员可以清楚地了解到本发明实施例中的技术方案可借助计算机程序以及其对应的通用硬件平台的方式来实现。基于这样的理解，本发明实施例中的技术方案本质上或者说对现有技术做出贡献的部分可以以计算机程序即软件产品的形式体现出来，该计算机程序软件产品可以存储在存储介质中，包括若干指令用以使得一台包含数据处理单元的设备(可以是个人计算机，服务器，单片机，muu或者网络设备等)执行本发明
各个实施例或者实施例的某些部分所述的方法。
[0097]
本发明提供了特别是一种基于联盟形成博弈的异构无人机群任务分配方法的思路及方法，具体实现该技术方案的方法和途径很多，以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。本实施例中未明确的各组成部分均可用现有技术加以实现。

技术特征：
1.一种基于联盟形成博弈的异构无人机群任务分配方法，其特征在于，包括如下步骤：步骤1：针对无人机的任务类型，分别定义无人机群协同任务执行效能；步骤2：将无人机群协同任务执行问题建模为联盟形成博弈模型，其中博弈参与者为机群内各无人机；步骤3：利用基于部分合作的联盟形成算法进行求解，使得各无人机的任务执行效能最大化，得到各无人机的任务选择结果；步骤4：根据上述任务选择结果，分配无人机群任务，完成基于联盟形成博弈的异构无人机群任务分配。2.根据权利要求1所述的一种基于联盟形成博弈的异构无人机群任务分配方法，其特征在于，步骤1中所述的无人机的任务类型，包括协同监测与协同评估两类任务。3.根据权利要求2所述的一种基于联盟形成博弈的异构无人机群任务分配方法，其特征在于，步骤1中所述的分别定义无人机群协同任务执行效能，具体包括：步骤1-1，当无人机群执行协同监测任务类型时，计算无人机群的任务执行效能p
r
(s
m
)；步骤1-2，当无人机群执行协同评估任务类型时，计算无人机群的任务执行效能p
c
(s
m
)。4.根据权利要求3所述的一种基于联盟形成博弈的异构无人机群任务分配方法，其特征在于，步骤1-1中所述的计算无人机群的任务执行效能p
r
(s
m
)，具体方法如下：当无人机群s
m
执行协同任务m，且该任务为协同监测任务类型时，无人机群的任务执行效能p
r
(s
m
)定义为：其中，是无人机n对监测任务m的完成概率，n∈s
m
表示无人机n属于无人机群s
m
，v
m
是协同任务m的价值系数，r
m
是协同任务m的威胁系数。5.根据权利要求4所述的一种基于联盟形成博弈的异构无人机群任务分配方法，其特征在于，步骤1-2中所述的计算无人机群的任务执行效能p
c
(s
m
)，具体方法如下：当无人机群s
m
执行协同任务m，且该任务为协同评估任务类型时，无人机群的任务执行效能p
c
(s
m
)定义为：其中，是无人机n对评估任务m的完成概率。6.根据权利要求5所述的一种基于联盟形成博弈的异构无人机群任务分配方法，其特征在于，步骤2中所述的将无人机群协同任务执行问题建模为联盟形成博弈模型，该博弈模型如下：其中，表示执行任务的无人机群中n个无人机序号，表示执行任务的无人机群中n个无人机序号，表示无人机所需执行的m个任务的集合，为n个无人机的动作集合，
其中a
n
为无人机n的动作选择；为n个无人机的效用函数集合，其中u
n
为无人机n的效用函数，为联盟分区，即无人机群形成的联盟状态。7.根据权利要求6所述的一种基于联盟形成博弈的异构无人机群任务分配方法，其特征在于，步骤2中所述的无人机效用函数如下：利用平均分配准则，定义无人机n的效用函数u
n
为：其中，|s
m
|为执行任务m的无人机数目。8.根据权利要求7所述的一种基于联盟形成博弈的异构无人机群任务分配方法，其特征在于，步骤3中所述的基于部分合作的联盟形成算法，具体步骤如下：步骤3-1、初始化：各无人机随机选择一个任务，构成初始联盟分区步骤3-2、随机选择一个无人机n，其他无人机保持任务选择不变，计算无人机n当前任务执行效能u
n
；步骤3-3、无人机n随机选择不同于任务a
n
的任务其中，\表示将集合元素a
n
从该集合中剔除，根据步骤3-2计算改变任务选择后无人机n任务执行效能u
′
n
；步骤3-4、若u
n
<u
′
n
，则无人机n将其任务选择从任务a
n
改变至a
′
n
；若u
n
≥u
′
n
，则无人机n保持其任务选择a
n
不变；步骤3-5、当收敛到稳定联盟分区时，输出当前各无人机的任务选择与任务执行效能；否则重复执行步骤3-2，直到收敛到稳定联盟分区。9.根据权利要求8所述的一种基于联盟形成博弈的异构无人机群任务分配方法，其特征在于，步骤3-2中所述的计算无人机n当前任务执行效能u
n
，具体方法如下：其中，u
j
为无人机j的效用函数，为无人机n加入后的联盟，为无人机n未加入前的联盟。10.根据权利要求9所述的一种基于联盟形成博弈的异构无人机群任务分配方法，其特征在于，步骤3-5中所述的收敛到稳定联盟分区，即所有无人机的任务执行效能总和在迭代中保持不变。

技术总结
本发明公开了一种基于联盟形成博弈的异构无人机群任务分配方法，包括：步骤1：针对协同监测与协同评估两类任务，分别定义无人机群协同任务执行效能；步骤2：将无人机群协同任务执行问题建模为联盟形成博弈模型，其中博弈参与者为机群内各无人机；步骤3：利用基于部分合作的联盟形成算法进行求解，使得各无人机的任务执行效能最大化，得到各无人机的任务选择结果；步骤4：根据上述任务选择结果，分配无人机群任务，完成基于联盟形成博弈的异构无人机群任务分配。本发明利用博弈的方法，使得各无人机具备自主决策能力，具备时效性高、信息交互少的特点，可有效提高无人机群自主性，发挥机群任务执行效能。群任务执行效能。群任务执行效能。


技术研发人员：陈佳馨 李清伟 贺嘉璠 夏之杰 毛一鸣 费爱国
受保护的技术使用者：中国电子科技集团公司第二十八研究所
技术研发日：2023.06.06
技术公布日：2023/10/15