面向城市超低空物流场景的最小风险路径规划算法

程洁， 郑远， 李诚龙，3， 江波， 刘东来

(1.中国民用航空飞行学院空中交通管理学院， 广汉 618307； 2.中国民用航空飞行学院计算机学院， 广汉 618307； 3.北京航空航天大学电子信息工程学院， 北京 100191)

无人机(unmanned aerial vehicle， UAV)作为中国科技创新的重要产业，其技术日渐成熟，能够执行复杂、危险的任务，以“小、快、灵活”的优势逐渐应用于城市物流配送中[1]，在低空航空领域占有一席之地[2]。美国联邦航空管理局(Federal Aviation Administration， FAA)在107部规章中提出了轻小型无人机可在距离地面120 m高度下飞行[3]，并将120 m以下城市空域划为城市超低空空域。在120 m以下的城市超低空场景中，无人机工作环境较为复杂，使得无人机在飞行过程中具有一定失控坠落的概率，从而撞击地面的行人、车辆及关键基础设施，造成一定的财产损失。因此，路径规划是帮助无人机运行安全管理、高效完成任务的关键之一[4]。如何在一定约束条件下，快速搜索一条或多条起始点到目标位置的无碰撞安全性较高的低风险路径[5]，已成路径规划领域的研究热点。近年来，多种算法被用来解决无人机路径规划问题，其中A*算法[6]是经典的启发式搜索算法，具有计算量较小、路径规划结果较优等特点，被广泛应用于路径规划研究。

现有基于传统A*算法的改进工作主要集中于优化启发函数、提高搜索效率。Duchoň等[7]基于栅格地图对A*算法的启发函数权重系数进行改进，使改进后的算法可以适应不同场景；郑煜坤等[8]提出了一种基于“追踪”思想的改进A*算法，满足实际飞机飞行安全性需求；詹京吴等[9]提出一种基于安全考虑的改进A*算法，与动态窗口法相融合进行路径规划，可以在复杂环境中保证飞机的安全性；袁千贺等[10]提出一种基于改进A*与动态窗口方法相融合的移动无人机导航算法，引入环境信息自适应调整代价函数，提高了搜索效率；张启钱等[11]针对复杂低空物流无人机路径规划问题，提出一种改进A*算法，引入栅格危险度因子等系数，保证无人机飞行安全；王维等[12]通过估价函数进行指数衰减的方式加权减少了冗余的扩展；沈克宇等[13]针对A*算法遍历节点过多、转折角度较大的问题提出一种能自适应场景地图的改进A*算法，进而减少遍历节点数量、提高搜索效率；程杰等[14]针对A*算法在无人水面艇路径规划中由于无约束导致的安全问题，提出了一种优化搜索和平滑的A*算法，从而提高无人水面艇路径规划的安全性；除A*算法外，李少波等[15]深入调查遗传算法(GA)在机器人路径规划应用领域，阐述现阶段技术难点，并对发展趋势进行展望。从上述文献可以看出，现有研究主要以路径代价为目标函数，在安全性方面仅保证不与障碍物相撞；然而在无人机飞行过程中，还应考虑障碍物对应的地区类型。由此，无人机对地面风险等级的研究受到中外学者的广泛关注。Pang等[16]提出了一种考虑综合成本评估模型的路径优化方法，该方法能够有效降低飞行成本；Koh等[17]研究了无人机失控坠落与地面人员撞击并致死间的关系；胡莘婷等[18]建立基于城区行人安全的无人机运行风险评估模型，提高无人机在城区运行的安全性。但上述文献仅考虑了无人机运行安全性与地面区域之间的关系，没有基于城市超低空物流场景且在路径规划方面没有实际应用。

综上所述，针对现有路径规划算法无法满足超低空物流运输无人机在密集障碍物场景下进行安全轨迹规划问题，现提出一种基于120 m以下的超低空城市物流运输仿真场景的面向城市超低空物流场景的最小风险路径规划算法。

