基于改进A*算法的物流无人机航路网络协同规划

王非，张洪海，冯讴歌，任真苹，钟罡

（南京航空航天大学民航学院,江苏 南京 211106）

引言

智能化的快速发展使无人机慢慢走入了大众的视野，无人机的生产和运行成本低廉、机动性和可操作性高、无需人员随机运行的特点都使其在诸多领域有着巨大的发展潜能［1］。同时，随着互联网时代的到来，网购成为了一种备受欢迎的购物方式，物流配送的需求也越来越大。但由于物流运输的目的地往往较分散，运输链末端“挨家挨户”式的配送方式耗费了大量的资源，亟需探索低空空域的潜力，改善“最后一公里”的货物运输问题［2］。受疫情影响，无接触配送日渐流行，而无人机的运行特点与无接触配送的物流需求十分契合，因此研究无人机物流运输也顺应了物流运输行业的发展趋势。

航路网络作为无人机在空域内实现飞行活动的载体，可以使相同起降点的无人机以规定的路径进行飞行，有效躲避障碍物及禁飞区，确保飞行的安全；同时，限定的飞行路线也使无人机以“流”的形式在系统中运行，便于管理人员在系统运行时对物流无人机进行监视和管控。因此，研究物流无人机航路网络的规划方法对推动无人机物流运输的发展具有重大价值。

对于物流无人机航路网络的划设，国内外学者的研究多集中于无人机路径规划领域。Damilano等［3］强调创建路由是无人机任务分配的核心步骤，并以最短时间、最小距离、最小风险等作为无人机飞行路由的优化目标。Yang等［4］基于高斯过程，利用快速搜索随机树的方法开发了一种无人机路径规划模型，该模型可用于无人机在未知环境中进行地形探索和路径规划，但其在大面积规划时算法复杂度过高，且输出路径并不能确定为最优解。Jayaweera等［5］为解决无人机在执行侦察探测任务时路径规划的问题，基于改进的人工势场法建立了一种支持“展望覆盖”的无人机三维路径规划模型，并验证该模型在无人机动态路径规划问题中的优越性。吴振等［6］以山区环境为模拟场景，考虑到无人机的飞行行为约束，提出精英池的概念以降低最优解丢失的概率，采用改进的遗传算法对无人机进行路径规划。徐晨晨等［7］将A*算法融入到蚁群算法中，开发出一套可以快速收敛的规划方法。Jason等［8］基于A*算法，以最短距离为目标函数，设计了基于A*算法的无人机路径规划器，并分析了不同启发函数对算法速度和准确度的影响；宋宇［9］对A*算法进行优化，通过几何法将传统A*算法规划的折线拐角优化为弧形拐角，并验证了该方法对缩短路径长度的有效性。张洪海等［10］考虑到最小步长、无人机飞行行为限制等约束，对A*算法进一步改进，综合航程代价、高度代价和危险度代价提出了一种城市区域物流无人机路径规划方法。此外，也有一些研究侧重于无人机航路网络的构建，Mcfadyen等［11］认为构建航路网络的关键是寻找合适的网络节点，以无向图的形式组建了类似于地面道路网的无人机运行网络；李姗等［12］考虑无人机运行风险，提出了一种基于改进元胞自动机算法的无人机航路网络，但并未考虑物流仓库与用户取货点这一典型的物流运输场景。

本文选取“物流仓库——取货点”间物流运输作为典型研究场景，结合城市低空的复杂飞行环境，以保障物流运输安全性和高效性为目标，提出一种城市区域物流无人机航路网络构建方法，以获得便于监控、易于管制的无人机配送航路。

1 航路环境建模

1.1 任务假设

针对某城市物流配送区域，已知物流仓库与用户取货点位置，需规划一距离短、冲突少、风险小的无人机航路网络，供无人机从物流仓库携货物出发运往用户取货点并在卸货后空机返回。假设无人机为可垂直起降的多旋翼无人机，航路网络设计时采用分层航路，即除在起降场区域无人机不调整其飞行高度层，飞行高度保持不变，如图1所示。

1.2 运行环境构建

基于任务假设，无人机仅在其起降区域进行爬升和下降操作，其余飞行阶段均在一二维平面内进行。假设该二维平面长度为Length、宽度为Width的矩形，将该矩形以粒度为lg的方形栅格进行分割，可得到u×v个栅格，其中u=int(Length/lg)，v=int(Width/lg)，int()为取整函数，栅格中心点为可选航路点。

