基于代价反馈与瓶颈匹配的多无人机空间巡检任务规划方法与流程

摘要: 本发明涉及无人机,具体是指一种基于代价反馈与瓶颈匹配的多无人机空间巡检任务规划方法。背景技术:1、多无人机空间巡检任务是指多架无人机从各自起始位置同时出发,分别...
基于代价反馈与瓶颈匹配的多无人机空间巡检任务规划方法与流程

本发明涉及无人机,具体是指一种基于代价反馈与瓶颈匹配的多无人机空间巡检任务规划方法。

背景技术:

1、多无人机空间巡检任务是指多架无人机从各自起始位置同时出发,分别访问空间中部分目标位点,要求在尽量短的时间内完成全部位点的访问。该问题与多旅行商问题(multiple traveling salesman problem,mtsp)密切相关,可表述为路径开放的最小化最长路径多旅行商问题(min-max mtsp)。该问题是np-hard问题,目前尚无高效的精确求解算法。

2、对于小规模问题,现有技术通常采用暴力求解、整数规划或混合整数规划等方式求解;对于一般情形,则常采用模拟退火、遗传算法、蚁群算法等通用启发式算法或强化学习方法进行处理。此外,现有技术中还广泛采用“聚类+路径规划”的启发式架构进行处理,其基本流程为:首先利用k-means等聚类算法对目标位点进行划分,然后在每个类别中采用贪心算法或tsp近似算法进行路径规划,最后通过匹配或邻域搜索确定各无人机的最终路径方案。

3、然而,上述现有“聚类+路径规划”方法在以下方面存在显著不足:第一,聚类与路径代价脱节。k-means等聚类算法仅考虑目标位点的欧几里得空间分布,未考虑无人机的初始位置以及“不返航”的开放路径特性,导致聚类中心偏离实际路径代价最优位置,易产生交叉路径,增加整体巡检时间。第二,负载不均衡。简单聚类方法难以实现各无人机之间工作量的严格均衡,常出现单架无人机任务量过重的情况,导致整体巡检时间被拉长,无法充分发挥多无人机并行作业的优势。第三,匹配错位。现有技术通常采用最小权重匹配来分配无人机与任务簇,该匹配方式以最小化总路径长度为目标,偏离了多无人机巡检任务最小化最长路径的优化目标,导致进一步延长了任务完成时长。

4、综上,现有“聚类+路径规划”方法在解决多无人机空间巡检任务时,存在路径交叉、负载不均衡及匹配错位等技术缺陷,亟需改进。

技术实现思路

1、本发明的目的在于克服目前多无人机空间巡检任务时存在路径交叉、负载不均衡及匹配错位等技术缺陷,提供一种基于代价反馈与瓶颈匹配的多无人机空间巡检任务规划方法。

2、为实现上述目的,本发明采用以下技术方案来实现:一种基于代价反馈与瓶颈匹配的多无人机空间巡检任务规划方法,包括以下步骤:

3、s1、采用k-means算法对空间中的目标位点进行聚类划分,得到k个簇,其中k为无人机数目,且k小于目标位点总数;

4、s2、将各无人机的起始点分别带入各所述簇中,分别以各无人机的起始点为起点、以各所述簇中的目标位点为后续节点进行路径规划,得到k×k的代价矩阵m和k×k个对应的规划路径组r;

5、s3、利用代价矩阵m进行瓶颈匹配,确定各无人机与各簇之间的匹配关系,并从规划路径组r中选取与匹配关系对应的规划路径,得到分配方案,其中为第k个无人机的规划路径;

6、s4、识别当前规划方案中巡检时间最长的瓶颈路径,从瓶颈路径中选取位于簇边缘的位点迁移至相邻较短路径,若迁移后能够降低瓶颈路径的路径长度,则执行所述位点迁移,重复直至收敛,记录更新后的规划方案及最长路径值;

7、s5、重复执行s2~s4,比较前后两轮迭代的最长路径值,若后一轮的最长路径值小于前一轮的最长路径值,则接收该新的规划方案并进行更新,直至该最长路径值收敛或到达指定迭代步数,输出最终的规划方案。

8、作为优选方式,步骤s2中所述的“路径规划”采用带随机尝试的2-opt局域搜索算法进行计算。

9、进一步地,步骤s3中所述的“瓶颈匹配”,其具体是指:先利用二分法确定瓶颈θ,再由瓶颈θ及代价矩阵m生成瓶颈代价矩阵,最后通过最小权重匹配算法对瓶颈代价矩阵求解,得到匹配关系。

