一种无人机图匹配任务决策方法和系统

摘要: 本发明属于无人机集群协同任务决策,尤其涉及一种无人机图匹配任务决策方法和系统。背景技术:1、随着无人机集群技术的快速发展,多架无人机协同执行复杂任务已成为无人系...
一种无人机图匹配任务决策方法和系统

本发明属于无人机集群协同任务决策,尤其涉及一种无人机图匹配任务决策方法和系统。

背景技术:

1、随着无人机集群技术的快速发展,多架无人机协同执行复杂任务已成为无人系统智能化应用的重要方向。在无源定位、协同侦察、目标跟踪、区域覆盖以及通信中继等任务中,无人机不仅需要被分配至相应任务点,还需要在空间上满足特定的协同构型要求。例如,在基于到达时间差的无源定位的任务中,不同无人机之间的相对位置关系会直接影响定位几何精度;在广域协同侦察任务中,无人机之间的距离、视场覆盖关系以及通信链路关系会影响整体任务效能。

2、传统的无人机任务分配方法通常将任务分配问题建模为线性分配问题,其目标函数主要考虑单架无人机与单个任务点之间的匹配代价,例如飞行距离、剩余能量、到达时间或任务收益等。该类方法可以采用匈牙利算法、拍卖算法或合同网算法进行求解,具有模型简单、计算速度快等优点。但是,当任务要求无人机之间保持特定的协同拓扑关系时,仅考虑“无人机—任务点”之间的一对一匹配代价是不充分的,还需要同时考虑“无人机—无人机”之间的相对关系与“任务点—任务点”之间的期望构型关系是否一致。

3、在引入成对约束后,多无人机任务匹配问题可转化为二次分配问题。所谓二次分配问题,是指在确定单个无人机与单个任务点匹配关系的同时,还需要评价两个无人机之间的关系与两个任务点之间的关系是否匹配。因此,该问题不仅包含节点匹配代价,还包含边匹配代价,能够更准确地描述多无人机协同构型任务。然而,二次分配问题属于np-hard问题,随着无人机数量和任务点数量增加,计算规模会快速增长,导致传统方法在机载算力受限条件下面临较大困难。

4、现有技术在求解带有成对约束的多无人机二次分配问题时,主要存在以下不足:

5、1. 维数灾难与计算瓶颈。对于包含架无人机和个任务点的匹配问题,若直接构造全局亲和力矩阵,则需要对所有可能的“无人机—任务点”匹配对及匹配对之间的组合关系进行建模,其矩阵维度通常达到。当无人机数量或任务点数量增大时,该矩阵的存储量和计算量会迅速增加。对于机载计算资源有限的无人机集群而言,显式计算和存储该类高维矩阵容易造成内存占用过高、计算延迟增加,难以满足实时任务决策需求。

6、2. 连续松弛与离散分配之间存在精度损失。现有图匹配或谱匹配方法通常先将原始整数约束问题松弛为连续优化问题,得到连续形式的匹配结果后,再通过舍入或投影等后处理方法将其转换为满足一对一分配约束的整数解。由于连续优化步骤和离散化步骤相互分离,舍入过程可能破坏原有优化目标的最优性,导致输出结果出现次优匹配,甚至产生不满足物理分配约束的方案。

7、3. 对扰动和节点失效的适应能力不足。在实际无人机集群任务中,无人机位置、速度、剩余能量、通信状态以及局部链路关系可能受到风场扰动、通信干扰或单机故障影响。当集群拓扑发生变化时,传统任务分配方法往往需要重新构造完整代价矩阵并重新求解,难以在较短时间内完成动态重构。

技术实现思路

1、针对现有技术中存在的全局亲和力矩阵维度高、连续松弛后舍入误差大以及动态扰动下重构能力不足的问题,本发明提供一种无人机图匹配任务决策方法和系统,该方法将多无人机集群的当前状态和目标任务构型分别建模为属性图,通过节点亲和度和边亲和度同时描述单机任务匹配关系与多机协同构型关系;进一步利用图结构关联矩阵和特征亲和矩阵对全局亲和力矩阵进行因子化分解,避免直接构造高维全局矩阵;最后采用路径跟随的连续—离散联合优化策略,使匹配结果逐步由连续松弛域收敛至满足一对一分配约束的整数域,从而得到最终无人机—任务匹配矩阵。

2、本发明的技术方案为:

3、一方面,本发明提供一种无人机图匹配任务决策方法,包括以下步骤:

4、将多无人机集群的当前状态和目标任务构型分别构建为无人机资源能力图和任务需求图,并计算节点亲和度矩阵和边亲和度矩阵,共同构成用于图匹配求解的双层图结构。

5、基于双层图结构构建多无人机图匹配任务决策的目标函数,并利用因子分解将多无人机图匹配任务决策的目标函数重构为等效的迹形式,进而构建多无人机图匹配任务决策问题。

6、利用基于路径跟随的连续-离散联合优化方法对多无人机图匹配任务决策问题进行求解,得到最终无人机与任务的匹配矩阵。

