赵其定，汪夏荣

（1.江西经济管理干部学院 飞行技术学院，江西 南昌 330088；2.深圳市大疆创新科技有限公司，上海 200120）

0 引言

无人驾驶飞行器（Unmanned Aerial Vehicle,UAV）也称为无人机，近年来的使用率增长非常迅速，在很多领域都有应用，如电力巡检、摄影摄像、应急救援、地形探测、智慧警务等等。在无人机的研究中如何规避障碍，寻找安全的飞行路径也是无人机研究的热门领域之一。覆盖路径规划（Coverage Path Planning,CPP），在无人机飞行区域中为其建立一条路径能够探索该区域中关键的位置点，CPP 主要的关注点是时间效率和覆盖的完整性。CPP 工作主要有以下几个方面的性能指标，如路径长度、任务完成时间和转弯次数，同时这些指标与无人机能量消耗有关。

覆盖路径规划CPP 的主要挑战之一是区域中出现障碍物或突发的威胁建立路径。在规划区域中可能存在障碍物和禁飞区域区，障碍物可能是静态的或移动的，如树木和鸟类。突发性的威胁是无人机在事先不知道的情况下出现影响无人机安全的物体，不同的路径规划方法主要依赖于区域场景的二维或三维信息来构建飞行轨迹。

目前三维路径规划的最新方法是利用三维视图来检测和避开障碍物，这种方法没有考虑无人机在避障过程中的资源消耗。在本文的工作中，提出了一种具有能量感知的三维避障方法（Energy-Aware Grid Based 3D Obstacle Avoidance,EGTOA），使用基于网格技术在三维视图中避开障碍物的能力为无人机区域覆盖规划合理路径。

三维路径规划有着明显的优势，与二维路径规划不同，二维路径规划有图形上的限制。二维解决方案不仅受到无人机尺寸、重量和飞行机制的限制，还应该考虑航路长度、区域覆盖率和能量消耗间的最优化解决方案。无人机在覆盖任务中的转弯次数也是一个需要考虑的问题，转弯次数尽量减少，能够节约更多的无人机能源消耗。

本文提出了一个基于能量网格的覆盖路径规划和一个三维避障技术，结合了包括障碍物在内区域的顶视图和正面视图，在包括障碍物的区域内利用该算法顶视图离线生成第一条路径，然后用场景的正视图重新规划。文中处理的障碍物是静态障碍物，这些障碍物的位置对无人机来说是预先知道的，目标是以最短的路径和最少的转弯次数避开障碍物，还要考虑到两个主要因素，就是无人机的能源消耗和完成时间。

1 基于能量感知的三维网格避障

1.1 基本原理

基于网格原理的避障是通过移动来避开包含障碍物的整个单元格而移动到另一个相邻的网格单元。如图1所示，第二行中的障碍物1 是通过移动到单元格的边缘来避免，但是在第三行中，另一个障碍物2 是通过绕行来避开障碍物。这两种方式中绕道而行的转弯次数少，路径也相对较短。在2.2 节中，展示了采用这种方法进行障碍物的规避，由于利用二维顶视图并不提供最短的路径或确保最佳的覆盖范围，通过利用三维信息扩展了基本方法，依靠该区域的正面视图来决定障碍物的位置和形状以及要绕行的路线从而降低转弯次数及距离。

图1 两种不同的避障方式

1.2 系统准备工作

在网格避障原理中，区域被划分为网格单元，每个网格单元有一个矩形的形状这是无人机需要在飞行过程中覆盖的区域。为了达到良好的区域覆盖，无人机的飞行轨迹是一个环形轨迹。在飞行过程无人机投射的飞行轨迹覆盖相应的单元格。如图2所示，深色代表自由区域，浅色是障碍区域，初始的计划轨迹从网格单元边缘开始，并穿过单元格的中心。

图2 无人机覆盖路径俯视图

在图1 中，用G表示一个网格单元，用P表示经过G中心的垂直平面，同一网格列上的两个连续平面P和P距l 个单位，其中l 是G的长度。在本文中，假设障碍物的位置是固定且已知的，通过三维信息来避免它们，利用二维图所规划的原始路径，无人机将按照该路径飞行，并在包含障碍物的单元前，无人机捕获前面区域的图像，以便决定无人机接下来的飞行路径。

如图3所示，假设在平面中有障碍物，图中虚线代表图3 中的原始路径，实线代表新的轨迹，是无人机根据障碍物的位置。这项工作的目的是为无人机确定一个新的位置并且在维持总路径和能量不变的情况下使得无人机的能量消耗最低。

图3 无人机飞行正视图

2 扫描尺寸及热图的生成

2.1 扫描框架尺寸的确定

无人机在飞行过程中要确定正视图的框架尺寸，这样在避障过程中才通过能量感知网格进行判断定位无人机的下一个位置。如图4所示三维视图中，（i，j）平面表示无人机飞行区域俯视图，（i，k）平面表示表示无人机飞行的正视图。

图4 无人机在A 点的正面视图