在城市区域中，存在高大楼宇等地形障碍物禁飞区、政策性禁飞区以及事故危害性过高禁飞区，在规划无人机飞行航路时应严格避开此类区域。划设禁飞区时应确保实际禁飞区覆盖区域相对严格禁飞区域存在一定的安全裕度，即设定一定范围的禁飞区保护区［13］。同时，为防止物流无人机运行故障导致不必要的损害，在规划航路时应尽量避免飞跃人流密集区及交通主干路等地面活动较多的危险运行区。为定量描述空域特征，可为不同特殊区域的栅格赋予不同栅格危险度值，如表1所示。

表1 栅格危险度值

2 基于改进A*的航路网络协同规划算法

2.1 传统A*算法原理

由于无人机载重及运输距离限制，本文所研究的物流仓库与用户取货点间的货物运输场景覆盖范围较小、地点复杂度较低，可参照多航路协同规划的结果优化生成航路网络。A*算法作为被广泛应用于路径规划领域的启发式算法，通过估价函数f(x)判断航迹点的优劣，引导算法快速收敛，即：

式中g(x)为实际代价函数，表示无人机飞行起点S至当前航迹点Px的实际代价；h(x)为启发函数，表示当前航迹点Px至无人机飞行终点E的预估代价。

使用A*算法进行寻路时，无人机仅可由当前栅格中点向周围8个栅格中点移动，具体的行进方向如图2所示。

2.2 基于改进A*的航路网络协同规划算法设计方案

2.2.1 估价函数

（1）代价函数

在同一个高度层内运行的无人机，假设其起点S坐标为(X0，Y0)，路径规划终点E坐标为(Xn，Yn)，路径中经过某点Px的坐标为(Xx，Yx)，考虑具体代价函数如下：

式中CL(x)和CD(x)分别表示起点S至当前点Px的实际航程代价及危险度代价，可分别表示为：

式中k为危险度惩罚系数；di为栅格的危险度；li为无人机在相应栅格内行进的距离。

（2）启发函数

欧氏距离常被用来表示两点间的直线距离，是A*算法中经常使用的启发函数形式。本文的启发函数取当前点Px和终点E间的欧式距离，表示为：

式中Xx和Yx分别为当前栅格点的横纵坐标。

2.2.2 约束条件

（1）最小航段长度约束

无人机在配送货物的过程中，由于转弯、机动、气象等原因其运动轨迹无法与规划的路径严格重合，且运输过程中无人机的地理位置、速度等信息都是实时变化的。但由于监视系统的传输存在延时，无人机做出姿态改变也需要一定的时间，因此需要为无人机预留出一段距离使其能在这段时间内保持直飞但不至于影响其执行运输任务。这段距离定义为最小航段长度，路径规划的各航段应满足：

式中li为各航段的长度；lmin为最小航段长度。

（2）最大载重约束

由于无人机的动力有限，物流无人机运输可配送的货物重量也需要控制在一定范围内，过重的货物可能会导致无人机在运输过程中难以控制飞行轨迹、缩短无人机最大飞行航程，甚至无法正常配送。因此，对于无人机的载重W应满足：

式中Wmax为无人机的最大载重。

（3）最大飞行航程约束

虽然无人机具有体积小、重量轻的优点，但也正因如此，无人机的动力和运行距离是十分有限的。在对无人机进行路径规划时，需要确保无人机有足够的动力将货物送达目的地并空机返回。对于飞行航程L的约束如下所示：

式中EUAV为无人机电池容量；WUAV为无人机空重；γ为无人机单位重量单位距离的能耗；ll为送货去程各航段的飞行航程；lr为送货返程各航段的飞行航程。

（4）最大转弯角度约束

在物流配送的过程中，为满足配送的需求可能会出现无人机转弯角度过大的情况，但考虑到无人机的真实运行情况，过大的转弯角度无法在实际运行中成功执，因此无人机的转弯操作应满足：

式中θmax为系统允许的无人机最大转弯角。

2.2.3 初始航路协同规划

在对物流无人机航路网络进行协同规划时为往返航路分配不同的飞行高度层。同时，为便于监控管制并防止去程和返程的无人机发生故障时互相影响，尽量保证往返航路之间存在一定的水平安全距离。因此可按照如下规则进行航路网络协同规划：对所有去程航路进行航路规划并设置一定宽度的运行保护区；在规划返程路径时，去程路径的运行保护区同样被视为危险运行区，应尽量绕飞。保护区宽度需满足：