具体而言，本文研究以规划风险最小轨迹为目标，通过在飞行时避开高风险区域减轻突发情况造成的风险和影响；首先，从时间、风险两个维度对成本估计函数进行重构，兼顾航程距离和风险成本；其次，基于重构后的成本函数，提出一种适用于城市物流场景的最小风险路径规划算法，规划得到安全性较高的无人机飞行路径；最后。考虑高度层架构，基于先到先服务原则将该算法应用于多无人机场景，实现多无人机在不同飞行高度层的无冲突低风险路径规划。

1 问题描述与环境设定

安全飞行是民航无人机的生命线[19]，然而无人机所处的超低空空域的飞行环境随着无人机行业的发展逐渐呈现出复杂化、多变化的趋势，因此为确保无人机在飞行过程中的安全性，需要对路径进行合理、安全地规划。通常情况下，轻小型无人机进近与离场阶段由地面机场直接控制，而巡航阶段只在某一确定高度范围的高度层中进行[20]。在120 m以下超低空城市物流运输交通网络中，运用划分高度层的方式，可以使无人机在路径规划时选择更短直的路径，更大程度的降低拥堵的概率，有效提高无人机在飞行过程中的安全性[21]，城市空中交通高度层划分后路径规划示意图如图1[22]所示。因此，将120 m以下巡航空域划分为多个高度层，仅考虑确定高度层的巡航阶段轨迹预规划问题，更符合实际应用的需求。

首先对环境进行建模，依据文献 [23]，将空域划分为层高15 m的多个高度层，符合无人机规模、无人机间安全距离等因素，即将120 m以下的三维超低空空域划分为45～60 m、60～75 m、75～90 m、90～105 m和105～120 m 5个高度层空域，图2为划分高度层示意图。

以每个高度层的上限层作为障碍物投影面，无人机抽象为质点，在投影面中进行二维路径规划。本文主要考虑的是如何在起飞前进行预规划，因此不考虑飞行过程中的动态障碍物。首先根据栅格粒度lgrid，即栅格边长[24]，将环境划分为u×v个单元格。环境约束为

{(x，y)|0≤x≤lgridu， 0≤y≤lgridv}

(1)

式(1)中：(x，y)为栅格中心坐标；lgrid为栅格粒度；u、v为x轴、y轴对应栅格数。每个栅格状态信息表示为

图1 飞行高度层划分示意图Fig.1 Schematic diagram of flight level division

图2 飞行高度层Fig.2 Flight level

(2)

式(2)中：N(x，y)=0表示无障碍物，无人机可自由通行；N(x，y)=1表示有障碍物，无人机禁止通行；(x，y)为栅格中心坐标。

2 基于A*算法的最小风险路径规划算法

针对120 m以下的超低空城市物流运输仿真场景，如何通过改进A*算法得到无人机在多高度层基础上获得安全性较高的路径显得较为重要。本节简述了传统A*算法、改进A*算法启发函数、风险等级代价函数设计、路径评价指标4个方面，阐述了面向城市超低空物流场景的最小风险路径规划算法如何解决密集障碍物场景下的无人机路径规划问题，并在2.5节描述了本文方法应用于多无人机运行场景。

2.1 传统A*算法

A*算法是一种启发式的图搜索算法，以Dijkstra[25]启发式搜索算法为基础，其搜索框架与Dijkstra算法相同，但A*算法启发式函数优于Dijkstra算法，适用于快速搜索最短路径，并能够在多约束条件及任意形状的威胁环境下进行路径规划，特别是在大面积的地图中[26]。A*算法的核心是在候选路径点集中选择代价函数值最小的节点进行拓展，将最小值节点作为下一步拓展的节点，循环以上步骤，直到达到目标点。A*算法的启发函数[27]为

f(n)=g(n)+h(n)

(3)

式(3)中：n为当前节点；g(n)为积累代价，即从起始点到当前节点累计的实际距离；h(n)为目标代价，即从当前节点到目标节点的估计代价值。

通常情况下，g(n)使用曼哈顿距离计算，表达式如式(4)所示；h(n)运用欧几里得距离作为函数估计值，表达式为

g(n)=|xn-xs|+|yn-ys|

(4)

(5)

式中：(xn，yn)为当前点坐标；(xs，ys)为起始点坐标；(xg，yg)为目标点坐标。

