精华内容
下载资源
问答
  • 浅谈路径规划算法

    万次阅读 多人点赞 2017-09-19 16:32:09
    1导言 1.1算法 1.2Dijkstra算法与最佳优先搜索 1.3A*算法 2启发式算法 2.1A*对启发式函数的使用 2.2速度还是精确度? 2.3衡量单位 2.4精确的启发式函数 2.4.1预计算的精确启发式函数 2.4.2线性精

     

     

    原文地址:http://theory.stanford.edu/~amitp/GameProgramming/

     

     

     

    1 导言

    1.1 算法

    1.2 Dijkstra算法与最佳优先搜索

    1.3 A*算法

    2 启发式算法

    2.1 A*对启发式函数的使用

    2.2 速度还是精确度?

    2.3 衡量单位

    2.4 精确的启发式函数

    2.4.1 预计算的精确启发式函数

    2.4.2 线性精确启发式算法

    2.5 网格地图中的启发式算法

    2.5.1 曼哈顿距离

    2.5.2 对角线距离

    2.5.3 欧几里得距离

    2.5.4 平方后的欧几里得距离

    2.5.5 Breaking ties

    2.5.6 区域搜索

    3 Implementation notes

    3.1 概略

    3.2 源代码

    3.3 集合的表示

    3.3.1 未排序数组或链表

    3.3.2 排序数组

    3.3.3 排序链表

    3.3.4 排序跳表

    3.3.5 索引数组

    3.3.6 哈希表

    3.3.7 二元堆

    3.3.8 伸展树

    3.3.9 HOT队列

    3.3.10 比较

    3.3.11 混合实现

    3.4 与游戏循环的交互

    3.4.1 提前退出

    3.4.2 中断算法

    3.4.3 组运动

    3.4.4 细化

    4 A*算法的变种

    4.1 beam search

    4.2 迭代深化

    4.3 动态衡量

    4.4 带宽搜索

    4.5 双向搜索

    4.6 动态A*与终身计划A*

    5 处理运动障碍物

    5.1 重新计算路径

    5.2 路径拼接

    5.3 监视地图变化

    5.4 预测障碍物的运动

    6 预计算路径的空间代价

    6.1 位置VS方向

    6.2 路径压缩

    6.2.1 位置存储

    6.2.2 方向存储

    6.3 计算导航点

    6.4 极限路径长度

    6.5 总结

     

    导言

      移动一个简单的物体(object)看起来是容易的。而路径搜索是复杂的。为什么涉及到路径搜索就产生麻烦了?考虑以下情况:

     

     

      物体(unit)最初位于地图的底端并且尝试向顶部移动。物体扫描的区域中(粉红色部分)没有任何东西显示它不能向上移动,因此它持续向上移动。在靠近顶部时,它探测到一个障碍物然后改变移动方向。然后它沿着U形障碍物找到它的红色的路径。相反的,一个路径搜索器(pathfinder)将会扫描一个更大的区域(淡蓝色部分),但是它能做到不让物体(unit)走向凹形障碍物而找到一条更短的路径(蓝色路径)。

      然而你可以扩展一个运动算法,用于对付上图所示的障碍物。或者避免制造凹形障碍,或者把凹形出口标识为危险的(只有当目的地在里面时才进去):

     

      比起一直等到最后一刻才发现问题,路径搜索器让你提前作出计划。不带路径搜索的运动(movement)可以在很多种情形下工作,同时可以扩展到更多的情形,但是路径搜索是一种更常用的解决更多问题的方法。

    1.1 算法

      计算机科学教材中的路径搜索算法在数学视角的图上工作——由边联结起来的结点的集合。一个基于图块(tile)拼接的游戏地图可以看成是一个图,每个图块(tile)是一个结点,并在每个图块之间画一条边:

      目前,我会假设我们使用二维网格(grid)。稍后我将讨论如何在你的游戏之外建立其他类型的图。

      许多AI领域或算法研究领域中的路径搜索算法是基于任意(arbitrary)的图设计的,而不是基于网格(grid-based)的 图。我们可以找到一些能使用网格地图的特性的东西。有一些我们认为是常识,而算法并不理解。例如,我们知道一些和方向有关的东西:一般而言,如果两个物体 距离越远,那么把其中一个物体向另一个移动将花越多的时间;并且我们知道地图中没有任何秘密通道可以从一个地点通向另一个地点。(我假设没有,如果有的 话,将会很难找到一条好的路径,因为你并不知道要从何处开始。)

    1.2 Dijkstra算法与最佳优先搜索

      Dijkstra算法从物体所在的初始点开始,访问图中的结点。它迭代检查待检查结点集中的结点,并把和该结点最靠近的尚未检查的结点加入待检查结点集。该结点集从初始结点向外扩展,直到到达目标结点。Dijkstra算法保证能找到一条从初始点到目标点的最短路径,只要所有的边都有一个非负的代价值。(我说“最短路径”是因为经常会出现许多差不多短的路径。)在下图中,粉红色的结点是初始结点,蓝色的是目标点,而类菱形的有色区域(注:原文是teal areas)则是Dijkstra算法扫描过的区域。颜色最淡的区域是那些离初始点最远的,因而形成探测过程(exploration)的边境(frontier):

      最佳优先搜索(BFS)算法按照类似的流程运行,不同的是它能够评估(称为启发式的)任意结点到目标点的代价。与选择离初始结点最近的结点不同的是,它选择离目标最近的结点。BFS不能保证找到一条最短路径。然而,它比Dijkstra算法快的多,因为它用了一个启发式函数(heuristic )快速地导向目标结点。例如,如果目标位于出发点的南方,BFS将趋向于导向南方的路径。在下面的图中,越黄的结点代表越高的启发式值(移动到目标的代价高),而越黑的结点代表越低的启发式值(移动到目标的代价低)。这表明了与Dijkstra 算法相比,BFS运行得更快。

      然而,这两个例子都仅仅是最简单的情况——地图中没有障碍物,最短路径是直线的。现在我们来考虑前边描述的凹型障碍物。Dijkstra算法运行得较慢,但确实能保证找到一条最短路径:

      另一方面,BFS运行得较快,但是它找到的路径明显不是一条好的路径:

      问题在于BFS是基于贪心策略的,它试图向目标移动尽管这不是正确的路径。由于它仅仅考虑到达目标的代价,而忽略了当前已花费的代价,于是尽管路径变得很长,它仍然继续走下去。

      结合两者的优点不是更好吗?1968年发明的A*算法就是把启发式方法(heuristic approaches)如BFS,和常规方法如Dijsktra算法结合在一起的算法。有点不同的是,类似BFS的启发式方法经常给出一个近似解而不是保证最佳解。然而,尽管A*基于无法保证最佳解的启发式方法,A*却能保证找到一条最短路径。

    1.3 A*算法

      我将集中讨论A*算法。A*是路径搜索中最受欢迎的选择,因为它相当灵活,并且能用于多种多样的情形之中。

      和其它的图搜索算法一样,A*潜在地搜索图中一个很大的区域。和Dijkstra一样,A*能用于搜索最短路径。和BFS一样,A*能用启发式函数(注:原文为heuristic)引导它自己。在简单的情况中,它和BFS一样快。

      在凹型障碍物的例子中,A*找到一条和Dijkstra算法一样好的路径:

      成功的秘决在于,它把Dijkstra算法(靠近初始点的结点)和BFS算法(靠近目标点的结点)的信息块结合起来。在讨论A*的标准术语中,g(n)表示从初始结点到任意结点n的代价,h(n)表示从结点n到目标点的启发式评估代价(heuristic estimated cost)。在上图中,yellow(h)表示远离目标的结点而teal(g)表示远离初始点的结点。当从初始点向目标点移动时,A*权衡这两者。每次进行主循环时,它检查f(n)最小的结点n,其中f(n) = g(n) + h(n)。

    启发式算法

      启发式函数h(n)告诉A*从任意结点n到目标结点的最小代价评估值。选择一个好的启发式函数是重要的。

    2.1 A*对启发式函数的使用

      启发式函数可以控制A*的行为:

    • 一种极端情况,如果h(n)0,则只有g(n)起作用,此时A*演变成Dijkstra算法,这保证能找到最短路径。
    • 如果h(n)经常都比从n移动到目标的实际代价小(或者相等),则A*保证能找到一条最短路径。h(n)越小,A*扩展的结点越多,运行就得越慢。
    • 如果h(n)精确地等于从n移动到目标的代价,则A*将会仅仅寻找最佳路径而不扩展别的任何结点,这会运行得非常快。尽管这不可能在所有情况下发生,你仍可以在一些特殊情况下让它们精确地相等(译者:指让h(n)精确地等于实际值)。只要提供完美的信息,A*会运行得很完美,认识这一点很好。
    • 如果h(n)有时比从n移动到目标的实际代价高,则A*不能保证找到一条最短路径,但它运行得更快。
    • 另一种极端情况,如果h(n)比g(n)大很多,则只有h(n)起作用,A*演变成BFS算法。

      所以我们得到一个很有趣的情况,那就是我们可以决定我们想要从A*中获得什么。理想情况下(注:原文为At exactly the right point),我们想最快地得到最短路径。如果我们的目标太低,我们仍会得到最短路径,不过速度变慢了;如果我们的目标太高,那我们就放弃了最短路径,但A*运行得更快。

    在游戏中,A*的这个特性非常有用。例如,你会发现在某些情况下,你希望得到一条好的路径("good" path)而不是一条完美的路径("perfect" path)。为了权衡g(n)和h(n),你可以修改任意一个。

    :在学术上,如果启发式函数值是对实际代价的低估,A*算法被称为简单的A算法(原文为simply A)。然而,我继续称之为A*,因为在实现上是一样的,并且在游戏编程领域并不区别A和A*。

    2.2 速度还是精确度?

      A*改变它自己行为的能力基于启发式代价函数,启发式函数在游戏中非常有用。在速度和精确度之间取得折衷将会让你的游戏运行得更快。在很多游戏中,你并不真正需要得到最好的路径,仅需要近似的就足够了。而你需要什么则取决于游戏中发生着什么,或者运行游戏的机器有多快。

      假设你的游戏有两种地形,平原和山地,在平原中的移动代价是1而在山地则是3。A* is going to search three times as far along flat land as it does along mountainous land. 这是因为有可能有一条沿着平原到山地的路径。把两个邻接点之间的评估距离设为1.5可以加速A*的搜索过程。然后A*会将3和1.5比较,这并不比把3和1比较差。It is not as dissatisfied with mountainous terrain, so it won't spend as much time trying to find a way around it. Alternatively, you can speed up up A*'s search by decreasing the amount it searches for paths around mountains―just tell A* that the movement cost on mountains is 2 instead of 3. Now it will search only twice as far along the flat terrain as along mountainous terrain. Either approach gives up ideal paths to get something quicker.

    速度和精确度之间的选择前不是静态的。你可以基于CPU的速度、用于路径搜索的时间片数、地图上物体(units)的数量、物体的重要性、组(group)的大小、难度或者其他任何因素来进行动态的选择。取得动态的折衷的一个方法是,建立一个启发式函数用于假定通过一个网格空间的最小代价是1,然后建立一个代价函数(cost )用于测量(scales):

    g’(n) = 1 + alpha * ( g(n) – 1 )

      如果alpha是0,则改进后的代价函数的值总是1。这种情况下,地形代价被完全忽略,A*工作变成简单地判断一个网格可否通过。如果alpha是1,则最初的代价函数将起作用,然后你得到了A*的所有优点。你可以设置alpha的值为0到1的任意值。

      你也可以考虑对启发式函数的返回值做选择:绝对最小代价或者期望最小代价。例如,如果你的地图大部分地形是代价为2的草地,其它一些地方是代价为1的道路,那么你可以考虑让启发式函数不考虑道路,而只返回2*距离。

      速度和精确度之间的选择并不是 全局的。在地图上的某些区域,精确度是重要的,你可以基于此进行动态选择。例如,假设我们可能在某点停止重新计算路径或者改变方向,则在接近当前位置的地 方,选择一条好的路径则是更重要的,因此为何要对后续路径的精确度感到厌烦?或者,对于在地图上的一个安全区域,最短路径也许并不十分重要,但是当从一个 敌人的村庄逃跑时,安全和速度是最重要的。(译者注:译者认为这里指的是,在安全区域,可以考虑不寻找精确的最短路径而取近似路径,因此寻路快;但在危险 区域,逃跑的安全性和逃跑速度是重要的,即路径的精确度是重要的,因此可以多花点时间用于寻找精确路径。)

    2.3 衡量单位

     A*计算f(n) = g(n) + h(n)。为了对这两个值进行相加,这两个值必须使用相同的衡量单位。如果g(n)用小时来衡量而h(n)用米来衡量,那么A*将会认为g或者h太大或者太小,因而你将不能得到正确的路径,同时你的A*算法将运行得更慢。

    2.4 精确的启发式函数

      如果你的启发式函数精确地等于实际最佳路径(optimal path),如下一部分的图中所示,你会看到此时A*扩展的结点将非常少。A*算法内部发生的事情是:在每一结点它都计算f(n) = g(n) + h(n)。当h(n)精确地和g(n)匹配(译者注:原文为match)时,f(n)的值在沿着该路径时将不会改变。不在正确路径(right path)上的所有结点的f值均大于正确路径上的f值(译者注:正确路径在这里应该是指最短路径)。如果已经有较低f值的结点,A*将不考虑f值较高的结点,因此它肯定不会偏离最短路径。

    2.4.1 预计算的精确启发式函数

      构造精确启发函数的一种方法是预先计算任意一对结点之间最短路径的长度。在许多游戏的地图中这并不可行。然后,有几种方法可以近似模拟这种启发函数:

    • Fit a coarse grid on top of the fine grid. Precompute the shortest path between any pair of coarse grid locations.
    • Precompute the shortest path between any pair of waypoints. This is a generalization of the coarse grid approach.

      (译者:此处不好翻译,暂时保留原文)

    然后添加一个启发函数h’用于评估从任意位置到达邻近导航点(waypoints)的代价。(如果愿意,后者也可以通过预计算得到。)最终的启发式函数可以是:

    h(n) = h'(n, w1) + distance(w1, w2), h'(w2, goal)

    或者如果你希望一个更好但是更昂贵的启发式函数,则分别用靠近结点和目标的所有的w1,w2对对上式进行求值。(译者注:原文为or if you want a better but more expensive heuristic, evaluate the above with all pairs w1, w2 that are close to the node and the goal, respectively.)

    2.4.2 线性精确启发式算法

      在特殊情况下,你可以不通过预计算而让启发式函数很精确。如果你有一个不存在障碍物和slow地形,那么从初始点到目标的最短路径应该是一条直线。

      如果你正使用简单的启发式函数(我们不知道地图上的障碍物),则它应该和精确的启发式函数相符合(译者注:原文为match)。如果不是这样,则你会遇到衡量单位的问题,或者你所选择的启发函数类型的问题。

    2.5 网格地图中的启发式算法

      在网格地图中,有一些众所周知的启发式函数。

    2.5.1 曼哈顿距离

    标准的启发式函数是曼哈顿距离(Manhattan distance)。考虑你的代价函数并找到从一个位置移动到邻近位置的最小代价D。因此,我的游戏中的启发式函数应该是曼哈顿距离的D倍:

           H(n) = D * (abs ( n.x – goal.x ) + abs ( n.y – goal.y ) )

    你应该使用符合你的代价函数的衡量单位。

     

    (Note: the above image has a tie-breaker added to the heuristic.}

    (译者注:曼哈顿距离——两点在南北方向上的距离加上在东西方向上的距离,即DIJ=|XI-XJ|+|YI-YJ|。对于一个具有正南正北、正东正西方向规则布局的城镇街道,从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离因此曼哈顿距离又称为出租车距离,曼哈顿距离不是距离不变量,当坐标轴变动时,点间的距离就会不同——百度知道)

    2.5.2 对角线距离

    如果在你的地图中你允许对角运动那么你需要一个不同的启发函数。(4 east, 4 north)的曼哈顿距离将变成8*D。然而,你可以简单地移动(4 northeast)代替,所以启发函数应该是4*D。这个函数使用对角线,假设直线和对角线的代价都是D:

    h(n) = D * max(abs(n.x - goal.x), abs(n.y - goal.y))

    如果对角线运动的代价不是D,但类似于D2 = sqrt(2) * D,则上面的启发函数不准确。你需要一些更准确(原文为sophisticated)的东西:

    h_diagonal(n) = min(abs(n.x - goal.x), abs(n.y - goal.y))

    h_straight(n) = (abs(n.x - goal.x) + abs(n.y - goal.y))

    h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))

    这里,我们计算h_diagonal(n):沿着斜线可以移动的步数;h_straight(n):曼哈顿距离;然后合并这两项,让所有的斜线步都乘以D2,剩下的所有直线步(注意这里是曼哈顿距离的步数减去2倍的斜线步数)都乘以D。

    2.5.3 欧几里得距离

    如果你的单位可以沿着任意角度移动(而不是网格方向),那么你也许应该使用直线距离:

    h(n) = D * sqrt((n.x-goal.x)^2 + (n.y-goal.y)^2)

    然而,如果是这样的话,直接使用A*时将会遇到麻烦,因为代价函数g不会match启发函数h。因为欧几里得距离比曼哈顿距离和对角线距离都短,你仍可以得到最短路径,不过A*将运行得更久一些:

    2.5.4 平方后的欧几里得距离

    我曾经看到一些A*的网页,其中提到让你通过使用距离的平方而避免欧几里得距离中昂贵的平方根运算:

    h(n) = D * ((n.x-goal.x)^2 + (n.y-goal.y)^2)

    不要这样做!这明显地导致衡量单位的问题。当A*计算f(n) = g(n) + h(n),距离的平方将g的代价大很多,并且你会因为启发式函数评估值过高而停止。对于更长的距离,这样做会靠近g(n)的极端情况而不再计算任何东西,A*退化成BFS

    2.5.5 Breaking ties

    导致低性能的一个原因来自于启发函数的ties(注:这个词实在不知道应该翻译为什么)。当某些路径具有相同的f值的时候,它们都会被搜索(explored),尽管我们只需要搜索其中的一条:


    Ties in f values.

    为了解决这个问题,我们可以为启发函数添加一个附加值(译者注:原文为small tie breaker)。附加值对于结点必须是确定性的(也就是说,不能是随机的数),而且它必须让f值体现区别。因为A*f值排序,让f值不同意味着只有一个"equivalent"f值会被检测。

    一种添加附加值的方式是稍微改变(译者注:原文为nudgeh的衡量单位。如果我们减少衡量单位(译者注:原文为scale it downwards),那么当我们朝着目标移动的时候f将逐渐增加。很不幸,这意味着A*倾向于扩展到靠近初始点的结点,而不是靠近目标的结点。我们可以增加衡量单位(译者注:原文为scale it downwards scale h upwards slightly)(甚至是0.1%),A*就会倾向于扩展到靠近目标的结点。

    heuristic *= (1.0 + p)

    选择因子p使得p < 移动一步(step)的最小代价 / 期望的最长路径长度。假设你不希望你的路径超过1000步(step),你可以使p = 1 / 1000。添加这个附加值的结果是,A*比以前搜索的结点更少了。


    Tie-breaking scaling added to heuristic.

    当存在障碍物时,当然仍要在它们周围寻找路径,但要意识到,当绕过障碍物以后,A*搜索的区域非常少:


    Tie-breaking scaling added to heuristic, works nicely with obstacles.

    Steven van Dijk建议,一个更直截了当的方法是把h传递到比较函数(comparison )。当f值相等时,比较函数检查h,然后添加附加值。

    一个不同的添加附加值的方法是,倾向于从初始点到目标点的连线(直线):

    dx1 = current.x - goal.x

    dy1 = current.y - goal.y

    dx2 = start.x - goal.x

    dy2 = start.y - goal.y

    cross = abs(dx1*dy2 - dx2*dy1)

    heuristic += cross*0.001

    这段代码计算初始-目标向量(start to goal vector)和当前-目标向量(current point to goal vector)的向量叉积(vector cross-product)。When these vectors don't line up, the cross product will be larger.结果是,这段代码选择的路径稍微倾向于从初始点到目标点的直线。当没有障碍物时,A*不仅搜索很少的区域,而且它找到的路径看起来非常棒:


    Tie-breaking cross-product added to heuristic, produces pretty paths.

    然而,因为这种附加值倾向于从初始点到目标点的直线路径,当出现障碍物时将会出现奇怪的结果(注意这条路径仍是最佳的,只是看起来很奇怪):


    Tie-breaking cross-product added to heuristic, less pretty with obstacles.

    为了交互地研究这种附加值方法的改进,请参考James MacgillA*applethttp://www.ccg.leeds.ac.uk/james/aStar/ [如果链接无效,请使用这个镜像(http://www.vision.ee.ethz.ch/~buc/astar/AStar.html](译者注:两个链接均无效)。使用“Clear”以清除地图,选择地图对角的两个点。当你使用“Classic A*”方法,你会看到附加值的效果。当你使用“Fudge”方法,你会看到上面给启发函数添加叉积后的效果。

    然而另一种添加附加值的方法是,小心地构造你的A*优先队列,使新插入的具有特殊f值的结点总是比那些以前插入的具有相同f值的旧结点要好一些。

    你也许也想看看能够更灵活地(译者注:原文为sophisticated)添加附加值的AlphA*算法(http://home1.stofanet.dk/breese/papers.html),不过用这种算法得到的路径是否能达到最佳仍在研究中。AlphA*具有较好的适应性,而且可能比我在上面讨论的附加值方法运行得都要好。然而,我所讨论的附加值方法非常容易实现,所以从它们开始吧,如果你需要得到更好的效果,再去尝试AlphA*

    2.5.6 区域搜索

      如果你想搜索近目标的任意不确定结点,而不是某个特定的结点,你应该建立一个启发函数h’(x),使得h’(x)h1(x), h2(x), h3(x)。。。的最小值,而这些h1, h2, h3是邻近结点的启发函数。然而,一种更快的方法是让A*仅搜索目标区域的中心。一旦你从OPEN集合中取得任意一个邻近目标的结点,你就可以停止搜索并建立一条路径了。

    3 Implementation notes

    3.1 概略

      如果不考虑具体实现代码,A*算法是相当简单的。有两个集合,OPEN集和CLOSED集。其中OPEN集保存待考查的结点。开始时,OPEN集只包含一个元素:初始结点。CLOSED集保存已考查过的结点。开始时,CLOSED集是空的。如果绘成图,OPEN集就是被访问区域的边境(frontier)而CLOSED集则是被访问区域的内部(interior)。每个结点同时保存其父结点的指针因此我们可以知道它是如何被找到的。

      在主循环中重复地从OPEN集中取出最好的结点nf值最小的结点)并检查之。如果n是目标结点,则我们的任务完成了。否则,结点n被从OPEN集中删除并加入CLOSED集。然后检查它的邻居n’。如果邻居n’CLOSED集中,那么它是已经被检查过的,所以我们不需要考虑它*;如果n’OPEN集中,那么它是以后肯定会被检查的,所以我们现在不考虑它*。否则,把它加入OPEN集,把它的父结点设为n。到达n’的路径的代价g(n’),设定为g(n) + movementcost(n, n’)

    (*)这里我忽略了一个小细节。你确实需要检查结点的g值是否更小了,如果是的话,需要重新打开(re-open)它。

    OPEN = priority queue containing START

    CLOSED = empty set

    while lowest rank in OPEN is not the GOAL:

      current = remove lowest rank item from OPEN

      add current to CLOSED

      for neighbors of current:

        cost = g(current) + movementcost(current, neighbor)

        if neighbor in OPEN and cost less than g(neighbor):

          remove neighbor from OPEN, because new path is better

        if neighbor in CLOSED and cost less than g(neighbor): **

          remove neighbor from CLOSED

        if neighbor not in OPEN and neighbor not in CLOSED:

          set g(neighbor) to cost

          add neighbor to OPEN

          set priority queue rank to g(neighbor) + h(neighbor)

          set neighbor's parent to current

     

    reconstruct reverse path from goal to start

    by following parent pointers

    (**) This should never happen if you have an admissible heuristic. However in games we often have inadmissible heuristics.

     

     

    3.2 源代码

    我自己的(旧的)C++A*代码是可用的:path.cpp (http://theory.stanford.edu/~amitp/ GameProgramming/path.cpp)path.h (http://theory.stanford.edu/~amitp/GameProgramming/ path.h),但是不容易阅读。还有一份更老的代码(更慢的,但是更容易理解),和很多其它的A*实现一样,它在Steve Woodcock'的游戏AI页面(http://www.gameai.com/ai.html)。

    在网上,你能找到CC++Visual Basic Java(http://www.cuspy.com/software/pathfinder/ doc/)Flash/Director/Lingo, C#(http://www.codeproject.com/csharp/CSharpPathfind.asp), Delphi, Lisp, Python, Perl, Prolog 实现的A*代码。一定的阅读Justin Heyes-JonesC++实现(http://www.geocities.com/jheyesjones/astar.html)。

    3.3 集合的表示

    你首先想到的用于实现OPEN集和CLOSED集的数据结构是什么?如果你和我一样,你可能想到“数组”。你也可能想到“链表”。我们可以使用很多种不同的数据结构,为了选择一种,我们应该考虑我们需要什么样的操作。

    OPEN集上我们主要有三种操作:主循环重复选择最好的结点并删除它;访问邻居结点时需要检查它是否在集合里面;访问邻居结点时需要插入新结点。插入和删除最佳是优先队列(http://members.xoom.com/killough/heaps.html)的典型操作。

    选择哪种数据结构不仅取决于操作,还取决于每种操作执行的次数。检查一个结点是否在集合中这一操作对每个被访问的结点的每个邻居结点都执行一次。删除最佳操作对每个被访问的结点都执行一次。被考虑到的绝大多数结点都会被访问;不被访问的是搜索空间边缘(fringe)的结点。当评估数据结构上面的这些操作时,必须考虑fringe(F)的最大值。

    另外,还有第四种操作,虽然执行的次数相对很少,但还是必须实现的。如果正被检查的结点已经在OPEN集中(这经常发生),并且如果它的f值比已经在OPEN集中的结点要好(这很少见),那么OPEN集中的值必须被调整。调整操作包括删除结点(f值不是最佳的结点)和重插入。这两个步骤必须被最优化为一个步骤,这个步骤将移动结点。

    3.3.1 未排序数组或链表

    最简单的数据结构是未排序数组或链表。集合关系检查操作(Membership test)很慢,扫描整个结构花费O(F)。插入操作很快,添加到末尾花费O(1)。查找最佳元素(Finding the best element)很慢,扫描整个结构花费O(F)。对于数组,删除最佳元素(Removing the best element)花费O(F),而链表则是O(1)。调整操作中,查找结点花费O(F),改变值花费O(1)

    3.3.2 排序数组

    为了加快删除最挂操作,可以对数组进行排序。集合关系检查操作将变成O(log F),因为我们可以使用折半查找。插入操作会很慢,为了给新元素腾出空间,需要花费 O(F)以移动所有的元素。查找最佳元素操作会很快,因为它已经在末尾了所以花费是O(1)。如果我们保证最佳排序至数组的尾部(best sorts to the end of the array),删除最佳元素操作花费将是O(1)。调整操作中,查找结点花费O(logF),改变值/位置花费O(F)

    3.3.3 排序链表

    在排序数组中,插入操作很慢。如果使用链表则可以加速该操作。集合关系检查操作很慢,需要花费O(F)用于扫描链表。插入操作是很快的,插入新元素只花费O(1)时间,但是查找正确位置需要花费O(F)。查找最佳元素很快,花费O(1)时间,因为最佳元素已经在表的尾部。删除最佳元素也是O(1)。调整操作中,查找结点花费O(F),改变值/位置花费O(1)

    3.3.4 排序跳表

    在未排序链表中查找元素是很慢的。如果用跳表(http://en.wikipedia.org/wiki/Skip_list)代替链表的话,可以加速这个操作。在跳表中,如果有排序键(sort key)的话,集合关系检查操作会很快:O(log F)。如果你知道在何处插入的话,和链表一样,插入操作也是O(1)。如果排序键是f,查找最佳元素很快,达到O(1),删除一个元素也是O(1)。调整操作涉及到查找结点,删除结点和重插入。

    如果我们用地图位置作为跳表的排序键,集合关系检查操作将是O(log F)。在完成集合关系检查后,插入操作是O(1)。查找最佳元素是O(F),删除一个结点是O(1)。因为集合关系检查更快,所以它比未排序链表要好一些。

    如果我们用f值作为跳表的排序键,集合关系检查操作将是O(F)。插入操作是O(1)。查找最佳元素是O(1),删除一个结点是O(1)。这并不比排序链表好。

    3.3.5 索引数组

    如果结点的集合有限并且数目是适当的,我们可以使用直接索引结构,索引函数i(n)把结点n映射到一个数组的索引。未排序与排序数组的长度等于OPEN集的最大值,和它们不同,对所有的n,索引数组的长度总是等于max(i(n))。如果你的函数是密集的(没有不被使用的索引),max(i(n))将是你地图中结点的数目。只要你的地图是网格的,让索引函数密集就是容易的。

    假设i(n)O(1)的,集合关系检查将花费O(1),因为我们几乎不需要检查Array[i(n)]是否包含任何数据。Insertion is O(1), as we just ste Array[i(n)].查找和删除最佳操作是O(numnodes),因为我们必须搜索整个结构。调整操作是O(1)

    3.3.6 哈希表

    索引数组使用了很多内存用于保存不在OPEN集中的所有结点。一个选择是使用哈希表。哈希表使用了一个哈希函数h(n)把地图上每个结点映射到一个哈希码。让哈希表的大小等于N的两倍,以使发生冲突的可能性降低。假设h(n) O(1)的,集体关系检查操作花费O(1);插入操作花费O(1);删除最佳元素操作花费O(numnodes),因为我们需要搜索整个结构。调整操作花费O(1)

    3.3.7 二元堆

    一个二元堆(不要和内存堆混淆)是一种保存在数组中的树结构。和许多普通的树通过指针指向子结点所不同,二元堆使用索引来查找子结点。C++ STL包含了一个二元堆的高效实现,我在我自己的A*代码中使用了它。

    在二元堆中,集体关系检查花费O(F),因为你必须扫描整个结构。插入操作花费O(log F)而删除最佳操作花费也是O(log F)。调整操作很微妙(tricky),花费O(F)时间找到节点,并且很神奇,只用O(log F)来调整。

    我的一个朋友(他研究用于最短路径算法的数据结构)说,除非在你的fringe集里有多于10000个元素,否则二元堆是很不错的。除非你的游戏地图特别大,否则你不需要更复杂的数据结构(如multi-level bucketshttp://www-cs-students.stanford.edu/~csilvers/))。你应该尽可能不用Fibonacci 堆(http://www.star-lab.com/goldberg/pub/neci-tr-96-062.ps),因为虽然它的渐近复杂度很好,但是执行起来很慢,除非F足够大。

    3.3.8 伸展树

    堆是一种基于树的结构,它有一个期望的O(log F)代价的时间操作。然而,问题是在A*算法中,通常的情况是,一个代价小的节点被移除(花费O(log F)的代价,因为其他结点必须从树的底部向上移动),而紧接着一些代价小的节点被添加(花费O(log F)的代价,因为这些结点被添加到底部并且被移动到最顶部)。在这里,堆的操作在预期的情况下和最坏情况下是一样的。如果我们找到这样一种数据结构,最坏情况还是一样,而预期的情况好一些,那么就可以得到改进。

    伸展树(Splay tree)是一种自调整的树结构。任何对树结点的访问都尝试把该结点推到树的顶部(top)。这就产生了一个缓存效果("caching" effect):很少被使用的结点跑到底部(bottom)去了并且不减慢操作(don't slow down operations)。你的splay树有多大并不重要,因为你的操作仅仅和你的“cache size”一样慢。在A*中,低代价的结点使用得很多,而高代价结点经常不被使用,所以高代价结点将会移动到树的底部。

    使用伸展树后,集体关系检查,插入,删除最佳和调整操作都是期望的O(log F)(注:原文为expected O(log F) ),最坏情况是O(F)。然而有代表性的是,缓存过程(caching)避免了最坏情况的发生。Dijkstra算法和带有低估的启发函数(underestimating heuristic)的A*算法却有一些特性让伸展树达不到最优。特别是对结点n和邻居结点n’来说,f(n') >= f(n)。当这发生时,也许插入操作总是发生在树的同一边结果是使它失去了平衡。我没有试验过这个。

    3.3.9 HOT队列

    还有一种比堆好的数据结构。通常你可以限制优先队列中值的范围。给定一个限定的范围,经常会存在更好的算法。例如,对任意值的排序可以在O(N log N)时间内完成,但当固定范围时,桶排序和基数排序可以在O(N)时间内完成。

    我们可以使用HOTHeap On Top)队列(http://www.star-lab.com/goldberg/pub /neci-tr-97-104.ps)来利用f(n') >= f(n),其中n’是n的一个邻居结点。我们删除f(n)值最小的结点n,插入满足f(n) <= f(n') <= f(n) + delta的邻居n',其中delta <= C。常数C是从一结点到邻近结点代价改变量的最大值。因为f(n)OPEN集中的最小f值,并且正要被插入的所有结点都小于或等于f(n) + delta,我们知道OPEN集中的所有f值都不超过一个0..delta的范围。在桶/基数排序中,我们可以用“桶”(buckets)对OPEN集中的结点进行排序。

    使用K桶,我们把O(N)的代价降低到平均O(N/K)。通过HOT队列,顶端的桶使用二元堆而所有其他的桶都是未排序数组。因而,对顶部的桶,集合关系检查代价是预期的O(F/K),插入和删除最佳是O(log (F/K))。对其他桶,集合关系检查是O(F/K),插入是O(1),而删除最佳根本不发生!如果顶端的桶是空的,那么我们必须把下一个桶即未排序数组转换为二元堆。这个操作(“heapify”)可以在O(F/K)时间内完成。在调整操作中,删除是O(F/K),然后插入是O(log (F/K))O(1)

    A*中,我们加入OPEN集中的许多结点实际上根本是不需要的。在这方面HOT队列很有优势,因为不需要的元素的插入操作只花费O(1)时间。只有需要的元素被heapified(代价较低的那些)。唯一一个超过O(1)的操作是从堆中删除结点,只花费O(log (F/K))

    另外,如果C比较小,我们可以只让K = C,则对于最小的桶,我们甚至不需要一个堆,国为在一个桶中的所有结点都有相同的f值。插入和删除最佳都是O(1)时间!有人研究过,HOT队列在至多在OPEN集中有800个结点时和堆一样快,并且如果OPEN集中至多有1500个结点,则比堆快20%。我期望随着结点的增加,HOT队列也更快。

    HOT队列的一个简单的变化是一个二层队列(two-level queue):把好的结点放进一个数据结构(堆或数组)而把坏的结点放进另一个数据结构(数组或链表)。因为大多数进入OPEN集中的结点都“坏的”,它们从不被检查,因而把它们放进出一个大数组是没有害处的。

    3.3.10 比较

    注意有一点很重要,我们并不是仅仅关心渐近的行为(大O符号)。我们也需要关心小常数(low constant)下的行为。为了说明原因,考虑一个O(log F)的算法,和另一个O(F)的算法,其中F是堆中元素的个数。也许在你的机器上,第一个算法的实现花费10000*log(F)秒,而另一个的实现花费2*F秒。当F=256时,第一个算法将花费80000秒而第二个算法花费512秒。在这种情况下,“更快”的算法花费更多的时间,而且只有在当F>200000时才能运行得更快。

    你不能仅仅比较两个算法。你还要比较算法的实现。同时你还需要知道你的数据的大小(size)。在上面的例子中,第一种实现在F>200000时更快,但如果在你的游戏中,F小于30000,那么第二种实现好一些。

    基本数据结构没有一种是完全合适的。未排序数组或者链表使插入操作很快而集体关系检查和删除操作非常慢。排序数组或者链表使集体关系检查稍微快一些,删除(最佳元素)操作非常快而插入操作非常慢。二元堆让插入和删除操作稍微快一些,而集体关系检查则很慢。伸展树让所有操作都快一些。HOT队 列让插入操作很快,删除操作相当快,而集体关系检查操作稍微快一些。索引数组让集体关系检查和插入操作非常快,但是删除操作不可置信地慢,同时还需要花费 很多内存空间。哈希表和索引数组类似,但在普通情况下,它花费的内存空间少得多,而删除操作虽然还是很慢,但比索引数组要快。

    关于更高级的优先队列的资料和实现,请参考Lee Killough的优先队列页面(http://members.xoom.com/killough/heaps.html)。

    3.3.11 混合实现

    为了得到最佳性能,你将希望使用混合数据结构。在我的A*代码中,我使用一个索引数组从而集合关系检查是O(1)的,一个二元堆从而插入操作和删除最佳都是O(log F)的。对于调整操作,我使用索引数组从而花费O(1)时间检查我是否真的需要进行调整(通过在索引数组中保存g值),然后在少数确实需要进行调整的情况中,我使用二元堆从而调整操作花费O(F)时间。你也可以使用索引数组保存堆中每个结点的位置,这让你的调整操作变成O(log F)

    3.4 与游戏循环的交互

    交互式的(尤其是实时的)游戏对最佳路径的计算要求很高。能够得到一个解决方案比得到最佳方案可能更重要。然而在所有其他因素都相同的情况下,短路径比长路径好。

    一般来说,计算靠近初始结点的路径比靠近目标结点的路径更重要一些。立即开始原理(The principle of immediate start):让游戏中的物体尽可能快地开始行动,哪怕是沿着一条不理想的路径,然后再计算一条更好的路径。在实时游戏中,应该更多地关注A*的延迟情况(latency)而不是吞吐量(throughput)。

    可以对物体编程让它们根据自己的本能(简单行为)或者智力(一条预先计算好的路径)来行动。除非它们的智力告诉它们怎么行动,否则它们就根据自己的本能来行动(这是实际上使用的方法,并且Rodney Brook在他的机器人体系结构中也用到)。和立即计算所有路径所不同,让游戏在每一个,两个,或者三个循环中搜索一条路径。让物体在开始时依照本能行动(可能仅仅是简单地朝着目标直线前进),然后才为它们寻找路径。这种方法让让路径搜索的代价趋于平缓,因此它不会集中发生在同一时刻。

    3.4.1 提前退出

    可以从A*算法的主循环中提前退出来同时得到一条局部路径。通常,当找到目标结点时,主循环就退出了。然而,在此之前的任意结点,可以得到一条到达OPEN中当前最佳结点的路径。这个结点是到达目标点的最佳选择,所以它是一个理想的中间结点(原文为so it's a reasonable place to go)。

    可以提前退出的情况包括检查了一定数量的结点,A*算法已经运行了几毫秒时间,或者扫描了一个离初始点有些距离的结点。当使用路径拼接时,应该给被拼接的路径一个比全路径(full path)小的最大长度。

    3.4.2 中断算法

    如果需要进行路径搜索的物体较少,或者如果用于保存OPENCLOSED集的数据结构较小,那么保存算法的状态是可行的,然后退出到游戏循环继续运行游戏。

    3.4.3 组运动

    路径请求并不是均匀分布的。即时策略游戏中有一个常见的情况,玩家会选择多个物体并命令它们朝着同样的目标移动。这给路径搜索系统以沉重的负载。

    在这种情况下,为某个物体寻找到的路径对其它物体也是同样有用的。一种方法是,寻找一条从物体的中心到目的地中心的路径P。对所有物体使用该路径的绝大部分,对每一个物体,前十步和后十步使用为它自己寻找的路径。物体i得到一条从它的开始点到P[10]的路径,紧接着是共享的路径P[10..len(P)-10],最后是从P[len(P)-10]到目的地的路径。

    为每个物体寻找的路径是较短的(平均步数大约是10),而较长的路径被共享。大多数路径只寻找一次并且为所有物体所共享。然而,当玩家们看到所有的物体都沿着相同的路径移动时,将对游戏失去兴趣。为了对系统做些改进,可以让物体稍微沿着不同的路径运动。一种方法是选择邻近结点以改变路径。

    另一种方法是让每个物体都意识到其它物体的存在(或许是通过随机选择一个“领导”物体,或者是通过选择一个能够最好地意识到当前情况的物体),同时仅仅为领导寻路。然后用flocking算法让它们以组的形式运动。

    然而还有一种方法是利用A*算法的中间状态。这个状态可以被朝着相同目标移动的多个物体共享,只要物体共享相同的启发式函数和代价函数。当主循环退出时,不要消除OPENCLOSED集;用A*上一次的OPENCLOSED集开始下一次的循环(下一个物体的开始位置)。(这可以被看成是中断算法和提前退出部分的一般化)

    3.4.4 细化

    如果地图中没有障碍物,而有不同代价的地形,那么可以通过低估地形的代价来计算一条初始路径。例如,如果草地的代价是1,山地代价是2,山脉的代价是3,那么A*会考虑通过3个草地以避免1个山脉。通过把草地看成1,山地看成1.1,而山脉看成1.2来计算初始路径,A*将会用更少的时间去设法避免山脉,而且可以更快地找到一条路径(这接近于精确启发函数的效果)。一旦找到一条路径,物体就可以开始移动,游戏循环就可以继续了。当多余的CPU时间是可用的时候,可以用真实的移动代价去计算更好的路径。

    4 A*算法的变种

    4.1 beam search

    A*的主循环中,OPEN集保存所有需要检查的结点。Beam SearchA*算法的一个变种,这种算法限定了OPEN集的尺寸。如果OPEN集变得过大,那些没有机会通向一条好的路径的结点将被抛弃。缺点是你必须让排序你的集合以实现这个,这限制了可供选择的数据结构。

    4.2 迭代深化

    迭代深化是一种在许多AI算法中使用的方法,这种方法从一个近似解开始,逐渐得到更精确的解。该名称来源于游戏树搜索,需要查看前面几步(比如在象棋里),通过查看前面更多步来提高树的深度。一旦你的解不再有更多的改变或者改善,就可以认为你已经得到足够好的解,当你想要进一步精确化时,它不会再有改善。在ID-A*中,深度是f值的一个cutoff。当f的值太大时,结点甚至将不被考虑(例如,它不会被加入OPEN集中)。第一次迭代只处理很少的结点。此后每一次迭代,访问的结点都将增加。如果你发现路径有所改善,那么就继续增加cutoff,否则就可以停止了。更多的细节请参考这些关于ID-A*的资料:http://www.apl.jhu.edu/~hall/AI-Programming/IDA-Star.html

    我本人认为在游戏地图中没有太大的必要使用ID-A*寻路。ID算法趋向于增加计算时间而减少内存需求。然而在地图路径搜索中,“结点”是很小的——它们仅仅是坐标而已。我认为不保存这些结点以节省空间并不会带来多大改进。

    4.3 动态衡量

    在动态衡量中,你假设在开始搜索时,最重要的是讯速移动到任意位置;而在搜索接近结束时,最重要的是移动到目标点。

    f(p) = g(p) + w(p) * h(p)

    启发函数中带有一个权值(weight)(w>=1)。当你接近目标时,你降低这个权值;这降低了启发函数的重要性,同时增加了路径真实代价的相对重要性。

    4.4 带宽搜索

    带宽搜索(Bandwidth Search)有两个对有些人也许有用的特性。这个变种假设h是过高估计的值,但不高于某个数e。如果这就是你遇到的情况,那么你得到的路径的代价将不会比最佳路径的代价超过e。重申一次,你的启发函数设计的越好,最终效果就越好。

    另一个特性是,你可以丢弃OPEN集中的某些结点。当h+d比路径的真实代价高的时候(对于某些d),你可以丢弃那些f值比OPEN集中的最好结点的f值高至少e+d的结点。这是一个奇怪的特性。对于好的f值你有一个“范围”("band"),任何在这个范围之外的结点都可以被丢弃掉,因为这个结点肯定不会在最佳路径上。

    好奇地(Curiously),你可以对这两种特性使用不同的启发函数,而问题仍然可以得到解决。使用一个启发函数以保证你得到的路径不会太差,另一个用于检查从OPEN集中去掉哪些结点。

    4.5 双向搜索

    与从开始点向目标点搜索不同的是,你也可以并行地进行两个搜索——一个从开始点向目标点,另一个从目标点向开始点。当它们相遇时,你将得到一条好的路径。

    这听起来是个好主意,但我不会给你讲很多内容。双向搜索的思想是,搜索过程生成了一棵在地图上散开的树。一棵大树比两棵小树差得多,所以最好是使用两棵较小的搜索树。然而我的试验表明,在A*中你得不到一棵树,而只是在搜索地图中当前位置附近的区域,但是又不像Dijkstra算法那样散开。事实上,这就是让A*算法运行得如此快的原因——无论你的路径有多长,它并不进行疯狂的搜索,除非路径是疯狂的。它只尝试搜索地图上小范围的区域。如果你的地图很复杂,双向搜索会更有用。

    面对面的方法(The front-to-front variation)把这两种搜索结合在一起。这种算法选择一对具有最好的g(start,x) + h(x,y) + g(y,goal)的结点,而不是选择最好的前向搜索结点——g(start,x) + h(x,goal),或者最好的后向搜索结点——g(y,goal) + h(start,y)。

    Retargeting方法不允许前向和后向搜索同时发生。它朝着某个最佳的中间结点运行前向搜索一段时间,然后再朝这个结点运行后向搜索。然后选择一个后向最佳中间结点,从前向最佳中间结点向后向最佳中间结点搜索。一直进行这个过程,直到两个中间结点碰到一块。

    4.6 动态A*与终身计划A*

    有一些A*的变种允许当初始路径计算出来之后,世界发生改变。D*用于当你没有全局所有信息的时候。如果你没有所有的信息,A*可能会出错;D*的贡献在于,它能纠正那些错误而不用过多的时间。LPA*用于代价会改变的情况。在A*中,当地图发生改变时,路径将变得无效;LPA*可以重新使用之前A*的计算结果并产生新的路径。然而,D*LPA*都需要很多内存——用于运行A*并保存它的内部信息(OPENCLOSED集,路径树,g值),当地图发生改变时,D*或者LPA*会告诉你,是否需要就地图的改变对路径作调整。在一个有许多运动着的物体的游戏中,你经常不希望保存所有这些信息,所以D*LPA*在这里并不适用。它们是为机器人技术而设计的,这种情况下只有一个机器人——你不需要为别的机器人寻路而重用内存。如果你的游戏只有一个或者少数几个物体,你可以研究一下D*或者LPA*

    处理运动障碍物

    一个路径搜索算法沿着固定障碍物计算路径,但是当障碍物会运动时情况又怎样?当一个物体到达一个特写的位置,原来的障碍物也许不再在那儿了,或者一个新的障碍物也许到达那儿。处理该问题的一个方法是放弃路径搜索而使用运动算法(movement algorithms)替代,这就不能look far ahead;这种方法会在后面的部分中讨论。这一部分将对路径搜索方法进行修改从而解决运动障碍物的问题。

    5.1 重新计算路径

    当时间渐渐过去,我们希望游戏世界有所改变。以前搜索到的一条路径到现在也许不再是最佳的了。对旧的路径用新的信息进行更新是有价值的。以下规则可以用于决定什么时候需要重新计算路径:

    • 每N步:这保证用于计算路径的信息不会旧于N步。
    • 任何可以使用额外的CPU时间的时候:这允许动态调整路径的性质;在物体数量多时,或者运行游戏的机器比较慢时,每个物体对CPU的使用可得到减少。
    • 当物体拐弯或者跨越一个导航点(waypoint)的时候。
    • 当物体附近的世界改变了的时候。

    重计算路径的主要缺点是许多路径信息被丢弃了。例如,如果路径是100步长,每10步重新计算一次,路径的总步数将是100+90+80+70+60+50+40+30+20+10 = 550。对M步长的路径,大约需要计算M^2步。因此如果你希望有许多很长的路径,重计算不是个好主意。重新使用路径信息比丢弃它更好。

    5.2 路径拼接

    当 一条路径需要被重新计算时,意味着世界正在改变。对于一个正在改变的世界,对地图中当前邻近的区域总是比对远处的区域了解得更多。因此,我们应该集中于在 附近寻找好的路径,同时假设远处的路径不需要重新计算,除非我们接近它。与重新计算整个路径不同,我们可以重新计算路径的前M步:

    1. 令p[1]..p[N]为路径(N步)的剩余部分
    2. 为p[1]到p[M]计算一条新的路径
    3. 把这条新路径拼接(Splice)到旧路径:把p[1]..p[M]用新的路径值代替

    因为p[1]p[M]比分开的M步小(原文:Since p[1] and p[M] are fewer than M steps apart),看起来新路径不会很长。不幸的是,新的路径也许很长而且不够好。上面的图显示了这种情况。最初的红色路径是1-2-3-4,褐色的是障碍物。如果我们到达2并且发现从2到达3的路径被封锁了,路径拼接技术会把2-32-5-3取代,结果是物体沿着路径1-2-5-3-4运动。我们可以看到这不是一条好的路径,蓝色的路径1-2-5-4是一条更好的路径。

    通常可以通过查看新路径的长度检测到坏的路径。如果这严格大于M,就可能是不好的。一个简单的解决方法是,为搜索算法设置一个最大路径长度。如果找不到一条短的路径,算法返回错误代码;这种情况下,用重计算路径取代路径拼接,从而得到路径1-2-5-4.

    对于其它情况,对于N步的路径,路径拼接会计算2N或者3N步,这取决于拼接新路径的频率。对于对世界的改变作反应的能力而言,这个代价是相当低的。令人吃惊的是这个代价和拼接的步数M无关。M不影响CPU时间,而控制了响应和路径质量的折衷。如果M太大,物体的移动将不能快速对地图的改变作出反应。如果M太小,拼接的路径可能太短以致不能正确地绕过障碍物;许多不理想的路径(如1-2-5-3-4)将被找到。尝试不同的M值和不同的拼接标准(如每3/4 M),看看哪一种情况对你的地图最合适。

    路径拼接确实比重计算路径要快,但它不能对路径的改变作出很好的反应。经常可以发现这种情况并用路径重计算来取代。也可以调整一些变量,如M和寻找新路径的时机,所以可以对该方法进行调整(甚至在运行时)以用于不同的情况。

    NoteBryan Stout 有两个算法,Patch-OnePatch-All,他从路径拼接中得到灵感,并在实践中运行得很好。他出席了GDC 2007https://www.cmpevents.com/GD07/a.asp?option =C &V=11& SessID=4608);一旦他把资料放在网上,我将链接过去。

    Implementation Note:

    反向保存路径,从而删除路径的开始部分并用不同长度的新路径拼接将更容易,因为这两个操作都将在数组的末尾进行。本质上你可以把这个数组看成是堆栈因为顶部的元素总是下一个要使用的。

    5.3 监视地图变化

    与 间隔一段时间重计算全部或部分路径不同的是,可以让地图的改变触发一次重计算。地图可以分成区域,每个物体都可以对某些区域感兴趣(可以是包含部分路径的 所有区域,也可以只是包含部分路径的邻近区域)。当一个障碍物进入或者离开一个区域,该区域将被标识为已改变,所有对该区域感兴趣的物体都被通知到,所以 路径将被重新计算以适应障碍物的改变。

    这种技术有许多变种。例如,可以每隔一定时间通知物体,而不是立即通知物体。多个改变可以成组地触发一个通知,因此避免了额外的重计算。另一个例子是,让物体检查区域,而不是让区域通知物体。

    监视地图变化允许当障碍物不改变时物体避免重计算路径,所以当你有许多区域并不经常改变时,考虑这种方法。

    5.4 预测障碍物的运动

    如果障碍物的运动可以预测,就能为路径搜索考虑障碍物的未来位置。一个诸如A*的算法有一个代价函数用以检查穿过地图上一点的代价有多难。A*可以被改进从而知道到达一点的时间需求(通过当前路径长度来检查),而现在则轮到代价函数了。代价函数可以考虑时间,并用预测的障碍物位置检查在某个时刻地图某个位置是否可以通过。这个改进不是完美的,然而,因为它并不考虑在某个点等待障碍物自动离开的可能性,同时A*并不区分到达相同目的地的不同的路径,而是针对不同的目的地,所以还是可以接受的。

    预计算路径的空间代价

    有时,路径计算的限制因素不是时间,而是用于数以百计的物体的存储空间。路径搜索器需要空间以运行算法和保存路径。算法运行所需的临时空间(在A*中是OPENCLOSED集)通常比保存结果路径的空间大许多。通过限制在一定的时间计算一条路径,可以把临时空间数量最小化。另外,为OPENCLOSED集所选择的数据结构的不同,最小化临时空间的程度也有很大的不同。这一部分聚集于优化用于计算路径的空间代价。

    6.1 位置VS方向

    一条路径可以用位置或者方向来表示。位置需要更多的空间,但是有一个优点,易于查询路径中的任意位置或者方向而不用沿着路径移动。当保存方向时,只有方向容易被查询;只有沿着整个路径移动才能查询位置。在一个典形的网格地图中,位置可以被保存为两个16位整数,每走一步是32位。而方向是很少的,因此用极少的空间就够了。如果物体只能沿着四个方向移动,每一步用两位就够了;如果物体能沿着6个或者8个方向移动,每一步也只需要三位。这些对于保存路径中的位置都有明显的空间节省。Hannu Kankaanpaa指出可以进一步减少空间需求,那就是保存相对方向(右旋60度)而不是绝对方向(朝北走)。有些相对方向对某些物体来说意义不大。比如,如果你的物体朝北移动,那么下一步朝南移动的可能性很小。在只有六种方向的游戏中,你只有五个有意义的方向。在某些地图中,也许只有三个方向(直走,左旋60度,右旋60度)有意义,而其它地图中,右旋120度是有效的(比如,沿着陡峭的山坡走之字形的路径时)。

    6.2 路径压缩

    一旦找到一条路径,可以对它进行压缩。可以用一个普通的压缩算法,但这里不进行讨论。使用特定的压缩算法可以缩小路径的存储,无论它是基于位置的还是基于方向的。在做决定之前,考察你的游戏中的路径以确定哪种压缩效果最好。另外还要考虑实现和调试,代码量,and whether it really matters.如果你有300个物体并且在同一时刻只有50个在移动,同时路径比较短(100步),内存总需求大概只有不到50k,总之,没有必要担心压缩的效果。

    6.2.1 位置存储

    在障碍物比地形对路径搜索影响更大的地图中,路径中有大部分是直线的。如果是这种情况,那么路径只需要包含直线部分的终止点(有时叫waypoints)。此时移动过程将包含检查下一结点和沿着直线向前移动。

    6.2.2 方向存储

    保存方向时,有一种情况是同一个方向保存了很多次。可以用简单的方法节省空间。

    一种方法是保存方向以及朝着该方向移动的次数。和位置存储的优化不同,当一个方向并不是移动很多次时,这种优化的效果反而不好。同样的,对于那些可以进行位置压缩的直线来说,方向压缩是行不通的,因为这条直线可能没有和正在移动的方向关联。通过相对方向,你可以把“继续前进”当作可能的方向排除掉。Hannu Kankaanpaa指出,在一个八方向地图中,你可以去掉前,后,以及向左和向右135度(假设你的地图允许这个),然后你可以仅用两个比特保存每个方向。

    另一种保存路径的方法是变长编码。这种想法是使用一个简单的比特(0)保存最一般的步骤:向前走。使用一个“1”表示拐弯,后边再跟几个比特表示拐弯的方向。在一个四方向地图中,你只能左转和右转,因此可以用“10”表示左转,“11”表示右转。

    变长编码比run length encoding更一般,并且可以压缩得更好,但对于较长的直线路径则不然。序列(向北直走6步,左转,直走3步,右转,直走5步,左转,直走2步)用run length encoding表示是[(NORTH, 6), (WEST, 3), (NORTH, 5), (WEST, 2)]。如果每个方向用2比特,每个距离用8比特,保存这条路径需要40比特。而对于变长编码,你用1比特表示每一步,2比特表示拐弯——[NORTH 0 0 0 0 0 0 10 0 0 0 11 0 0 0 0 0 10 0 0]——一共24比特。如果初始方向和每次拐弯对应1步,则每次拐弯都节省了一个比特,结果只需要20比特保存这条路径。然而,用变长编码保存更长的路径时需要更多的空间。序列(向北直走200)run length encoding表示是[(NORTH, 200)],总共需要10比特。用变长编码表示同样的序列则是[NORTH 0 0 ...],一共需要202比特。

    6.3 计算导航点

    一个导航点(waypoint)是路径上的一个结点。与保存路径上的每一步不同,在进行路径搜索之后,一个后处理(post-processing)的步骤可能会把若干步collapse(译者:不好翻译,保留原单词)为一个简单的导航点,这经常发生在路径上那些方向发生改变的地方,或者在一个重要的(major)位置如城市。然后运动算法将在两个导航点之间运行。

    6.4 极限路径长度

    当地图中的条件或者秩序会发生改变时,保存一条长路径是没有意义的,因为在从某些点开始,后边的路径已经没有用了。每个物体都可以保存路径开始时的特定几步,然后当路径已经没用时重新计算路径。这种方法虑及了(allows for)对每个物体使用数据的总量的管理。

    6.5 总结

    在游戏中,路径潜在地花费了许多存储空间,特别是当路径很长并且有很多物体需要寻路时。路径压缩,导航点和beacons通过把多个步骤保存为一个较小数据从而减少了空间需求。Waypoints rely on straight-line segments being common so that we have to store only the endpoints, while beacons rely on there being well-known paths calculated beforehand between specially marked places on the map.(译者:此处不好翻译,暂时保留原文)如果路径仍然用了许多存储空间,可以限制路径长度,这就回到了经典的时间-空间折衷法:为了节省空间,信息可以被丢弃,稍后才重新计算它。

    原文地址:http://theory.stanford.edu/~amitp/GameProgramming/

     

    1 导言

    1.1 算法

    1.2 Dijkstra算法与最佳优先搜索

    1.3 A*算法

    2 启发式算法

    2.1 A*对启发式函数的使用

    2.2 速度还是精确度?

    2.3 衡量单位

    2.4 精确的启发式函数

    2.4.1 预计算的精确启发式函数

    2.4.2 线性精确启发式算法

    2.5 网格地图中的启发式算法

    2.5.1 曼哈顿距离

    2.5.2 对角线距离

    2.5.3 欧几里得距离

    2.5.4 平方后的欧几里得距离

    2.5.5 Breaking ties

    2.5.6 区域搜索

    3 Implementation notes

    3.1 概略

    3.2 源代码

    3.3 集合的表示

    3.3.1 未排序数组或链表

    3.3.2 排序数组

    3.3.3 排序链表

    3.3.4 排序跳表

    3.3.5 索引数组

    3.3.6 哈希表

    3.3.7 二元堆

    3.3.8 伸展树

    3.3.9 HOT队列

    3.3.10 比较

    3.3.11 混合实现

    3.4 与游戏循环的交互

    3.4.1 提前退出

    3.4.2 中断算法

    3.4.3 组运动

    3.4.4 细化

    4 A*算法的变种

    4.1 beam search

    4.2 迭代深化

    4.3 动态衡量

    4.4 带宽搜索

    4.5 双向搜索

    4.6 动态A*与终身计划A*

    5 处理运动障碍物

    5.1 重新计算路径

    5.2 路径拼接

    5.3 监视地图变化

    5.4 预测障碍物的运动

    6 预计算路径的空间代价

    6.1 位置VS方向

    6.2 路径压缩

    6.2.1 位置存储

    6.2.2 方向存储

    6.3 计算导航点

    6.4 极限路径长度

    6.5 总结

     

    导言

      移动一个简单的物体(object)看起来是容易的。而路径搜索是复杂的。为什么涉及到路径搜索就产生麻烦了?考虑以下情况:

     

     

     

     

      物体(unit)最初位于地图的底端并且尝试向顶部移动。物体扫描的区域中(粉红色部分)没有任何东西显示它不能向上移动,因此它持续向上移动。在靠近顶部时,它探测到一个障碍物然后改变移动方向。然后它沿着U形障碍物找到它的红色的路径。相反的,一个路径搜索器(pathfinder)将会扫描一个更大的区域(淡蓝色部分),但是它能做到不让物体(unit)走向凹形障碍物而找到一条更短的路径(蓝色路径)。

      然而你可以扩展一个运动算法,用于对付上图所示的障碍物。或者避免制造凹形障碍,或者把凹形出口标识为危险的(只有当目的地在里面时才进去):

     

     

      比起一直等到最后一刻才发现问题,路径搜索器让你提前作出计划。不带路径搜索的运动(movement)可以在很多种情形下工作,同时可以扩展到更多的情形,但是路径搜索是一种更常用的解决更多问题的方法。

    1.1 算法

      计算机科学教材中的路径搜索算法在数学视角的图上工作——由边联结起来的结点的集合。一个基于图块(tile)拼接的游戏地图可以看成是一个图,每个图块(tile)是一个结点,并在每个图块之间画一条边:

     

      目前,我会假设我们使用二维网格(grid)。稍后我将讨论如何在你的游戏之外建立其他类型的图。

      许多AI领域或算法研究领域中的路径搜索算法是基于任意(arbitrary)的图设计的,而不是基于网格(grid-based)的 图。我们可以找到一些能使用网格地图的特性的东西。有一些我们认为是常识,而算法并不理解。例如,我们知道一些和方向有关的东西:一般而言,如果两个物体 距离越远,那么把其中一个物体向另一个移动将花越多的时间;并且我们知道地图中没有任何秘密通道可以从一个地点通向另一个地点。(我假设没有,如果有的 话,将会很难找到一条好的路径,因为你并不知道要从何处开始。)

    1.2 Dijkstra算法与最佳优先搜索

      Dijkstra算法从物体所在的初始点开始,访问图中的结点。它迭代检查待检查结点集中的结点,并把和该结点最靠近的尚未检查的结点加入待检查结点集。该结点集从初始结点向外扩展,直到到达目标结点。Dijkstra算法保证能找到一条从初始点到目标点的最短路径,只要所有的边都有一个非负的代价值。(我说“最短路径”是因为经常会出现许多差不多短的路径。)在下图中,粉红色的结点是初始结点,蓝色的是目标点,而类菱形的有色区域(注:原文是teal areas)则是Dijkstra算法扫描过的区域。颜色最淡的区域是那些离初始点最远的,因而形成探测过程(exploration)的边境(frontier):

     

      最佳优先搜索(BFS)算法按照类似的流程运行,不同的是它能够评估(称为启发式的)任意结点到目标点的代价。与选择离初始结点最近的结点不同的是,它选择离目标最近的结点。BFS不能保证找到一条最短路径。然而,它比Dijkstra算法快的多,因为它用了一个启发式函数(heuristic )快速地导向目标结点。例如,如果目标位于出发点的南方,BFS将趋向于导向南方的路径。在下面的图中,越黄的结点代表越高的启发式值(移动到目标的代价高),而越黑的结点代表越低的启发式值(移动到目标的代价低)。这表明了与Dijkstra 算法相比,BFS运行得更快。

     

      然而,这两个例子都仅仅是最简单的情况——地图中没有障碍物,最短路径是直线的。现在我们来考虑前边描述的凹型障碍物。Dijkstra算法运行得较慢,但确实能保证找到一条最短路径:

     

      另一方面,BFS运行得较快,但是它找到的路径明显不是一条好的路径:

     

      问题在于BFS是基于贪心策略的,它试图向目标移动尽管这不是正确的路径。由于它仅仅考虑到达目标的代价,而忽略了当前已花费的代价,于是尽管路径变得很长,它仍然继续走下去。

      结合两者的优点不是更好吗?1968年发明的A*算法就是把启发式方法(heuristic approaches)如BFS,和常规方法如Dijsktra算法结合在一起的算法。有点不同的是,类似BFS的启发式方法经常给出一个近似解而不是保证最佳解。然而,尽管A*基于无法保证最佳解的启发式方法,A*却能保证找到一条最短路径。

    1.3 A*算法

      我将集中讨论A*算法。A*是路径搜索中最受欢迎的选择,因为它相当灵活,并且能用于多种多样的情形之中。

      和其它的图搜索算法一样,A*潜在地搜索图中一个很大的区域。和Dijkstra一样,A*能用于搜索最短路径。和BFS一样,A*能用启发式函数(注:原文为heuristic)引导它自己。在简单的情况中,它和BFS一样快。

     

      在凹型障碍物的例子中,A*找到一条和Dijkstra算法一样好的路径:

     

      成功的秘决在于,它把Dijkstra算法(靠近初始点的结点)和BFS算法(靠近目标点的结点)的信息块结合起来。在讨论A*的标准术语中,g(n)表示从初始结点到任意结点n的代价,h(n)表示从结点n到目标点的启发式评估代价(heuristic estimated cost)。在上图中,yellow(h)表示远离目标的结点而teal(g)表示远离初始点的结点。当从初始点向目标点移动时,A*权衡这两者。每次进行主循环时,它检查f(n)最小的结点n,其中f(n) = g(n) + h(n)。

    启发式算法

      启发式函数h(n)告诉A*从任意结点n到目标结点的最小代价评估值。选择一个好的启发式函数是重要的。

    2.1 A*对启发式函数的使用

      启发式函数可以控制A*的行为:

    • 一种极端情况,如果h(n)0,则只有g(n)起作用,此时A*演变成Dijkstra算法,这保证能找到最短路径。
    • 如果h(n)经常都比从n移动到目标的实际代价小(或者相等),则A*保证能找到一条最短路径。h(n)越小,A*扩展的结点越多,运行就得越慢。
    • 如果h(n)精确地等于从n移动到目标的代价,则A*将会仅仅寻找最佳路径而不扩展别的任何结点,这会运行得非常快。尽管这不可能在所有情况下发生,你仍可以在一些特殊情况下让它们精确地相等(译者:指让h(n)精确地等于实际值)。只要提供完美的信息,A*会运行得很完美,认识这一点很好。
    • 如果h(n)有时比从n移动到目标的实际代价高,则A*不能保证找到一条最短路径,但它运行得更快。
    • 另一种极端情况,如果h(n)比g(n)大很多,则只有h(n)起作用,A*演变成BFS算法。

      所以我们得到一个很有趣的情况,那就是我们可以决定我们想要从A*中获得什么。理想情况下(注:原文为At exactly the right point),我们想最快地得到最短路径。如果我们的目标太低,我们仍会得到最短路径,不过速度变慢了;如果我们的目标太高,那我们就放弃了最短路径,但A*运行得更快。

    在游戏中,A*的这个特性非常有用。例如,你会发现在某些情况下,你希望得到一条好的路径("good" path)而不是一条完美的路径("perfect" path)。为了权衡g(n)和h(n),你可以修改任意一个。

    :在学术上,如果启发式函数值是对实际代价的低估,A*算法被称为简单的A算法(原文为simply A)。然而,我继续称之为A*,因为在实现上是一样的,并且在游戏编程领域并不区别A和A*。

    2.2 速度还是精确度?

      A*改变它自己行为的能力基于启发式代价函数,启发式函数在游戏中非常有用。在速度和精确度之间取得折衷将会让你的游戏运行得更快。在很多游戏中,你并不真正需要得到最好的路径,仅需要近似的就足够了。而你需要什么则取决于游戏中发生着什么,或者运行游戏的机器有多快。

      假设你的游戏有两种地形,平原和山地,在平原中的移动代价是1而在山地则是3。A* is going to search three times as far along flat land as it does along mountainous land. 这是因为有可能有一条沿着平原到山地的路径。把两个邻接点之间的评估距离设为1.5可以加速A*的搜索过程。然后A*会将3和1.5比较,这并不比把3和1比较差。It is not as dissatisfied with mountainous terrain, so it won't spend as much time trying to find a way around it. Alternatively, you can speed up up A*'s search by decreasing the amount it searches for paths around mountains―just tell A* that the movement cost on mountains is 2 instead of 3. Now it will search only twice as far along the flat terrain as along mountainous terrain. Either approach gives up ideal paths to get something quicker.

    速度和精确度之间的选择前不是静态的。你可以基于CPU的速度、用于路径搜索的时间片数、地图上物体(units)的数量、物体的重要性、组(group)的大小、难度或者其他任何因素来进行动态的选择。取得动态的折衷的一个方法是,建立一个启发式函数用于假定通过一个网格空间的最小代价是1,然后建立一个代价函数(cost )用于测量(scales):

    g’(n) = 1 + alpha * ( g(n) – 1 )

      如果alpha是0,则改进后的代价函数的值总是1。这种情况下,地形代价被完全忽略,A*工作变成简单地判断一个网格可否通过。如果alpha是1,则最初的代价函数将起作用,然后你得到了A*的所有优点。你可以设置alpha的值为0到1的任意值。

      你也可以考虑对启发式函数的返回值做选择:绝对最小代价或者期望最小代价。例如,如果你的地图大部分地形是代价为2的草地,其它一些地方是代价为1的道路,那么你可以考虑让启发式函数不考虑道路,而只返回2*距离。

      速度和精确度之间的选择并不是 全局的。在地图上的某些区域,精确度是重要的,你可以基于此进行动态选择。例如,假设我们可能在某点停止重新计算路径或者改变方向,则在接近当前位置的地 方,选择一条好的路径则是更重要的,因此为何要对后续路径的精确度感到厌烦?或者,对于在地图上的一个安全区域,最短路径也许并不十分重要,但是当从一个 敌人的村庄逃跑时,安全和速度是最重要的。(译者注:译者认为这里指的是,在安全区域,可以考虑不寻找精确的最短路径而取近似路径,因此寻路快;但在危险 区域,逃跑的安全性和逃跑速度是重要的,即路径的精确度是重要的,因此可以多花点时间用于寻找精确路径。)

    2.3 衡量单位

     A*计算f(n) = g(n) + h(n)。为了对这两个值进行相加,这两个值必须使用相同的衡量单位。如果g(n)用小时来衡量而h(n)用米来衡量,那么A*将会认为g或者h太大或者太小,因而你将不能得到正确的路径,同时你的A*算法将运行得更慢。

    2.4 精确的启发式函数

      如果你的启发式函数精确地等于实际最佳路径(optimal path),如下一部分的图中所示,你会看到此时A*扩展的结点将非常少。A*算法内部发生的事情是:在每一结点它都计算f(n) = g(n) + h(n)。当h(n)精确地和g(n)匹配(译者注:原文为match)时,f(n)的值在沿着该路径时将不会改变。不在正确路径(right path)上的所有结点的f值均大于正确路径上的f值(译者注:正确路径在这里应该是指最短路径)。如果已经有较低f值的结点,A*将不考虑f值较高的结点,因此它肯定不会偏离最短路径。

    2.4.1 预计算的精确启发式函数

      构造精确启发函数的一种方法是预先计算任意一对结点之间最短路径的长度。在许多游戏的地图中这并不可行。然后,有几种方法可以近似模拟这种启发函数:

    • Fit a coarse grid on top of the fine grid. Precompute the shortest path between any pair of coarse grid locations.
    • Precompute the shortest path between any pair of waypoints. This is a generalization of the coarse grid approach.

      (译者:此处不好翻译,暂时保留原文)

    然后添加一个启发函数h’用于评估从任意位置到达邻近导航点(waypoints)的代价。(如果愿意,后者也可以通过预计算得到。)最终的启发式函数可以是:

    h(n) = h'(n, w1) + distance(w1, w2), h'(w2, goal)

    或者如果你希望一个更好但是更昂贵的启发式函数,则分别用靠近结点和目标的所有的w1,w2对对上式进行求值。(译者注:原文为or if you want a better but more expensive heuristic, evaluate the above with all pairs w1, w2 that are close to the node and the goal, respectively.)

    2.4.2 线性精确启发式算法

      在特殊情况下,你可以不通过预计算而让启发式函数很精确。如果你有一个不存在障碍物和slow地形,那么从初始点到目标的最短路径应该是一条直线。

      如果你正使用简单的启发式函数(我们不知道地图上的障碍物),则它应该和精确的启发式函数相符合(译者注:原文为match)。如果不是这样,则你会遇到衡量单位的问题,或者你所选择的启发函数类型的问题。

    2.5 网格地图中的启发式算法

      在网格地图中,有一些众所周知的启发式函数。

    2.5.1 曼哈顿距离

    标准的启发式函数是曼哈顿距离(Manhattan distance)。考虑你的代价函数并找到从一个位置移动到邻近位置的最小代价D。因此,我的游戏中的启发式函数应该是曼哈顿距离的D倍:

           H(n) = D * (abs ( n.x – goal.x ) + abs ( n.y – goal.y ) )

    你应该使用符合你的代价函数的衡量单位。

     

     

    (Note: the above image has a tie-breaker added to the heuristic.}

    (译者注:曼哈顿距离——两点在南北方向上的距离加上在东西方向上的距离,即DIJ=|XI-XJ|+|YI-YJ|。对于一个具有正南正北、正东正西方向规则布局的城镇街道,从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离因此曼哈顿距离又称为出租车距离,曼哈顿距离不是距离不变量,当坐标轴变动时,点间的距离就会不同——百度知道)

    2.5.2 对角线距离

    如果在你的地图中你允许对角运动那么你需要一个不同的启发函数。(4 east, 4 north)的曼哈顿距离将变成8*D。然而,你可以简单地移动(4 northeast)代替,所以启发函数应该是4*D。这个函数使用对角线,假设直线和对角线的代价都是D:

    h(n) = D * max(abs(n.x - goal.x), abs(n.y - goal.y))

     

    如果对角线运动的代价不是D,但类似于D2 = sqrt(2) * D,则上面的启发函数不准确。你需要一些更准确(原文为sophisticated)的东西:

    h_diagonal(n) = min(abs(n.x - goal.x), abs(n.y - goal.y))

    h_straight(n) = (abs(n.x - goal.x) + abs(n.y - goal.y))

    h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))

    这里,我们计算h_diagonal(n):沿着斜线可以移动的步数;h_straight(n):曼哈顿距离;然后合并这两项,让所有的斜线步都乘以D2,剩下的所有直线步(注意这里是曼哈顿距离的步数减去2倍的斜线步数)都乘以D。

    2.5.3 欧几里得距离

    如果你的单位可以沿着任意角度移动(而不是网格方向),那么你也许应该使用直线距离:

    h(n) = D * sqrt((n.x-goal.x)^2 + (n.y-goal.y)^2)

    然而,如果是这样的话,直接使用A*时将会遇到麻烦,因为代价函数g不会match启发函数h。因为欧几里得距离比曼哈顿距离和对角线距离都短,你仍可以得到最短路径,不过A*将运行得更久一些:

     

    2.5.4 平方后的欧几里得距离

    我曾经看到一些A*的网页,其中提到让你通过使用距离的平方而避免欧几里得距离中昂贵的平方根运算:

    h(n) = D * ((n.x-goal.x)^2 + (n.y-goal.y)^2)

    不要这样做!这明显地导致衡量单位的问题。当A*计算f(n) = g(n) + h(n),距离的平方将比g的代价大很多,并且你会因为启发式函数评估值过高而停止。对于更长的距离,这样做会靠近g(n)的极端情况而不再计算任何东西,A*退化成BFS

     

    2.5.5 Breaking ties

    导致低性能的一个原因来自于启发函数的ties(注:这个词实在不知道应该翻译为什么)。当某些路径具有相同的f值的时候,它们都会被搜索(explored),尽管我们只需要搜索其中的一条:


    Ties in f values.

    为了解决这个问题,我们可以为启发函数添加一个附加值(译者注:原文为small tie breaker)。附加值对于结点必须是确定性的(也就是说,不能是随机的数),而且它必须让f值体现区别。因为A*f值排序,让f值不同意味着只有一个"equivalent"f值会被检测。

    一种添加附加值的方式是稍微改变(译者注:原文为nudgeh的衡量单位。如果我们减少衡量单位(译者注:原文为scale it downwards),那么当我们朝着目标移动的时候f将逐渐增加。很不幸,这意味着A*倾向于扩展到靠近初始点的结点,而不是靠近目标的结点。我们可以增加衡量单位(译者注:原文为scale it downwards scale h upwards slightly)(甚至是0.1%),A*就会倾向于扩展到靠近目标的结点。

    heuristic *= (1.0 + p)

    选择因子p使得p < 移动一步(step)的最小代价 / 期望的最长路径长度。假设你不希望你的路径超过1000步(step),你可以使p = 1 / 1000。添加这个附加值的结果是,A*比以前搜索的结点更少了。


    Tie-breaking scaling added to heuristic.

    当存在障碍物时,当然仍要在它们周围寻找路径,但要意识到,当绕过障碍物以后,A*搜索的区域非常少:


    Tie-breaking scaling added to heuristic, works nicely with obstacles.

    Steven van Dijk建议,一个更直截了当的方法是把h传递到比较函数(comparison )。当f值相等时,比较函数检查h,然后添加附加值。

    一个不同的添加附加值的方法是,倾向于从初始点到目标点的连线(直线):

    dx1 = current.x - goal.x

    dy1 = current.y - goal.y

    dx2 = start.x - goal.x

    dy2 = start.y - goal.y

    cross = abs(dx1*dy2 - dx2*dy1)

    heuristic += cross*0.001

    这段代码计算初始-目标向量(start to goal vector)和当前-目标向量(current point to goal vector)的向量叉积(vector cross-product)。When these vectors don't line up, the cross product will be larger.结果是,这段代码选择的路径稍微倾向于从初始点到目标点的直线。当没有障碍物时,A*不仅搜索很少的区域,而且它找到的路径看起来非常棒:


    Tie-breaking cross-product added to heuristic, produces pretty paths.

    然而,因为这种附加值倾向于从初始点到目标点的直线路径,当出现障碍物时将会出现奇怪的结果(注意这条路径仍是最佳的,只是看起来很奇怪):


    Tie-breaking cross-product added to heuristic, less pretty with obstacles.

    为了交互地研究这种附加值方法的改进,请参考James MacgillA*applethttp://www.ccg.leeds.ac.uk/james/aStar/ [如果链接无效,请使用这个镜像(http://www.vision.ee.ethz.ch/~buc/astar/AStar.html](译者注:两个链接均无效)。使用“Clear”以清除地图,选择地图对角的两个点。当你使用“Classic A*”方法,你会看到附加值的效果。当你使用“Fudge”方法,你会看到上面给启发函数添加叉积后的效果。

    然而另一种添加附加值的方法是,小心地构造你的A*优先队列,使新插入的具有特殊f值的结点总是比那些以前插入的具有相同f值的旧结点要好一些。

    你也许也想看看能够更灵活地(译者注:原文为sophisticated)添加附加值的AlphA*算法(http://home1.stofanet.dk/breese/papers.html),不过用这种算法得到的路径是否能达到最佳仍在研究中。AlphA*具有较好的适应性,而且可能比我在上面讨论的附加值方法运行得都要好。然而,我所讨论的附加值方法非常容易实现,所以从它们开始吧,如果你需要得到更好的效果,再去尝试AlphA*

    2.5.6 区域搜索

      如果你想搜索近目标的任意不确定结点,而不是某个特定的结点,你应该建立一个启发函数h’(x),使得h’(x)h1(x), h2(x), h3(x)。。。的最小值,而这些h1, h2, h3是邻近结点的启发函数。然而,一种更快的方法是让A*仅搜索目标区域的中心。一旦你从OPEN集合中取得任意一个邻近目标的结点,你就可以停止搜索并建立一条路径了。

    3 Implementation notes

    3.1 概略

      如果不考虑具体实现代码,A*算法是相当简单的。有两个集合,OPEN集和CLOSED集。其中OPEN集保存待考查的结点。开始时,OPEN集只包含一个元素:初始结点。CLOSED集保存已考查过的结点。开始时,CLOSED集是空的。如果绘成图,OPEN集就是被访问区域的边境(frontier)而CLOSED集则是被访问区域的内部(interior)。每个结点同时保存其父结点的指针因此我们可以知道它是如何被找到的。

      在主循环中重复地从OPEN集中取出最好的结点nf值最小的结点)并检查之。如果n是目标结点,则我们的任务完成了。否则,结点n被从OPEN集中删除并加入CLOSED集。然后检查它的邻居n’。如果邻居n’CLOSED集中,那么它是已经被检查过的,所以我们不需要考虑它*;如果n’OPEN集中,那么它是以后肯定会被检查的,所以我们现在不考虑它*。否则,把它加入OPEN集,把它的父结点设为n。到达n’的路径的代价g(n’),设定为g(n) + movementcost(n, n’)

    (*)这里我忽略了一个小细节。你确实需要检查结点的g值是否更小了,如果是的话,需要重新打开(re-open)它。

    OPEN = priority queue containing START

    CLOSED = empty set

    while lowest rank in OPEN is not the GOAL:

      current = remove lowest rank item from OPEN

      add current to CLOSED

      for neighbors of current:

        cost = g(current) + movementcost(current, neighbor)

        if neighbor in OPEN and cost less than g(neighbor):

          remove neighbor from OPEN, because new path is better

        if neighbor in CLOSED and cost less than g(neighbor): **

          remove neighbor from CLOSED

        if neighbor not in OPEN and neighbor not in CLOSED:

          set g(neighbor) to cost

          add neighbor to OPEN

          set priority queue rank to g(neighbor) + h(neighbor)

          set neighbor's parent to current

     

    reconstruct reverse path from goal to start

    by following parent pointers

    (**) This should never happen if you have an admissible heuristic. However in games we often have inadmissible heuristics.

     

     

    3.2 源代码

    我自己的(旧的)C++A*代码是可用的:path.cpp (http://theory.stanford.edu/~amitp/ GameProgramming/path.cpp)path.h (http://theory.stanford.edu/~amitp/GameProgramming/ path.h),但是不容易阅读。还有一份更老的代码(更慢的,但是更容易理解),和很多其它的A*实现一样,它在Steve Woodcock'的游戏AI页面(http://www.gameai.com/ai.html)。

    在网上,你能找到CC++Visual Basic Java(http://www.cuspy.com/software/pathfinder/ doc/)Flash/Director/Lingo, C#(http://www.codeproject.com/csharp/CSharpPathfind.asp), Delphi, Lisp, Python, Perl, Prolog 实现的A*代码。一定的阅读Justin Heyes-JonesC++实现(http://www.geocities.com/jheyesjones/astar.html)。

    3.3 集合的表示

    你首先想到的用于实现OPEN集和CLOSED集的数据结构是什么?如果你和我一样,你可能想到“数组”。你也可能想到“链表”。我们可以使用很多种不同的数据结构,为了选择一种,我们应该考虑我们需要什么样的操作。

    OPEN集上我们主要有三种操作:主循环重复选择最好的结点并删除它;访问邻居结点时需要检查它是否在集合里面;访问邻居结点时需要插入新结点。插入和删除最佳是优先队列(http://members.xoom.com/killough/heaps.html)的典型操作。

    选择哪种数据结构不仅取决于操作,还取决于每种操作执行的次数。检查一个结点是否在集合中这一操作对每个被访问的结点的每个邻居结点都执行一次。删除最佳操作对每个被访问的结点都执行一次。被考虑到的绝大多数结点都会被访问;不被访问的是搜索空间边缘(fringe)的结点。当评估数据结构上面的这些操作时,必须考虑fringe(F)的最大值。

    另外,还有第四种操作,虽然执行的次数相对很少,但还是必须实现的。如果正被检查的结点已经在OPEN集中(这经常发生),并且如果它的f值比已经在OPEN集中的结点要好(这很少见),那么OPEN集中的值必须被调整。调整操作包括删除结点(f值不是最佳的结点)和重插入。这两个步骤必须被最优化为一个步骤,这个步骤将移动结点。

    3.3.1 未排序数组或链表

    最简单的数据结构是未排序数组或链表。集合关系检查操作(Membership test)很慢,扫描整个结构花费O(F)。插入操作很快,添加到末尾花费O(1)。查找最佳元素(Finding the best element)很慢,扫描整个结构花费O(F)。对于数组,删除最佳元素(Removing the best element)花费O(F),而链表则是O(1)。调整操作中,查找结点花费O(F),改变值花费O(1)

    3.3.2 排序数组

    为了加快删除最挂操作,可以对数组进行排序。集合关系检查操作将变成O(log F),因为我们可以使用折半查找。插入操作会很慢,为了给新元素腾出空间,需要花费 O(F)以移动所有的元素。查找最佳元素操作会很快,因为它已经在末尾了所以花费是O(1)。如果我们保证最佳排序至数组的尾部(best sorts to the end of the array),删除最佳元素操作花费将是O(1)。调整操作中,查找结点花费O(logF),改变值/位置花费O(F)

    3.3.3 排序链表

    在排序数组中,插入操作很慢。如果使用链表则可以加速该操作。集合关系检查操作很慢,需要花费O(F)用于扫描链表。插入操作是很快的,插入新元素只花费O(1)时间,但是查找正确位置需要花费O(F)。查找最佳元素很快,花费O(1)时间,因为最佳元素已经在表的尾部。删除最佳元素也是O(1)。调整操作中,查找结点花费O(F),改变值/位置花费O(1)

    3.3.4 排序跳表

    在未排序链表中查找元素是很慢的。如果用跳表(http://en.wikipedia.org/wiki/Skip_list)代替链表的话,可以加速这个操作。在跳表中,如果有排序键(sort key)的话,集合关系检查操作会很快:O(log F)。如果你知道在何处插入的话,和链表一样,插入操作也是O(1)。如果排序键是f,查找最佳元素很快,达到O(1),删除一个元素也是O(1)。调整操作涉及到查找结点,删除结点和重插入。

    如果我们用地图位置作为跳表的排序键,集合关系检查操作将是O(log F)。在完成集合关系检查后,插入操作是O(1)。查找最佳元素是O(F),删除一个结点是O(1)。因为集合关系检查更快,所以它比未排序链表要好一些。

    如果我们用f值作为跳表的排序键,集合关系检查操作将是O(F)。插入操作是O(1)。查找最佳元素是O(1),删除一个结点是O(1)。这并不比排序链表好。

    3.3.5 索引数组

    如果结点的集合有限并且数目是适当的,我们可以使用直接索引结构,索引函数i(n)把结点n映射到一个数组的索引。未排序与排序数组的长度等于OPEN集的最大值,和它们不同,对所有的n,索引数组的长度总是等于max(i(n))。如果你的函数是密集的(没有不被使用的索引),max(i(n))将是你地图中结点的数目。只要你的地图是网格的,让索引函数密集就是容易的。

    假设i(n)O(1)的,集合关系检查将花费O(1),因为我们几乎不需要检查Array[i(n)]是否包含任何数据。Insertion is O(1), as we just ste Array[i(n)].查找和删除最佳操作是O(numnodes),因为我们必须搜索整个结构。调整操作是O(1)

    3.3.6 哈希表

    索引数组使用了很多内存用于保存不在OPEN集中的所有结点。一个选择是使用哈希表。哈希表使用了一个哈希函数h(n)把地图上每个结点映射到一个哈希码。让哈希表的大小等于N的两倍,以使发生冲突的可能性降低。假设h(n) O(1)的,集体关系检查操作花费O(1);插入操作花费O(1);删除最佳元素操作花费O(numnodes),因为我们需要搜索整个结构。调整操作花费O(1)

    3.3.7 二元堆

    一个二元堆(不要和内存堆混淆)是一种保存在数组中的树结构。和许多普通的树通过指针指向子结点所不同,二元堆使用索引来查找子结点。C++ STL包含了一个二元堆的高效实现,我在我自己的A*代码中使用了它。

    在二元堆中,集体关系检查花费O(F),因为你必须扫描整个结构。插入操作花费O(log F)而删除最佳操作花费也是O(log F)。调整操作很微妙(tricky),花费O(F)时间找到节点,并且很神奇,只用O(log F)来调整。

    我的一个朋友(他研究用于最短路径算法的数据结构)说,除非在你的fringe集里有多于10000个元素,否则二元堆是很不错的。除非你的游戏地图特别大,否则你不需要更复杂的数据结构(如multi-level bucketshttp://www-cs-students.stanford.edu/~csilvers/))。你应该尽可能不用Fibonacci 堆(http://www.star-lab.com/goldberg/pub/neci-tr-96-062.ps),因为虽然它的渐近复杂度很好,但是执行起来很慢,除非F足够大。

    3.3.8 伸展树

    堆是一种基于树的结构,它有一个期望的O(log F)代价的时间操作。然而,问题是在A*算法中,通常的情况是,一个代价小的节点被移除(花费O(log F)的代价,因为其他结点必须从树的底部向上移动),而紧接着一些代价小的节点被添加(花费O(log F)的代价,因为这些结点被添加到底部并且被移动到最顶部)。在这里,堆的操作在预期的情况下和最坏情况下是一样的。如果我们找到这样一种数据结构,最坏情况还是一样,而预期的情况好一些,那么就可以得到改进。

    伸展树(Splay tree)是一种自调整的树结构。任何对树结点的访问都尝试把该结点推到树的顶部(top)。这就产生了一个缓存效果("caching" effect):很少被使用的结点跑到底部(bottom)去了并且不减慢操作(don't slow down operations)。你的splay树有多大并不重要,因为你的操作仅仅和你的“cache size”一样慢。在A*中,低代价的结点使用得很多,而高代价结点经常不被使用,所以高代价结点将会移动到树的底部。

    使用伸展树后,集体关系检查,插入,删除最佳和调整操作都是期望的O(log F)(注:原文为expected O(log F) ),最坏情况是O(F)。然而有代表性的是,缓存过程(caching)避免了最坏情况的发生。Dijkstra算法和带有低估的启发函数(underestimating heuristic)的A*算法却有一些特性让伸展树达不到最优。特别是对结点n和邻居结点n’来说,f(n') >= f(n)。当这发生时,也许插入操作总是发生在树的同一边结果是使它失去了平衡。我没有试验过这个。

    3.3.9 HOT队列

    还有一种比堆好的数据结构。通常你可以限制优先队列中值的范围。给定一个限定的范围,经常会存在更好的算法。例如,对任意值的排序可以在O(N log N)时间内完成,但当固定范围时,桶排序和基数排序可以在O(N)时间内完成。

    我们可以使用HOTHeap On Top)队列(http://www.star-lab.com/goldberg/pub /neci-tr-97-104.ps)来利用f(n') >= f(n),其中n’是n的一个邻居结点。我们删除f(n)值最小的结点n,插入满足f(n) <= f(n') <= f(n) + delta的邻居n',其中delta <= C。常数C是从一结点到邻近结点代价改变量的最大值。因为f(n)OPEN集中的最小f值,并且正要被插入的所有结点都小于或等于f(n) + delta,我们知道OPEN集中的所有f值都不超过一个0..delta的范围。在桶/基数排序中,我们可以用“桶”(buckets)对OPEN集中的结点进行排序。

    使用K桶,我们把O(N)的代价降低到平均O(N/K)。通过HOT队列,顶端的桶使用二元堆而所有其他的桶都是未排序数组。因而,对顶部的桶,集合关系检查代价是预期的O(F/K),插入和删除最佳是O(log (F/K))。对其他桶,集合关系检查是O(F/K),插入是O(1),而删除最佳根本不发生!如果顶端的桶是空的,那么我们必须把下一个桶即未排序数组转换为二元堆。这个操作(“heapify”)可以在O(F/K)时间内完成。在调整操作中,删除是O(F/K),然后插入是O(log (F/K))O(1)

    A*中,我们加入OPEN集中的许多结点实际上根本是不需要的。在这方面HOT队列很有优势,因为不需要的元素的插入操作只花费O(1)时间。只有需要的元素被heapified(代价较低的那些)。唯一一个超过O(1)的操作是从堆中删除结点,只花费O(log (F/K))

    另外,如果C比较小,我们可以只让K = C,则对于最小的桶,我们甚至不需要一个堆,国为在一个桶中的所有结点都有相同的f值。插入和删除最佳都是O(1)时间!有人研究过,HOT队列在至多在OPEN集中有800个结点时和堆一样快,并且如果OPEN集中至多有1500个结点,则比堆快20%。我期望随着结点的增加,HOT队列也更快。

    HOT队列的一个简单的变化是一个二层队列(two-level queue):把好的结点放进一个数据结构(堆或数组)而把坏的结点放进另一个数据结构(数组或链表)。因为大多数进入OPEN集中的结点都“坏的”,它们从不被检查,因而把它们放进出一个大数组是没有害处的。

    3.3.10 比较

    注意有一点很重要,我们并不是仅仅关心渐近的行为(大O符号)。我们也需要关心小常数(low constant)下的行为。为了说明原因,考虑一个O(log F)的算法,和另一个O(F)的算法,其中F是堆中元素的个数。也许在你的机器上,第一个算法的实现花费10000*log(F)秒,而另一个的实现花费2*F秒。当F=256时,第一个算法将花费80000秒而第二个算法花费512秒。在这种情况下,“更快”的算法花费更多的时间,而且只有在当F>200000时才能运行得更快。

    你不能仅仅比较两个算法。你还要比较算法的实现。同时你还需要知道你的数据的大小(size)。在上面的例子中,第一种实现在F>200000时更快,但如果在你的游戏中,F小于30000,那么第二种实现好一些。

    基本数据结构没有一种是完全合适的。未排序数组或者链表使插入操作很快而集体关系检查和删除操作非常慢。排序数组或者链表使集体关系检查稍微快一些,删除(最佳元素)操作非常快而插入操作非常慢。二元堆让插入和删除操作稍微快一些,而集体关系检查则很慢。伸展树让所有操作都快一些。HOT队 列让插入操作很快,删除操作相当快,而集体关系检查操作稍微快一些。索引数组让集体关系检查和插入操作非常快,但是删除操作不可置信地慢,同时还需要花费 很多内存空间。哈希表和索引数组类似,但在普通情况下,它花费的内存空间少得多,而删除操作虽然还是很慢,但比索引数组要快。

    关于更高级的优先队列的资料和实现,请参考Lee Killough的优先队列页面(http://members.xoom.com/killough/heaps.html)。

    3.3.11 混合实现

    为了得到最佳性能,你将希望使用混合数据结构。在我的A*代码中,我使用一个索引数组从而集合关系检查是O(1)的,一个二元堆从而插入操作和删除最佳都是O(log F)的。对于调整操作,我使用索引数组从而花费O(1)时间检查我是否真的需要进行调整(通过在索引数组中保存g值),然后在少数确实需要进行调整的情况中,我使用二元堆从而调整操作花费O(F)时间。你也可以使用索引数组保存堆中每个结点的位置,这让你的调整操作变成O(log F)

    3.4 与游戏循环的交互

    交互式的(尤其是实时的)游戏对最佳路径的计算要求很高。能够得到一个解决方案比得到最佳方案可能更重要。然而在所有其他因素都相同的情况下,短路径比长路径好。

    一般来说,计算靠近初始结点的路径比靠近目标结点的路径更重要一些。立即开始原理(The principle of immediate start):让游戏中的物体尽可能快地开始行动,哪怕是沿着一条不理想的路径,然后再计算一条更好的路径。在实时游戏中,应该更多地关注A*的延迟情况(latency)而不是吞吐量(throughput)。

    可以对物体编程让它们根据自己的本能(简单行为)或者智力(一条预先计算好的路径)来行动。除非它们的智力告诉它们怎么行动,否则它们就根据自己的本能来行动(这是实际上使用的方法,并且Rodney Brook在他的机器人体系结构中也用到)。和立即计算所有路径所不同,让游戏在每一个,两个,或者三个循环中搜索一条路径。让物体在开始时依照本能行动(可能仅仅是简单地朝着目标直线前进),然后才为它们寻找路径。这种方法让让路径搜索的代价趋于平缓,因此它不会集中发生在同一时刻。

    3.4.1 提前退出

    可以从A*算法的主循环中提前退出来同时得到一条局部路径。通常,当找到目标结点时,主循环就退出了。然而,在此之前的任意结点,可以得到一条到达OPEN中当前最佳结点的路径。这个结点是到达目标点的最佳选择,所以它是一个理想的中间结点(原文为so it's a reasonable place to go)。

    可以提前退出的情况包括检查了一定数量的结点,A*算法已经运行了几毫秒时间,或者扫描了一个离初始点有些距离的结点。当使用路径拼接时,应该给被拼接的路径一个比全路径(full path)小的最大长度。

    3.4.2 中断算法

    如果需要进行路径搜索的物体较少,或者如果用于保存OPENCLOSED集的数据结构较小,那么保存算法的状态是可行的,然后退出到游戏循环继续运行游戏。

    3.4.3 组运动

    路径请求并不是均匀分布的。即时策略游戏中有一个常见的情况,玩家会选择多个物体并命令它们朝着同样的目标移动。这给路径搜索系统以沉重的负载。

    在这种情况下,为某个物体寻找到的路径对其它物体也是同样有用的。一种方法是,寻找一条从物体的中心到目的地中心的路径P。对所有物体使用该路径的绝大部分,对每一个物体,前十步和后十步使用为它自己寻找的路径。物体i得到一条从它的开始点到P[10]的路径,紧接着是共享的路径P[10..len(P)-10],最后是从P[len(P)-10]到目的地的路径。

    为每个物体寻找的路径是较短的(平均步数大约是10),而较长的路径被共享。大多数路径只寻找一次并且为所有物体所共享。然而,当玩家们看到所有的物体都沿着相同的路径移动时,将对游戏失去兴趣。为了对系统做些改进,可以让物体稍微沿着不同的路径运动。一种方法是选择邻近结点以改变路径。

    另一种方法是让每个物体都意识到其它物体的存在(或许是通过随机选择一个“领导”物体,或者是通过选择一个能够最好地意识到当前情况的物体),同时仅仅为领导寻路。然后用flocking算法让它们以组的形式运动。

    然而还有一种方法是利用A*算法的中间状态。这个状态可以被朝着相同目标移动的多个物体共享,只要物体共享相同的启发式函数和代价函数。当主循环退出时,不要消除OPENCLOSED集;用A*上一次的OPENCLOSED集开始下一次的循环(下一个物体的开始位置)。(这可以被看成是中断算法和提前退出部分的一般化)

    3.4.4 细化

    如果地图中没有障碍物,而有不同代价的地形,那么可以通过低估地形的代价来计算一条初始路径。例如,如果草地的代价是1,山地代价是2,山脉的代价是3,那么A*会考虑通过3个草地以避免1个山脉。通过把草地看成1,山地看成1.1,而山脉看成1.2来计算初始路径,A*将会用更少的时间去设法避免山脉,而且可以更快地找到一条路径(这接近于精确启发函数的效果)。一旦找到一条路径,物体就可以开始移动,游戏循环就可以继续了。当多余的CPU时间是可用的时候,可以用真实的移动代价去计算更好的路径。

    4 A*算法的变种

    4.1 beam search

    A*的主循环中,OPEN集保存所有需要检查的结点。Beam SearchA*算法的一个变种,这种算法限定了OPEN集的尺寸。如果OPEN集变得过大,那些没有机会通向一条好的路径的结点将被抛弃。缺点是你必须让排序你的集合以实现这个,这限制了可供选择的数据结构。

    4.2 迭代深化

    迭代深化是一种在许多AI算法中使用的方法,这种方法从一个近似解开始,逐渐得到更精确的解。该名称来源于游戏树搜索,需要查看前面几步(比如在象棋里),通过查看前面更多步来提高树的深度。一旦你的解不再有更多的改变或者改善,就可以认为你已经得到足够好的解,当你想要进一步精确化时,它不会再有改善。在ID-A*中,深度是f值的一个cutoff。当f的值太大时,结点甚至将不被考虑(例如,它不会被加入OPEN集中)。第一次迭代只处理很少的结点。此后每一次迭代,访问的结点都将增加。如果你发现路径有所改善,那么就继续增加cutoff,否则就可以停止了。更多的细节请参考这些关于ID-A*的资料:http://www.apl.jhu.edu/~hall/AI-Programming/IDA-Star.html

    我本人认为在游戏地图中没有太大的必要使用ID-A*寻路。ID算法趋向于增加计算时间而减少内存需求。然而在地图路径搜索中,“结点”是很小的——它们仅仅是坐标而已。我认为不保存这些结点以节省空间并不会带来多大改进。

    4.3 动态衡量

    在动态衡量中,你假设在开始搜索时,最重要的是讯速移动到任意位置;而在搜索接近结束时,最重要的是移动到目标点。

    f(p) = g(p) + w(p) * h(p)

    启发函数中带有一个权值(weight)(w>=1)。当你接近目标时,你降低这个权值;这降低了启发函数的重要性,同时增加了路径真实代价的相对重要性。

    4.4 带宽搜索

    带宽搜索(Bandwidth Search)有两个对有些人也许有用的特性。这个变种假设h是过高估计的值,但不高于某个数e。如果这就是你遇到的情况,那么你得到的路径的代价将不会比最佳路径的代价超过e。重申一次,你的启发函数设计的越好,最终效果就越好。

    另一个特性是,你可以丢弃OPEN集中的某些结点。当h+d比路径的真实代价高的时候(对于某些d),你可以丢弃那些f值比OPEN集中的最好结点的f值高至少e+d的结点。这是一个奇怪的特性。对于好的f值你有一个“范围”("band"),任何在这个范围之外的结点都可以被丢弃掉,因为这个结点肯定不会在最佳路径上。

    好奇地(Curiously),你可以对这两种特性使用不同的启发函数,而问题仍然可以得到解决。使用一个启发函数以保证你得到的路径不会太差,另一个用于检查从OPEN集中去掉哪些结点。

    4.5 双向搜索

    与从开始点向目标点搜索不同的是,你也可以并行地进行两个搜索——一个从开始点向目标点,另一个从目标点向开始点。当它们相遇时,你将得到一条好的路径。

    这听起来是个好主意,但我不会给你讲很多内容。双向搜索的思想是,搜索过程生成了一棵在地图上散开的树。一棵大树比两棵小树差得多,所以最好是使用两棵较小的搜索树。然而我的试验表明,在A*中你得不到一棵树,而只是在搜索地图中当前位置附近的区域,但是又不像Dijkstra算法那样散开。事实上,这就是让A*算法运行得如此快的原因——无论你的路径有多长,它并不进行疯狂的搜索,除非路径是疯狂的。它只尝试搜索地图上小范围的区域。如果你的地图很复杂,双向搜索会更有用。

    面对面的方法(The front-to-front variation)把这两种搜索结合在一起。这种算法选择一对具有最好的g(start,x) + h(x,y) + g(y,goal)的结点,而不是选择最好的前向搜索结点——g(start,x) + h(x,goal),或者最好的后向搜索结点——g(y,goal) + h(start,y)。

    Retargeting方法不允许前向和后向搜索同时发生。它朝着某个最佳的中间结点运行前向搜索一段时间,然后再朝这个结点运行后向搜索。然后选择一个后向最佳中间结点,从前向最佳中间结点向后向最佳中间结点搜索。一直进行这个过程,直到两个中间结点碰到一块。

    4.6 动态A*与终身计划A*

    有一些A*的变种允许当初始路径计算出来之后,世界发生改变。D*用于当你没有全局所有信息的时候。如果你没有所有的信息,A*可能会出错;D*的贡献在于,它能纠正那些错误而不用过多的时间。LPA*用于代价会改变的情况。在A*中,当地图发生改变时,路径将变得无效;LPA*可以重新使用之前A*的计算结果并产生新的路径。然而,D*LPA*都需要很多内存——用于运行A*并保存它的内部信息(OPENCLOSED集,路径树,g值),当地图发生改变时,D*或者LPA*会告诉你,是否需要就地图的改变对路径作调整。在一个有许多运动着的物体的游戏中,你经常不希望保存所有这些信息,所以D*LPA*在这里并不适用。它们是为机器人技术而设计的,这种情况下只有一个机器人——你不需要为别的机器人寻路而重用内存。如果你的游戏只有一个或者少数几个物体,你可以研究一下D*或者LPA*

    处理运动障碍物

    一个路径搜索算法沿着固定障碍物计算路径,但是当障碍物会运动时情况又怎样?当一个物体到达一个特写的位置,原来的障碍物也许不再在那儿了,或者一个新的障碍物也许到达那儿。处理该问题的一个方法是放弃路径搜索而使用运动算法(movement algorithms)替代,这就不能look far ahead;这种方法会在后面的部分中讨论。这一部分将对路径搜索方法进行修改从而解决运动障碍物的问题。

    5.1 重新计算路径

    当时间渐渐过去,我们希望游戏世界有所改变。以前搜索到的一条路径到现在也许不再是最佳的了。对旧的路径用新的信息进行更新是有价值的。以下规则可以用于决定什么时候需要重新计算路径:

    • 每N步:这保证用于计算路径的信息不会旧于N步。
    • 任何可以使用额外的CPU时间的时候:这允许动态调整路径的性质;在物体数量多时,或者运行游戏的机器比较慢时,每个物体对CPU的使用可得到减少。
    • 当物体拐弯或者跨越一个导航点(waypoint)的时候。
    • 当物体附近的世界改变了的时候。

    重计算路径的主要缺点是许多路径信息被丢弃了。例如,如果路径是100步长,每10步重新计算一次,路径的总步数将是100+90+80+70+60+50+40+30+20+10 = 550。对M步长的路径,大约需要计算M^2步。因此如果你希望有许多很长的路径,重计算不是个好主意。重新使用路径信息比丢弃它更好。

    5.2 路径拼接

    当 一条路径需要被重新计算时,意味着世界正在改变。对于一个正在改变的世界,对地图中当前邻近的区域总是比对远处的区域了解得更多。因此,我们应该集中于在 附近寻找好的路径,同时假设远处的路径不需要重新计算,除非我们接近它。与重新计算整个路径不同,我们可以重新计算路径的前M步:

    1. 令p[1]..p[N]为路径(N步)的剩余部分
    2. 为p[1]到p[M]计算一条新的路径
    3. 把这条新路径拼接(Splice)到旧路径:把p[1]..p[M]用新的路径值代替

     

    因为p[1]p[M]比分开的M步小(原文:Since p[1] and p[M] are fewer than M steps apart),看起来新路径不会很长。不幸的是,新的路径也许很长而且不够好。上面的图显示了这种情况。最初的红色路径是1-2-3-4,褐色的是障碍物。如果我们到达2并且发现从2到达3的路径被封锁了,路径拼接技术会把2-32-5-3取代,结果是物体沿着路径1-2-5-3-4运动。我们可以看到这不是一条好的路径,蓝色的路径1-2-5-4是一条更好的路径。

    通常可以通过查看新路径的长度检测到坏的路径。如果这严格大于M,就可能是不好的。一个简单的解决方法是,为搜索算法设置一个最大路径长度。如果找不到一条短的路径,算法返回错误代码;这种情况下,用重计算路径取代路径拼接,从而得到路径1-2-5-4.

    对于其它情况,对于N步的路径,路径拼接会计算2N或者3N步,这取决于拼接新路径的频率。对于对世界的改变作反应的能力而言,这个代价是相当低的。令人吃惊的是这个代价和拼接的步数M无关。M不影响CPU时间,而控制了响应和路径质量的折衷。如果M太大,物体的移动将不能快速对地图的改变作出反应。如果M太小,拼接的路径可能太短以致不能正确地绕过障碍物;许多不理想的路径(如1-2-5-3-4)将被找到。尝试不同的M值和不同的拼接标准(如每3/4 M),看看哪一种情况对你的地图最合适。

    路径拼接确实比重计算路径要快,但它不能对路径的改变作出很好的反应。经常可以发现这种情况并用路径重计算来取代。也可以调整一些变量,如M和寻找新路径的时机,所以可以对该方法进行调整(甚至在运行时)以用于不同的情况。

    NoteBryan Stout 有两个算法,Patch-OnePatch-All,他从路径拼接中得到灵感,并在实践中运行得很好。他出席了GDC 2007https://www.cmpevents.com/GD07/a.asp?option =C &V=11& SessID=4608);一旦他把资料放在网上,我将链接过去。

    Implementation Note:

    反向保存路径,从而删除路径的开始部分并用不同长度的新路径拼接将更容易,因为这两个操作都将在数组的末尾进行。本质上你可以把这个数组看成是堆栈因为顶部的元素总是下一个要使用的。

    5.3 监视地图变化

    与 间隔一段时间重计算全部或部分路径不同的是,可以让地图的改变触发一次重计算。地图可以分成区域,每个物体都可以对某些区域感兴趣(可以是包含部分路径的 所有区域,也可以只是包含部分路径的邻近区域)。当一个障碍物进入或者离开一个区域,该区域将被标识为已改变,所有对该区域感兴趣的物体都被通知到,所以 路径将被重新计算以适应障碍物的改变。

    这种技术有许多变种。例如,可以每隔一定时间通知物体,而不是立即通知物体。多个改变可以成组地触发一个通知,因此避免了额外的重计算。另一个例子是,让物体检查区域,而不是让区域通知物体。

    监视地图变化允许当障碍物不改变时物体避免重计算路径,所以当你有许多区域并不经常改变时,考虑这种方法。

    5.4 预测障碍物的运动

    如果障碍物的运动可以预测,就能为路径搜索考虑障碍物的未来位置。一个诸如A*的算法有一个代价函数用以检查穿过地图上一点的代价有多难。A*可以被改进从而知道到达一点的时间需求(通过当前路径长度来检查),而现在则轮到代价函数了。代价函数可以考虑时间,并用预测的障碍物位置检查在某个时刻地图某个位置是否可以通过。这个改进不是完美的,然而,因为它并不考虑在某个点等待障碍物自动离开的可能性,同时A*并不区分到达相同目的地的不同的路径,而是针对不同的目的地,所以还是可以接受的。

    预计算路径的空间代价

    有时,路径计算的限制因素不是时间,而是用于数以百计的物体的存储空间。路径搜索器需要空间以运行算法和保存路径。算法运行所需的临时空间(在A*中是OPENCLOSED集)通常比保存结果路径的空间大许多。通过限制在一定的时间计算一条路径,可以把临时空间数量最小化。另外,为OPENCLOSED集所选择的数据结构的不同,最小化临时空间的程度也有很大的不同。这一部分聚集于优化用于计算路径的空间代价。

    6.1 位置VS方向

    一条路径可以用位置或者方向来表示。位置需要更多的空间,但是有一个优点,易于查询路径中的任意位置或者方向而不用沿着路径移动。当保存方向时,只有方向容易被查询;只有沿着整个路径移动才能查询位置。在一个典形的网格地图中,位置可以被保存为两个16位整数,每走一步是32位。而方向是很少的,因此用极少的空间就够了。如果物体只能沿着四个方向移动,每一步用两位就够了;如果物体能沿着6个或者8个方向移动,每一步也只需要三位。这些对于保存路径中的位置都有明显的空间节省。Hannu Kankaanpaa指出可以进一步减少空间需求,那就是保存相对方向(右旋60度)而不是绝对方向(朝北走)。有些相对方向对某些物体来说意义不大。比如,如果你的物体朝北移动,那么下一步朝南移动的可能性很小。在只有六种方向的游戏中,你只有五个有意义的方向。在某些地图中,也许只有三个方向(直走,左旋60度,右旋60度)有意义,而其它地图中,右旋120度是有效的(比如,沿着陡峭的山坡走之字形的路径时)。

    6.2 路径压缩

    一旦找到一条路径,可以对它进行压缩。可以用一个普通的压缩算法,但这里不进行讨论。使用特定的压缩算法可以缩小路径的存储,无论它是基于位置的还是基于方向的。在做决定之前,考察你的游戏中的路径以确定哪种压缩效果最好。另外还要考虑实现和调试,代码量,and whether it really matters.如果你有300个物体并且在同一时刻只有50个在移动,同时路径比较短(100步),内存总需求大概只有不到50k,总之,没有必要担心压缩的效果。

    6.2.1 位置存储

    在障碍物比地形对路径搜索影响更大的地图中,路径中有大部分是直线的。如果是这种情况,那么路径只需要包含直线部分的终止点(有时叫waypoints)。此时移动过程将包含检查下一结点和沿着直线向前移动。

    6.2.2 方向存储

    保存方向时,有一种情况是同一个方向保存了很多次。可以用简单的方法节省空间。

    一种方法是保存方向以及朝着该方向移动的次数。和位置存储的优化不同,当一个方向并不是移动很多次时,这种优化的效果反而不好。同样的,对于那些可以进行位置压缩的直线来说,方向压缩是行不通的,因为这条直线可能没有和正在移动的方向关联。通过相对方向,你可以把“继续前进”当作可能的方向排除掉。Hannu Kankaanpaa指出,在一个八方向地图中,你可以去掉前,后,以及向左和向右135度(假设你的地图允许这个),然后你可以仅用两个比特保存每个方向。

    另一种保存路径的方法是变长编码。这种想法是使用一个简单的比特(0)保存最一般的步骤:向前走。使用一个“1”表示拐弯,后边再跟几个比特表示拐弯的方向。在一个四方向地图中,你只能左转和右转,因此可以用“10”表示左转,“11”表示右转。

    变长编码比run length encoding更一般,并且可以压缩得更好,但对于较长的直线路径则不然。序列(向北直走6步,左转,直走3步,右转,直走5步,左转,直走2步)用run length encoding表示是[(NORTH, 6), (WEST, 3), (NORTH, 5), (WEST, 2)]。如果每个方向用2比特,每个距离用8比特,保存这条路径需要40比特。而对于变长编码,你用1比特表示每一步,2比特表示拐弯——[NORTH 0 0 0 0 0 0 10 0 0 0 11 0 0 0 0 0 10 0 0]——一共24比特。如果初始方向和每次拐弯对应1步,则每次拐弯都节省了一个比特,结果只需要20比特保存这条路径。然而,用变长编码保存更长的路径时需要更多的空间。序列(向北直走200)run length encoding表示是[(NORTH, 200)],总共需要10比特。用变长编码表示同样的序列则是[NORTH 0 0 ...],一共需要202比特。

    6.3 计算导航点

    一个导航点(waypoint)是路径上的一个结点。与保存路径上的每一步不同,在进行路径搜索之后,一个后处理(post-processing)的步骤可能会把若干步collapse(译者:不好翻译,保留原单词)为一个简单的导航点,这经常发生在路径上那些方向发生改变的地方,或者在一个重要的(major)位置如城市。然后运动算法将在两个导航点之间运行。

    6.4 极限路径长度

    当地图中的条件或者秩序会发生改变时,保存一条长路径是没有意义的,因为在从某些点开始,后边的路径已经没有用了。每个物体都可以保存路径开始时的特定几步,然后当路径已经没用时重新计算路径。这种方法虑及了(allows for)对每个物体使用数据的总量的管理。

    6.5 总结

    在游戏中,路径潜在地花费了许多存储空间,特别是当路径很长并且有很多物体需要寻路时。路径压缩,导航点和beacons通过把多个步骤保存为一个较小数据从而减少了空间需求。Waypoints rely on straight-line segments being common so that we have to store only the endpoints, while beacons rely on there being well-known paths calculated beforehand between specially marked places on the map.(译者:此处不好翻译,暂时保留原文)如果路径仍然用了许多存储空间,可以限制路径长度,这就回到了经典的时间-空间折衷法:为了节省空间,信息可以被丢弃,稍后才重新计算它。

    展开全文
  • 剑指Offer——动态规划算法

    万次阅读 多人点赞 2016-08-03 15:24:27
    剑指Offer——动态规划算法什么是动态规划? 和分治法一样,动态规划(dynamicprogramming)是通过组合子问题而解决整个问题的解。 分治法是将问题划分成一些独立的子问题,递归地求解各子问题,然后合并子问题的解...

    剑指Offer——动态规划算法

    什么是动态规划?

         和分治法一样,动态规划(dynamic programming)是通过组合子问题而解决整个问题的解。

         分治法是将问题划分成一些独立的子问题,递归地求解各子问题,然后合并子问题的解。

         动态规划适用于子问题不是独立的情况,也就是各子问题包含公共的子子问题。

         此时,分治法会做许多不必要的工作,即重复地求解公共的子问题。动态规划算法对每个子问题只求解一次,将其结果保存起来,从而避免每次遇到各个子问题时重新计算答案。

    适用范围

         最优性原理体现为问题的最优子结构特性。当一个问题的最优解中包含了子问题的最优解时,则称该问题具有最优子结构特性。

         最优性原理是动态规划的基础。任何一个问题,如果失去了这个最优性原理的支持,就不可能用动态规划设计求解。

         1.问题中的状态满足最优性原理。

         2.问题中的状态必须满足无后效性。

         所谓无后效性是指:“下一时刻的状态只与当前状态有关,而和当前状态之前的状态无关,当前状态是对以往决策的总结”。

    动态规划算法的设计

         两种方法:

         自顶向下(又称记忆化搜索、备忘录):基本上对应着递归函数实现,从大范围开始计算,要注意不断保存中间结果,避免重复计算

         自底向上(递推):从小范围递推计算到大范围

    动态规划的重点

        递归方程+边界条件

    爬楼梯问题

         一个人每次只能走一层楼梯或者两层楼梯,问走到第80层楼梯一共有多少种方法。

         设DP[i]为走到第i层一共有多少种方法,那么DP[80]即为所求。很显然DP[1]=1, DP[2]=2(走到第一层只有一种方法:就是走一层楼梯;走到第二层有两种方法:走两次一层楼梯或者走一次两层楼梯)。同理,走到第i层楼梯,可以从i-1层走一层,或者从i-2走两层。很容易得到:

          递推公式:DP[i]=DP[i-1]+DP[i-2]

          边界条件:DP[1]=1   DP[2]=2

          (a)自顶向下的解法:

     

    long long dp[81] = {0};/*用于保存中间结果否则会重复计算很多重复的子问题*/
    long long DP(int n)
    {
        if(dp[n])
            return dp[n];
        if(n == 1)
            return 1;
        if(n == 2)
            return 2;
        dp[n] = DP(n-1) + DP(n-2);
        return dp[n];
    }  

     

         (b)自底向上的解法:

     

    int i;  
    long long dp[81]; /* 注意当n超过75时,结果值将超过int范围 */  
    dp[1] = 1;  
    dp[2] = 2;  
    for(i=3; i <= 80; i++)  
        dp[i] = dp[i-1] + dp[i-2];

     

    最长上升子序列

         对于序列:4 1 2 24,它的最长上升子序列是1 2 4,长度为3。

         对于序列:4 2 4 25 6,它的最长上升子序列是2 4 5 6,长度为4。

         设a[i]表示原序列,设DP[i]表示以第i个数结尾的最长上升序列的长度,那么很显然想导出DP[i]的值,需要在DP[k](1<=k<i)中找出满足a[k]<a[i]最大的一项。假设第kk项是我们找到的答案,那么第i个数就可以接在第kk个数之后,成为以第i个数结尾的最长升序列。如果没有找到答案,换言之第i个数比前面的数都要小,那么DP[i]=1,也即生成了从自己开始又以自己结尾的最长升序列。综上,我们很容易得出:

         递推公式:DP[i]=max(DP[k]+1,DP[i])  1<=k<i

         边界条件:DP[i]=1                   1<=i<=n

         算法复杂度为O(n^2)

     

    void RiseSequence(int Array[], int num)  
    {  
    #define MAX_LENGTH  30  
        struct  
        {  
            int SequenceValue;  /* max length ending with this num */  
            int PreviousIndex;  /* record the previous number */  
        }ArrayInfo[MAX_LENGTH], temp;  
        int i;  
        for(i = 0; i < num; i++)  
        {  
            int j;  
            ArrayInfo[i].SequenceValue = 1;  
            ArrayInfo[i].PreviousIndex = -1;  
            for(j = 0; j < i; j++)  
            {  
                if(Array[j] < Array[i] && (ArrayInfo[j].SequenceValue + 1 > ArrayInfo[i].SequenceValue))  
                {  
                    ArrayInfo[i].SequenceValue = ArrayInfo[j].SequenceValue + 1;  
                    ArrayInfo[i].PreviousIndex = j;  
                }  
            }  
        }  
        temp.SequenceValue = ArrayInfo[0].SequenceValue;  
        for(i = 1; i < num; i++)  
        {  
            if(temp.SequenceValue < ArrayInfo[i].SequenceValue)  
            {  
                temp.SequenceValue = ArrayInfo[i].SequenceValue;  
                temp.PreviousIndex = i;  
            }  
        }  
        for(i = 0; i < temp.SequenceValue; i++)  
        {  
            printf("%d  ", Array[temp.PreviousIndex]);  /* in reverse order */  
            temp.PreviousIndex = ArrayInfo[temp.PreviousIndex].PreviousIndex;  
        }  
        printf("\nthe max rising sequence length is %d\n", temp.SequenceValue);  
    }  

     

    最长公共子序列

         给定两个序列X和Y,称序列Z是X和Y的公共子序列如果Z既是X的一个子序列,又是Y的一个子序列。例如,如果X={a,b,c,b,d,a,b} Y={b,d,c,a,b,a} 那么序列{b,c,a}就是X和Y的一个公共子序列,但是它并不是X和Y的最长公共子序列,因为它的长度为3。而同为X和Y公共子序列的{b,c,b,a},长度为4,因为找不到长度为5或更大的公共子序列,所以X和Y的最长公共子序列长度就为4。

         假设两个序列数组分别为a,b。定义f(i,j)为计算到a数组第i个数、b数组第j个数时所得到的最长公共子序列的长度。这时有两种情况:

         1.假如a[i]=b[j],那么f(i,j)=f(i-1,j-1)+1

         2.假如a[i]!=b[j],那么f(i,j)=max(f(i-1,j),f(i,j-1))

         边界条件为:f(i,0)=0     1<=i<=len(a)

                f(0,j)=0     1<=j<=len(b)

         算法复杂度:O(n^2),len(a)表示数组a的长度。

    尾声

         动态规划绝对不是一两篇文章可以讲清楚的。当然也不是通过一两道题目可以完全学会。学习的关键是用动规的思想去想问题,去设计状态转移方程式。

    动态规划还有很多变形,如状态压缩,树形等等。

        虽然通常我们用递归的方式分析动态规划问题,但最终都会基于循环去编码。

    美文美图

     

    展开全文
  • 作者根据自己本科和硕士阶段的学习经历,整理归纳了所接触过的规划算法。1.自主机器人近距离操作运动规划体系在研究自主运动规划问题之前,首先需建立相对较为完整的自主运动规划体系,再由该体系作为指导,对自主...

    本文来自知乎网友@搬砖的旺财,地平线机器人算法工程师。作者根据自己本科和硕士阶段的学习经历,整理归纳了所接触过的规划算法。

    1.自主机器人近距离操作运动规划体系

    在研究自主运动规划问题之前,首先需建立相对较为完整的自主运动规划体系,再由该体系作为指导,对自主运动规划的各项具体问题进行深入研究。本节将根据自主机器人的思维方式、运动形式、任务行为等特点,建立与之相适应的自主运动规划体系。并按照机器人的数量与规模,将自主运动规划分为单个机器人的运动规划与多机器人协同运动规划两类规划体系。

    1.1单个自主机器人的规划体系

    运动规划系统是自主控制系统中主控单元的核心部分,因此有必要先研究自主控制系统和其主控单元的体系结构问题。

    自主控制技术研究至今,先后出现了多种体系结构形式,目前被广泛应用于实践的是分布式体系结构,其各个功能模块作为相对独立的单元参与整个体系。随着人工智能技术的不断发展,基于多Agent的分布式体系结构逐渐成为了主流,各功能模块作为独立的智能体参与整个自主控制过程,该体系结构应用的基本形式如图1所示。一方面,主控单元与测控介入处理、姿态控制系统、轨道控制系统、热控系统、能源系统、数传、有效载荷控制等功能子系统相互独立为智能体,由总线相连;另一方面,主控单元为整个系统提供整体规划,以及协调、管理各子系统Agent的行为。测控介入处理Agent保证地面系统对整个系统任意层面的控制介入能力,可接受上行的使命级任务、具体的飞行规划和底层的控制指令;各子系统Agent存储本分系统的各种知识和控制算法,自主完成主控单元发送的任务规划,并将执行和本身的健康等信息传回主控单元,作为主控单元Agent运行管理和调整计划的依据。

    4c02aa8a8d58af018bf4a6a0de2647d5.png
    图1 基于多Agent的分布式自主控制系统体系结构基本形式示意图

    主控单元Agent采用主流的分层递阶式结构,这种结构层次鲜明,并且十分利于实现,其基本结构如图2所示。主控单元由任务生成与调度、运动行为规划和控制指令生成三层基本结构组成,由任务生成与调度层获得基本的飞行任务,经过运动行为规划层获得具体的行为规划,再由控制指令生成层得到最终的模块控制指令,发送给其它功能Agent。各功能Agent发送状态信息给主控单元的状态检测系统,状态检测系统将任务执行情况和子系统状态反馈回任务生成与调度层,以便根据具体情况对任务进行规划调整。当遇到突发情况时,还可启用重规划模块,它可根据当时情况迅速做出反应快速生成行为规划,用以指导控制指令生成层得到紧急情况的控制指令。此外,地面控制系统在三个层次上都分别具有介入能力。图2中,点划线内是主控单元全部模块,虚线内为运动规划系统,包括运动行为规划模块和重规划模块,这也是运动规划系统的主要功能。

    174dd5907e82b81caaefb0cf04b25944.png
    图2 主控单元基本结构示意图

    明确了自主控制系统与其主控单元的基本结构,以及运动规划系统在主控单元中的基本功能,便可建立运动规划系统的体系结构。运动规划系统的体系结构如图3所示,该系统由规划器和重规划器两大执行单元组成,分别承担对飞行任务的一般规划和对突发事件紧急处理的运动规划。当然,这两部分也可理解为离线规划与在线规划两种,离线规划一般解决平时按部就班的飞行任务,在线规划一般解决突然下达的飞行任务。除规划器以外,系统还配有知识域模块,用以利用特定语言描述相关知识。知识域包括行为域和模型域两个部分,行为域用来存储服务系统一般的运动行为描述和紧急情况下的一些运动行为方面的处理方法(如急停、转向等),模型域用来存储规划所需模型知识,包括环境模型、组装体模型、组装任务对象模型和任务模型等等。

    a2b61c7a3884737ca15b75dbac17d40f.png
    图3 运动规划系统体系结构示意图

    1.2多自主机器人协同规划体系

    多智能体系统的群体体系结构一般分为集中式、分散式两种基本结构,分散式结构又可以进一步分为分层式和分布式结构。集中式结构通常由一个主控单元掌握全部环境和受控机器人信息,运用规划算法对任务进行分解,并分配给各受控机器人,组织它们完成任务。其优点是理论条理清晰,实现较为直观;缺点是容错性、灵活性和对环境的适应性较差,与各受控机器人存在通讯瓶颈问题。相对于集中式结构,分散式结构无法得到全局最优解,但它凭借着可靠性、灵活性和较强的环境适应性越来越受到广泛的青睐。分散式结构中的分布式结构没有主控单元,各智能体地位平等,通过各智能体间的通讯和信息交流达到协商的目的,实现最终的决策,但该结构容易片面强调个体,导致占用资源过多,且难于得到磋商结果。分层式结构介乎于集中式和分布式之间,存在主控单元,但并不是由主控单元掌控一切,各智能体也具备一定的自主性,上下级之间按照一定的规则,通过信息流形成完整的整体,共同完成协同任务。

    多自主机器人系统应采用分层式结构,以保证整个系统既适于统一领导,又满足系统灵活、快速的需求。多自主机器人协同规划体系结构如图4所示,按照分层式结构建立两种工作模式:事先的离线规划由主控单元负责,首先获得协同任务,经过规划器得到具体的行为运动规划,并分发给各分系统执行单元,相关的知识域中主要是用于描述各分系统协商规则的协商域,主控单元从外界获取环境信息,从各分系统获取状态信息;当遇到突发事件或紧急任务变更以及主控单元停止工作时,各分系统采用分布式结构,单独规划各自运动行为,并从各自的知识域中获取协商方式,外界环境信息由主控单元发送和自我感知相结合获得(主控单元停止工作时,仅靠自我感知获取信息),其它机器人信息的传输由机器人间的数据链实现。

    de784541e15988209b5bf4d93836c76c.png
    图4 多自主机器人协同规划体系结构示意图

    2.路径规划研究

    当给定了某一特定的任务之后,如何规划机器人的运动方式将至关重要。机器人的规划包括两部分内容:基座移动到适合操作的位置和转动手臂关节完成操作。包括三个问题:基座点到点运动规划;关节空间规划;综合规划。

    本章研究几种常用的运动规划算法:图搜索法、RRT算法、人工势场法、BUG算法。并对部分算法的自身缺陷进行了一些改进。

    2.1 图搜索法

    图搜索法依靠已知的环境地图以及地图中的障碍物信息构造从起点到终点的可行路径。主要分成深度优先和广度优先两个方向。深度优先算法优先扩展搜索深度大的节点,可以快速的得到一条可行路径,但是深度优先算法得到的第一条路径往往是较长的路径。广度优先算法优先扩展深度小的节点,呈波状的搜索方式。广度优先算法搜索到的第一条路径就是最短路径。

    2.1.1 可视图法

    可视图法由Lozano-Perez和Wesley于1979年提出,是机器人全局运动规划的经典算法。可视图法中,机器人用点来描述,障碍物用多边形描述。将起始点 827d493b-c752-eb11-8da9-e4434bdf6706.svg 、目标点 867d493b-c752-eb11-8da9-e4434bdf6706.svg 和多边形障碍物的各顶点(设 887d493b-c752-eb11-8da9-e4434bdf6706.svg 是所有障碍物的顶点构成的集合)进行组合连接,要求起始点和障碍物各顶点之间、目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线均不能穿越障碍物,即直线是“可视的”。给图中的边赋权值,构造可见图 897d493b-c752-eb11-8da9-e4434bdf6706.svg 。其中点集 8c7d493b-c752-eb11-8da9-e4434bdf6706.svg , 8e7d493b-c752-eb11-8da9-e4434bdf6706.svg 为所有弧段即可见边的集合。然后釆用某种优化算法搜索从起始点 827d493b-c752-eb11-8da9-e4434bdf6706.svg 到目标点 867d493b-c752-eb11-8da9-e4434bdf6706.svg 的最优路径,那么根据累加和比较这些直线的距离就可以获得从起始点到目标点的最短路径。

    387f9a4d535a0902fe0f800d81c17d87.png
    图5 可视图

    由此可见,利用可视图法规划避障路径主要在于构建可视图,而构建可视图的关键在于障碍物各顶点之间可见性的判断。判断时主要分为两种情况,同一障碍物各顶点之间可见性的判断以及不同障碍物之间顶点可见性的判断。

    1. 同一障碍物中,相邻顶点可见(通常不考虑凹多边形障碍物中不相邻顶点也有可能可见的情况),不相邻顶点不可见,权值赋为 a47d493b-c752-eb11-8da9-e4434bdf6706.svg 。

    2. 不同障碍物之间顶点可见性的判断则转化为判断顶点连线是否会与其它顶点连线相交的几何问题。如下图虚线所示,a77d493b-c752-eb11-8da9-e4434bdf6706.svgac7d493b-c752-eb11-8da9-e4434bdf6706.svg 分别是障碍物 b07d493b-c752-eb11-8da9-e4434bdf6706.svgb37d493b-c752-eb11-8da9-e4434bdf6706.svg 的顶点,但 a77d493b-c752-eb11-8da9-e4434bdf6706.svg 与 ac7d493b-c752-eb11-8da9-e4434bdf6706.svg 连线与障碍物其它顶点连线相交,故 a77d493b-c752-eb11-8da9-e4434bdf6706.svgac7d493b-c752-eb11-8da9-e4434bdf6706.svg 之间不可见;而实线所示的 bc7d493b-c752-eb11-8da9-e4434bdf6706.svg 与 bd7d493b-c752-eb11-8da9-e4434bdf6706.svg 连线不与障碍物其它顶点连线相交,故 bc7d493b-c752-eb11-8da9-e4434bdf6706.svg 、 bd7d493b-c752-eb11-8da9-e4434bdf6706.svg 之间可见。

    9dc5f9e518c4005b330d6ff42dfa7ab7.png
    图6 顶点可见性判断

    可视图法能求得最短路径,但搜索时间长,并且缺乏灵活性,即一旦机器人的起始点和目标点发生改变,就要重新构造可视图,比较麻烦。可视图法适用于多边形障碍物,对于圆形障碍物失效。切线图法和Voronoi图法对可视图法进行了改进。切线图法用障碍物的切线表示弧,因此是从起始点到目标点的最短路径的图,移动机器人必须几乎接近障碍物行走。其缺点是如果控制过程中产生位置误差,机器人碰撞障碍物的可能性会很高。Voronoi图法用尽可能远离障碍物和墙壁的路径表示弧。因此,从起始点到目标点的路径将会增长,但采用这种控制方式时,即使产生位置误差,移动机器人也不会碰到障碍物。

    2.1.2 Dijkstra算法

    Dijkstra算法由荷兰计算机科学家艾兹赫尔·戴克斯特拉(Edsger Wybe Dijkstra)发明,通过计算初始点到自由空间内任何一点的最短距离可以得到全局最优路径。算法从初始点开始计算周围4个或者8个点与初始点的距离,再将新计算距离的点作为计算点计算其周围点与初始点的距离,这样计算像波阵面一样在自由空间内传播,直到到达目标点。这样就可以计算得到机器人的最短路径。

    Dijkstra算法是一种经典的广度优先的状态空间搜索算法,即算法会从初始点开始一层一层地搜索整个自由空间直到到达目标点。这样会大大增加计算时间和数据量。而且搜索得到的大量对于机器人运动是无用的。

    详情请参考:路径规划——Dijkstra算法:https://zhuanlan.zhihu.com/p/51112799

    2.1.3 A*算法

    为了解决Dijkstra算法效率低的问题,A*算法作为一种启发式算法被提出。该算法在广度优先的基础上加入了一个估价函数。

    详情请参考:路径规划——A*算法:https://zhuanlan.zhihu.com/p/51099376

    2.2RRT算法

    快速搜索随机树(RRT)算法是一种增量式采样的搜索方法,该方法在应用中不需要任何参数整定,具备良好的使用性能。它利用增量式方法构建搜索树,以逐渐提高分辨能力,而无须设置任何分辨率参数。在极限情况,该搜索树将稠密的布满整个空间,此时搜索树由很多较短曲线或路经构成,以实现充满整个空间的目的。增量式方法构建的搜索树其导向取决于稠密采样序列,当该序列为随机序列时,该搜索树称为快速搜索随机树(Rapidly Exploring Random Tree,RRT),而不论该序列为随机还是确定性序列,都被称为快速搜索稠密树(Rapidly Exploring Dense Trees,RDTs),这种规划方法可处理微分等多种约束。

    2.2.1 算法步骤

    考虑二维和三维工作空间,环境中包含静态障碍物。初始化快速随机搜索树T,只包括根节点,即初始状态S。在自由空间中随机选取一个状态点 c27d493b-c752-eb11-8da9-e4434bdf6706.svg ,遍历当前的快速随机搜索树T,找到T上距离 c27d493b-c752-eb11-8da9-e4434bdf6706.svg 最近的节点 c57d493b-c752-eb11-8da9-e4434bdf6706.svg ,考虑机器人的动力学约束从控制输入集 c77d493b-c752-eb11-8da9-e4434bdf6706.svg 中选择输入 c87d493b-c752-eb11-8da9-e4434bdf6706.svg ,从状态 c57d493b-c752-eb11-8da9-e4434bdf6706.svg 开始作用,经过一个控制周期 cc7d493b-c752-eb11-8da9-e4434bdf6706.svg 到达新的状态 cd7d493b-c752-eb11-8da9-e4434bdf6706.svg 。满足 cd7d493b-c752-eb11-8da9-e4434bdf6706.svgc27d493b-c752-eb11-8da9-e4434bdf6706.svg 的控制输入 d37d493b-c752-eb11-8da9-e4434bdf6706.svg 为最佳控制量。将新状态 cd7d493b-c752-eb11-8da9-e4434bdf6706.svg 添加到快速随机搜索树T中。按照这样得到方法不断产生新状态,直到到达目标状态G。完成搜索树构建后,从目标点开始,逐次找到父节点直到到达初始状态,即搜索树的根节点。

    52a33fb75bf77711169766128bbcfc01.png
    图7 随机树构建过程

    由于在搜索过程中考虑了机器人的动力学约束,因此生成的路径的可行性很好。但是算法的随机性导致其只具备概率完备性。

    2.2.2 改进算法

    LaValle等人的工作奠定了RRT方法的基础。在采样策略方面,RRTGoalBiaS方法在控制机器人随机运动的同时,以一定概率向最终目标运动;RRTGoalZoom方法分别在整个空间和目标点周围的空间进行采样;RRTCon方法则通过加大随机步长改进规划速度。双向规划思想也被采用,衍生出RRTExtExt,RRTExtCon,RRTConCon等多种算法。

    基本RRT算法收敛到终点位姿的速度可能比较慢。为了提高算法的效率和性能,需不断对该算法进行改进。如为了提高搜索效率采用双向随机搜索树(Bi~RRT),从起始点和目标点并行生成两棵RRT,直至两棵树相遇,算法收敛。由于这个算法相比于原始RRT有更好的收敛性,因此在目前路径规划中是很常见的。NikAMelchior提出的粒子RRT算法,考虑了地形的不确定性,保证了在不确定性环境下搜索树的扩展。Kuffner和Lavane又提出RRT-connectlv,使得节点的扩展效率大大提高。运动规划中,距离的定义非常复杂,Pengcheng研究了在RRT生长过程中距离函数不断学习的算法以降低距离函数对环境的敏感性。考虑到基本RRT规划器得到的路径长度一般是最优路径的1.3~1.5倍,英国的J.desmithl研究了变分法技术使其达到最优。Amna A引入KD树作为二级数据结构加速查找距离从环境中取出的随机点最近的叶节点,降低了搜索成本。该算法在动态障碍物、高维状态空间和存在运动学、动力学等微分约束的环境中的运动规划已经得到广泛的应用。

    关于改进RRT算法详情可参考:路径规划——改进RRT算法:https://zhuanlan.zhihu.com/p/51087819

    2.3滚动在线RRT算法

    基本RRT算法倾向于遍历整个自由空间直到获得可行路径,这使其不可能用于未知或动态环境中的机器人在线运动规划。利用滚动规划的思想可以将RRT算法进行改进,使其具备在线规划能力。

    2.3.1 滚动规划

    机器人在未知或动态环境中运动时,只能探知其传感器范围内有限区域内的环境信息。机器人利用局部信息进行局部运动规划,并根据一定的评价准则得到局部目标。机器人到达局部目标后再次进行新的局部规划。如此反复进行直到到达全局目标。

    滚动规划算法的基本原理:

    1. 环境信息预测:在滚动的每一步,机器人根据探测到的视野内的信息、或所有已知的环境信息,建立环境模型,包括设置已知区域内的节点类型信息等;

    2. 局部滚动优化:将上述环境信息模型看成一个优化的窗口,在此基础上,根据目标点的位置和特定的优化策略计算出下一步的最优子目标,然后根据子目标和环境信息模型,选择局部规划算法,确定向子目标行进的局部路径,并实施当前策略,即依所规划的局部路径行进若干步,窗口相应向前滚动;

    3. 反馈信息校正:根据局部最优路径,驱动机器人行走一段路径后,机器人会探测到新的未知信息,此时可以根据机器人在行走过程探测到的新信息补充或校正原来的环境模型,用于滚动后下一步的局部规划。

    其中,局部子目标是在滚动窗口中寻找一个全局目标的映射,它必须避开障碍物,且满足某种优化指标。子目标的选择方法反映了全局优化的要求与局部有限信息约束的折衷,是在给定信息环境下企图实现全局优化的自然选择。

    基于滚动窗口的路径规划算法依靠实时探测到的局部环境信息,以滚动方式进行在线规划。在滚动的每一步,根据探测到的局部信息,用启发式方法生成优化子目标,在当前滚动窗口内进行局部路径规划,然后实施当前策略(依局部规划路径移动一步),随滚动窗口推进,不断取得新的环境信息,从而在滚动中实现优化与反馈的结合。由于规划问题压缩到滚动窗口内,与全局规划相比其计算量大大下降。

    基于滚动窗口的路径规划算法的具体步骤如下:

    • 步骤0:对起点、终点、工作环境、机器人的视野半径、步长进行初始化;

    • 步骤1:如果终点到达,规划中止;

    • 步骤2:对当前滚动窗口内的环境信息进行刷新;

    • 步骤3:产生局部子目标;

    • 步骤4:根据子目标及已知环境信息,在当前滚动窗口内规划一条优化的局部可行路径;

    • 步骤5:依规划的局部路径行进一步,步长小于视野半径;

    • 步骤6:返回步骤1。

    2.3.2 滚动在线RRT算法流程

    在一个滚动窗口内,随机树以当前位置为起始点,构建传感器范围内的随机树。构建方法与基本RRT算法一致。为了使全局环境中随机树具有向目标方向生长的趋势,在运动规划时引入启发信息,减少随机树的随机性,提高搜索效率。

    令 da7d493b-c752-eb11-8da9-e4434bdf6706.svg 代表随机树中两个位姿节点间的路径代价, dd7d493b-c752-eb11-8da9-e4434bdf6706.svg 代表随机树中两个位姿节点间的欧几里德距离。类似于A*算法,本算法为随机树中每个节点定义一个估价函数: df7d493b-c752-eb11-8da9-e4434bdf6706.svg 。其中 e07d493b-c752-eb11-8da9-e4434bdf6706.svg 是随机节点 c27d493b-c752-eb11-8da9-e4434bdf6706.svg 到树中节点 e67d493b-c752-eb11-8da9-e4434bdf6706.svg 所需的路径代价。 e87d493b-c752-eb11-8da9-e4434bdf6706.svg 为启发估价函数,这里取随机节点 c27d493b-c752-eb11-8da9-e4434bdf6706.svg 到目标点 ec7d493b-c752-eb11-8da9-e4434bdf6706.svg 的距离为估价值, ed7d493b-c752-eb11-8da9-e4434bdf6706.svg 。因此 ee7d493b-c752-eb11-8da9-e4434bdf6706.svg 表示从节点 e67d493b-c752-eb11-8da9-e4434bdf6706.svg 经随机节点 c27d493b-c752-eb11-8da9-e4434bdf6706.svg 到目标节点 ec7d493b-c752-eb11-8da9-e4434bdf6706.svg 的路径估计值。遍历滚动窗口内随机树T,取估价函数最小值的节点 c57d493b-c752-eb11-8da9-e4434bdf6706.svg ,有 f67d493b-c752-eb11-8da9-e4434bdf6706.svg 。这使得随机树沿着到目标节点估价值 ee7d493b-c752-eb11-8da9-e4434bdf6706.svg 最小的方向进行扩展。

    由于在随机树生长中引入了导向目标的启发估价因子,叶节点 c57d493b-c752-eb11-8da9-e4434bdf6706.svg 总是选择离目标最近的节点,这可能会使随机树遇到局部极小值问题。因此随机树生长的新节点 cd7d493b-c752-eb11-8da9-e4434bdf6706.svg 必须要克服这个问题,引导随机树更好的探索未知空间。

    这里利用统计学中回归分析生成新节点,将RRT算法探索未知空间的能力进一步增强以避免因启发估价因子导致的局部极小。其思想是探索以前到过的空间是无用的,而且容易陷入局部极小。引进回归分析(regression analysis)是考察新节点与其他节点之间关系,利用回归函数约束,使得随机树不探索以前到过的空间,因此避免了局部极小。

    新节点生成方法是遍历随机树,如果 cd7d493b-c752-eb11-8da9-e4434bdf6706.svg 与其父节点 c57d493b-c752-eb11-8da9-e4434bdf6706.svg 的距离小于 cd7d493b-c752-eb11-8da9-e4434bdf6706.svg 与扩展树上其他任意节点的距离,即 017e493b-c752-eb11-8da9-e4434bdf6706.svg ,则选择该节点为随机树新生节点。下图解释了新节点的判断过程。

    b7cc2e4bbef59190d02ace144a1d92e6.png
    图8 新节点的判断

    上图中各个空心点是中间的父节点的可能扩展。椭圆圈起的空心点表示这个新节点不符合回归函数约束,剩下的两个未被圈起的空心节点到其父节点的距离小于该节点到随机树上任意节点的距离,这两个点可以成为随机树的新节点。

    综上,滚动窗口内随机树构建的具体步骤如下:

    1. 对滚动窗口随机树T初始化,T开始只包含初始位置S;

    2. 滚动窗口自由空间中随机选择一个状态 c27d493b-c752-eb11-8da9-e4434bdf6706.svg

    3. 根据最短路径思想寻找树T中和 c27d493b-c752-eb11-8da9-e4434bdf6706.svg 距离最近的节点 c57d493b-c752-eb11-8da9-e4434bdf6706.svg

    4. 选择输入 d37d493b-c752-eb11-8da9-e4434bdf6706.svg ,使机器人状态由 c57d493b-c752-eb11-8da9-e4434bdf6706.svg 到 cd7d493b-c752-eb11-8da9-e4434bdf6706.svg

    5. 确定 cd7d493b-c752-eb11-8da9-e4434bdf6706.svg 是否符合回归分析,不符合则回到第4步;

    6. 将 cd7d493b-c752-eb11-8da9-e4434bdf6706.svg 作为随机树T的一个新节点, d37d493b-c752-eb11-8da9-e4434bdf6706.svg 则被记录在连接节点 c57d493b-c752-eb11-8da9-e4434bdf6706.svg 和 cd7d493b-c752-eb11-8da9-e4434bdf6706.svg 的边上。

    滚动窗口状态空间进行K次采样后,遍历随机树,根据启发估价思想寻找滚动窗口子目标 197e493b-c752-eb11-8da9-e4434bdf6706.svg。 197e493b-c752-eb11-8da9-e4434bdf6706.svg 是当前滚动窗口中的子树中估价函数最小的点。确定子目标后,机器人前进到子目标点,进行下一轮的滚动RRT规划。如此反复,直到到达目标点G。

    2.4人工势场法

    人工势场法是由Khatib提出的一种用于机器人运动规划的虚拟力方法。其基本思想是将目标和障碍物对机器人运动的影响具体化成人造势场。目标处势能低,障碍物处势能高。这种势差产生了目标对机器人的引力和障碍物对机器人的斥力,其合力控制机器人沿势场的负梯度方向向目标点运动。人工势场法计算方便,得到的路径安全平滑,但是复杂的势场环境可能在目标点之外产生局部极小点导致机器人无法到达目标。为了解决人工势场法的局部极小点问题,学者们提出了各种改进方法。主要分成两个方向:一个是构造合适的势函数以减小或避免局部极小点的出现;另一种是在机器人遇到局部极小点后结合其他的方法使机器人离开局部极小点。前者一般需要全局地图信息,并且依赖于障碍物的形状。当环境复杂时难以应用。后者多利用搜索法、多势场法和沿墙行走法等方法使机器人离开局部极小点。搜索法利用最佳优先、模拟退火、随即搜索等策略寻找比局部极小点势场值更低的点使机器人继续移动。由于未知环境中大多缺乏启发信息,搜索方法的效率很低。多势场法构造多个全局极小点相同,而局部极小点不同的势函数,在机器人陷入某个局部极小点时,规划器就切换势函数使机器人离开该点。但是在未知的环境中这样的多个势场很难构造,而且该方法可能导致机器人在回到曾逃离的局部极小点。由于局部极小点是某个或多个障碍物的斥力势场与引力势场共同作用产生,其位置与障碍物距离必然不远,沿墙行走法正是利用这样的远离,使机器人在遇到局部极小点后参照类似BUG算法的环绕行为绕过产生局部极小点的障碍物继续前进。这种方法可靠性高,不依赖环境的先验信息和障碍物形状。

    本节构造人工势场进行机器人平动的在线运动规划,利用一种沿墙行走法对基本的人工势场法进行改进。

    2.4.1 基本人工势场法

    作用在机器人上的假想引力和斥力为势函数的负梯度,因而人工势函数应该具有以下特征:

    1. 非负且连续可微;

    2. 斥力势强度距离障碍物越近其强度越大;

    3. 引力势强度离目标位置越近其强度越小。

    空间中的合势场是引力势场与斥力势场之和: 1f7e493b-c752-eb11-8da9-e4434bdf6706.svg

    其中, 217e493b-c752-eb11-8da9-e4434bdf6706.svg 是目标产生的引力势场; 237e493b-c752-eb11-8da9-e4434bdf6706.svg 是各个障碍物产生的斥力势场之和,即: 267e493b-c752-eb11-8da9-e4434bdf6706.svg

    这里构造如下的引力势函数和斥力势函数:

    287e493b-c752-eb11-8da9-e4434bdf6706.svg

    2b7e493b-c752-eb11-8da9-e4434bdf6706.svg

    其中, 307e493b-c752-eb11-8da9-e4434bdf6706.svg 表示引力势的相对影响; 337e493b-c752-eb11-8da9-e4434bdf6706.svg 表示第 377e493b-c752-eb11-8da9-e4434bdf6706.svg 个障碍物的斥力势的相对影响, e67d493b-c752-eb11-8da9-e4434bdf6706.svg 表示机器人当前位置, 867d493b-c752-eb11-8da9-e4434bdf6706.svg 表示目标点位置, 3d7e493b-c752-eb11-8da9-e4434bdf6706.svg 表示机器人距目标的距离, 3e7e493b-c752-eb11-8da9-e4434bdf6706.svg 的作用是在机器人距离目标较远时,削弱目标引力势的作用, 3f7e493b-c752-eb11-8da9-e4434bdf6706.svg 表示机器人距离第 377e493b-c752-eb11-8da9-e4434bdf6706.svg 个障碍物的距离, 437e493b-c752-eb11-8da9-e4434bdf6706.svg 表示第 377e493b-c752-eb11-8da9-e4434bdf6706.svg 个障碍物的斥力势作用范围。

    307e493b-c752-eb11-8da9-e4434bdf6706.svg337e493b-c752-eb11-8da9-e4434bdf6706.svg 对势场形状的影响很大,适当的增大 307e493b-c752-eb11-8da9-e4434bdf6706.svg 能够增强引力势场的作用,有助于减少产生局部极小点的可能,并加快机器人向目标运动。 337e493b-c752-eb11-8da9-e4434bdf6706.svg 影响机器人在障碍物附近的运动特性, 337e493b-c752-eb11-8da9-e4434bdf6706.svg 比较大可以使机器人距离障碍物更远,运动路径更安全; 337e493b-c752-eb11-8da9-e4434bdf6706.svg 比较小,机器人在避开障碍物时运动比较平滑。

    利用上面势函数的梯度可以计算机器人收到的假想引力和斥力:

    527e493b-c752-eb11-8da9-e4434bdf6706.svg

    547e493b-c752-eb11-8da9-e4434bdf6706.svg

    2.4.2 人工势场法算法改进

    当机器人的运行环境中包含形状复杂或者距离很近的障碍物时,可能出现势场局部极小点,导致机器人在该处停止或在其周围振动。如下图所示,当环境中出现“陷阱”形障碍物或者与目标成特定位置关系的障碍物时,可能在人工势场中产生局部极小点(图中L点),当机器人运动到局部极小点附近时,势场的负梯度方向指向L点。机器人将在L点处停止或在其附近振动或作圆周运动。

    cc92d6e35cddb51a0dbe4568242f4775.png
    6847277b614d95423fe91d070455b71e.png
    图9 人工势场法的局部极小点

    为了使机器人从局部极小点中逃离,在人工势场法的基础上引入应激行为,即增加绕行行为。当机器人遇到局部极小点时,忽略目标引力势的作用,沿着斥力势的等势面方向移动,直到机器人离开局部极小区域。改进的算法流程如下:

    1. 根据传感器信息计算当前位置的引力和斥力;

    2. 判断是否处于绕行行为,若是,执行3;若否,执行4;

    3. 判断是否离开局部极小区域,若是,机器人沿着合力方向运动,结束绕行行为;若否,机器人沿着斥力场等势线运动,继续绕行行为;

    4. 判断是否遇到局部极小点,若是,机器人沿着斥力场等势线运动,开始绕行行为;若否,机器人沿着合力方向运动;

    5. 判断是否到达目标,若是,退出算法;若否,继续1;

    使用下面的判别条件判断机器人是否遇到局部极小点。

    条件1: 597e493b-c752-eb11-8da9-e4434bdf6706.svg

    条件2: 5a7e493b-c752-eb11-8da9-e4434bdf6706.svg

    当条件1或者条件2出现时,就认为机器人遇到了局部极小点。条件1中 5b7e493b-c752-eb11-8da9-e4434bdf6706.svg 是一个很小的正数,其含义是机器人受到的虚拟合力接近0。这是最直接局部极小点判断方法。条件2中 5f7e493b-c752-eb11-8da9-e4434bdf6706.svg 为0,1之间某一正数, 617e493b-c752-eb11-8da9-e4434bdf6706.svg 为机器人运动过程中某一状态, 627e493b-c752-eb11-8da9-e4434bdf6706.svg 表示机器人从 617e493b-c752-eb11-8da9-e4434bdf6706.svg 到达当前位置 e67d493b-c752-eb11-8da9-e4434bdf6706.svg 的总路程,条件2成立意味着机器人在运动很长路程后,位移很小。用来检测机器人在局部极小点附近发生的振动和圆周运动。

    2.5BUG算法

    BUG算法是一种完全应激的机器人避障算法。其算法原理类似昆虫爬行的运动决策策略。在未遇到障碍物时,沿直线向目标运动;在遇到障碍物后,沿着障碍物边界绕行,并利用一定的判断准则离开障碍物继续直行。这种应激式的算法计算简便,不需要获知全局地图和障碍物形状,具备完备性。但是其生成的路径平滑性不够好,对机器人的各种微分约束适应性比较差。

    2.5.1 BUG1算法

    该算法的基本思想是在没有障碍物时,沿着直线向目标运动可以得到最短的路线。当传感器检测到障碍物时,机器人绕行障碍物直到能够继续沿直线目标运动。BUG1算法实现了最基本的向目标直行和绕行障碍物的思想。

    假设机器人能够计算两点之间的距离,并且不考虑机器人的定位误差。初始位置和目标位置分别用 677e493b-c752-eb11-8da9-e4434bdf6706.svg 和 687e493b-c752-eb11-8da9-e4434bdf6706.svg 表示;机器人在 6b7e493b-c752-eb11-8da9-e4434bdf6706.svg 时刻的位置表示为 6d7e493b-c752-eb11-8da9-e4434bdf6706.svg ; 6e7e493b-c752-eb11-8da9-e4434bdf6706.svg 表示连接机器人位置 6d7e493b-c752-eb11-8da9-e4434bdf6706.svg 和目标点的直线。初始时, 707e493b-c752-eb11-8da9-e4434bdf6706.svg 。若没有探测到障碍物,那么机器人就沿着 6e7e493b-c752-eb11-8da9-e4434bdf6706.svg 向目标直行,直到到达目标点或者遇到障碍物。当遇到障碍物时,记下当前位置 747e493b-c752-eb11-8da9-e4434bdf6706.svg 。然后机器人环绕障碍物直到又一次到达 747e493b-c752-eb11-8da9-e4434bdf6706.svg ,找到环绕路线上距离目标最近的点 777e493b-c752-eb11-8da9-e4434bdf6706.svg ,并沿着障碍物边界移动到该点。随后,直线 6e7e493b-c752-eb11-8da9-e4434bdf6706.svg 更新,机器人继续沿直线向目标运动。如果沿这条直线运动时还会遇到该障碍物,那么机器人不能到达目标点。否则算法不断循环直到机器人到达目标点或者规划器认为机器人无法到达目标点。

    e2e97c450434bc68808c7e7b002a6e9d.png
    图10 BUG1算法运动规划
    1a4aa219f9ab61768d6c346366933634.png
    图11 BUG1算法中认为机器人无法到达目标点的情况
    b90da3e26ab3010640f39d0d2a97f1fe.png
    图12 BUG1算法伪代码

    2.5.2 BUG2算法

    BUG2算法也有两种运动:朝向目标的直行和沿边界绕行。与BUG1算法不同的是,BUG2算法中的直线 6e7e493b-c752-eb11-8da9-e4434bdf6706.svg 是连接初始点和目标点的直线,在计算过程中保持不变。当机器人在点遇到障碍物时,机器人开始绕行障碍物,如果机器人在绕行过程中在距离目标更近的点再次遇到直线 6e7e493b-c752-eb11-8da9-e4434bdf6706.svg ,那么就停止绕行,继续沿着直线 6e7e493b-c752-eb11-8da9-e4434bdf6706.svg 向目标直行。如此循环,直到机器人到达目标点 687e493b-c752-eb11-8da9-e4434bdf6706.svg 。如果机器人在绕行过程中未遇到直线 6e7e493b-c752-eb11-8da9-e4434bdf6706.svg 上与目标更近的 777e493b-c752-eb11-8da9-e4434bdf6706.svg 点而回到了 747e493b-c752-eb11-8da9-e4434bdf6706.svg 点,那么得出结论,机器人不能到达目标。

    5e3d5984bc50c34cc7de2ed3ed74e7b3.png
    图13 BUG2算法运动规划
    bb2b79f6fb2f4e1d62856bb1a25da2df.png
    图14 BUG2算法中认为机器人无法到达目标点的情况
    6b5b40cef3995fdddd357de305b259ad.png
    图15 BUG2算法伪代码

    BUG1和BUG2算法提供了搜索问题的两种基本方法:比较保守的BUG1算法进行详细的搜索来获得最佳的离开点。这需要机器人环绕整个障碍物的边界。而BUG2算法使用一种投机的方法。机器人不环绕完整的障碍物,而选择第一个可用的点作为离开点。对于一般的环境,BUG2算法的效率更高;而对于复杂形状的障碍物,保守的BUG1算法性能更优。

    2.5.3 TangentBUG算法

    TangentBUG算法是对BUG2算法的提高。它利用机器人上距离传感器的读数对障碍物做出提前规避,可以获得更短更平滑的机器人路径。在一个静态环境中,传感器读数 8f7e493b-c752-eb11-8da9-e4434bdf6706.svg 是机器人位置 e67d493b-c752-eb11-8da9-e4434bdf6706.svg 和传感器扫描角度 937e493b-c752-eb11-8da9-e4434bdf6706.svg 的函数,具体点说, 8f7e493b-c752-eb11-8da9-e4434bdf6706.svg 是沿着 e67d493b-c752-eb11-8da9-e4434bdf6706.svg 的射线以角度 937e493b-c752-eb11-8da9-e4434bdf6706.svg 到达最近障碍物的距离,

    997e493b-c752-eb11-8da9-e4434bdf6706.svg

    其中 9a7e493b-c752-eb11-8da9-e4434bdf6706.svg 。

    对于某一个固定的位置 e67d493b-c752-eb11-8da9-e4434bdf6706.svg , 9d7e493b-c752-eb11-8da9-e4434bdf6706.svg 被传感器视野内的障碍物分割成多个连续区间。如下图所示。 9d7e493b-c752-eb11-8da9-e4434bdf6706.svg 出现不连续或者到达传感器最大测量范围的角度就是这些连续区间的端点。TangentBUG算法利用这些区间的端点避开工作空间中的障碍物。

    b9af37b49991e87473dcaa2babbb716d.png
    图16 距离传感器扫描障碍物

    对 9d7e493b-c752-eb11-8da9-e4434bdf6706.svg 不连续的情况做出说明(如图17所示):点 b07d493b-c752-eb11-8da9-e4434bdf6706.svg , b37d493b-c752-eb11-8da9-e4434bdf6706.svg , a57e493b-c752-eb11-8da9-e4434bdf6706.svg , a67e493b-c752-eb11-8da9-e4434bdf6706.svg , a77e493b-c752-eb11-8da9-e4434bdf6706.svg , a97e493b-c752-eb11-8da9-e4434bdf6706.svg , aa7e493b-c752-eb11-8da9-e4434bdf6706.svg 和 ac7e493b-c752-eb11-8da9-e4434bdf6706.svg 与障碍物的不连续性相关;请注意,这里的射线与障碍物相切。点 a67e493b-c752-eb11-8da9-e4434bdf6706.svg 是不连续的,因为障碍物边界落在传感器的范围之外。 b07d493b-c752-eb11-8da9-e4434bdf6706.svg 和 b37d493b-c752-eb11-8da9-e4434bdf6706.svg , a57e493b-c752-eb11-8da9-e4434bdf6706.svg 和 a67e493b-c752-eb11-8da9-e4434bdf6706.svg , a77e493b-c752-eb11-8da9-e4434bdf6706.svg 和 a97e493b-c752-eb11-8da9-e4434bdf6706.svg , aa7e493b-c752-eb11-8da9-e4434bdf6706.svg 和 ac7e493b-c752-eb11-8da9-e4434bdf6706.svg 之间的free space边界上的点集是连续性的间隔(加线部分)。

    061cc32cb420538d31019d544940f6f6.png
    图17 不连续的示意图

    与其他的BUG算法一样,TangentBUG算法也有两种行为:直行(motion-to-go)和环绕障碍物(boundary-following)。

    首先机器人沿着直线向目标运动,直到它利用传感器观测到在其运动方向的前方有障碍物。不在机器人前方的障碍物对其向目标运动没有影响。比如下图中的障碍物 b87e493b-c752-eb11-8da9-e4434bdf6706.svg,障碍物 b87e493b-c752-eb11-8da9-e4434bdf6706.svg 在传感器视野内,但是不阻碍机器人的运动。机器人在刚刚探测到障碍物时,传感器视野圆与障碍物边界相切。随着机器人继续向前移动,这个切点分裂成两个交点 b07d493b-c752-eb11-8da9-e4434bdf6706.svg 和 b37d493b-c752-eb11-8da9-e4434bdf6706.svg ( a57e493b-c752-eb11-8da9-e4434bdf6706.svg 和 a67e493b-c752-eb11-8da9-e4434bdf6706.svg ), b07d493b-c752-eb11-8da9-e4434bdf6706.svg 和 b37d493b-c752-eb11-8da9-e4434bdf6706.svg 之间的障碍物边界区间与机器人运动直线相交。

    65bef2a27ceb1df688ea19f2ac91239e.png
    图18 机器人向目标运动遇到障碍物

    此时,机器人不能继续向目标运动,而从两个交点中选择一个作为局部目标。为比较两个交点对于机器人向目标运动的优劣性,定义探索距离 c47e493b-c752-eb11-8da9-e4434bdf6706.svg。在没有关于障碍物的其他信息时,可以将探索距离 c47e493b-c752-eb11-8da9-e4434bdf6706.svg 定义为从 e67d493b-c752-eb11-8da9-e4434bdf6706.svg 经过一个交点到目标点的折线长度,即: c87e493b-c752-eb11-8da9-e4434bdf6706.svg

    例如图19,机器人“看见”了障碍 ca7e493b-c752-eb11-8da9-e4434bdf6706.svg ,并选择向 b37d493b-c752-eb11-8da9-e4434bdf6706.svg 移动,因为 cc7e493b-c752-eb11-8da9-e4434bdf6706.svg 。

    当机器人位于 e67d493b-c752-eb11-8da9-e4434bdf6706.svg 时,它无法知道 b87e493b-c752-eb11-8da9-e4434bdf6706.svg 阻挡了从 b37d493b-c752-eb11-8da9-e4434bdf6706.svg 到目标 687e493b-c752-eb11-8da9-e4434bdf6706.svg 的路径。

    在图20中,当机器人位于 e67d493b-c752-eb11-8da9-e4434bdf6706.svg 但目标 687e493b-c752-eb11-8da9-e4434bdf6706.svg 不同时,它具有足够的传感器信息来得出结论: b87e493b-c752-eb11-8da9-e4434bdf6706.svg 确实阻挡了从 b37d493b-c752-eb11-8da9-e4434bdf6706.svg 到目标 687e493b-c752-eb11-8da9-e4434bdf6706.svg 的路径,从而朝 a67e493b-c752-eb11-8da9-e4434bdf6706.svg 行驶。

    因此,选择向 b37d493b-c752-eb11-8da9-e4434bdf6706.svg 行驶刚开始的时候可能使得 dd7e493b-c752-eb11-8da9-e4434bdf6706.svg 最小化,而不是向 a67e493b-c752-eb11-8da9-e4434bdf6706.svg 行驶,但是planner有效地为 e17e493b-c752-eb11-8da9-e4434bdf6706.svg 分配无限大的成本代价,因为它有足够的信息来推断任何通过 b37d493b-c752-eb11-8da9-e4434bdf6706.svg 的路径都不是最理想的。

    fe9defac153242bdb75a72fcb315f459.png
    图19
    12e6579aca3bc623b5371231986c186c.png
    图20

    机器人将选择探索距离短的交点作为局部目标,向之运动。随着机器人不断运动,交点不断更新,探索距离也不断减小。如下图所示。当 e77e493b-c752-eb11-8da9-e4434bdf6706.svg 时,机器人还没有探测到障碍物,因而它向目标作直线运动;当 e97e493b-c752-eb11-8da9-e4434bdf6706.svg 时,机器人开始探测到障碍物,并朝向障碍物探索距离近的一侧运动;当 ea7e493b-c752-eb11-8da9-e4434bdf6706.svgec7e493b-c752-eb11-8da9-e4434bdf6706.svg 时,机器人继续移动,同时更新探测区域,在这个过程中探索距离不断减小。

    1002f42237fe942cb6375b85e04d8867.png
    图21 机器人运动时不断更新局部目标和探测距离

    在机器人运动过程中,探索距离不再减小时,就停止向目标运动行为,切换到环绕边界行为。此时,机器人找到了探测距离的一个极小值,并可计算已探测的障碍物边界与目标 687e493b-c752-eb11-8da9-e4434bdf6706.svg 的最近距离 f07e493b-c752-eb11-8da9-e4434bdf6706.svg。机器人按照原来的方向环绕障碍物运动,同时机器人更新当前探测的障碍物边界与目标的最近距离 f37e493b-c752-eb11-8da9-e4434bdf6706.svg。当发现 f47e493b-c752-eb11-8da9-e4434bdf6706.svg 时,机器人停止障碍物环绕行为,继续向目标运动。

    ff5b37a4cc01769e82d11578586911cc.png
    图22 机器人环绕障碍物运动

    如上图所示,当机器人探索到障碍物上的 f77e493b-c752-eb11-8da9-e4434bdf6706.svg 点后,探索距离就不再减小,即 f77e493b-c752-eb11-8da9-e4434bdf6706.svg 点是机器人探索距离在障碍物边界上的局部极小点。机器人开始沿着障碍物边界进行环绕,图中虚线路径就是机器人环绕障碍物时所走的路径。当机器人探测到与目标距离相比 f77e493b-c752-eb11-8da9-e4434bdf6706.svg 点更近的点时,重新开始接近目标的运动。

    2.6 增量式启发算法

    2.6.1 LPA*算法

    LPA*算法,即Lifelong Planning A*算法,该算法于2001年由Sven Koenig和Maxim Likhachev提出,是一种增量启发式搜索版本的A*算法,这种路径规划算法适用于随着时间改变导致有限栅格地图上的边缘代价c(s1,s2)改变的问题,也就是随着时间改变障碍物增多或减少,网格点发生增删等,在许多场合下比再利用A*重新搜索更高效。

    详情请参考:路径规划——Lifelong Planning A*算法:https://zhuanlan.zhihu.com/p/51114323

    2.6.2 D* Lite算法

    D* Lite算法是以LPA*为基础,是Maxim Likhachev和Sven Koenig于2002年基于LPA*,结合A*算法思想,提出一种增量启发式算法,适用于在未知环境中的导航以及路径规划,广泛用于目前各种移动机器人和自主车辆载具,例如“机遇号”和“勇气号”火星车测试的原型导航系统。

    详情请参考:路径规划——D* Lite算法:https://zhuanlan.zhihu.com/p/51124179

    关于A*、LPA*、D* Lite算法的小结,详情请参考:

    (1)路径规划——关于A*、LPA*、D* Lite算法的小结:https://zhuanlan.zhihu.com/p/51131414

    (2)路径规划——启发式动态规划算法发展研究:https://zhuanlan.zhihu.com/p/51098426

    2.7小结

    本章研究了几种常用的运动规划算法。其中,人工势场法应用灵活,可以在保证安全的情况下获得一条平滑路径,并且对于动态环境可以实现实时运动控制。适合用于长距离机动且障碍物较少的情况。而基于随机采样的搜索树方法可以在复杂约束环境中获得可行解,适合用于机械臂近距离操作。

    参考文献:

    【1】Choset H , Kantor G A , Thrun S . Principles of Robot Motion: Theory, Algorithms, and Implementations[M]. MIT Press, 2005.

    e1e088ea9a44a9d4f2a502256b45b3f1.png

    展开全文
  • 自动驾驶汽车的路径规划算法最早源于机器人的路径规划研究,但是就工况而言却比机器人的路径规划复杂得多,自动驾驶车辆需要考虑车速、道路的附着情况、车辆最小转弯半径、外界天气环境等因素。本文将为大家介绍四种...

    d586f59cb860ee6b28a7bd9e022918a8.png

    自动驾驶汽车的路径规划算法最早源于机器人的路径规划研究,但是就工况而言却比机器人的路径规划复杂得多,自动驾驶车辆需要考虑车速、道路的附着情况、车辆最小转弯半径、外界天气环境等因素。
    本文将为大家介绍四种常用的路径规划算法,分别是搜索算法、随机采样、曲线插值和人工势场法。1.搜索算法
    搜索算法主要包括遍历式和启发式两种,其中Dijkstra算法属于传统的遍历式,A*算法属于启发式,在A*算法的基础上,还衍生出了D*Lite算法、Weighted A*算法等其他类型。Dijkstra算法最早由荷兰计算机学家狄克斯特拉于1959年提出,算法核心是计算从一个起始点到终点的最短路径,其算法特点是以起始点开始向周围层层扩展,直到扩展到终点为止,再从中找到最短路径,算法搜索方式如图(1-1)所示。A*算法在Dijkstra算法上结合了最佳优先算法,在空间的每个节点定义了一个启发函数(估价函数),启发函数为当前节点到目标节点的估计值,从而减少搜索节点的数量从而提高效率。A*算法中的启发函数
    包括两部分,表示从初始点到任意节点n的代价,表示节点n到目标点的启发式评估代价,在对象从初始点开始向目标点移动时,不断计算的值,从而选择代价最小的节点。一般来说遍历式算法可以取得全局最优解,但是计算量大,实时性不好;启发式算法结合了遍历式算法以及最佳优先算法的优点,具有计算小、收敛快的特点。图(1-2)是最佳优先算法示意图,可以看出该算法有一定的选择性,但是面对图中的u型障碍物会出现计算效率低的情况。而A*算法完美的结合了Dijkstra算法和最佳优先算法,不仅有一定的选择性,并且计算量相对也是最少的,更快得找到了最短路径。

    6d613ca2d3cf90b30b9564adb4bf9373.png


    图1-1 Dijkstra算法示意图

    c4d7cfbb955fdb2be124c20429e7fb97.png


    图1-2 最佳优先算法示意图

    583c59e86cf7bc2b6e2296bd45af7df2.png


    图1-3 A*算法示意图2.随机采样
    随机采样主要包括蚁群算法以及RRT(快速扩展随机树)算法。蚁群算法是由Dorigo M等人于1991年首先提出,并首先使用在解决TSP(旅行商问题)上。其算法基本原理如下:1.蚂蚁在路径上释放信息素。2.碰到还没走过的路口,随机选一条走,同时释放与路径长度有关的信息素。3.信息素浓度与路径长度成反比。后来蚂蚁再次碰到该路口时,就选择信息浓度较高的路径。4.最优路径上的信息素浓度越来越大。5.信息素浓度最大的路径为最优路径。其在小规模TSP中性能尚可,再大规模TSP问题中性能下降,容易停滞。实际道路环境是比较复杂的,不光有道路、障碍物等的限制,也有其自身动力学的约束,所以该算法更适合做全局路径规划,不太适合局部路径规划。

    4116e3537363b03c4bb1d10b017d45dc.png


    图2-1 蚁群算法示意图3.曲线插值
    曲线插值的方法是按照车辆在某些特定条件(安全、快速、高效)下,进行路线的曲线拟合,常见的有贝塞尔曲线、多项式曲线、B样条曲线等。一般就多项式算法而言,主要考虑以下几个几何约束,从而确定曲线的参数。几何约束:1.起始点的位置与姿态。2.最小转弯半径。3.障碍物约束。4.目标点的位置与姿态。根据考虑的几何约束不同,多项式算法的阶数从三阶到六阶甚至更高阶,阶数越高的算法复杂度越高,收敛速度越慢。四次多项式的形式如式(3-1)所示,参数由几何约束条件确定。基于参数化曲线来描述轨迹,这种类型的算法比较直观,也可以更加准确的描述车辆所需满足的道路条件,规划出的轨迹也十分平坦、曲率变化连续并可进行约束。缺点是计算量较大,实时性不太好,并且其评价函数也比较难以找到最优的,未来的研究方向主要集中于简化算法以及更加完善的评价函数。目前,曲线拟合算法是采用比较广泛的规划方法。

    2cfe6a4d78e56d62cd2075aaf9c75e3a.png

    (3-1)4.人工势场法
    人工势场法(Artificial PotentialField,APF)是由Khatib于1986年提出的。该算法是假设目标点会对自动驾驶车辆产生引力,障碍物对自动驾驶车辆产生斥力,从而使自动驾驶车辆沿“势峰”间的“势谷”前进。这种算法的优点就是结构简单,有利于底层控制的实时性,可大大减少计算量和计算时间,并且生成相对光滑的路径,利于保持自动驾驶车辆的稳定性。算法的缺点是有可能陷入局部最优解,难以对规划出的路径进行车辆动力学约束,复杂环境下的势场搭建也比较棘手。势场的基本步骤如下:首先搭建势场,包括障碍物势场以及目标点势场,然后通过求势场负梯度,可以得到车辆在势场中所受的障碍物斥力以及目标点引力。将所受的所有障碍物斥力与目标点引力叠加,就可以得到车辆在势场中任意位置的受力情况,最后根据合力情况不断迭代更新位置,就可以得到从起始点到终点的完整路径。

    08b5bf82f6532206dbc0055315e3544d.png


    图4-1 基于人工势场法搭建的势能场

    06cadfec70ac0304e433b3400d89f490.png


    图4-2 基于人工势场法规划的路径点
    最后以下表对本文介绍的四种算法的优缺点、计算效率进行一个简要的对比总结。不难发现,其中人工势场法的计算速度最快,实时性也最好,但是存在局部最优解、复杂势场难以搭建的情况,这也是未来该算法的研究热点、难点;其中,曲线插值是目前较常见的一种算法,虽然该算法的计算效率不高,但是相信在未来车载计算机的计算能力大幅度提升之后,该算法可以被更广泛得使用。

    7f6f910bef207e934af3fcb310979eef.png

    【欢迎大家提供行业新闻热点,商业合作请联系:18562613430】

    展开全文
  • 动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。 什么是动态规划 动态规划(Dynamic Programming)对于子问题重叠的情况特别有效,因为它将子问题...
  • 路径规划算法:基于GWO的路径规划算法- 附代码 文章目录路径规划算法:基于GWO的路径规划算法- 附代码1.算法原理1.1 环境设定1.2 约束条件1.3 适应度函数2.算法结果3.MATLAB代码4.参考文献 摘要:本文主要介绍利用...
  • PSO路径规划算法,源码
  • 路径规划算法

    千次阅读 2019-07-19 15:38:56
    前言:关于路径规划算法的一些汇总资料 原文地址:http://theory.stanford.edu/~amitp/GameProgramming/ 浅谈路径规划算法:https://blog.csdn.net/chauncygu/article/details/78031602 路径规划之 A* 算法:...
  • 基于蚁群算法的二维路径规划算法

    千次阅读 多人点赞 2021-01-05 00:20:50
    文章目录一、理论基础1、路径规划算法三级目录 一、理论基础 1、路径规划算法 路径规划算法是指在有障碍物的工作环境中寻找一条从起点到终点、无碰撞地绕过所有障碍物的运动路径。路径规划算法较多,大体上可分为...
  • RRT路径规划算法

    千次阅读 2019-08-29 21:43:42
    RRT路径规划算法地图RRT算法原理路径平滑处理总结 RRT(Rapidly-Exploring Random Tree)算法是一种基于采样的路径规划算法,常用于移动机器人路径规划,适合解决高维空间和复杂约束下的路径规划问题。基本思想是以...
  • PRM路径规划算法

    万次阅读 2017-09-19 17:13:45
    传统的人工势场、单元分解法需要对空间中的障碍物进行精确建模,当环境中的障碍物较为复杂时,将导致规划算法计算量较大。基于随机采样技术的PRM法可以有效解决高维空间和复杂约束中的路径规划问题。  PRM是一种...
  • 动态规划算法

    千次阅读 2016-12-26 20:49:05
    1. 动态规划算法动态规划:通过把原问题分解为相对简单的子问题来求解复杂问题。动态规划常常适用于有重叠子问题和最优子结构性质的问题。 算法总体思想 动态规划算法与分治法类似,其基本思想也是将待求解问题...
  • 路径规划算法学习Day3

    千次阅读 多人点赞 2020-12-13 15:14:57
    路径规划算法学习Day3-Dijkstra算法实现前言一、Dijkstra算法二、使用步骤1.引入库2.读入数据总结 前言 算法原理:参考路径规划算法学习Day1 提示:本文会用matlab实现Dijkstra算法,并且会分享一些函数用法的链接...
  • 动态规划算法介绍

    千次阅读 2019-02-17 19:34:49
    动态规划算法及其应用 动态规划是运筹学的一个分支,是求解决策过程最优化的数学方法。动态规划算法的思想和分治算法类似,基本思想也是将待求问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原...
  • 路径规划算法进阶

    2020-03-28 18:14:49
    路径规划算法进阶 最早是在大学期间学习路径规划算法,严蔚敏_吴伟民的《数据结构》讲的最短路径。当时感到有些晦涩难懂,并没有理解算法思想。回头看,主要是因为应付考试,没有和实际应用场景建立连接,所以体会...
  • 贪心算法和动态规划算法比较

    千次阅读 2018-08-09 16:22:20
    动态规划和贪心算法都是一种递推算法 均用局部最优解来推导全局最优解 不同点: 贪心算法: 1.贪心算法中,作出的每步贪心决策都无法改变,...动态规划算法: 1.全局最优解中一定包含某个局部最优解,但不一定...
  • matlab实现动态规划算法

    千次阅读 2020-09-18 16:19:11
    matlab实现动态规划算法论文例子实现算法代码 最近看缓存相关论文,里面提到动态规划算法来解决小规模组合优化最优解,便尝试复DP算法,论文给出了一个简单例子,先从实现该例子开始,话说动态规划算法可以写好多...
  • Lattice Planner规划算法

    2020-04-16 15:43:02
    点击即可打开链接:社群分享内容 | Lattice Planner规划算法
  • 路径规划算法学习Day4-Astar算法

    千次阅读 2020-12-26 20:31:13
    路径规划算法学习Day4-Astar算法前言1.2、matlab实现1.3、20*20地图1.4、50*50地图2.函数解读 前言 算法原理:参考路径规划算法学习Day1 路径规划算法学习Day1 # 1、Astar算法 ## 1.1、地图创建 总所周知:栅格法...
  • 路径规划算法简介

    千次阅读 2019-09-24 01:50:29
    路径规划算法简介 1.涉及问题: 这里的路径规划是指如何寻找一条从给定起点到终点的路径,使机器人沿该路径移动的过程中不与障碍物发生碰撞且路程最短或移动代价最小。 2.简要介绍的算法: 1.遗传算法; 2.模拟退火...
  • 路径规划算法 一、A*算法总结 基本思想 A算法把Dijkstra算法(靠近初始点的结点)和最佳优先搜索算法(BFS)(靠近目标点的结点)的信息块结合起来。 在讨论A算法的标准术语中,g(n)表示从初始结点到任意结点n的...
  • D* Lite路径规划算法

    万次阅读 多人点赞 2018-12-19 21:43:39
    D* Lite路径规划算法D* Lite算法简述 D* Lite算法简述 D_star Lite算法是Koenig S和Likhachev M基于LPA_star 算法基础上提出的路径规划算法。 D_star Lite 算法之于 LPA_star 算法犹如 D_star 算法之于 A_star 算法...
  • APOLLO规划算法Lattice plan算法学习

    千次阅读 2019-06-17 19:45:56
    最近在看百度阿波罗的动态规划算法,当前版本主要使用的是lattice plan,2.0版本使用的是EM plan,本篇文章主要记录Lattice plan算法: Lattice planner程序入口: Status LatticePlanner::PlanOnReferenceLine( ...
  • 路径规划算法学习Day5

    千次阅读 2021-01-18 11:31:46
    路径规划算法学习Day5-A*算法的实现
  • 文章目录1.序2.动态规划的基本概念[^1]3.动态规划算法的基本思想[^2]4....这篇文章主要介绍动态规划算法的基本思想、使用动态规划算法求解问题的基本步骤、动态规划算法的两个基本要素以及一些经典的动态规划问题。...
  • 这里写自定义目录标题移动机器人路径规划算法介绍及A*算法详解路径规划算法总结各种算法比较A*算法详解 移动机器人路径规划算法介绍及A*算法详解 随着人工智能的兴起,移动机器人逐渐走入了更多人的视线,ML和DL为...
  • 路径规划_RRT路径规划算法

    千次阅读 2019-09-04 16:54:47
    RRT路径规划算法 https://www.cnblogs.com/21207-iHome/p/7210543.html
  • 五大常用算法之二:动态规划算法

    万次阅读 2018-03-14 12:52:53
    动态规划算法一、基本概念 动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。二、基本思想与...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 44,934
精华内容 17,973
关键字:

规划算法