A-Star算法在无人机路径规划中的研究

谈雅婷 吕艳辉 侯英娟

摘 要 无人机消费市场飞速上升，而无人机的技术研究中，路径规划是重要的组成部分，对周围环境建立数字地图，依据数字地图，通过A-Star算法进行路径规划，针对无人机飞行任务，寻找一条最短路径。A-Star算法将 Dijkstra 算法和BFS算法搜索策略融合，既拥有启发式算法快速搜索路径的优点，同时还能保证找到一条最短路径，但对于无人机飞行需要一定的安全距离，因此对A-Star算法进行相应改进可以很好地解决规划路径距离障碍物很近的情况。

关键词 无人机;数字地图;路径规划;安全距离

1飞行环境建模

无人机路径规划过程中，对威胁回避和地形分别考虑，这样会使路径规划算法获取环境信息时间比较长，导致整个规划过程复杂，因此，采用将无人机飞行前环境已知地形及相应威胁信息融合，简化路径规划算法，减少数字地图[1]存储空间。

1.1 基准地势模型建立

无人机路径规划问题需结合无人机飞行的真实地理环境，在路径规划之前，首先需要对飞行环境建模。构建环境模型时主要考虑山体地貌信息、基准地形信息。本文采取构建基准地形的方式如（1）所示。

（1）

为三维数字地形上某点在水平面的投影坐标，为对应的地形高程值，到是常系数负责控制基准地形的起伏状态。

1.2 模拟山地建模及威胁建模

通过信息融合的方式构建模型，用山地模型代表障碍和威胁。在无人机执行任务时，将环境中的障碍及威胁信息进行快速建模，融合到数字地图中，便于无人机进行实时的在线路径规划策略，及时规划出可行路径。构建山地模型的数学表达式如（2）所示。

（2）

为数字地图中点处的高程值，n控制山峰的个数，控制高度，为第m个山峰的中心坐标。对公式中相关变量赋值不同，可得到不同高度，数目的模拟山地模型。

2A-Star算法基本原理

A-Star算法是經典的路径规划算法之一，A-Star算法继承Dijkstra 算法的贪心性质，同时继承了最佳优先搜索策略的启发式性质，将两者结合，通过启发式函数选择代价值最小的节点作为下一节点，从而能够是其规划处一条从起点到终点最短的路径，同时具有较少的运算量。

2.1 代价函数选取

代价函数的设计在A-Star算法中起着决定性作用，节点代价计算过高或过低都会影响节点扩展时丢失本来为最优路径上的节点。A-Star的代价函数[2]通用表达式如（3）所示。

（3）

式中为起点与当前点m的代价值，为当前点m与终点的估算代价。为了计算和，需要确定起点与终点之间的距离，常见的距离算法有曼哈顿距离、对角线距离和欧几里得距离。本文研究中，将无人机视为质点，可以在其八邻域范围内搜索路径，所以采用欧几里得距离作为距离计算方法。

2.2 节点扩展与路径点确定

A-Star算法的整个规划过程可总结为：从起始点，检查八邻域范围内节点代价，不断寻找代价值最小的节点，向终点方向扩展直到达到终点。

路径规划过程表述如下：

（1）定义开启集，关闭集，起始节点为0，将起始点放入开启集，搜索领域节点，计算代价放入开启集。

（2）开启集中删除起点，将起点加入关闭集，在开启集中寻找代价值最小的函数，放入关闭集中，将最小代价节点作为当前节点，继续扩展节点，计算其邻域内节点代价。

（3）扩展当前节点，计算邻域内的所有可行节点，并且去掉关闭集中存放的节点，当开启集中没有终点时，跳转到第二步，继续搜索节点，否则，进行下一步。

（4）从终点开始回溯，通过追溯父节点指针，确定路径节点，将节点反序输出即为最终路径。

传统A-Star算法仅考虑了选择最优路径进行路径规划，但在无人机实际飞行过程中，无人机自身有一定体积，并且无人机容易受到天气因素影响，在小范围内漂移，所以为了确保无人机更安全的飞行，本文提出增加代价函数的方法，对障碍物一定范围内设置代价函数。改进 A-Star算法的评价函数之后，在原有的评价函数中增加了新的约束条件，即无人机与建筑物边缘的距离。整个路径的评价因素不再仅仅是距离的长短，而是无人机防止与建筑物擦碰最优的路径[3]。

3结束语

本文首先通过对无人机飞行环境进行建模，其次分析传统的A-Star路径规划算法，根据无人机自身体积及飞行特点，对传统算法进行增加代价函数设计，使A-Star算法从仅考虑最短路径到将路径长短为影响整个系统的关键因素，规划路径时也考虑到与障碍物之间的安全距离，从而确保规划出一条安全的飞行路径。

参考文献

[1]田疆.基于固定翼无人机的航迹规划优化模型[J].西北民族大学学报（自然科学版），2017，38（1）：7-10.

[2] 谭宝成，王培.A-Star路径规划算法的改进及实现[J].西安工业大学学报，2012，32（4）：325-329.

[3] 姚雨，李庆，陈曦.优化的A-Star算法在航迹规划上的应用[J].微电子学与计算机，2017，34（7）：51-55.

作者简介

谈雅婷（1995-），女，甘肃兰州人;学历：硕士研究生，现就职单位：沈阳理工大学，研究方向：图像处理与分析技术。