2.2 改进启发函数

A*算法在路径搜索过程中，启发函数g(n)和h(n)对路径评估的影响是不同的，权重系数的变化会引起最终搜索路径的变化[28]，加权后的启发函数为

f(n)=αg(n)+βh(n)

(6)

式(6)中：α为g(n)代价的权重系数；β为h(n)代价的权重系数。α、β的取值会影响A*算法的计算效率，选择合适的权重系数十分重要[29]。根据文献[30]，当α+β=1时，能够在规划过程中平衡两种代价函数。本文考虑加权评估后的合理性，选择α和β分别为

α=e-0.1tn

(7)

β=1-e-0.1tn

(8)

将式(6)和式(7)代入式(5)，可以得到优化后A*算法的估计代价函数，即

f(n)=e-0.1tng(n)+(1-e-0.1tn)h(n)

(9)

(10)

式中：tn为位置系数，表征当前位置和起始点、目标点间的关系，由积累代价g(n)与目标代价h(n)的比值确定。

2.3 风险等级代价函数设计

传统A*算法在搜索路径时并未将与障碍物的安全距离纳入启发函数中，当障碍物较密集的区域人群也相对密集，为避免无人机在飞行过程中发生突发事件造成严重后果，在飞行前规划过程中应尽可能远离障碍物，保证无人机飞行安全与地面高密集区域的人群安全。

将无人机路径点与最近障碍物栅格中心的欧几里得距离作为安全距离，充分考虑飞机与障碍物之间的安全距离，将环境根据距最近障碍物栅格的距离划分为3个风险等级，越靠近障碍物的栅格风险等级越高，反之风险等级越低，如式(10)～式(12)所示。

(11)

(12)

(13)

式中：R(xi，yi)为栅格(xi，yi)风险等级；k为障碍物个数；risk(xi，yi，xo，yo)为栅格风险等级筛选条件；d(xi，yi，xo，yo)为安全距离，即(xi，yi)与距离最近障碍物中心坐标(xo，yo)的欧几里得距离。风险等级划分示意图如图3所示，图3中黑色栅格为障碍物，栅格中数字代表栅格风险等级。

在选择下一节点时，不同风险等级的当前节点与下一节点之间存在9种扩展情况，如图4所示。

图3 风险等级划分示意图Fig.3 Risk level classification diagram

图4 节点扩展情况Fig.4 Node expansion

(14)

与传统A*算法代价函数不同，本文将风险等级代价纳入启发函数，在规划过程中具有一定的自适应性，能够自主避开障碍物的同时兼顾飞行路径的运行风险，与传统算法仅考虑运行时间与航程有较大区别。将风险等级代价函数值纳入启发函数f(n)，优化后的A*算法启发函数W(n)为

W(n)=f(n)+γr(n)

=αg(n)+βh(n)+γr(n)

(15)

式(15)中：f(n)为估计代价函数；r(n)为风险等级代价函数；γ为风险等级代价函数值权重系数，γ根据扩展节点所在风险等级由低至高依次增大，即

(16)

式(16)中：n为G(n)的输入变量；i为扩展栅格风险等级。

2.4 路径评价指标

A*算法常使用路径代价作为评价指标[31]，但忽略了路径的安全距离，因此，本文兼顾路径的安全性，重新定义路径的评价指标，即

(17)

式(17)中：L(n)为路径总长度；T(n)为路径节点距最近障碍物距离总和。

(18)

(19)

式中：(xn，yn)为路径节点坐标；m为路径点个数；d(xn，yn，xo，yo)为(xn，yn)与距离最近障碍物中心坐标(xo，yo)的欧几里得距离；k为障碍物个数。

2.5 多无人机场景应用

针对多无人机路径规划问题，基于高度层架构及上述最小风险路径规划算法，在多无人机路径规划中兼顾路径安全性，在先到先服务的基础上，依据起飞次序规划各无人机在每个高度层中路径，并计算路径评价指标，选择最小评价指标的高度层作为无人机最终飞行高度层，即

(20)

式(20)中：ω为高度层。

