多无人机的路径规划算法

刘浩 李剑锋 曾达

摘要：考虑到多无人机可在数据采集时可在传感器圆周边界进行的情形，将此场景视为一种组合优化问题，该无人机的路径应用问题具有较大解空间特点，在路径规划问题中的经典的算法（如n-splitour、RA、APF等算法）无法进行多无人机无交叉路径优化，为此本文以n-splitour算法获得n条无人机最短路径并设计消除n条无人机路径之间存在交叉可能的方法，同时寻求局部寻优，再通过设计对局部优化方法以确定每个传感器圆周边界访问点的位置，从而可以高效地获取多个无人机的规划路径解。最后通过仿真实验验证了所设计的多无人机路径规划算法能较为良好地解决多无人机在传感器下数据采集中的路径规划问题。

引言

从目前实际应用分析，无人机数据采集是无人机无线网络中最重要的工作任务之一。传统的无人机数据采集模式首先依赖于各个传感器的实际地理位置进行，无人机数据的传输和收集得贴近传感器，才能完成所需数据的传输。

而在实际无人机工作的场景中，经常会存在如下因素影响无人机感知数据的采集：

1） 对于大量且范围广的目标监控应用，通过随机喷洒的方式部署传感器节点可能本身就会形成一个非完全连通的传感器网络;

2） 由于传感器的实际位置限制、无人机和传感器能量损耗过快、航飞时风速过大等原因，无人机可能无法按时到达或根本无法到达传感器所在位置，从而影响实时的数据采集工作;

3）各无人机在访问传感器时，可能会因为自身能耗限制，导致同一传感器数据频繁转发采集，会造成非必要的数据重复或滞后，就会造成数据采集中的实时性和有效性。

针对上述问题，本文主要研究，如何获得多无人机在多传感器数据采集工作任务中的最短路径，从而降低传感器中的数据采集延迟或者失效及无人机航飞时的能耗的问题。在充分研究了传感器节点在传送数据时确实有有效的数据传输范围之后，本文研究的问题可理解为带有圆形邻域（传感器节点的数据有效传输近似范围）且相邻数据传输范围可相互覆盖的旅行商问题，目前该问题已经被证明为APX-Hard。在实际无人机应用之中，由于传感器的数目非常多，且所在地域较为辽阔，所以该问题的解决和优化就显得更为重要。

本文的数据采集路径规划问题研究是基于多无人机且航飞路径端点设在传感器数据传输范围的圆周边界上的节点路径规划的问题，该优化问题具有解空间大难于求解优化的特点，经典的n-splitour等算法无法进行多无人机路径优化，而且较大概率会产生交叉的无人机低效的路径解，对此本研究首先利用n-splitour算法得到n条无人机路径，并设计了顺序交换的局部寻优方法，再通过设计多无人机算法确定每个传感器数据传输圆形范围上访问点的位置以达到对其多无人机路径规划的局部寻优，从而可以高效地获取近似最优的多无人机的规划路径的解。

1 多无人机路径的问题描述

假设在实际工作平面上放置了n个传感器节点，其中表示第1至n个传感器的所在地理位置，其数据通信范围是一个标准圆形的区域，R表示对应的数据通信半径，其中Lbase-station表示基站（无人机初始位置）位置，Rbase-station=0。现假设有x个无人机分别由基站出发，每个无人机则会根据自己所分配规划完成的航飞路径依次经过所在路径下的传感器节点的圆形通信范围，完成数据采集后将再次回到基站，记第p个无人机需要访问的传感器节点数目为mp。将第p条无人机路径第一次进入到路径上第q个传感器节点的通信范围的位置称为节点q上的数据采集点，记作。在各种可能的无人机路径规划方案中，让每一个无人机路径长度中最大的取值最小，减少无人机的路径遍历时间，从而降低数据采集的航飞路径时间损耗。多无人机路径规划问题的公式就可表示为：

