随着无人机城市低空场景的应用需求日益增长，提出规模化的路径规划方法，应对低空空域空地要素复杂交互、飞行风险分布不均的环境特点，实现无人机安全高效运行已成为研究的热点与难点^{[1 − 2]}。其中，空域网格化技术是构建结构化低空空域的基础性技术，也是无人机路径规划的前置步骤，合理准确的网格化方法是路径规划研究的关键。

三维空间的建模方法主要包括几何建模法、拓扑建模法和栅格法。其中栅格法因其适用于复杂空域环境而被广泛应用于城市无人机路径规划研究，该方法将环境空间分解为若干个不相交的单元，每个单元作为一个栅格，通过赋予各栅格属性从而实现空域的划分与计算^[3]。代表性研究包括：Han等^[3]基于全球细分网格GeoSOT-3D模型，使用优化的栅格法实现无人机的室内路径规划，有效解决了室内死区的路径规划问题；李翰^[4]针对城市区域的物流无人机配送安全避障与飞行效率问题，引入了栅格危险度以区分栅格的差异性，构建了城市区域物流无人机的路径规划模型；Lv等^[5]为了减少栅格数量，提出了一种高度降维的三维环境建模方法，有效提升了路径规划的计算效率。

然而，均匀密度的立方体栅格法并不适用于现阶段城市无人机起降场终端区的航路规划需求。其一，根据《城市场景轻小型无人驾驶航空器物流航线划设规范》^[6]，无人机起降场终端区上方为圆形管制区，内设进离场点和等待点，立方体栅格的设置不符合实际需求。其次，无人机的进离场可视为由进离场圈向起降场终端区的汇聚过程，且不同汇聚阶段对栅格的密度需求不同，均匀密度的栅格不符合实际情况^{[7 − 8]}。以上问题导致现有的栅格化空域构建方法无法克服求解效率与环境描述精度之间的矛盾。因此，本文针对无人机起降场终端区的航路规划，提出了基于柱坐标系的可变密度栅格法，旨在节省计算时间资源，优化求解路径。

1.   求解方法

基于直角坐标系的传统栅格法通过对$ x $方向、$ y $方向及$ z $方向进行限制来确定空域范围，而基于柱坐标系的可变密度栅格法则是通过对径向和纵向进行限制来确定空域范围的。针对上述两坐标系限制空域范围方式的区别，本文采用$ \mathrm{A}^* $算法^{[9 − 10]}和遗传算法^{[11 − 12]}作为航路规划算法基础，分别设计了基于$ \mathrm{A}^* $算法的柱坐标系可变密度栅格法和基于遗传算法的柱坐标系可变密度栅格法。

1.1   构建空域模型

据《城市场景轻小型无人驾驶航空器物流航线划设规范》^[6]可知，无人机起降点上方空域根据具体垂直距离划设不同半径的等待圈和进离场圈，进离场圈半径大于等待圈，且两者圆心投影重合，等待点和进离场点分别分布于等待圈和进离场圈上，如图1所示。

图  1  无人机终端区航线组成示意图

Figure  1.  Schematic diagram of route composition of UAV terminal area

下载: 全尺寸图片 幻灯片

传统栅格法基于直角坐标系构建空域模型，如图2（a）所示，将空域分割为等大、规则的立方体栅格，并根据环境特征及路径规划需求设定栅格大小及密度^[13]。多无人机由进场点到等待点的飞行航路可近似为多点由大半径向小半径圆的汇聚过程，在无人机不断靠近等待圈的过程中，无人机、建筑及交通要素分布更加密集，空域情况逐渐复杂。若以等待点为标准，采用细粒度的立方体栅格虽可实现空域环境的准确描述，但将导致计算量剧增；而若以进场点为标准，采用粗粒度的立方体栅格虽可提高数据处理效率，却难以实现空域环境的精确刻画，导致空域资源浪费。综上分析，传统栅格法无法克服规划效率与环境描述精度冲突的矛盾。本文针对传统栅格法弊端，提出了基于柱坐标系的可变密度栅格法构建空域模型。如图2（b）所示，该模型以进离场圈及等待圈的圆心投影为柱坐标系原点，水平面过原点的法线方向为$ z $轴方向，将空域以径向、周向、纵向等间距划分，由$ z $轴向外栅格密度递减，实现空域的发射状分割。模型中各栅格的位置用 $ (r,\theta ,z) $ 表示，其中$ r $为径向坐标，$ \theta $为由径向坐标轴逆时针转过的方位角坐标，$ z $为纵向坐标。在风险计算时，将涉及障碍物的栅格属性设为1，代表禁飞区；无障碍物的栅格属性设为0，代表可飞行区。