实际操作中，在前序规划得到的无人机路径点纳入障碍物列表，并在无人机降落后予以删除；若后续无人机无法在所有高度层中规划得到无冲突路径，则推迟该无人机起飞时间，直至可以规划到无冲突路径时。

3 仿真结果与分析

3.1 规划区域定义

本次实验基于Python进行仿真。随着高度层增加，障碍物栅格占地图栅格比例逐渐减少，取地图栅格的20%、15%、12%、8.75%和6%作为障碍物数，与高度层45～60 m、60～75 m、75～90 m、90～105 m和105～120 m依次对应。设置场景1、场景2和场景3分别对应实际范围为1 500 m×1 500 m、2 000 m×2 000 m及2 500 m×2 500 m的场景，栅格粒度lgrid取50 m，即地图场景分别是场景1∶30×30、场景2∶40×40和场景3∶50×50。基于这3个场景，本文研究进行了3个仿真实验：实验一为相同场景下的算法对比试验，展现了本文所提方法在低风险路径规划上的优越性；实验二为本文所提方法在多无人机多高度层复杂场景下验证实验，展现本文方法在复杂城市空中交通场景下的通用型；实验三为蒙特卡洛仿真实验，验证了本文所提方法的实用性和可靠性。

3.2 实验一：优化A*算法路径规划对比实验

将原A*算法启发函数权重系数优化为动态变化，并加入风险等级代价函数。在实验中各场景中，无人机的起始点坐标均为(0，0)，目标点的坐标分别为(29，29)、(39，39)和(49，49)。在保持各项权重系数计算公式不变的条件下，在场景1、场景2和场景3下分别进行30次实验，将本文算法较原算法在地图场景中不同高度层路径规划后的安全距离和路径代价的平均增长比数据如表1和表2所示；将不同场景下本文算法较原算法评价指标的平均增长比数据如表3所示。

从表1和表2看出，与原算法安全距离与路径代价相比，优化后算法评价指标都有不同程度的增长，是由于优化后的启发函数同时考虑路径代价和风险等级，所以路径代价有小幅度增加。但从表3中看出，优化后算法的安全距离较原算法提高约60%，平均路径代价较原算法增长约14%；画出原算法与本文算法在15种不同情况下的路径代价和安全距离的对比图，如图5所示，可以看出本文算法的安全距离有大幅提升。

表1 安全距离增长比Table 1 Safe distance growth ratio

表2 路径代价增长比Table 2 Path cost growth ratio

表3 优化后平均增长比Table 3 Average growth ratio after optimization

图5 评价指标对比图Fig.5 Evaluation index comparison chart

以地图尺度30×30的场景1为例，比较原算法与改进后算法在障碍物比例分别为20%、15%、12%、8.75%和6%的5个高度层下，规划得到的路径结果，结果如图6所示。图中黑线为原A*算法全局路径规划结果；蓝线为改进后A*算法路径规划结果；黑色栅格为障碍物，栅格颜色依次变浅表示风险等级依次降低，除障碍物栅格外均为可扩展栅格。从图5中可以明显看出，改进后A*算法的与障碍物的安全距离有大幅提升。

3.3 实验二：多无人机多高度层路径规划实验

实验一已经验证了本文提出面向城市超低空物流场景的最小风险路径规划算法能够大幅提升无人机路径的安全性，而本节实验主要考虑了多无人机路径规划问题，将本文提出方法在多无人机多高度层的运行场景中进行验证。如表4所示，现有八架无人机运用于场景1中，各无人机起降点坐标、飞行时间都不相同。基于2.5节将综合权值的路径评价指标作为选择飞行高度层的依据，将前序规划得到的无人机路径纳入障碍物列表，在该无人机降落后予以删除；若后续无人机无法在所有高度层中规划得到无冲突路径，则推迟该无人机的起飞时间，直至可以规划得到无冲突路径。

图6 场景1：不同高度层的路径规划算法结果对比图Fig.6 Scenario 1:comparison chart of path planning algorithm results at different flight levels

表4 多无人机数据Table 4 Multi-UAV data