10、所述“利用二分法确定瓶颈θ”的具体方法为:首先,对代价矩阵m中的元素按大小进行排序,设置测试瓶颈θ为最大元素值,配置测试代价函数,其中,所述的元素由代价矩阵m中的对应元素确定;若 则,否则为一个大数,且大数,其中,表示第i个无人机巡检第j个簇的路径长度;其次,通过最小权重匹配算法对代价函数求解,若能找到权重和小于大数的解,则将搜索区间的上界更新为当前瓶颈θ;否则将搜索区间的下界更新为当前瓶颈θ,重复此过程直至瓶颈θ不再变化。

11、作为优选方式,步骤s4中所述“从瓶颈路径中选取位于簇边缘的位点”,是指从瓶颈路径中识别离其它簇的位点距离最近的位点作为位于簇边缘的位点。

12、进一步地,步骤s4中所述“迁移后能够降低瓶颈路径的路径长度”的判定方法为:计算将所述位点从瓶颈路径中移除的代价变化与将所述位点插入相邻较短路径的增量;若满足,则判定迁移后能够降低瓶颈路径的路径长度,其中为相邻较短路径的路径长度。

13、所述步骤s4中所述的“收敛”,其条件为:相邻两轮迭代的最长路径值的相对变化在1%以内。

14、所述步骤s5中的“直至该最长路径值收敛”,其收敛条件为:相邻两轮迭代的最长路径值改进变化低于1%或为负值

15、与现有技术相比,本发明的有益效果是:

16、(1)本发明通过构建“路径规划—瓶颈匹配—聚类调整”的闭环迭代架构,将路径代价作为反馈信号动态引导聚类划分,有效克服了传统k-means聚类仅依赖欧氏空间分布而与路径代价脱节的缺陷,避免了因聚类中心偏差产生的交叉路径问题,显著提升了多无人机协同巡检的路径合理性。

17、(2)本发明采用最小化最长路径(min-max)导向的瓶颈匹配策略,通过二分法确定最优瓶颈阈值并结合最小权重匹配算法求解匹配关系,相对于传统采用最小权重和匹配的方案,能够精准实现各无人机任务负载的均衡分配,有效抑制单机任务量过重导致的整体巡检时间延长。

18、(3)本发明通过聚类调整步骤中的瓶颈路径识别与位点迁移机制,以代价变化和增量作为量化判据,仅在迁移能有效降低全局最长路径时执行迁移,实现了对系统瓶颈的精准消减,兼顾了局部调整有效性与全局收敛稳定性。

19、(4)本发明能有效克服单轮“聚类-匹配-调整”流程可能陷入局部最优的问题,进一步提升了最终规划方案的全局优化质量,且收敛条件可调,具备良好的工程适用性与灵活性。

1.一种基于代价反馈与瓶颈匹配的多无人机空间巡检任务规划方法,其特征在于,包括以下步骤:

2.根据权利要求1所述的基于代价反馈与瓶颈匹配的多无人机空间巡检任务规划方法,其特征在于,步骤s2中所述的“路径规划”采用带随机尝试的2-opt局域搜索算法进行计算。

3.根据权利要求1所述的基于代价反馈与瓶颈匹配的多无人机空间巡检任务规划方法,其特征在于,步骤s3中所述的“瓶颈匹配”,其具体是指:先利用二分法确定瓶颈θ,再由瓶颈θ及代价矩阵m生成瓶颈代价矩阵,最后通过最小权重匹配算法对瓶颈代价矩阵求解,得到匹配关系。

4.根据权利要求3所述的基于代价反馈与瓶颈匹配的多无人机空间巡检任务规划方法,其特征在于,所述“利用二分法确定瓶颈θ”的具体方法为:

5.根据权利要求4所述的基于代价反馈与瓶颈匹配的多无人机空间巡检任务规划方法,其特征在于,步骤s4中所述“从瓶颈路径中选取位于簇边缘的位点”,是指从瓶颈路径中识别离其它簇的位点距离最近的位点作为位于簇边缘的位点。

6.根据权利要求1所述的基于代价反馈与瓶颈匹配的多无人机空间巡检任务规划方法,其特征在于,步骤s4中所述“迁移后能够降低瓶颈路径的路径长度”的判定方法为:计算将所述位点从瓶颈路径中移除的代价变化与将所述位点插入相邻较短路径的增量;若满足,则判定迁移后能够降低瓶颈路径的路径长度,其中为相邻较短路径的路径长度。

7.根据权利要求6所述的基于代价反馈与瓶颈匹配的多无人机空间巡检任务规划方法,其特征在于,所述步骤s4中所述的“收敛”,其条件为:相邻两轮迭代的最长路径值的相对变化在1%以内。

8.根据权利要求7所述的基于代价反馈与瓶颈匹配的多无人机空间巡检任务规划方法,其特征在于,所述步骤s5中的“直至该最长路径值收敛”,其收敛条件为:相邻两轮迭代的最长路径值改进变化低于1%或为负值。