图  2  栅格法空间分割图

Figure  2.  Space segmentation diagram by grid method

下载: 全尺寸图片 幻灯片

1.2   基于$ \mathit{\mathrm{A}}^{\mathit{*}} $算法的柱坐标系可变密度栅格法

在柱坐标系下基于$ \mathrm{A}^* $算法实现路径规划，为避免在搜索子节点的过程中，由于子节点与父节点之间跨越了径向轴而被判断为越过飞行限制区，并标记为超出空域范围而不被选取。本文通过改变周向坐标，使子节点的周向坐标回归到空域范围，防止错误判断。具体方法为：设定周向坐标编码范围为[0,周向等分数)，若子节点周向坐标为−1，更新其为周向等分数减1；若子节点周向坐标为周向等分数，则更新其为0，由此使周向形成闭合连续的空域。

设计基于$ \mathrm{A}^* $算法的柱坐标系可变密度栅格法的估价函数$ f\left(n\right) $如下所示。

式中：$ f\left(n\right) $为无人机由起点经当前航路点到终点的估价函数；$ g\left(n\right) $为由初始节点到当前节点的实际代价；$ h\left(n\right) $为当前节点到目标节点的估计代价；$ ({r}_{0},{\theta }_{0},{z}_{0}) $为初始节点，即无人机起点；$ ({r}_{i},{\theta }_{i},{z}_{i}) $为当前航路点；$ ({r}_{e},{\theta }_{e},{z}_{e}) $为目标节点，即无人机终点。

1.3   基于遗传算法的柱坐标系可变密度栅格法

遗传算法在种群初始化时，通过不断插入两不连续栅格的中点栅格使路径连续，直至找到初始连续路径，完成种群初始化。针对直角坐标系与柱坐标系构建空域模型方法的不同，本文设计了适用于柱坐标系的可变密度栅格法的中点栅格选取方法。本文规定两不连续栅格的周向夹角为以周向坐标小的栅格为基准，逆时针转向周向坐标大的栅格的角度。为避免两不连续栅格周向夹角大于π而导致插入栅格并非最优选择，本文通过先判断再选择的方法确定插入的中点栅格，具体公式如下所示。

当两不连续栅格周向夹角小于π时，

当两不连续栅格周向夹角大于π时，

式中：$ ({r}_{i},{\theta }_{i},{z}_{i}) $为当前栅格的坐标；$ ({r}_{i+1},{\theta }_{i+1},{z}_{i+1}) $为下一栅格的坐标；$ ({r}_{\mathrm{n}\mathrm{e}\mathrm{w}},{\theta }_{\mathrm{n}\mathrm{e}\mathrm{w}},{z}_{\mathrm{n}\mathrm{e}\mathrm{w}}) $为新插入栅格的坐标；num为周向等分数。

2.   仿真结果与分析

2.1   仿真环境及参数设置

本实验使用python语言，在PyCharm上搭建仿真环境。仿真实验根据规范设定在进离场圈径向600 m、高度75 m处均匀分布24个无人机临时终端区空中停靠点，设定在等待圈径向30 m、高度45 m 处均匀分布8个无人机等待点开展实验，以长方体表示障碍物，构建了无人机进近航路规划环境模型，如图3所示。

