基于改进A*算法的物流无人机航迹规划研究

陈继伟，包长春，赵子恒

（内蒙古工业大学 航空学院，内蒙古 呼和浩特 010051）

0 引言

随着科学技术和人民生活水平提高，无人机不仅广泛应用在航拍、特技表演等领域，而且应用在物流配送领域，具有配送效率高、成本低、适应性强等突出优点，在低空飞行中不易受复杂路况影响，可实现较快速度运输，极大节约了人力成本。

无人机航迹规划主要指无人机根据相关地图信息计算出一条从起点位置到终点位置最优、安全可行的路径［1］。常用全局路径规划算法［2-3］包括RRT 算法［4］、遗传算法［5-6］、蚁群算法［7-8］、Dijkstra 算法［9］、D*算法［10］、A*算法［11-12］等。其中，RRT 算法搜索速度快，但路径通常远离最优路径；遗传算法、蚁群算法在收敛速度方面相对较慢；D*算法在动态环境中的搜索效果非常好，但在静态全局环境下搜索效果不如A*算法；A*算法结构简单、搜索效率高，在静态全局环境下能得到最优解［13］，但路径规划需要一直查询Openlist、Closelist 中的节点，并对其进行插入和删除操作，随着地图信息增多，搜索节点大量增加，将使得算法运算时间较长［14］。

为此，相关学者针对A*算法的问题提出了很多改进方法。Korf［15］提出融合A*算法和迭代加深算法优化状态判重和估价排序，提升了算法效率。Duchon 等［16］采取一种新的节点搜索方法提升路径搜索速度。高民东等［17］采用多邻栅格距离公式和改进双向时效的方法提升路径规划效率。王文明等［18］构建正六边形栅格地图，修改算法的邻居剪枝和强迫邻居判断规则，提升路径规划的质量和效率。辛煜等［19］利用无限领域的思想解决A*算法的八领域搜索方向问题。

研究发现，现有路径规划算法具有各自优势，但均存在一定缺陷。例如，蚁群收敛速度慢，易陷入局部最优；遗传算法可获得最优解，但计算量大，因此不适用于大型实时性地图。为此，本文根据A*算法优点对其进行改良，具体为对搜索策略、启发函数、起点搜索方向和搜索方法进行设计，使改进算法在物流无人机航迹规划方面具有更优路径、更短的搜索时间。

1 算法基础

1.1 A*算法

A*算法是一种基于栅格的启发式搜索算法，结合Dijkstra、BFS 算法的理论优势，按照f(n) 值从小到大排序Openlist 的节点，选取代价最小的节点作为下一个父节点，循环处理该步骤直至搜索到终点位置完成路径规划，最终生成规划路径。A*算法的评价函数为：

A*算法的基本流程如下：

步骤1：创建、初始化Openlist、Closelist 集合，将起点位置放入Openlist。

步骤2：计算Openlist 中所有节点的f(n)值，按照f(n)值排序Openlist的节点，将f(n)最小的节点设为当前节点。

步骤3：搜索当前节点周围8 个方向的邻域节点（见图1），将处理后符合要求的节点加入Openlist，并将该节点加入Closelist。

Fig.1 Search direction图1 搜索方向

步骤4：判断当前节点是否为终点位置，如果是终点位置则开始溯源每一个节点的父节点直至起始位置，连接所有父节点就是最终规划路径，如果不是终点位置则继续执行步骤2、步骤3。

1.2 跳点搜索算法

Harabor 等［20］基于A*算法的路径规划策略，通过减少搜索过程产生的大量中间节点，从而减少计算量的全局路径规划，提出跳点搜索（Jump Point Search）算法。JPS 算法的规划策略包含跳点筛选规划和评价函数。

1.2.1 自然邻域节点

在栅格地图中，JPS 算法搜索方向分为水平、竖直和斜向搜索，如图2 所示。水平搜索时，x节点是由其父节点（4号节点）扩展得到，当x节点的八邻域节点无障碍物时，x节点扩展的5 号节点为其自然邻域节点；斜向搜索时，x节点由其父节点（6 号节点）扩展得到，当x节点的八邻域节点无障碍物，则x节点扩展的2、3、5 号节点为其自然邻域节点。

Fig.2 JPS algorithm search direction图2 JPS算法搜索方向

1.2.2 强制邻域节点

