机器人A*寻路算法详解

A*(A-star)算法是一种静态网路中求解最短路径最有效的直接搜索算法。在电子游戏中最主要的应用是寻找地图上两点间的最佳路线。在机器人领域中,A*算法常用于移动机器人路径规划。

为了便于理解,本文将以正方形网格地图为例进行讲解。如图,蓝色格子是障碍物,灰色格子是可通过区域,绿色格子是起点(S),红色格子是终点(D)。我们要做的是找到一条从起点到终点的最佳路线。

为了顺利地解决问题,我们先要设定一些约束条件: 1. 从一个格子可以朝周围 8 个方向移动。其中朝上、下、左、右移动的成本为 1,朝左上、右上、左下、右下移动的成本为 1.4(√2 近似值);

2. 不能朝障碍物所在格子移动(显然啦!);

3. 如果右边和上边两个格子都是障碍物,则不能朝右上方的格子移动(如图:不能朝右上和右下两个格子移动,太窄挤不过去呀~)。

好,下面开始找路!首先,我们把起点 S 加入一个待检查节点的列表(Open List)。接下来,找出 S 周围所有可移动的格子(邻居),算出从 S 移动到该格子的总成本(记为 G),并将 S 设为其父节点。

好,这样我们已经完成了对 S 的检查。把上一步找到的邻居都加入 Open List。从 Open List 中移除 S,并将其加入另一个已检查节点的列表(Closed List)。如图,橙色边框代表待检查节点,黑色边框代表已检查节点。

这下问题来了,Open List 一下有了 8 个待检查节点,先检查哪一个呢?每一个待检查节点都有一个 G 值,代表从起点 S 移动到这个节点的成本。我们再计算出每一个待检查节点与终点 D 之间的曼哈顿距离(只通过朝上、下、左、右四个方向的移动,抵达终点 D 的最短距离。例如,在平面上,坐标(x1, y1)的i点与坐标(x2, y2)的j点的曼哈顿距离为d(i,j)=|x1-x2|+|y1-y2|),作为从该节点移动到终点 D 的估算成本(记为 H)。注意!这里计算曼哈顿距离时要忽略所有障碍物。最后把 G 和 H 相加(记为 F)。

现在,从 Open List 中选出 F 值最小的节点(上图中应该是 S 右边 F 值为 4 的格子),对它执行前面的检查。不过这一次搜索邻居时需要注意以下几点:

1. 如果邻居已经在 Closed List 中,直接忽略; 2. 如果邻居不在 Open List 中,计算 G、H、F,设置父节点,并将其加入 Open List; 3. 这一点非常重要!如果邻居已经在 Open List 中(即该邻居已有父节点),计算从当前节点移动到该邻居是否能使其得到更小的 G 值。如果能,则把该邻居的父节点重设为当前节点,并更新其 G 和 F 值。 完成检查后,把当前节点从 Open List 中移除,放入 Closed List。

继续处理其他待检查节点。

注意!在下面这一次检查中,S 下方两格的节点(星标)更新了 G 值和父节点。

在下面这一步中,我们注意到终点 D 已经进入了 Open List,并且是其中 F 值最小的。

我们从 Open List 取出的 F 值最小的节点后,发现它的 H 值为 0,这意味着我们已经找到了终点 D,搜索到此就可以告一段落。

从终点 D 开始,依次向父节点移动,直到回到起点 S,途经即最佳路线,总长 5.6。

补充几点: 1. 最佳路线可能有多条,比如本文的示例,下图也是一条总长为 5.6 的路线。这取决于当 Open List 存在多个 F 值最小的节点时,先选取哪一个进行搜索;

2. 曼哈顿距离只是估算 H 值最简单的一种方法,常用的方法还有欧几里德距离、切比雪夫距离等。估算方法的优劣是影响算法效率的重要因素; 3. Open List 的数据结构也是算法实现的改良点。通常为了从中取出 F 值最小的节点,我们需要遍历整个 Open List,对其排序。因此,维护一个好的 Open List 结构,减少遍历,也能够提高算法的效率; 4. 实际应用中,为提高效率,还可以进行双向搜索。从起点和终点分别发起搜索,一方搜索到另一方的已检查节点时,即找到最佳路线。地图较复杂时,双向搜索可以显著减少寻路过程中检查的节点数量。 5. 除了正方形网格地图,A* 算法也能处理其他正多边形镶嵌和复杂甚至不规则多边形镶嵌的地图。其区别在于对邻居的处理和计算;

6. A* 算法并不保证得到的路线是平滑的。为了解决这个问题,我们可以对转向进行惩罚。即当移动方向发生变化时,增加额外的 G 值,以此提高转向的成本,从而得到更平滑(转向少、转角小)的最佳路线; 7. A* 算法的在游戏中的实际应用可能会复杂得多。比如不同种族或技能的单位在同一地形上的移动成本各有差异,同一单位在草地、泥地、砂石、沼泽等各种地形上移动的成本也不尽相同(对应不同的 G 值增量),甚至允许以较高的成本翻越障碍(翻墙、过河等); 8. 在机器人路径规划中,你可能还需要处理与障碍物和其他移动物体的碰撞。

原文发布于微信公众号 - 机器人网(robot_globalsources)

原文发表时间:2017-11-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法工程师

LightGBM大战XGBoost,谁将夺得桂冠?

如果你是一个机器学习社区的活跃成员,你一定知道 **提升机器**(Boosting Machine)以及它们的能力。提升机器从AdaBoost发展到目前最流行的...

1813
来自专栏游戏开发那些事

【小白学游戏常用算法】二、A*启发式搜索算法

  在上一篇博客中,我们一起学习了随机迷宫算法,在本篇博客中,我们将一起了解一下寻路算法中常用的A*算法。

1652
来自专栏开心的学习之路

用责任链模式实现图像处理方法的选择(python)

结合我们822实验室开源的图像处理平台(http://822lab.top)介绍用责任链模式实现图像处理方法的选择(python),供后续学弟学妹参考,整个平台...

1514
来自专栏Petrichor的专栏

深度学习: 局部响应归一化 (Local Response Normalization,LRN)

局部响应归一化(Local Response Normalization,LRN):

9084
来自专栏目标检测和深度学习

教程 | 如何使用DeepFake实现视频换脸

1.5K2
来自专栏WOLFRAM

Mathematica 11在代数与数论中的新功能

1855
来自专栏Hadoop数据仓库

HAWQ + MADlib 玩转数据挖掘之(八)——聚类方法之k-means

一、聚类方法简介         所谓“物以类聚,人以群分”,其核心思想就是聚类。通过聚类,人们能意识到密集和稀疏的区域,发现全局的分布模式,以及数据属性之间有...

2825
来自专栏人工智能

将图像转换位mnist数据格式

利用mnist数据对数字符号进行识别基本上算是深度学习的Hello World了。在我学习这个“hello world”的过程中,总感觉缺点什么,于是发现无论是...

35210
来自专栏js编程在工科课程中的简单应用

4.1 数值积分、高等函数绘制

is defined informally as the signed area of the region in the xy-plane that is ...

930
来自专栏Coding迪斯尼

神经网络实战:快速构建一个基于神经网络的手写数字识别系统

1262

扫码关注云+社区

领取腾讯云代金券