• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

(三)【机器人路径规划】Astar算法

人工智能 二进制人工智能 2416次浏览 0个评论

Aster(A*)算法

Aster算法是在Dijkstra算法基础上发展出来的,是在静态路径中用于求解最优路径有效的直接搜索算法,比dijkstra算法多了一个启发式的搜索函数,也就是通过一个代价函数来确定搜索方向(从起点开始向周围扩张,通过代价函数,计算得到周围每个节点的代价值,选出最小代价节点作为下一个扩展点,重复这个过程直到到达目标点。)。

算法对比:

(三)【机器人路径规划】Astar算法

A ∗ 算法的代价函数f(n)表示为:

(三)【机器人路径规划】Astar算法

例子:要求机器人从起始点绕过障碍物到达目标点,这里我们使用 A*算法寻找出最优的路径。
第一步:将地图简化成易于表示的区域。
我们使用正方形作为寻路算法的单元(也可用其他形状),将如图所示区域分为5X7的栅格。

(三)【机器人路径规划】Astar算法

第二步:建立open和closed列表

open列表:记录下所有被考虑来寻找最短路径的方格;把起始点定义为“父节点”,靠近父节点的点称为子节点,将所有可通过的点放入open列表中作为待查点(图中的8 9 10 15 17 22 23 24八个方格。)
closed列表:记录下不会再被考虑的方格。如图首先将起始点添加到closed列表中。

(三)【机器人路径规划】Astar算法

A算法中的代价函数f(n)=g(n)+h(n)中:

  • g值:g值表示从当前方格到达起始点代价值。我们规定机器人水平(或垂直)移动一个格代价值为10,对角线方向移动代价值为14.方格左下角为g值。

(三)【机器人路径规划】Astar算法

  • h值:h值表示从当前方格到目标点(图中可乐所在位置)的代价。这里我们用曼哈顿距离表示。下图表示了不同点h值得度量。(h值我们放在格子得右下角)

(三)【机器人路径规划】Astar算法

算g时要考虑障碍物的存在,h则不用。

(三)【机器人路径规划】Astar算法

h:指的是17这个格子到终点的h值

(三)【机器人路径规划】Astar算法

(三)【机器人路径规划】Astar算法

(三)【机器人路径规划】Astar算法

。。。。。。
。。。。。。
。。。。。。

(三)【机器人路径规划】Astar算法


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明(三)【机器人路径规划】Astar算法
喜欢 (0)

您必须 登录 才能发表评论!

加载中……