摘要
一.介绍
二.相关工作
2.12D覆盖路径规划
2.2传统的3D覆盖路径规划
2.3智能3D路径规划
三.DRL GIS培训环境
3.1复杂GIS地形采样
3.22无人机路点生成及能见度分析
四.基于DRL无人机智能覆盖导航
4.11无人机覆盖导航状态
4.2基于TK - MCTS无人机覆盖导航奖励
4.3无人机覆盖导航DRL实现
五.实验和结果
5.1地形数据采样与能见度分析
5.2TK -MCTS的性能
5.3本地和全球搜索的结合
5.4DRL智能路径规划
5.4.1化步长覆盖性能
5.4.2.平均地形覆盖率
六.结论
摘要
无人机(UAV)覆盖机动性和灵活性成为覆盖探测任务的首选工具之一。无人机在复杂的几何环境中独立确定航迹是一项具有挑战性的工作。提出了基于深度强化学习的无人机智能导航方法。我们建议使用地理信息系统(GIS)作为DRL克服训练环境与测试环境的不一致性。我们以图像的形式创造性地保存了飞行路线。蒙特卡洛树的蒙特卡洛树搜索方法与局部搜索方法相结合，既能有效避免局部搜索，又能在计算能力的限制下学习最佳搜索方向。实验表明，训练有素的无人机可以通过智能导航找到良好的飞行路径，并在复杂的几何环境中做出有效的飞行决策。
关键词：无人机 智能导航 覆盖 深度加强学习 搜索蒙特卡洛树
一.介绍
无人机具有体积小、成本低、使用方便、环境要求最低、空中监测视野灵活、范围广等优点。因此，它被应用于监测、搜索、救援、野生动物、边境巡逻等领域[1-4]。无人机传感器，如相机，在复杂的几何环境中容易受到干扰。覆盖任务的主要挑战是规划无人机路径，有效覆盖给定区域[5]。这些挑战包括：
覆盖感知质量UAV许多覆盖问题的研究假设给定区域有理想的平坦地形[6]。事实上，大多数目标地形都是崎岖不平的。传统方法获得的图像素质量不相等[5，7]。假设无人机在水平面上飞行，如图1所示。传感器在无人机红色区域拍摄的照片分辨率较高，但在蓝色区域拍摄的照片像素较低。无人机需要实时调整高度以获得高质量的地形照片。各种障碍物可能会阻挡相机的视野。为了满足传感分辨率的要求，无人机需要能够改变飞行高度，这需要在三维域内优化路径规划[8、9]。
能量限制和时间限制无人机应在时间限制下通过路点[10和11]。搜索满足时间和能量限制的无人机的最佳路径是一个不确定的多项时间难度(NP-hard)问题。现有的无人机航迹规划算法通常采用近最优航迹，搜索成本相同，搜索时间短得多。
阶乘时间的复杂性寻找最佳飞行路径(O(n!))[12]。N飞行路径路径点的数量。
智能实时导航无人机智能导航是指无人机可以根据环境和覆盖任务进行飞行决策。近年来，深入加强学习(deep reinforcement learning, DRL)该方法试图解决智能路径规划问题[13、14]。机器人以深度图像为输入，以控制命令为输出，移动并找到合适的路径。然而，大多数RGB-D相机功能范围有限，无法达到令人满意的效果，导航时用作唯一的长距离传感器[15]。DRL该方法不是在测试阶段，而是在训练阶段[16]。换句话说，在现实世界中找到一条需要反复飞行才能学习策略的路径是不现实的。
图1无人机水平样本地形高程测绘
基于传感质量感知的覆盖和智能路径规划方案，针对具有不同高度和屏蔽的复杂几何场景。
目标是在无人机能量的限制下，为目标区域提供满意的空间和时间分辨率。本文的主要贡献如下：（1）研究了无人机在大规模复杂环境中导航的研究DRL框架。我们使用地形图（如谷歌地形图，它非常接近真实的无人机飞行环境）作为DRL的模型。DRL框架使我们更容易找到全球最佳飞行路径。在GIS在中学学习和训练后，无人机可以做出独立的飞行决策。(2)深度神经网络(DNN)具有良好的图像理解和分析能力。我们以无人机已经通过的路线为当前路线agent的观测。我们创造性地使用投影方法3D路径转换为2D图像。(3)基于地形知识的快速进化MCTS (TK-MCTS)方法。TK-MCTS利用地形信息引导无人机以更高的概率搜索未探测区域。(4)根据地形覆盖任务的特点，将局部地形探测与全局探测相结合。这样，无人机就可以避免局部最优。同时，还可以降低全局估计误差[17]。
二.相关工作
2.12D覆盖路径规划
假设目标区域的地形是理想的平面。螺旋模型、螺旋模型、割草机模型、Zamboni模型、Dubis路径模型以及改进的割草机、Zamboni路径规划策略[19]。然而，大部分地形崎岖不平。障碍物会影响无人机相机传感器的覆盖范围。如果在二维空间中只考虑地形覆盖，很难保证传感器的质量。
2.2传统的3D覆盖路径规划
随着计算能力的提高，最新的研究集中在三维空间覆盖路径规划方面。Dai等人[8]指出，为了实现对目标区域内所有点的全覆盖，需要拍摄比理想平坦地形情况下更多的图像。在一次覆盖任务中，[20]通过在线构建地形地图，在连续的三维空间中规划信息丰富的轨迹，对得到的初始解进行优化。Scott等人[21]提出了一种遮挡感知的无人机覆盖技术，通过寻找在目标区域拍照的最佳航路点集。然后通过求解车辆路径问题(VRP)将所选航路点分配给无人机。在矩阵补全的基础上，[22]首先选择支配采样点，然后选择虚拟支配采样点。最后，根据所选择的采样点，采用最优模拟退火算法对无人机航路进行规划。在[23]中，作者提出了一种基于目标区域六边形平铺的覆盖算法。但该方法不能推广到三维空间。在[24]中，作者开发了一种基于一般偏好的多目标进化算法来收敛于偏好解，并通过参考点引出决策者的偏好。但是，这种方法不能有效地处理存在障碍物的环境。Zhang et al.[25]利用新定义的单个代价矩阵，提出了一种高效的多无人机路径规划算法。但该算法在相对复杂的地形环境中容易失效。在[26]中，给出了覆盖路径规划问题的一个整数线性规划公式，它能以蛮力方法的一小部分计算成本提供几乎最优的策略。Bircher等人[27]能够通过交替两步优化算法计算短检查路径。在这种方法中，首先发现观点，然后连接形成链接。这种方法得到的路径往往不是最优路径。
2.3智能3D路径规划
DNN具有优秀的学习能力和记忆能力。最近DRL的改进已经允许解决许多2D领域的问题，如Atari游戏[28,29]。Wang et al.[30]，基于深度Q-Network框架，将原始深度图像作为唯一输入来估计对应于所有移动命令的Q值。将深度学习(deep learning, DL)与强化学习(reinforcement learning, RL)相结合，使复杂的三维地形路径规划取得了比以往更好的效果。近年来，DRL方法已被用于导航[31,32]和路径规划[33-35]的应用。[36]中使用DNN进行实时路径规划。这项研究的重点是避免与障碍物发生碰撞。[37]针对自主无人地面车辆进行规划，提出了一种基于图卷积神经网络(CNN)的约束最短路径搜索方法。
三.DRL GIS培训环境
DRL算法已经证明了在具有挑战性的环境中学习寻找目标的进展。[16]中的实验表明，DRL算法不是在测试阶段记忆地图，而是在训练阶段。
我们建议使用GIS作为DRL训练环境，以克服训练环境与测试环境[38]之间的不一致性。无人机经过地理信息系统的训练，具有智能决策能力，使无人机能够在现实世界中做出准确的决策。建立GIS地形训练环境的步骤包括地形采样、航路点生成和可见性分析。
3.1复杂GIS地形采样
我们将地形转换为一组离散的地理坐标点B = {b1，…， bn}， bi = (xi, yi, zi)根据地平面上的经纬度，我们采样地平面上的二维坐标，步长为b。我们可以得到每个采样点的地形高程。
3.2无人机航路点生成与能见度分析
可以在每个地形采样点的顶部生成不同高度[8]的航路点(照片位置)。可选路径点集合为R = {p1，…,点}。我们的目标是找到一个有序的路径点集合Wk = [p1 k，…]R, Wk⊆R。当无人机沿着这个有序的地理坐标点集合飞行时，形成了覆盖飞行路径l, l = p1 k→⋯→pj k。P1 k是起始位置。pjk是终止位置。
将GIS上一个点的可见范围测量问题转化为两点视觉判断问题。我们采用插值可见性分析方法来判断两点是否可见。
插补可见性分析方法的详细内容如算法1所示。GIS可以计算高程(lat1, long1, e1)…(latn, longn, en)根据纬度和经度。eti表示通过GIS计算得到的高程数据。如果∃ti, tj, hti≥eti, htj≤etj;a、b不可见。
当插值密度达到一定数值时，我们可以有效地判断a和b在视线内是否可见。我们可以从图2中看到。水平方向沿线段l每隔5m插补一次，从A到B, hA→B > eA→B。从A到C, hA→C ' > eA→C '， hC '→C " < eC '→C "， hC "→C > eC "→C。因此，我们无法从A中看到C。
四.基于DRL的无人机智能覆盖导航
提出了一种基于DRL的无人机智能导航方法。UAV是DRL结构中的一个代理。我们使用四旋翼无人机来执行覆盖任务。无人机不断改进其策略以最大限度地累积覆盖任务。通过收集其与复杂地形环境的交互样本(状态，行动和奖励)进行奖励。我们用神经网络来模拟E(l)函数。将状态输入神经网络，输出无人机飞行动作值。在每个离散时间步长，无人机从动作空间中选择一个动作(上、下、纬度+、纬度−、经度+和经度−)。创造性地将无人机飞行轨迹作为无人机当前状态，并将其作为神经网络的输入状态。
图2插值可见性分析
4.1无人机覆盖导航状态
我们创造性地将飞行轨迹以图像的形式保存下来，并将图像作为DNN的输入。DNN具有出色的分析和理解图像形式数据的能力。若将无人机路径信息转换为图像形式，DNN将更好地进行特征提取和分类。我们提出了高程压缩方法，将3D GPS路径数据转换为二维图像。
为了说明算法，我们以图convert3dgpspathdatainto2image为例。假设图3a是初始状态。通过高程压缩方法，我们得到了路径的二维图，如图3e。从图3a开始，经过20次动作后，无人机状态如图3b所示。图3(f)为图3b的二维图。图3c, d为每20个动作间隔时的无人机路径。图3g, h是3c, d的映射。我们看到，随着路径的增加，灰色矩形的总数减少。DNN能有效识别图像灰度的变化，并能区分路径。
高程压缩方法如图2所示。步骤2将路径点存储在3D矩阵m中。我们将z轴上的数据同xy轴转换成二进制序列。每个二进制数据都以十进制形式存储在矩阵V中。将矩阵V转换为灰度图像。例如，我们取z列，其中X轴为i, Y轴为j。假设M[i][j] =[0,1,0,1,1]。我们将[0,1,0,1,1]视为二进制数01011。将二进制数字01011转换为十进制数字11。我们将11存储在一个二维矩阵V[i][j] = 11中。使用算法2步骤3-10计算所有z列。得到二维矩阵V来存储图像数据。
4.2基于TK - MCTS的无人机覆盖导航奖励
尽可能多地飞越先前未被发现的区域可以在有限的时间内产生更多的模拟飞行结果。通过路径覆盖性能比较，确定动作奖励值。无人机航路点的搜索空间很大，我们需要优化搜索。根据地形和覆盖状态，无人机在无覆盖方向飞行可以更有效地覆盖整个任务。提出了基于地形知识的蒙特卡洛树搜索(TK-MCTS)算法。将TK-MCTS方法与局部搜索方法相结合，既能有效避免陷入局部搜索，又能保证在计算能力限制下学习最优搜索方向。
TK-MCTS在开发上明显优于传统的MCTS。TK-MCTS算法使用地图知识引导无人机尽可能远地飞到先前未发现的区域。与传统的MCTS算法不同，该算法采用位置引导点(position guided points, PGP)来引导无人机的飞行方向。PGP是可选飞行点集合r的一个随机子集。PGP = {g0，…， gl}， PGP⊆R。
gi的可见地形面积为ti。PGPT = {t0，…, tl}。我们计算飞向不同方向的概率。用公式1计算每个方向的得分:
其中ni是I被模拟的次数。ρ ∈ (0, 1] .如果向量s → i 的方向在x,y,z轴和s → gi 是一样的。否则，ρ = 1。选择不同方向的最小分数作为模拟节点。
具体算法为算法3。根据不同方向的飞行模拟结果，我们设置模拟结果最好的方向奖励值为1，其他方向奖励值为0。
4.3无人机覆盖导航DRL实现
强化学习的核心是通过最大化预期回报，从状态s采取行动a开始，发现最优动作值函数Q (s, a):
终止前的总未来奖励是Rt。Π代表DRL策略，未来奖励折现系数为γ，未来估计的总回报是
DRL的基本假设是Bellman方程，该方程将目标转移到最大
其中s'是下一个状态。DRL利用带权值的卷积神经网络估计动作值方程θ。因此Q(s, a, θ) ≈ Q∗(s, a) 。设训练批量大小为b，损失函数为：
式中yk为目标输出评价网络。它是根据未来预期估计来计算的。如果采样的跃迁不是飞路样本，则对(sk, ak)对的评估设为终止奖励rter。本文输入的地形图像形状为10 × 10 × 3。结构如图4所示。我们使用两个三维卷积层来提取路径图像特征。我们采用10 × 10 × 4(通道数= 4)和10 × 10 × 64(通道数= 64)的卷积滤波器在图像。
卷积层的作用是局部感知。即首先对图像中的每个特征进行局部感知，然后在更高层次上进行局部综合运算，获得全局信息。每个卷积层的计算结果都输入到池化层。池化层的主要作用是降低特征维数。在图4中，长短时记忆(long- term memory, LSTM)不仅解决了RNN不能处理长距离依赖的问题，也解决了梯度爆炸或梯度消失的问题。我们使用另外两个完全连接的层进行探索策略学习。最后，神经网络输出无人机的动作值。每个Conv或全连接层后面都有一个整流线性单元(ReLU)激活功能层，以增加非线性。每层下面的数字是多维数据集的输出数据通道。
算法4显示了我们修改后的DRL流程的工作流程。我们将迭代回合数设置为M。如图4-16所示，在状态si执行动作at，获得下一个状态tt+1和当前奖励rt。将四个元组(st, at, rt, st+1)添加到经验池D。从经验池D中取m个随机样本(si, ai, ri, si+1)，其中i = 1,2,3 ....， m，计算目标值yi。步骤20使用均方误差损失函数更新Q网络参数。我们使用记忆回放法和e − greedy训练策略控制训练样本的动态分布。在每次重复探索循环的开始，无人机被设置为一个随机的起点。它将无人机位置的随机性从整个模拟世界扩展开来，并保持了存储在内存回放中的数据分布的多样性，以供训练使用。
图4无人机覆盖导航DRL
算法4的空间复杂度与神经网络层数密切相关。因此，我们需要一层一层地分析空间复杂度。假设卷积核大小为H × W，输入通道为I，输出通道为o，卷积层滤波器总数为H × W × I。每个过滤器将被映射到O个新通道。加上每个过滤器计算的偏差。因此，参数总数为(H × W × I + 1) × O。
池化层是一个没有加权因子的固定操作。一个全连接层是一个具有(n + 1) × m参数的ninput,moutput维度的输入和输出。LSTM将维持总共4组参数，分别对应输入门、输出门、遗忘门和候选状态。因此，参数总数为4 × (nhiddenminput + n2 hidden + nhidden)。Nhidden是隐藏的大小，minput是输入的大小。
训练神经网络的时间复杂度为O(E × D∕B × T)，其中E为集，D为内存大小，B为批大小，T为单个iter的时间复杂度。
T可以继续分解为O(T)≈O(L × nlayer)， L为每一层的平均时间复杂度，nlayer为层数。L可以进一步分解为O(L)≈O(MinputNoutputHmapWmapK)，其中计算卷积层的时间假设为每层的平均时间。Minput和Noutput分别为输入和输出通道数，K为卷积核的大小，Hmap和Wmap分别为输出特征图的空间维度。
五.实验和结果
5.1地形数据采样与能见度分析
在铯平台[39]上，我们选择了N86.8◦−87.0,E27.5◦−28.02的地理位置作为地形覆盖任务的区域。我们在地平面上采样沿经轴和纬度轴的二维坐标，步长为0.628 km。我们得到了每个地形采样点对应的铯高程。每个可选的航路点都进行可见性分析。在铯上，我们使用算法1(插补可见性分析方法)得到每个可选路径点pi的可见性集vi。我们随机选取10个航路点，如图5所示。可选航路点到整个地形采样点的平均视觉距离在2000米以上。我们将有效能见度阈值设为1500 m。每个可选的路径点只能看到一些地形样本点。
5.2TK -MCTS的性能
在同一飞行地形空间下，采用不同算法验证TK-MCTS算法的优越性。我们比较了穷举法和传统的MCTS算法[40,41]的总搜索次数和有效搜索次数。从图6(a)可以看出，在相同的时间框架内，衰竭法执行的搜索范围更广。而全覆盖地形路径搜索成功率仅占总搜索量的0.0388%。传统的MCTS搜索在同期内的搜索范围最小。传统的MCTS方法在同一时间段内对全覆盖地形路径的搜索成功率要高于衰竭法。我们看到，尽管TK-MCTS方法在同一时间段内的搜索次数不是最多的，但它是找到全覆盖路径的最有效方法。全覆盖地形路径搜索成功次数占总搜索次数的47.29%。
5.3本地和全球搜索的结合
覆盖路径规划搜索的空间复杂度约为O(n!)。虽然TK-MCTS方法显著提高了模拟的有效性，但它不能在几乎无限的搜索空间中进行广泛的搜索。在普通计算机上，当搜索时间为10秒时，平均有效搜索次数为326.89。找到完整的覆盖路径是153.12倍。有限的仿真样本会给评估当前运动方向的有效性带来较大的误差。
从当前的路径点开始，我们计算时间和覆盖范围，使用穷举方法查看n步内的所有路径。
图7a显示了不同步骤对覆盖率的影响。图7a显示，仅仅增加穷举搜索的次数并不能改善模拟效果。n阶穷举法只能判断是否为局部最优解。我们不能通过增加n来模拟全局最优解。随着n步的增加，耗尽时间指数也会增加。
针对上述问题，我们设计了一种局部搜索和全局搜索相结合的方法来确定仿真奖励值。通过TK-MCTS方法，我们可以大致估计出最优的全局方向。通过n步耗尽，我们确定了最优局部解的方向。模拟奖励设计见表1。
负没有航路点可以飞到当前状态;TK−MCTS为正只有通过TK-MCTS才能获得正奖励;穷尽性只有通过穷尽性才能获得积极奖励;穷举和TK−MCTS正通过穷举得到正奖励;其他未得到仿真结果。通过穷举法，TK-MCTS并没有得到有效的路径覆盖方法
5.4DRL智能路径规划
我们从正态分布初始化每一层权重(均值0，方差0.3)，偏差设置为0.1。训练参数如表2所示。所有模型都在一个NVIDIA GeForce GTX 1050ti上使用TensorFlow进行训练和测试。batch size对训练的影响是:如果batch size过小，会导致很大的梯度变化，损失振荡，网络难以收敛;如果过大，梯度非常精确，损失振荡很小，容易陷入局部最优。大量的实践表明，当批大小在2 ~ 32之间时，总能获得最佳的训练结果。学习率对训练的影响是:太小即为收敛需要更长的时间;太大可能不会聚或损失可能爆发。初始学习率通常设置在0.01-0.001。重放存储器通过存储采样打破了数据之间的相关性。重播内存大小没有特别的要求。折现系数= 0.9，这平衡了当前和未来的奖励。
通过实验分析了DRL智能路径规划的有效性。我们从覆盖质量和路径规划质量两方面对所提出的工作进行了评估。在不同步长下，我们比较了所提算法与耗尽算法和MCTS算法的覆盖率。计算结果有助于确定合适的步长，以确保生成的路径点完全覆盖地形。
5.4.1变化步长覆盖性能
地形样本点与航路点之间的距离直接影响无人机获得的地形图像的分辨率。我们将航路点到地形采样点的视距阈值设为1000 m。无人机的总步长可以近似表示无人机执行任务的时间。目标区域的覆盖结果如图8所示。垂直轴表示给定图像分辨率要求可覆盖的区域的百分比。水平轴上的步长表示块的数量。我们在每次迭代中搜索路径点时对环境进行步进操作，并测试从1000到1900的步进大小值。图8中，无人机从不同位置出发，验证了DRL方法训练无人机智能导航的有效性。采用DRL算法、衰竭算法和MCTS算法计算不同步骤的平均覆盖率。衰竭和MCTS的搜索时间为300 s。UAV在300秒内执行给定步长的多次搜索。
图5可选航路点可见性分析示例
图6 TK-MCTS、MCTS和Exhaustion性能比较
我们可以看到，当step = 1700时，DRL方法获得的地形覆盖率可以达到100%。从1000步到1900步，DRL总能达到比衰竭算法和MCTS算法更好的覆盖效果。
此外，从1000步到1900步，MCTS算法可以获得比衰竭算法更好的覆盖效果。在初始训练过程中，DRL以每一步50%的概率选择DNN计算出的动作，并随机选择50%概率的动作。该方法对无人机在各种情况下的导航进行了充分的探索。通过实验，我们证明了TK-MCTS模拟DRL可以获得良好的学习效果。
图7穷举迭代搜索时间和覆盖范围
表1无人机状态及奖励设计
5.4.2地形平均覆盖率
在覆盖任务中，我们关注无人机的有效覆盖。所有区域的有效覆盖都要求无人机采集的每一种地形数据具有较高的分辨率。我们用热图直观地描述了DRL算法在提高无人机地形覆盖质量方面的性能。图9a-c为DRL算法的热图，MCTS算法和穷举法。我们用颜色的深浅来表示距离。颜色越深，距离越大。
横轴代表纬度，纵轴代表经度。首先，我们可以看到DRL热图图9a的颜色普遍比另外两种颜色浅，MCTS热图图9b的颜色比图9c的颜色浅。我们可以看到，通过DRL算法导航的覆盖效果，航路点到地形采样点的最大距离可以小于200 m。在MCTS算法导航的覆盖效应下，航路点到地形采样点的最大距离为600 ~ 700 m。当使用穷举法导航时，路径点到地形采样点的最大距离会变大。其次，我们看到DRL方法实现的覆盖对于每一块地形是非常均匀的。由于部分较亮，部分较暗，所以其他方法对每一块地形的覆盖效果是不均匀的。尤其是穷尽法的覆盖率解析则有很大的不同。在训练阶段，DRL使用TK-MCTS方法计算下一步的最优模拟结果。DRL可以充分考虑本地最佳和全球最佳。
表2训练参数
图8不同步长下的覆盖性能
六.结论
针对无人机在大规模复杂环境下的导航问题，提出了一种DRL框架。通过将GPS路径数据转换为图像数据，可以利用数据准确丰富的GIS作为训练环境。该方法能有效克服训练环境与使用环境不一致所造成的巨大误差。TK-MCTS搜索方法与局部搜索方法的结合，既能有效避免陷入局部搜索，又能保证在有效计算力的限制下学习最优搜索方向。
结果表明，CNNs可以从三维环境的GPS路径信息中学习重要特征，并从TK-MCTS仿真中学习导航策略。
视觉导航与GPS导航的融合是提高导航精度的研究方向。对于未知地形环境，在线三维地形生成与GPS导航相结合也是未来需要研究的重要问题。