位置: IT常识 - 正文
【路径规划】A*算法方法改进思路简析(路径规划原理)
发布时间：2024-01-16推荐整理分享【路径规划】A*算法方法改进思路简析(路径规划原理)，希望有所帮助，仅作参考，欢迎阅读内容。
文章相关热门搜索词:路径规划的基本流程和方法,路径规划步骤,路径规划原理,路径规划什么意思,路径规划教程,路径规划最新算法,路径规划教程,路径规划 rrt,内容如对您有帮助，希望把文章链接给更多的朋友！
A算法作为经典的传统路径规划算法，在计算全局最优路径有着较好的性能，在机器人导航等领域上起着关键作用，针对这点出发，将对A算法进行基本功能实现，以分析其优缺点，并在此基础上进行改进。改进的内容为，将针对特定地图的相关特点，设计合理的预估函数，设置了包含代价函数和启发函数的权重函数，其次，将传统的8方向搜索降为5个方向，舍弃无用的方向，然后在此基础上，对开放列表的数据结构进行堆优化，并且采用双向A算法进一步提高计算速度，并针对实际机器人运动过程中的路径不平滑问题采用贝塞尔曲线进行平滑化处理。经过仿真，改进后的算法在路径计算时间，路径平滑度都有改善，并进一步验证了A算法的可行性。这是我第一次尝试写文章，因此更像是一个笔记之类的东西，难免有错误与不妥之处，敬请指出与海涵。
1. A*算法的总体流程A*算法作为Dijkstra算法和BFS的结合算法，其与这两种算法的区别就是采用了启发函数，这也是这个算法的核心。 启发函数的形式：
*f(n)=g(n)+h(n)* (1)*f(n)*表示结点的综合优先级，在选择结点时考虑该结点的综合优先级； *g(n)*表示起始点到当前结点的代价值； *h(n)*表示当前结点到目标点的代价估计值，也就是预估函数。 为了对这两个值进行相加，这两个值必须使用相同的衡量单位，以下的讨论也都是在此基础上进行的。 为了便于讨论与理解，下面的地图的形式都会已二维数组的形式表示。因此，为了简单预估当前节点到目标点的代价，采用较多的是欧几里得距离，即
d(n)=√(〖(be.x-end.x)〗^2+〖(be.y-end.y)〗^2 )
A*算法通过设置两个列表openlist和closelist来对地图中的点进行控制。算法伪代码如下：
将起始点s加入到开启列表openlist中重复以下过程： a) 遍历开启列表openlist，寻找F值最小的结点，并将其作为当前要处理的结点 b) 将要处理的结点移到关闭列表closelist c) 对当前结点的8个相邻结点的每个结点： i. 如果他是不可抵达的或者已经在关闭列表closelist中，忽略； ii. 如果他不在开启列表openlist中，将其加入openlist，并把当前结点设置为其父节点，记录当前结点的F、G、H值； iii. 如果他已经在开启列表openlist中，检查这条路径（即经由当前结点到达相邻结点）是否更好，用G值做参考，更小的G值表示这个更好的路径，如果是这样，将其父节点设置为当前结点，并重新计算他的G值和F值，如果开启列表openlist是按F值进行排序，改变后需要重新排序。 d) 停止，当 i. 终点加入到了开启列表openlist中，此时路径已经找到 ii. 查找重点失败，并且开启列表openlist中是空的，此时没有路径保存路径，从终点开始，每个结点沿着其父节点移动直到起点。2. A*算法的改进2.1 启发函数的选择与优化在A算法的总体流程中提到，A算法的核心就是启发函数，根据式(1),其中的g(n)作为起始点到当前点的代价，其值一般是固定的，所以围绕启发函数的优化一般都是围绕h(n)即预估函数展开的。
2.1.1 预估函数的选择前面提到，对于二维网格地图，一种常用的预估函数就是应用欧几里得距离。但是，需要注意的是，如果机器人的运动并不是无限制的，或者说是不允许无角度限制的进行运动，例如：当机器人被设定为只允许沿八方向运动时，此时欧氏距离并不能准确描述当前点到终点的运动代价，因为机器人不允许按这种方式直接抵达，而此时采用切比雪夫距离则可以更准确的描述运动代价。 切比雪夫距离公式：
*d(n)=max(abs(be.x-end.x),abs(be.y-end.y))*同样的，如果当机器人只允许沿四个方向运动，那么曼哈顿距离更能准确描述运动代价。 曼哈顿距离公式：
*d(n)=abs(be.x-end.x)+abs(be.y-end.y)*如果h(n)能够更为准确的描述当前点到终点的代价，那么就可以使在依赖启发函数f(n)进行选点时更加准确。 所以，针对实际的工作需求，确定合适的*h(n)*是十分重要的，预估函数越贴近实际的路径代价，其选点准确度越高，但也需要注意h函数的复杂程度，过于复杂的预估函数会极大的提高计算量，造成运算速度减慢。
2.1.2 为启发函数增加权重系数关于预估函数另一个方面的优化是改进启发函数的权重系数，对于A算法的基本原理，不难将其理解为迪杰斯特拉算法和BFS的综合应用， 其中Dijkstra算法能通过比较最优的实际代价来有效的找到当前的最优路径或是其大致方向，而BFS则可以快速扩展当前点的周围节点。 简言之，Dijkstra算法的特性是一定会找到最优路径，但速度很慢。而BFS则是运行速度很快，但是不能保证结果一定是最优路径。再通过观察这两个算法的原理，Dijkstra算法主要要求的是已计算的路径的代价。而BFS考察的是还有多少步到达终点，所以不难发现可以将启发函数与这两种算法进行对应，Dijkstra算法对应的就是代价函数g(n)，而BFS对应的是预估函数h(n)。 再回到我们对启发函数的定义，不难发现启发函数就是代价函数与估计函数1：1的和，但是，如果我们更改实际代价与预估代价的权重，就可控制A算法更偏向于实际代价或是预估代价，例如将代价权重改为2：1，即f(n)=2g(n)+h(n)，此时，f(n)会更偏向描述实际代价，也就是会更优先考虑当前路径已造成的代价，所以f会更贴近于Dijkstra算法，当我们推广这个结论，当g(n)>> h(n)时，就相当于f(n)只考虑实际代价而完全不考虑预估代价，即退化为Dijkstra算法。反之，若g(n)的权重系数小于h(n)的权重系数，则会优先考虑预估代价，做同样的推广，当h(n)>> g(n)时，A算法就会退化为BFS。结论如表1。
因此，调整实际代价与预估代价的权重，可以有效地减少搜索点，提高搜索速度。 为了便于考虑，我们可以将启发函数改为如下形式，即在预估函数前增加一个系数w，从而改变启发函数的权重。 f(n)=g(n)+wh(n) (2)* f(n)=g(n)+w*h(n) (2)
进一步的，我们不可能只考虑搜索速度而不考虑规划的路径，此时就考虑使用动态加权的方式，以原本的启发函数h(n)为判断依据，我们把它
上一篇：使用vue,实现前端导入excel数据(vue前端怎么运行)
下一篇：【2022.3】尚硅谷Vue.js从入门到精通基础笔记（理论+实操+知识点速查）(尚硅谷百度贴吧)