图  3  无人机终端区空域环境模型示意图

Figure  3.  Schematic diagram of UAV terminal area airspace environment model

下载: 全尺寸图片 幻灯片

拟以基于直角坐标系的传统栅格法和基于柱坐标系的可变密度栅格法分别构建空域模型。采用直角坐标系的传统栅格法时，设定将三维空间按$ x $方向、$ y $方向、$ z $方向以$ 10\;\mathrm{m}\times 10\;\mathrm{m}\times 10\;\mathrm{m} $的大小划分空域，实验空域被分割为约$ 9\times {10}^{4} $个栅格；采用柱坐标系的可变密度栅格法时，将三维空间按$ r $方向、$ \theta $方向、$ z $方向分别以$ 10\; \mathrm{m}\times \left(\dfrac{360}{80}\right)^{ \circ} \times 10\; \mathrm{m} $的大小划分空域，实验空域被分割为$ 3.84\times {10}^{4} $个栅格。进一步，分别基于$ \mathrm{A}^* $算法和遗传算法进行仿真实验，以验证本文方法的有效性。仿真实验中，设定无人机的动作方向为10个方向，分别为以无人机为中心的平面邻域的8个方向以及上、下2个方向。其中，基于遗传算法的实验，其具体参数设置如表1所示。

表  1  遗传算法主要参数

Table  1.  Main parameters of GA algorithm

参数	符号	参数值
种群大小	$ {\rm{popsize}} $	200
迭代次数	$ {\rm{maxGen}} $	200
交叉概率	$ {p}_{c} $	0.7
变异概率	$ {p}_{m} $	0.7
选择比例	$ \alpha $	0.7

下载: 导出CSV 

| 显示表格

2.2   仿真结果及分析

实验仿真结果如图4、图5所示，表2为航路规划所用计算时间及所得的总路径长度。

图  4  基于$ \mathrm{A}^* $算法的航路规划结果图

Figure  4.  Path planning result diagram based on $ \mathrm{A}^* $ algorithm

下载: 全尺寸图片 幻灯片

图  5  基于遗传算法的航路规划结果图

Figure  5.  Path planning result diagram based on genetic algorithm

下载: 全尺寸图片 幻灯片

表  2  仿真实验结果比较

Table  2.  Comparison of simulation experiment results

使用方法	计算时间/s	总路径长度/m
基于$ \mathrm{A}^* $算法的直角坐标系传统栅格法	3.764	15180.36
基于$ \mathrm{A}^* $算法的柱坐标系可变密度栅格法	0.655	14534.92
基于遗传算法的直角坐标系传统栅格法	417.078	15281.36
基于遗传算法的柱坐标系可变密度栅格法	117.937	15084.78

下载: 导出CSV 

| 显示表格

仿真结果表明，传统方法与本文提出的方法均可完成无人机起降场终端区的航路规划。对比航路规划结果，本文所提方法相较于直角坐标系传统栅格法，其路径平滑度得到提升。对比表2结果，基于$ \mathrm{A}^* $算法，柱坐标系可变密度栅格法比传统栅格法的航路规划效率提高了82.60%，路径总长度缩短了4.25%；基于遗传算法，柱坐标系可变密度栅格法比传统栅格法的航路规划效率提高了71.72%，路径总长度缩短了1.29%。

3.   结束语

针对无人机起降场终端区采用传统栅格法规划航路时，规划效率与环境描述精度无法兼顾的问题，本文提出了一种基于柱坐标系的可变密度栅格法，并将该方法应用于$ \mathrm{A}^* $算法、遗传算法，对无人机起降场终端区的航路规划进行仿真实验。结果表明，本文提出的面向无人机起降场终端区的柱坐标系可变密度栅格法，能有效应用于无人机的进近航路规划。本文方法在实现无人机起降场终端区附近环境细致描述的同时，能提高路径平滑度与规划效率，缩短路径长度，解决了传统栅格法无法兼顾规划效率与环境描述精度的研究难题。