在栅格地图中，强制邻域节点搜索方向同自然邻域节点相同，如图3 所示。水平搜索时，当x节点的八邻域节点有障碍物，扩展的3 号节点为其强制邻域节点；斜向搜索时，当x节点的八邻域节点有障碍物，扩展的1 号节点为其强制邻域节点。

Fig.3 Mandatory neighborhood nodes图3 强制邻域节点

1.2.3 跳点

JPS 算法规划路径时，当x为当前点，p(x)为x的父节点，搜索方向为水平、竖直或斜向，满足以下3 个条件之一即为跳点：①节点x为终点，则x为跳点；②节点x至少有一个强制邻域节点，则x为跳点；③斜向搜索时，按照x节点水平或竖直方向能到达跳点，则x为跳点。

2 改进A*算法

在较大范围无人机物流配送环境，从郊区仓库投送物资到城区投送点的过程中，大部分为空旷区域，而到投送终点附近存在大量建筑或其它不可穿越的障碍，使用A*算法规划路径存在计算量巨大、规划实时性差等问题。

为此，本文根据无人机物流配送飞行路线和环境特点设计算法，在A*算法搜索策略的基础上融入JPS 算法，并设计起点搜索方法和改进评价函数，从而提升A*算法路径搜索性能。

2.1 融入JPS搜索策略

A*算法搜索过程会对每一步符合要求的邻居节点加入Openlist，然后循环排序并选取Openlist 中节点代价最小值进行节点搜索。随着地图增大，算法计算量将呈指数增长，极大降低了算法的实时性。如图4所示，A*算法搜索过程中加入了Openlist 中的37 个节点，融入JPS 算法的搜索策略可使A*算法搜索时先筛选符合要求的跳点，再将跳点放入Openlist 列表，算法只需处理Openlist 中少量的跳点即可实现路径搜索。如图5 所示，JPS 算法的搜索过程中加入了Openlist中的8个节点。

Fig.4 A * algorithm search process图4 A*算法搜索过程

Fig.5 Search process of JPS algorithm search strategy图5 JPS算法的搜索策略搜索过程

2.2 设计起点搜索方法

当使用JPS 算法的搜索策略搜索时，起点作为当前节点进行搜索时无法判断当前节点的搜索方向，因此会对水平、竖直或斜向8 个方向进行跳点搜索。当起点位置附近环境障碍物很少时，会消耗大量时间在8 个方向搜索跳点。为了解决该缺陷，本文设计了一种起点搜索方法，将起点的非障碍物八邻域节点加入Openlist，然后计算起点到终点直线方向的角度，根据角度范围选择8 个方向中最接近的方向作为起点搜索方向，如图6所示。

Fig.6 Starting point search direction图6 起点搜索方向

2.3 改进评价函数

A*算法的评价函数由实际代价函数g(n)和预计代价函数h(n)组合而成，如式（1）所示。h(n)常用的预计代价函数包括曼哈顿距离（见式（3））、欧几里距离（见式（4））、切比雪夫距离（见式（5））、Octile 距离（见式（6））等，其中(x1，y1)为当前点坐标，(x2，y2)为目标点坐标。

h(n)函数是A*算法的核心，当h(n)小于等于实际代价时，算法能保证寻找到最优路径，但运算时间较长。当h(n)大于实际代价时，算法无法保证寻找到最优路径，但运算时间很短。为此，本文根据这个特性设计一个权重值w乘以h(n)以调节预计代价值。由图7 可见，在此类栅格地图中使用Octile 距离公式（见式（6））更符合要求。

Fig.7 Euclidean distance and Octile distance图7 欧氏距离和Octile距离

2.4 改进A*算法

改进A*算法基于A*算法结构和JPS 搜索策略，融入跳点搜索算法的搜索策略的目的是减少A*算法搜索过程中产生的大量中间节点；设计起点搜索方法目的是减少起点在空旷区域搜索的时间，结合这两种改进策略能明显缩短算法的搜索时间。当算法规划的预计代价h(n)小于等于实际代价时，算法保证能寻找到最优路径，改进评价函数通过设计一个权重值w乘以调节预计代价值，从而平衡算法搜索时间并判断是否为最优路径。本文将3 种方法结合构成改进A*算法，如图8所示。

Fig.8 Flow of improved A * algorithm图8 改进A*算法流程

创建Openlist 和Closelist 两个列表，设置起点、终点坐标和权重值w改进A*算法的步骤如下：