式中Smin为无人机运行的最小水平间隔。

航路保护区示意图如图3所示。

对各起降点使用上述方法进行往返航路协同规划，即可得到物流无人机初始航路网络。

2.2.4 航路网络优化

（1）航路平滑处理

如图2所示，由于A*算法寻路的方向限制，输出的往返航路可能会存在不必要的飞行转弯，此类转弯需对其进行平滑处理。在平滑时，应确保平滑后航路的总体走势与A*算法的输出结果保持一致，因此仅对受限于A*算法巡路方向导致的不必要转弯进行优化，此类转弯应符合：

式中Δl为航段的长度；lg为栅格的边长；Δang为前后两航段的方向变化。

并且，在对航路进行平滑时，仍要确保每条飞行路径的运行安全，航路的危险度代价不可增加，表示为：

式中R为所有航路的集合；CrDsmooth为某航路平滑后的危险度代价；CrD为该航路的初始危险度代价。

当航路中的某连续航段满足航路平滑条件时可对该弯折航段取其首尾，以一条直线进行连接，如图4所示。判断连接后的航段危险度代价是否增加，若危险度代价未出现增加则将此部分更新为平滑航段，若危险度代价增加则仍使用原航段。

（2）航路网络合并和重规划

为简化航路网络的结构，对不满足安全间隔（无人机不可在其内并排运行）的航段进行合并处理，此类航段应满足：

式中Δdmin为两待合并航段间的最小距离；ΔANG为两待合并航段的夹角；ANGmin为最小可合并夹角。

在对无人机航路网络进行合并时可能会牺牲网络局部的最优性来换取网络的整体优化，但过分增加某航路的飞行距离是不可取的，因此应限制：

式中lrmerge为合并后的航路长度；α为可接受的航路长度负优化最大比重。

一般情况下城区某区域内存在一物流仓库与多用户取货点，去程/返程航路呈辐射状分布。在进行航路网络合并时，对往返航路均进行取货点至物流仓库方向的合并条件搜索，如图5。由于使用此方向搜索时各航路均终止于物流仓库，因此当某两航段满足合并条件时可对其所属航路的后续所有航段进行合并。

设两待合并航段为较短航段m（属于航路a）和较长航段n（属于航路b），延伸m-1航段，若其能与n航段相交，则以该点为航路合并交点；若不能相交，则将航段n的起点与航段m的起点连接，以该点为航路合并交点，如图6所示。对于合并后航路的选取，为防止选择某一航路的后续航段导致另一航路的过度负优化，本文选择在交点处再次使用A*算法计算交点至终点的最优路径，将平滑后的计算结果作为合并点的后续航段。

（3）物流仓库终端区处理

无人机在起降场的起降方式也是建立航路网络时应考虑的重要问题。基于起降场在网络中的重要程度和进出起降场无人机飞行活动的复杂度，可将物流仓库视为高级起降场，将用户取货点视为普通起降场。普通起降场的无人机起降需求较少，因此对于普通起降场不需额外规定起降方向，无人机按照其既定飞行方向即可进行顺向起降。高级起降场处无人机起降方向众多，起降需求较大，但考虑到起降空域有限，不同起降方向的无人机运行时可能会存在互相干扰的情况，导致无人机在终端区内运行混乱。类比民航飞行的进近方法，将高级起降场一定范围内划设为终端区，并在终端区内设置多个起降走廊口和起降航线。起降航线应位于不同方向且彼此间隔，无人机根据其原本飞行航路选择距离负优化最小的起降走廊CORR：

式中disc1～disc2分别为终端区外待处理航路沿运行方向第一个航路点与可选取的四个走廊点的距离。

终端区形态如图7所示。

将物流无人机航路网络中各航路终端区外的第一个航路点与其选用的走廊口进行连接，即可完成对无人机航路网络终端区的处理，在航路网络运行时无人机可在终端区内按照起降航线进行排序起降。

2.2.5 算法实现

基于改进A*的航路网络协同规划算法主要分为两部分实现：首先基于不同的无人机物流需求使用改进的A*算法进行多航路协同规划；然后根据航路平滑、合并等优化准则对协同规划的结果进行优化从而得到最终航路网络，算法具体流程如下：

Step1：选择物流运输区域，对区域内的地理环境进行栅格化处理，标记危险栅格和禁飞栅格，统计物流无人机运输需求起降点对。

Step2：选取一对未规划去程航路的需求点对，以物流仓库为起点S，以取货点为终点E，转向Step3；若无未规划点对，转向Step6。

