| by msbeta | 1 comment

自动驾驶路径规划算法——给初学者看的A*算法

A*算法可以说是一种非常古老的算法,本身的思路可以说非常简单,不过要设计一个好的A*算法却并不容易。

1.问题定义

假设无人驾驶汽车要从 A 点(绿色方块)移动到 B 点(红色方块),但是这两点之间被一堵墙(蓝色方块)隔开,如下图所示。

无人驾驶路径规划算法——给初学者看的A*算法

你可能应该已经注意到了,我们把搜索的区域划分成了正方形的格子,它的状态就是walkable和unwalkable,通过计算出从A到B需要走过哪些方格,就找到了一条可通行的路径。每个方格都可以成为一个节点,很多A*的文章都在讨论节点,为什么不直接描述为方格呢?因为我们有可能把搜索区域划为为其他多变形而不是正方形,例如可以是六边形,矩形,甚至可以是任意多变形。而节点可以放在任意多边形里面,可以放在多变形的中心,也可以放在多边形的边上。

2.开始搜索(Starting the Search)

问题定义好之后下一步要做的便是查找最短路径。在 A* 中,我们从起点开始,检查其相邻的方格,然后向四周扩展,直至找到目标。具体过程如下:

1)把起点 A 加入到Open表中。Open表记录了所有已经知道但是尚未探索的道路。

2)检查与起点 A 相邻的方格,把其中可走的 (walkable) 或可到达的 (reachable) 节点加入到 Open表中,把起点 A 设置为这些节点的父节点 (parent node 或 parent square) 。当我们在追踪路径时,这些父节点的内容是很重要的。

3)把 A 从 Open表中移除,加入到 Close表中,Close表中的每个节点都是已经走过的路。

如下图所示,深绿色的方格为起点,它的外框是亮蓝色,表示该方格被加入到了Close表 。与它相邻的黑色方格是需要被检查的,他们的外框是亮绿色。每个黑方格都有一个灰色的指针指向他们的父节点。

无人驾驶路径规划算法——给初学者看的A*算法

下一步,我们需要从Open表中选一个与起点 A 相邻的方格,然后重复上述的搜索过程。但是到底选择哪个方格好呢?答案是具有最小 F 值的那个。

3.路径排序(Path Sorting)

路径排序的关键是下面启发函数,这也是A*算法的精髓所在:

F = G + H

这里:

G=从起点 A 移动到指定节点的移动代价。

H = 从指定的节点到达终点 B 的估算成本。

在本例中,假设横向和纵向的移动代价为 10 ,对角线的移动代价为 14 ,之所以使用这些数据,是因为实际的对角线移动距离是水平和垂直距离的平方根(近似的 1.414 倍的横向或纵向移动代价)。

既然我们是沿着到达指定方格的路径来计算 G 值,那么计算出该方格的 G 值的方法就是找出其父亲的 G 值,然后按父亲是直线方向还是斜线方向加上 10 或 14 。

有很多方法可以估算 H 值。这里我们使用 Manhattan 方法,计算从当前方格横向或纵向移动到达目标所经过的方格数,忽略对角移动,然后把总数乘以 10 。之所以叫做 Manhattan 方法,是因为这很像统计从一个地点到另一个地点所穿过的街区数,而你不能斜向穿过街区。

把 G 和 H 相加便得到 F 。我们第一步的结果如下图所示。每个方格都标上了 F , G , H 的值(左上角是 F ,左下角是 G ,右下角是 H)。

无人驾驶路径规划算法——给初学者看的A*算法

4.继续搜索(Continuing the Search)

我们从Open表中选择 F 值最小的节点,然后对所选择的节点作如下操作:

4)把它从Open表中取出,放到 Close表中。

5)检查所有与它相邻的节点,忽略在 Close表中或是不可走 (unwalkable) 的节点,如果方格不在Open表中,则把它们加入到Open表中。同时把正在搜索的节点设置为新加入的节点的父亲。

6)如果某个相邻的节点已经在Open表中,则检查这条路径是否更优,也就是说经由当前节点到达那个方格是否具有更小的 G 值。如果没有,不做任何操作;如果 G 值更小,则把那个节点的父亲设为当前节点,然后重新计算那个方格的 F 值和 G 值。

Ok ,让我们看看它是怎么工作的。在我们最初的 9 个方格中,还有 8 个在 Open表中,起点被放入了Close表中。在这些方格中,起点右边的格子的 F 值 40 最小,因此我们选择这个方格作为下一个要处理的方格。它的外框用蓝线打亮。