经过规划，得到上述8架无人机在不同飞行高度层的无冲突路径规划结果，即UAV-7在高度层1 中飞行；UAV-1在高度层2 中飞行；UAV-5和UAV-8在高度层3中飞行，尽管路径间存在交叉，但是在不同时通过交叉路径，不会产生冲突；UAV-2在高度层4中飞行；UAV-5在高度层5中飞行。最终路径规划结果如图7所示。

综上所述，本文所提方法不但能解决单机路径规划问题，还能应用于多无人机多高度层的复杂城市空中交通运行环境中。通过本多无人机多高度层路径规划实验可知，本文提出的面向城市超低空物流场景的最小风险路径规划算法能够在复杂场景下，将最小综合权值作为评价指标选择无人机飞行高度层，同时，在飞行前避开高密集区域，规划得到多架无人机的无冲突路径。

图7 多无人机多高度层路径规划结果Fig.7 Multi-UAV multi-layer path planning results

3.4 实验三：蒙特卡洛仿真实验

蒙特卡洛仿真法[32]是以概率统计为基础的一种仿真方法，其基本思路是通过大量的仿真实验，得到参数的统计特征，从而得到所求问题的近似值。仿真次数越多，仿真结果与实际情况越相近，蒙特卡洛仿真法的计算精度越高。因此，本次实验采用蒙特卡洛仿真实验结果证明本文算法的实用性和可靠性。

在本次蒙特卡洛仿真实验中，针对多高度层的城市超低空物流场景，随机选取各项实验参数，并在随机选取的参数中进行多次重复实验，具体实验设置如下：地图尺寸随机取值为20、30、40、50，无人机起终点在地图随机尺寸内；障碍物数量随机比例为6%～20%；无人机数量为5～8，无人机起飞时间在8:00—10:00随机选取，多无人机避障规则遵循2.5节中多无人机避障规则；该实验属于复杂仿真实验，为确保测试结果的真实性，进行多次实验并取平均值作为算法性能的统计结果，因此，本文设置1 000次蒙特卡洛仿真实验，同时设置传统A*算法在相同变量取值规则情况下的仿真结果作为对比，对比指标分别为：路径规划成功率、算法平均运行时间、距离障碍物距离，仿真实验对比结果如表5所示。

在随机选取障碍物的过程中，有几率在起点或终点周围产生环形障碍，造成无可行轨迹的情况。因此在表5中，本文提出的面向城市超低空物流场景的最小风险路径规划算法与A*算法的路径规划成功率都不为100%。同时，依据2.3节中将无人机路径点与最近障碍物栅格中心的欧几里得距离作为安全距离，由表5可知，本文算法安全距离较传统算法有大幅度提升，保证了路径的安全性。综上所述，本文提出的方法可以应用于多种城市空中交通场景，具有实用性和可靠性。

表5 仿真实验对比结果Table 5 Comparison results of simulation experiments

4 结论

从无人机飞行安全性角度出发，提出了一种面向城市超低空物流场景的最小风险路径规划算法，该算法基于传统A*算法，优化了启发函数的权重系数；将三维环境依据飞行高度划分为多个高度层，结合划分空域风险等级思想，构建风险等级代价函数，以规划风险最小轨迹为目标，从时间、风险两个维度对A*算法的成本估计函数进行重构，在尽可能避开密集障碍物的同时飞行距离最短，在无人机飞行前避开高风险区域，规划得到安全系数较高的路径，并应用于多无人机多高度层路径规划中。仿真实验表明本文优化后的A*算法与原算法相比，安全距离平均增加60%，路径代价平均仅增加约14%，路径更加合理；同时能够有效解决多无人机在复杂场景下路径规划问题，得到安全性较高的多无人机无冲突路径；通过蒙特卡洛仿真实验，对比本文算法与传统A*算法，证明本文算法具有实用性和可靠性。

本文高度层划分方式及障碍物模型为理想化情况，无人机飞行高度划分方式还在不断完善中，并且现实生活中障碍物形状多种多样，还存在动态障碍物，但以上缺陷并不影响优化后算法的可行性。因此，今后研究方向将着力于多无人机协同路径规划，更好地满足未来城市超低空物流场景的需求。