上式中，d（x，y）表示x与y两点间的距离。

2.多无人机路径规划近似算法

多无人机路径如何指派以及各个无人机访问点的位置及顺序等如何确定均需要优化。为此将上述问题分解为两个步骤求解：第一步是基于n-splitour解决多个无人机的航飞路径指派问题，并设计出无交叉路径的局部寻优方法，第二步是提出了梯度下降搜索算法解决访问点的位置优化问题，具体多无人机路径规划算法的设计步骤和分析如下。

2.1 n个无人机路径指派问题的求解

通过对n-splitour算法的研究可发现，每一条无人机路径的开始路劲和结束路劲，可能与自身规划路径之前的路劲发生边边相交关系。但是依据三角不等式，在TSP问题中最优解的路径是一定不会存在相交边的情况，为此设计交换的方法（TSP问题中2opt或3opt算法）对无人机路径去除边与边相交的情况，从而更进一步缩短每个无人机路径的长度，则可达到局部寻优的效果。具体设计的分为以下四步如下：

1使用现有TSP算法寻找到一条无人机航飞TSP回路;2采用n-splitour算法得到n个无人机的航飞路径;3检测各個无人机路径中的起始边及结束边产生的自相交;4若3）检测到有自相交，则消除各个无人机路径中的起始边及结束边产生的自相交。

2.2 访问点位置的优化

由上述算法可以得到每一个无人机航飞的路径的解，但还需要确定无人机路径上在传感器数据传输范围上即圆周边界上的访问点的位置。由于无人机所在的访问点要求在传感器通信圆周上。在寻找最短路径上，每一个无人机的访问点将对应的θ的取值范围，可以由[0，2π]缩小到由该传感器数据传输圆周到下一个传感器数据传输圆周的两条外切线所包围的区间。

为了压缩搜索范围，提高求解效率。如下图所示考虑无人机通过A、B两个传感器的情形，无人机从基站出发，依次访问传感器A、B后，再回到基站。传感器A上访问点的可行取值区域位于弧A1A2内侧，与弧A3A4内侧的交集部分即弧A2A3内侧之间，同理传感器B上的可行区域在弧B1B3内侧之间。对于有多个传感器节点的情形，每个传感器节点对应弧段的起始范围可用近似的方法计算得到。

3 算法仿真

为了验证本文所提出的多无人机路径规划模型的合理性及其优化求解算法的正确性，进行了如下仿真实验。计算机的硬件平台为英特尔处理器i7-9750H 2.6GHz，8GB内存，其软件平台为Matlab2018b。仿真实验在长宽各500的区域内随机抛洒100个传感器节点。实验随机生成了1000个样本，统计结果见表1，其中计算时间为各次计算的均值。通过实验结果，在ρ=π/40时可取得最短的平均长度，在ρ=π/20时虽与前者的平均长度接近，但相对前者计算时间有了明显减少。

下图显示了一个采用了3个无人机进行路径规划，传感器节点通信范围是均匀分布场景下的路径规划实例图。

4结论

本文将实际应用场景的多无人机航飞数据采集中的路径规划问题建模为路径端点在传感器通信圆周之上的组合优化问题，并设计了求解的近似算法，验证了多无人机路径规划模型的合理性及其优化求解算法的正确性，

参考文献：

[1]Gupta L.， Jain R.， Vaszkun G. 无人机通信网络中关键技术研究进展[J]。通信学报，2016，35（2）：457-461。

[2]Maurice K.，Joseph A.，Chadi A. 无人机辅助车辆网络建模与性能分析[J]。汽车工程学报，2019，38（9）：889 - 898。

基金号：南宁理工学院2019年度校级科研项目+基于无人机在无线传感网数据采集中的路径规划研究+KY200901;

2020年广西高校中青年教师科研基础能力提升项目+5050KY58011。

作者简介：刘浩（1990-），男，汉族，广西桂林人，桂林理工大学硕士，讲师，研究方向：计算智能