步骤1：初始化Openlist、Closelist，将起点加入Openlist。

步骤2：将起点周围8 个方向非障碍节点加入Openlist，计算起点得到终点直线方向，选择8 个方向中最接近的方向作为起点搜索方向。

步骤3：选取起点作为当前节点，按照起点搜索方向改进A*算法搜索跳点，若有跳点将其加入Openlist，并将起点从Openlist中移除，然后加入到Closelist。

步骤4：按照f(n)值从小到大排序Openlist 节点，选取f(n)最小值作为当前节点。

步骤5：判断当前节点是否为目标节点，若是将转到步骤10，否则从当前节点开始扩展搜索。

步骤6：改进A*算法搜索一步，寻找跳点。

步骤7：是否寻找到跳点，若找到将跳点加入Openlist。

步骤8：将当前节点从Openlist 移出，然后加入Closelist。

步骤9：转到步骤4。

步骤10：回溯目前最短路径，寻路完成。

3 仿真验证与分析

物流无人机实际配送环境属于三维环境，但对大范围三维环境进行建模较为困难、计算量大、对仿真计算平台要求高。二维环境是三维环境的分支，可在降低仿真平台要求的同时，准确获得算法的各项比较数据，并且本文算法应用场景主要在固定高度进行无人机实时规划及动态避障，因此选取在二维环境下对规划算法进行仿真。

为了验证改进A*算法与原始A*、JPS算法的优势，分别在不同尺寸的栅格地图进行仿真分析，实验计算机操作系统为Windows 10，运行内存为16 GB。

首先，建立一个50×50 的栅格地图，仿真中将物流无人机视为一个质点，初始点设置为（15，15），目标点设置为（49，49），权重值w=1。保持地图障碍不变，分别使用A*算法、JPS 算法和改进A*算法进行实验仿真（见图9-图11），实验数据如表1所示。

Table 1 Path planning data of three algorithms in 50×50 map environment表1 3种算法的路径规划在50×50地图环境下的数据

Fig.9 Path planning of A* algorithm in 50×50 map environment图9 A*算法在50×50地图环境下的路径规划

Fig.10 Path planning of JPS algorithm in 50×50 map environment图10 JPS算法在50×50地图环境下的路径规划

由表1 可知，保持预计代价小于等于实际代价时，改进A*算法在生成路径长度上保持了A*算法的最优路径，起点搜索方法和JPS 算法搜索策略使改进A*算法在搜索时间上相较于A*算法、JPS 算法减少90.33%、55.51%。仿真结果表明，改进A*算法显著提升了搜索效率，实现了路径优化目标。

下一步，在仿真中建立一个100×100 的栅格地图，将物流无人机视为一个质点，初始点设置为（30，30），目标点设置为（99，99），权重值w=1。保持地图障碍不变，分别使用A*算法、JPS 算法、和改进A*算法进行实验仿真（见图12-图14），实验数据如表2所示。

Table 2 Path planning data of three algorithms in 100×100 map environment表2 3种算法的路径规划在100×100地图环境下的数据

Fig.12 Path planning of A* algorithm in 100×100 map environment图12 A*算法在100×100地图环境下的路径规划

Fig.13 Path planning of JPS algorithm in 100×100 map environment图13 JPS算法在100×100地图环境下的路径规划

Fig.14 Path planning of improved A* algorithm in 100×100 map environment图14 改进A*算法在100×100地图环境下的路径规划

由表2 可知，在地图变大的情况下，改进A*算法依然在生成的路径长度上保持了A*算法的最优路径，并在搜索时间上相较于A*算法、JPS 算法分别减少97.01%、54.35%。仿真表明，地图变大后改进A*算法依然能显著提升搜索效率，实现路径优化目标。

4 结语

本文通过融入JPS 算法搜索策略，设计起点搜索方法和改进评价函数，提出一种改进A*算法。仿真表明，改进A*算法相较于A*算法、JPS 算法，既能显著减少搜索时间，又能保持A*算法的最优路径，在更复杂或更大尺寸地图环境下算法优势更明显，也可应用于港口、工厂等场景下的移动机器人路径规划领域。

然而，改进A*算法的路径规划目前并未进行优化，未考虑无人机转弯半径、航程等因素，后续将对算法进行优化，以进一步增加无人机在实际飞行中的适应性。