7、进一步地,所述将多无人机集群的当前状态和目标任务构型分别构建为无人机资源能力图和任务需求图,并计算节点亲和度矩阵和边亲和度矩阵,共同构成用于图匹配求解的双层图结构,具体包括:

8、设当前可用无人机数量为,待分配任务点数量为,将多无人机集群的当前状态构建为无人机资源能力图,其中,表示无人机节点集合;表示无人机节点之间的边集合,为无人机节点特征矩阵,为无人机边特征矩阵,为无人机节点与边的关联矩阵。

9、所述无人机节点特征矩阵用于描述每架无人机的自身状态,表示无人机的节点特征向量的维数,无人机节点特征矩阵的第行表示第架无人机的节点特征向量。

10、所述无人机节点之间的边集合用于描述无人机之间的空间邻接关系、通信链路关系或协同观测关系,其中的元素表示第架无人机和第架无人机构成的无人机边,表示无人机的编号;当两架无人机之间能够通信、协同观测或满足预设距离阈值时,认为二者之间存在无人机边;否则,二者之间不存在无人机边。

11、所述无人机边特征矩阵用于描述无人机之间的相对关系,表示无人机边数量,表示边特征向量的维数;对于由第架无人机和第架无人机构成的无人机边,其边特征向量表示为。

12、所述无人机节点与边的关联矩阵用于表示无人机节点与无人机边之间的连接关系,若第条无人机边与第架无人机对应的无人机节点相连,则无人机节点与边的关联矩阵中的元素,否则,,表示无人机边的编号。

13、同时,将目标任务构型构建为任务需求图,其中,表示任务节点集合;表示任务节点之间的边集合,为任务节点特征矩阵,为任务边特征矩阵,为任务节点与边的关联矩阵。

14、所述任务节点之间的边集合用于描述任务点之间的期望空间构型关系、协同关系及拓扑关系,其中的元素表示第个任务点对应的任务节点和第个任务点对应的任务节点构成的任务边,表示任务点的编号。

15、所述任务节点特征矩阵用于描述每个任务点的需求属性,表示任务节点特征向量的维数,任务节点特征矩阵的第行表示第个任务点的任务节点特征向量。

16、所述任务边特征矩阵用于描述目标任务构型中任务点之间的期望协同关系,表示任务边数量,表示任务边特征向量的维数,对于由第个任务点和第个任务点构成的任务边,其任务边特征向量表示为。

17、所述任务节点与边的关联矩阵中,若第条任务边与第个任务节点相连,则元素;否则,元素,表示任务边的编号。

18、所述节点亲和度矩阵用于描述第架无人机执行第个任务点的适配程度,其元素表示为,其中,为节点特征距离权重系数,为可行性掩码,当第架无人机满足第个任务点的能力、航程、电量或载荷要求时,;否则,。

19、边亲和度矩阵用于描述无人机之间的实际相对关系与任务点之间期望构型关系的相似程度,对于无人机边和任务边,在边亲和度矩阵中的对应元素表示为,其中,表示无人机边,表示任务边,为边特征距离权重系数。

20、进一步地,所述基于双层图结构构建多无人机图匹配任务决策的目标函数,并利用因子分解将多无人机图匹配任务决策的目标函数重构为等效的迹形式,进而构建多无人机图匹配任务决策问题,具体为:

21、所述多无人机图匹配任务决策的目标函数为:

22、(3);

23、其中,表示表示匹配矩阵对应的多无人机图匹配总得分,所述匹配矩阵为,匹配矩阵中的元素表示第架无人机被分配至第个任务点,表示二者不匹配;表示总节点匹配得分,表示总边匹配得分;为边匹配权重系数。

24、根据无人机资源能力图,定义无人机边的起点关联矩阵和终点关联矩阵分别为,,对于第条无人机边,若起点为第架无人机,则起点关联矩阵中的元素,否则元素为0;对于第条无人机边,若终点为第架无人机,则终点关联矩阵中的元素,否则元素为0。

25、对于任务需求图,定义任务边的起点关联矩阵和终点关联矩阵分别为和,对于第条任务边,若起点为第个任务点,则起点关联矩阵中的元素,否则元素为0;对于第条任务边,若终点为第个任务点,则,否则元素为0。

26、所述多无人机图匹配任务决策问题表示为:

27、(9);

28、其中,表示矩阵的迹运算,表示转置,和分别表示维度为和的全一向量。

29、进一步地,所述利用基于路径跟随的连续-离散联合优化方法对多无人机图匹配任务决策问题进行求解,得到最终无人机与任务的匹配矩阵,具体为:

30、首先,将原始整数可行域表示为,将原始整数可行域松弛为连续可行域;当无人机数量与任务点数量相等且要求一一匹配时,连续可行域写为双随机矩阵约束形式:。

31、构造由路径参数调节的插值目标函数:

32、,(10);