Step3：对 于 起 降 点S和E，建 立OPEN和CLOSE列表，将起点S作为父节点，计算起点S周围各栅格点的g(x)，h(x)，f(x)，并将这些栅格点加入OPEN列表中。

Step4：执行下述步骤：

Step4.1：弹出在OPEN列表中f(x)最小的栅格点P，将此栅格点P作为下一路径点，并放入CLOSE列表中。

Step4.2：判断P点是否为终点E，若P为终点则转向Step5，否则转向Step4.3。

Step4.3：检查P点相邻的栅格点，若相邻栅格点未在OPEN列表中，则将其加入OPEN列表，并将点P作为新的栅格的父节点；若相邻栅格点已在OPEN列表中，则检查当前路径代价是否最小。

Step4.4：重 新 计 算g(x)，h(x)，f(x)，返 回Step3.1。

Step5：存储算法得到的最优路径和最终代价，若正规划去程航路，则转回Step2；否则转向Step9。

Step6：遍历所有去程航路，对航路网络进行平滑、合并及终端区处理。

Step7：若经过Step6后航路网络未发生变化则转向Step8，否则转回Step6。

Step8：为所有去程航路设置宽度为Wprotect的保护区，统计无人机运输返程需求点对。

Step9：选取一对未规划返程航路的需求点对，以用户取货点为起点S，以物流仓库为终点E，转向Step3；若无未规划点对，转向Step10。

Step10：遍历所有返程航路，对航路网络进行平滑、合并及终端区处理。

Step11：若经过Step10后航路网络未发生变化则转向Step12，否则转回Step10。

Step12：为往返航路设置不同的飞行高度层并布置到相应场景中，算法结束。

算法流程图如图8所示。

3 仿真与分析

3.1 仿真实验环境

为验证本文提出的物流无人机航路网络规划算法的合理性和有效性，选择南京航空航天大学将军路校区为仿真实验场景，选取校区菜鸟驿站为物流仓库，学生宿舍及部分距仓库较远处为用户取货点，各起降点的地理位置信息如表2所示。

表2 起降点地理位置信息

划设校区内高楼为障碍物禁飞区、校区图书馆为行政禁飞区、高速公路为事故危害过高禁飞区，同时划设人流密集危险区及主干道路危险区，各特殊区域具体划设情况及起降点分布如图9所示。图中红色区域为禁飞区，橙色区域为危险区，蓝色区域为可穿越禁飞区的飞行通道，其余区域为自由空域。

各仿真参数设置如表3所示［10，13-14］。

表3 航路网络仿真参数

3.2 仿真结果分析

使用基于改进A*的航路网络协同规划算法对区域中的1个物流仓库及7个用户取货点进行航路网络规划，算法输出的优化航路网络如图10所示。

图中蓝色路线为送货去程路线，红色路线为空机返程路线。可以看出，算法生成的航路网络很好的实现了绕开高大建筑、间隔往返路径、合并相似路径、连接起降程序的需求。为进一步验证航路网络协同规划方法的有效性和优越性，采用A*算法直接规划得到的航路结构如图11所示。

对比表4中使用A*算法直接规划的航路与使用优化算法协同规划的航路，基于改进A*的航路网络协同规划算法输出的各航路长度较A*算法直接规划平均减少7.6%，转弯点数量平均减少59.3%，航路代价平均减少13.0%。对比图10和图11，A*算法直接规划输出的航路构型在物流仓库处复杂交错难以区分，存在多处交叉，且存在“X”型的交叉航路，不同航路的交叉互相影响，不同路线的无人机在其中执行任务时易互相干扰，不利于无人机的调配；协同规划算法输出的航路结构更为简单，只存在少量“Y”型汇聚/发散航路，不同路线的无人机执行任务时更易调配，能够高效承载无人机在其内执行物流配送任务。

表4 规划航路主要参数对比

4 结语

为推动无人机物流运输的发展、保障物流无人机在执勤过程中有序运行，本文提出了一种基于改进A*的航路网络协同规划算法。该算法以协同规划的形式，相比各需求点间独立规划在规划航路的长度、转弯点数量及运行带加上都更具优势。仿真实验表明，使用协同规划算法规划的航路长度平均减少7.6%，转弯点数量平均减少59.3%，航路代价平均减少13.0%。同时，协同规划输出的航路网络结构更为简洁，不存在相互影响的多交叉航路，易于对在航路网络中执行物流运输任务的无人机进行管控。