首先,我们把它从 Open表移到Close表中,然后我们检查与它相邻的方格。它右边的方格是墙壁,忽略之。它左边的方格是起点,在 Close表中,我们也忽略。其他 4 个相邻的方格均在Open表中,我们需要检查经由这个方格到达那里的路径是否更好。让我们看看上面的方格。它现在的 G 值为 14 。如果我们经由当前方格到达那里, G 值将会为 20(其中 10 为到达当前方格的 G 值,此外还要加上从当前方格纵向移动到上面方格的 G 值 10) 。显然 20 比 14 大,因此这不是最优的路径。

当把 4 个已经在Open表中的相邻方格都检查后,没有发现经由当前方格的更好路径,因此我们不做任何改变。现在我们已经检查了当前方格的所有相邻的方格,并也对他们作了处理,是时候选择下一个待处理的方格了。

再次遍历我们的Open表,现在它只有 7 个方格了,我们需要选择 F 值最小的那个。有趣的是,这次有两个方格的 F 值都 54,选哪个呢?没什么关系。从速度上考虑,选择最后加入 Open表的方格更快。这导致了在寻路过程中,当靠近目标时,优先使用新找到的方格的偏好。

我们选择起点右下方的方格,如下图所示。

无人驾驶路径规划算法——给初学者看的A*算法

这次,当我们检查相邻的方格时,我们发现它右边的方格是墙,忽略之。上面的也一样。

我们把墙下面的一格也忽略掉。为什么?因为如果不穿越墙角的话,你不能直接从当前方格移动到那个方格。你需要先往下走,然后再移动到那个方格,这样来绕过墙角。

这样还剩下 5 个相邻的方格。当前方格下面的 2 个方格还没有加入Open表,所以把它们加入,同时把当前方格设为他们的父亲。在剩下的3 个方格中,有 2 个已经在 Close表中 ( 一个是起点,一个是当前方格上面的方格,外框被加亮的 ) ,忽略它们。最后一个方格,也就是当前方格左边的方格,我们检查经由当前方格到达那里是否具有更小的 G 值。没有。因此我们准备从Open表中选择下一个待处理的方格。

不断重复这个过程,直到把终点也加入到了Open表中,此时如下图所示。

无人驾驶路径规划算法——给初学者看的A*算法

注意,在起点下面 2 格的方格的父亲已经与前面不同了。之前它的 G 值是 28 并且指向它右上方的方格。现在它的 G 值为 20 ,并且指向它正上方的方格。这在寻路过程中的某处发生,使用新路径时 G 值经过检查并且变得更低,因此父节点被重新设置, G 和 F 值被重新计算。

那么我们怎么样去确定实际路径呢?很简单,从终点开始,按着箭头向父节点移动,这样你就被带回到了起点,这就是你的路径。如下图所示。从起点 A 移动到终点 B 就是简单从路径上的一个方格的中心移动到另一个方格的中心,直至目标。就是这么简单!

无人驾驶路径规划算法——给初学者看的A*算法

5.A*算法总结(Summary of the A* Method)

Ok ,现在你已经看完了整个的介绍,现在我们把所有步骤放在一起:

1)把起点加入Open表 。

2) 重复如下过程:

a) 遍历Open表,查找 F 值最小的节点,把它作为当前要处理的节点。

b) 把当前节点移到Close表 。

c) 对当前方格的 8 个相邻方格的每一个方格?

◆ 如果它是不可抵达的或者它在Close表中,忽略它。否则,做如下操作。

◆ 如果它不在Open表中,把它加入Open表,并且把当前方格设置为它的父亲,记录该方格的 F , G 和 H 值。

◆ 如果它已经在Open表中,检查这条路径 ( 即经由当前方格到达它那里 ) 是否更好,用 G 值作参考。更小的 G 值表示这是更好的路径。如果是这样,把它的父亲设置为当前方格,并重新计算它的 G 和 F 值。如果你的Open表是按 F 值排序的话,改变后你可能需要重新排序。

d) 停止条件

◆ 把终点加入到了Open表中,此时路径已经找到了。

◆ 查找终点失败,并且Open表是空的,此时没有找到可行的路径。

3、保存路径。从终点开始,每个方格沿着父节点移动直至起点,这就是待查找的路径。

相关文章

1 Comment

Rodger

2020年10月17日 at 上午10:28 回复

How do I get an outside line? topamax 50 mg 60 film tablet For example, if the bulls seem to be overtaking them, runners can duck into a safety area or jump one of the fences. Medical staff also will be on hand. There will be no sharpened horns, which Dickens said was often the case elsewhere. Runners are barred from taunting or harassing the bulls to make them more aggressive.

发表评论