基于A星算法与人工势场法的无人机避障路径研究
摘要： A星算法和人工势场法作为如今两种最常用的避障寻路方法，都有各自明显的优缺点。本文提出了一种改进算法，将人工势场法和A星算法相结合，以人工势场法作为全局路径规划，A星算法作为局部路径规划，解决了人工势场法在避障时会出现的局部极小值、大型障碍物无法快速避障的问题，又进一步简化了A星算法扫描路径的过程。仿真结果验证了该算法的可行性和有效性，也证明了该算法具有更好的避障效果和更短的搜索时间。
关键词： 避障 人工势场法 A星算法
Abstract: The A-star algorithm and the artificial potential field method, as the two most commonly used obstacle avoidance methods, have their own obvious advantages and disadvantages. In this paper, an improved algorithm is proposed, which combines the artificial potential field method with the A-star algorithm, and takes the artificial potential field method as the global path planning algorithm and the A-star algorithm as the local path planning. The local minimum value of the artificial potential field method when avoiding obstacles is solved. The large obstacle can not avoid the obstacle quickly, which further simplifies the A star algorithm scanning path process. The simulation results show that the algorithm is feasible and effective, and that the algorithm has better obstacle avoidance effect and shorter search time.
Key words：obstacle avoidance; the artificial potential field method; The A * algorithm
0.引言
随着无人机技术的快速发展，人们对其路径规划能力有着越来越大的期望。无人机所面临的飞行环境有两种，分别为已知环境和未知环境。在已知环境中可以清楚了解障碍物的形状和位置，而在未知环境中障碍物的这些信息无法获取，需要无人机自行去探测。文献[1]提出路径规划的方法大体可以分成三类。第一类是处理已知环境的路径规划问题；第二类是基于传感器作用的局部路径规划法；第三类则是基于行为的路径规划法。对于已知环境可以人为规定一条最短最快的飞行路径，因此就不再详述。而当面临未知环境，无人机需要自主做出探测和判断，最终规划一条安全的飞行路径。
人工势场法和A星算法是现今比较常用的两种避障寻路的方法。是。它的基本思想就是在移动机器人的路径中加入两个虚拟力场。目标点给机器人一个引力，而障碍物给机器人一个斥力。机器人就在这两个力场合力作用下运动。而是一种在静态地图中寻找路径的一种方法，它由Dijkstra算法优化而来，运用来简化对地图的搜索，从而简化了路径探索的过程，达到避障寻路效果。两种算法都有各自的优点，但也存在着各自的不足。传统人工势场法将障碍物看成质点或者是形状均匀的圆，然而在现实情况中，运动的机器人所遇到的障碍物会是形状大小各异的物体，有时候很难去判断和计算斥力的方向。即使可以判断，由于机器人与障碍物之间距离不停发生变化，斥力也会相应发生各种改变，计算成本会因此变大。同时在仿真过程中，机器人的路径也会因此发生迭代现象。而A星算法相对而言，避障方法显得更加安全一些，但是多了一个扫描路径的过程。即使相对于Dijkstra算法来说，扫描过程已经相对简化很多，但是和人工势场法相比，路径扫描还是多出了很多时间和成本。如何将人工势场法和A星算法相结合起来，在保证更安全的避障的同时又可以降低不必要的成本，这成为一个亟需解决的问题。本文提出一种将人工势场法与A星算法相结合的改进算法，以人工势场法作为全局路径规划，A星算法作为局部路径规划。仿真结果显示该算法具有很强的实用性与经济性。
1.人工势场法
1.1无人机在人工势场下受到的引力
我们设定引力系数为，这个参数值由我们自己去设定。假设无人机的坐标为（x，y），终点的坐标为（），无人机在x轴方向受到的的引力为，在y轴方向受到的引力为，那么我们先去计算引力角A：
A=acrcos （1）
然后再计算出引力：
= . cosA （2）
= . sinA （3）
当然，障碍物只有在一定范围内才会对无人机产生影响和威胁。如果无人机在运动的全过程中，都要去计算每一个障碍物对其的斥力，那么计算过程会很繁琐，而且有的障碍物由于距离很远，斥力可以忽略不计。所以需要自行设置危险距离，当实际距离小于危险距离时，障碍物才会对无人机产生一个斥力。
1.2无人机在人工势场下受到的斥力
我们假设斥力系数为，无人机坐标为（x，y），障碍物坐标为（，），无人机在x轴方向受到的的斥力为，在y轴方向受到的斥力为。那斥力角R的计算公式为：
R=acrcos (4) 而斥力计算公式为：
= . cosR (5)
= . sinR (6)
1.3 人工势场法避障模型的建立
在人工势场法中需要先设定一些必要的参数，包括起点终点以及障碍物坐标点的参数，还有引力系数和斥力系数，从而计算合力及合力方向，最后判断下一步如何执行。流程图如图1所示：
图1 人工势场法流程图
Fig. 1 flow chart of artificial potential field method
从流程图可以看出，无人机每一次移动的距离都是一样的，即一个步长，而合力的作用则是告知无人机下一步的移动方向。无人机运行的步长次数由人为设定，如果设置移动次数太多，虽然无人机最后能够到达终点，但势必会在终点附近不停徘徊。因此设定当无人机离最终目标小于一个步长的时候，就可以终止整个程序。此外，设置的步长越小，无人机整个路径的计算量就会越大，但是得到的路径也会更加精确和安全。
1.4 人工势场法存在的不足
人工势场法中，无人机的运行是通过引力和斥力共同作用来完成的。如果存在一个障碍物刚好停留在无人机与终点连线的路径上，那么斥力的方向刚好与引力相反。这样无人机会面临三种情况：要么在某一时刻斥力等于引力，无人机停滞不前；要么引力大于斥力，无人机撞到到障碍物；要么斥力大于引力，无人机不停在障碍物前做往返运动。在文献[11]中提出通过计算和调整斥力引力系数范围来去避免局部极小值。文献[12]中提出加入一个填平势场来打破这种平衡。而文献[13]中提出增加一个虚拟目标点来帮助无人机摆脱极小值。可是这样解决问题的前提是障碍物相对于无人机较小，可以看作是一个质点。如果无人机遇到的障碍物相对机身较小，或者形状均匀，那么就可以很容易计算出斥力大小。但如图2所示，坐标轴左上角方格代表出发点，右上角方格代表终点，而出发点与终点之间的长方体代表障碍物，黑色障碍物相对于无人机过大，那么斥力的大小和方向就不易得到。
图2 无人机飞行地图
Figure 2 UAV flight map
2. A星算法
2.1 A星算法避障模型的建立
是当下一种很流行的算法，其探测路径的最大独特之处就是将每一个检查过的节点信息引入到全局的信息中，然后算法再对当前节点距终点的距离作出估计，将得到的信息会与其他节点得到的信息相对比，最后找到一条合适的路径。
A星算法中路径选择取决于一个最重要的公式：
F=G H （7）
其中F为无人机从起点到终点的总代价，G值是从起点到指定方格的移动代价，而H值表示这个方格到目标点的估算成本。如果H值是0，那么探测中只有G值起作用，那么A星算法就会变成Dijkstra算法。算法中设定了开放列表和封闭列表。每次探测一个方格，A星算法都会与其他方格进行比较，从而决定是将已探测的方格列入开放方格还是封闭方格。
A星算法运行流程如图3所示：
图3 A星算法流程图
Fig. 3A star algorithm flow chart
2.2 A星算法存在的不足
如图4所示，假设地图左下角黑点为起点，右上角黑点为终点，黑色长方形代表障碍物，灰色区域代表A星算法下扫描探测的区域。我们运用A星算法去探测一条可行路径。虽然相对于Dijkstra算法，A星算法有着很大的改善，但是由于启发式函数的存在，A星算法在进行探测的时候依然需要对地图进行部分扫描，而灰色的区域依然庞大。扫描区域越大，扫描的方格数越多，代表着需要计算更多部分方格的F值，并且存储到更多开放列表或者封闭列表中，这一过程依旧繁琐。
图4 A星算法下的无人机避障
Fig. 4 A star algorithm for UAV obstacle avoidance
3.A星算法下人工势场法的改进
3.1 改进算法避障模型的建立
如何在保证避开未知障碍物的前提下尽量减少其他不必要的路径探测呢？从图4可以看出，扫描探测最主要的任务就是检测障碍物并且规划出一条绕开障碍物的路径，那么在无人机检测到障碍物之前，A星算法所进行的扫描探测可以视为无用功，而只有在检测到障碍物后所进行的扫描探测才会对障碍物的避行起到作用。为了降低不必要的探测，我们完全可以用人工势场法来代替检测到障碍物之前的路径规划。在检测到障碍物之前，无人机在人工势场法下飞行成本更低，花费时间更短。如图5所示，将地图附加一个坐标系，横向向右的是x轴，纵向向下的是y轴，规定起点坐标为（0,99），终点为（99，10），实验环境如表1所示。首先运用人工势场法驱使无人机前进，当探测到障碍物的时候，设定在障碍物一个步长距离前停下，记录当前坐标。此时无人机坐标为（69,35），而图中直线代表了无人机在人工势场法下所运行的轨迹。
图5 遇到障碍物前的人工势场法寻路图
Fig. 5 path finding map of artificial potential field in front of obstacles
表1.实验环境
Tab.1 Experimental environment
|
起点 |
（0,99） |
|
终点 |
（99,10） |
|
步长 |
0.5 |
|
引力参数 |
2 |
通过人工势场法无人机很难躲开这个庞大的障碍物，此时就得使用A星算法。此时A星算法的起始点就是（69,35），通过黑色障碍物周围的灰色扫描区可以看出，此时使用A星算法可以在获得一条绕行的路线以外，扫描的区域大幅度减少，最后将存放在开放列表中的坐标连接起来则为避障路线。将两种算法相结合，得到最终的运动路径。如图6所示，蓝色连线就是最后无人机的运动轨迹。
图6 人工势场法与A星算法的结合寻路图
Fig. 6 the combination of artificial potential field method and A-star algorithm
当然，这只是一个障碍物的情况，而且这个障碍物离终点很近。但是如果障碍物离终点很远，这个时候单纯只是使用上面的思路，在成功绕开障碍物后，A星算法依旧在运行，不必要的扫描依然会需要大量的成本和时间，如图7所示。A星算法在绕过障碍物之后依然在进行探测，此时灰色扫描区域依旧很大，然而绕过障碍物后依然进行的探测是不必要的，而且还加大了成本。那么该如何尽量去减少这些不必要的探测呢？
图七 障碍物离目标点较
剩余内容已隐藏，支付完成后下载完整资料
毕业论文（设计）
英文翻译
原文标题 基于A星算法与人工势场法的无人机避障路径研究
译文标题 Research on obstacle avoidance path of UAV based on A * search algorithm and artificial potential Field method
学生姓名 陈辰 学号 20158313016
专业年级 2015自动化(专转本)
指导教师 李磊
二Ｏ一九 年 四 月 二十八 日
Research on obstacle avoidance path of UAV based on A * search algorithm and artificial potential Field method
Chenchen ，Lilei，Wangyunchang
Abstract: The A * search algorithm and the artificial potential field method, as the two most commonly used obstacle avoidance methods, have their own obvious advantages and disadvantages. In this paper, an improved algorithm is proposed, which combines the artificial potential field method with the A * search algorithm, and takes the artificial potential field method as the global path planning algorithm and the A * search algorithm as the local path planning. The local minimum value of the artificial potential field method when avoiding obstacles is solved. The large obstacle can not avoid the obstacle quickly, which further simplifies the A * search algorithm scanning path process. The simulation results show that the algorithm is feasible and effective, and that the algorithm has better obstacle avoidance effect and shorter search time.
Key words: obstacle avoidance; the artificial potential field method; The A * algorithm
0. Introduction
With the rapid development of UAV technology, people have more and more expectations for its path planning ability. There are two kinds of flight environments faced by unmanned aerial vehicles (UAVs), one is the known environment and the other is the unknown environment. The shape and position of obstacles can be clearly understood in a known environment, and in an unknown environment, this information about obstacles cant be obtained, so it is necessary for UAV to detect it by itself. The methods of path planning proposed in reference [1] can be divided into three categories. The first is to deal with path planning in known environments; The second kind is the local path planning method based on sensor action; The third category is behavior-based path planning. The shortest and fastest flight path can be artificially specified for a known environment, so its not going to go into detail. When facing the unknown environment, the UAV needs to make its own detection and judgment, and finally plan a safe flight path.
Artificial potential field method and. A * search algorithm is two kinds of obstacle avoidance and routing methods which are commonly used nowadays. Artificial potential Field method is a New obstacle avoidance method for path Planning proposed by Khatib. Its basic idea is to add two virtual force fields to the path of the mobile robot. The target point gives the robot a gravitational pull, while the obstacle gives the robot a repulsion. The robot moves under the combined action of these two force fields. A * search algorithm is a way to find a path in a static map. Its optimized by the Dijkstra algorithm., The heuristic function is used to simplify the search of the map, thus simplifying the process of path exploration and achieving the effect of obstacle avoidance and routing. Both algorithms have their own advantages, but there are also their own shortcomings. The traditional artificial potential field method regards an obstacle as a particle or a circle of uniform shape. However, in reality, the obstacles encountered by moving robots will be objects of different shapes and sizes. Sometimes its hard to judge and calculate the direction of the repulsion. Even if it can be judged, because the distance between the robot and the obstacle is constantly changing, the repulsion force will change accordingly, and the calculation cost will be increased as a result. At the same time, in the process of simulation, the path of the robot will also occur iterative phenomenon. Compared with the A * search algorithm, the obstacle avoidance method is more secure, but there is an additional scanning path process. Even though the scanning process has been relatively simplified compared with the Dijkstra algorithm, the path scanning still has a lot more time and cost than the artificial potential field method. How to combine the artificial potential field method with the A * search algorithm to ensure safer obstacle avoidance while reducing unnecessary costs has become an urgent problem to be solved. In this paper, an improved algorithm combining artificial potential field method with A * search algorithm is proposed. the artificial potential field method is used as global path planning and A * search algorithm as local path planning. The simulation results show that the algorithm has strong practicability and economy.
1. Artificial potential field method
1.1 Gravity of UAV in artificial potential Field
We set the gravity coefficient to , and this parameter value is set by ourselves. Assuming that the coordinates of the UAV are (x, y) and the coordinates of the end point are （）, the gravity of the UAV in the x-axis direction is , and in the y-axis direction is , so lets calculate the gravitational angle A first:
A=acrcos （1）
Then calculate the gravity:
= . cosA （2）
= . sinA （3）
Of course, obstacles only have an impact and threat on drones in a certain range. If the UAV has to calculate the repulsive force of ea
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[19281]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