确定无人机在（i，j）平面上的位置后，通过规划确定无人机的最小和最大允许高度范围分别表示为和，这个范围将指定面对区域的框架尺寸，把表示为扫描的正面框架，假设无人机位于点，高度为h。

如图5所示，框架由矩形ABCD 表示面积为×，其中和分别矩形的长度和宽度，矩形的长=（-），假设主视图是以相机角度=62°拍摄的在这个角度之外检测到的任何物体都不会对无人机造成任何危险。点是点的投影，这两点实际上都是平面上两个连续网格单元的中心（i，j），为了计算扫描框架的长度（BC）和宽度（AB），先要确定从矩形金字塔的尺寸（ABCDP），通过采取等腰三角形（PFH），其角度为，高度=PM。边PF（表示为）可以从以下方程（1）计算出来，因为PM 是已知的，并且等于俯视图网格单元的长度。

图5 无人机扫描区域尺寸

因此，帧的长度可以按以下方式计算。

现在已经知道了框架的尺寸，下一步是将转换为基于网格的形式用表示，中每个单元的尺寸与无人机的高度和宽度相适应。v表示为位于网格中第行和第列的单元，其尺寸为×（为长度，为宽度）。

2.2 热图的生成及无人机避障路径

在本节中，目的是确定无人机必须移动的最近位置，以便于避开途中的障碍物，主要步骤如下：

步骤1：生成帧的热图，举例来说，如图6所示，显示了一个20×40 一棵树的热图。

其中v代表中的一个网格单元元素，Γ表示网格中零单元的集合。

Γ表示为网格中一组非零单元（Γ=Γ）：

如图6所示，是框架中树状热图的例子，无人机的位置是（12，13），图中虚线方框代表边界单元，而实线方框代表解决方案的单元。

图6 框架中树状热图

步骤2：代表的是无人机在框架中的投影，检查它在网格中的位置，如果位于Γ中的一个单元，那么无人机的道路上就没有障碍物，当前路径就不会被修改。如果位于一个非零单元（即Γ中的一个单元），那么障碍物就存在于无人机的飞行路径上，此时无人机飞行的路径就需要修改，同时需要检查周围网格列表，为无人机找到一个合理路径避开障碍物。用N来表示一个网格单元v的邻居，它是直接围绕着v的单元的列表。

用B表示为Γ中与最近的非零单元格见公式（7），称为边界单元，将（，）表示为两点和之间的欧几里得距离：

为了找到距离v最接近和B，使得v属于Γ，用S的集合它的解，其中表示直接包围B低能量值网格的数量：

为了找到列表S的解，从开始以反向螺旋循环模式如图7所示，直到找到一个包含v=0 的外围单元。

图7 反向螺旋循环模式寻找外围为0 单元

如图6所示，无人机的投影位于网格中的单元格（12，13）。一组边界单元B由实线框表示（|B|=3），可能的解S是由实线框表示（|S|=3），需要注意的是，如果S=null，则规划必须增加框架尺寸。

步骤3：从S中选择最便捷的解决方案，表示为=B∪S；如图8所示，将每个单元格分成四个子单元格，如图9所示，这是为了更好地了解障碍物的位置，以确定无人机移动最近的下一个位置。单元格细分后，一个新的解集⊂S生成，如图10所示，深色背景区域代表无人机必须移动到的单元格以遍避开障碍物。

图8 获取的周边网格

图9 细分后的热图新的解决方案集

图10 细分后的热图—阴影部分是最佳解决方案

如图11所示的流程图展示了工作中的主要步骤，算法检查当前无人机在面对区域中的单元格位置，如果位于一个零值单元中，它将成为无人机的位置，否则该算法将检查邻近的单元，以找到最近的非零值单元格。

图11 障碍物检测与规避算法流程图

在周围寻找可能解S的列表，从开始以螺旋模式包围网格周围，解决方案列表通过筛选以选择最接近的可能解决方案单到，这可能是下一个无人机的位置。

为了确定周围障碍物的边界，找到边界单元的列表，表示为B，将S和B组合在一个分组框中，并决定无人机是否会安全地通过求解单元，对单元进行细分，这有助于找到比细分之前找到的更接近的更好解决方案。将每四个零值子单元分组在一个顶点中（表示为），这些顶点的列表表示为（S）0，稍后使过滤以找到确切的无人机位置（表示为Sposition）。

3 评估指标和结果

在无人机飞行避障过程中，沿无人机路径具有不同物形状的障碍物体，需要评估无人机的工作效果，主要从能源消耗、完成时间、路径长度和转弯角度进行评估。

3.1 评估指标

网格中的单元可以被看作是一个类似图的结构（，）中的顶点，其中是顶点列表，是边的列表。表示的是细分前的网格单元中心，将其视为图中一个顶点，如图12所示，每个顶点在笛卡尔平面上都有坐标。

图12 无人机转弯角度

3.1.1 转弯角度