33、其中,表示插值目标函数,表示路径参数,表示便于连续优化的初始松弛目标函数,表示用于引导解向离散整数域收敛的目标函数,具体地,取,,其中,为单位矩阵,为调节参数,,表示因子化得到的对称边亲和力矩阵,节点亲和度向量,向量。

34、将上述便于连续优化的初始松弛目标函数和用于引导解向离散整数域收敛的目标函数代入插值目标函数,得:

35、(11);

36、记,则:

37、(12);

38、在求解过程中,路径参数从0逐步增加至1:,,其中,表示路径跟随阶段的编号,为路径跟随的总阶段数,表示路径参数在第个路径跟随阶段的取值,每一个对应一个连续优化子问题:,在时,先在连续可行域中获得初始解,随后逐步增大,并以前一阶段的解作为后一阶段的初始值,使匹配矩阵沿着连续路径逐渐向原始整数可行域移动。

39、对于每一个路径参数,进行内层迭代求解:设当前迭代解为,其向量化形式为,插值目标函数关于的梯度为,表示路径参数取时插值目标函数的二次项系数矩阵,将梯度重新排列为矩阵形式:,其中,表示的逆操作,表示第

s次内层迭代时插值目标函数关于匹配矩阵的梯度矩阵,其维数与匹配矩阵

x相同。

40、然后求解如下线性分配子问题:,其中,表示矩阵内积,表示线性分配子问题中的候选匹配矩阵,表示第

s次内层迭代时求解得到的匹配矩阵,求解线性分配子问题得到后,更新方向为,接着,在更新方向上进行一维搜索,确定最优步长:,表示候选步长,表示第

s次内层迭代获得的最优步长。

41、令,则步长优化问题为关于的一元二次函数最大化问题:,因此,若则候选步长取为,并将其截断到区间内:,若,则分别比较和时的插值目标函数值,并选择插值目标函数值较大的步长,随后更新匹配矩阵:。

42、当满足如下任一条件时,停止当前下的内层迭代:,或,或达到最大迭代次数,其中,和分别表示目标函数变化阈值和匹配矩阵变化阈值,表示frobenius范数,当前路径参数下的最优解记为,当时,将其作为下一路径参数下的解的初始值:;重复上述过程,直至,最终,在时输出匹配矩阵。

43、当输出匹配矩阵中的元素不为0或1时,根据如下规则获得最终无人机-任务匹配结果:,其中,表示第架无人机最终被分配至第个任务点,表示输出匹配矩阵的元素;若任务点数量小于无人机数量,则未被选中的无人机保持空闲或作为备份无人机。

44、另一方面,本发明还提供一种无人机图匹配任务决策系统,用于实现一种无人机图匹配任务决策方法,包括:

45、双层图结构构建模块,用于将多无人机集群的当前状态和目标任务构型分别构建为无人机资源能力图和任务需求图,并计算节点亲和度矩阵和边亲和度矩阵,共同构成用于图匹配求解的双层图结构。

46、决策问题构建模块,用于基于双层图结构构建多无人机图匹配任务决策的目标函数,并利用因子分解将多无人机图匹配任务决策的目标函数重构为等效的迹形式,进而构建多无人机图匹配任务决策问题。

47、求解模块,利用基于路径跟随的连续-离散联合优化方法对多无人机图匹配任务决策问题进行求解,得到最终无人机与任务的匹配矩阵。

48、第三方面,本技术提出一种电子设备,包括:一个或多个处理器,以及存储器,所述存储器用于存储指令,当所述指令被所述一个或多个处理器执行时,使得所述一个或多个处理器执行所述的一种无人机图匹配任务决策方法。

49、第四方面,本技术提出一种计算机可读存储介质,其存储有可执行的指令,所述指令当被执行时使得处理器执行所述的一种无人机图匹配任务决策方法。

50、第五方面,本技术提出一种计算机程序产品,包括计算机程序或指令,该计算机程序或指令被处理器执行时实现所述的一种无人机图匹配任务决策方法。

51、与现有技术相比较,本发明的有益效果为:

52、1.算力与内存友好:本发明无需计算和存储空间、时间代价高昂的成对亲和力矩阵。通过矩阵的因子分解技术解耦了无人机网络结构与特征参数,极大降低了算法的空间和时间复杂度,非常适合算力受限的机载飞行平台集群使用。

53、2.提高离散匹配结果的可实施性:与传统算法先进行连续优化、再通过独立舍入获得离散解的处理方式不同,本发明在因子化图匹配目标函数基础上引入路径跟随优化策略,使匹配矩阵从连续松弛域逐步向满足分配约束的离散匹配域逼近,减少独立舍入后处理带来的匹配精度损失,提高无人机—任务匹配结果的可实施性和稳定性。

54、3.抗干扰与动态重构能力强:当集群面临外部扰动(如无人机偏航导致的边噪声)或部分节点失效时,本图模型及优化框架具有强鲁棒性,能够快速收敛产生高拟合度的新拓扑分配方案。