无人机的功耗受转弯角度的影响，在飞行期间转多少个弯是一个主要问题，假设无人机从顶点到并且将在处转弯，稍后前往，如图12所示。转弯角计算公式为：

其中cos（∠）是根据中的余弦定律计算的。因此可以找到角度从顶点之间的欧几里得距离，公式如下。

其中e=（v，v）是两个顶点v和v之间的欧几里得距离。

3.1.2 完成时间

优化轨迹长度和任务完成时间对于节能至关重要，无人机的路径规划技术，任务完成时间主要是飞行时间和依靠公式11 来表示为的完成时间：

其中为路径长度，为无人机速度，而v 为转弯次数，Φ为第次转弯的角度，为无人机旋转速率。

3.1.3 能量消耗

无人机的总能量成本表示为是行驶总距离所消耗的能量，表示（）和执行转弯所消耗的能量表示为（）：

其中是单位距离消耗的能量，是每角度消耗的能量，在这项工作中，假设=0.116 4 kJ/m 和=0.017 3 kJ/°。

3.2 结果

假设一个情景飞行的区域是100 m×115 m，俯视网格是6 行10 列，如图13所示，图中无人机在虚线内覆盖飞行，四角形标记的单元包含障碍物，将总的轨迹路径将与基本方案中获得的轨迹路径进行比较。对于框架的尺寸，假设中每个网格单元为0.7×0.5，为40 行×24 列，假设无人机位于10.2 m 高处，面对中的（12，13）单元，下一步将介绍能量图和无人机在每个障碍物上的位置。

图13 飞行区域网格图

第一步，假设障碍物为一棵高度为15 m 的树，如图6所示。无人机在障碍物的投影为（12，13），无人机选择通过网格解决方案如图14所示，执行水平左转弯3°，垂直向下转3°，然后减掉11.57 m 的距离。初始无人机的位置和新无人机的位置Sposition，为了到达树后的初始高度，执行6°的垂直回升，跨越同样的距离。

图14 无人机在障碍物1 的投影位置热图

障碍物二假设无人机位于障碍物棕榈树的网格单元（13，5）处，无人机的投影是（13，5）如图15所示。图15 显示了细分后的能量图，最近的边界单元是（13，1），无人机通过该单元时进行了16°的垂直向上转弯，然后减掉11.985 m 的距离，接着是一个垂直向下的转弯33°，无人机返回到障碍物后面的初始高度，画实线的单元代表解决方案单元即最终的无人机位置Sposition。

图15 无人机在障碍物2 的投影位置热图

障碍三假设无人机飞到树的一个地方，该地方的无人机位置投影是（8，9），最近的边界和解决方案单元格如图16所示，线框代表解决方案单元格即最终无人机位置Sposition。无人机穿过障碍物，首先进行水平转弯2°，然后垂直向上转弯2°，减去11.506 m，然后垂直向下转弯3°，回到障碍物后面的初始高度，再转一圈，回到初始方向。

图16 无人机在障碍物3 的投影位置热图

障碍四假设障碍物是建筑物的一部分，热图如图17所示。无人机的位置投影是单元格（6，8），细分单元格（3，8）被选为解Sposition，虚线单元代表边界集B，实线方框单元代表解单元S，最终的无人机位置在图17 中表示实线方框。无人机将通过该单元，它进行了一个28°的水平转弯，减少了13.07 m 的距离，然后又进行了一次57°的水平转弯，之后返回到初始路径方向。

图17 无人机在障碍物4 的投影位置热图

在任务结束时，基本方法的结果路径如图18所示，采用EATOA 获得的总路径如图19所示。

图18 基本方法无人机总路径

图19 EATOA 方法无人机总路径

这些路径是从俯视图看到的，采用不同轨迹规避算法的总轨迹路径。从不同的角度来看，工作轨迹计划与基本方法进行了比较，无人机速度是8 m/s，无人机旋转速度为30 °/s，如表1所示，显示了EATOA 比基本方法的完成时间缩短12.40%，能量减低了10.89%。应该注意到三维路径比基本方法中的二维路径短4.1%，总转角减少25.1%。

表1 基本方法和EAEO 方法仿真结果参数

仿真结果表明在三维路径中，与基本方法获得的结果相比任务完成时间平均减12.40%，无人机能量消耗节省了10.89%。应该指出的是，速度和旋转率之间的变化对完成任务的时间有影响，但对能耗没有影响。能源增加10.89%，这是因为和是平均总能耗，偏差的产生是由于距离、转弯的平均能耗。

4 结论

在路径规划任务期间提出了一种基于能量感知网格的3D 避障。该算法被命名为EATOA 并且有两个阶段，它首先使用区域顶视图网格，然后扫描该区域的正面视图以检测无人机路径上的障碍物，通过得到的能量感知网格算法在线重新规划路径，寻找合理路径绕过障碍物。结果显示EATOA方法能够节省能量和完成时间。在未来的工作中测试算法在嘈杂环境和动态障碍中的实际飞行情况，还打算利用动态规划来优化算法提高算法的性能。