路径规划算法

《路径规划算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、[选取日期][键入文档副标题]

2、刘绍翰nuaa未知环境的动态路径规划度量距离灰度化四连通和8连通。第一章、静态搜索与A*算法很多时候，我们需要在一个图中寻找一条从源点到目标节点的最短路径，我们称之为路径规划。搜索算法主要分为，盲目搜索和启发式搜索，它们的一个作用是能够从解空间中需找一条从源点到目标节点的最短路径。启发式搜索是在搜索的过程中，参考一定的指标函数来决定搜索的策略。迪杰斯特拉算法，类似于广度优先遍历，利用源点到当前节点的代价值作为指标，其一定可以获得从原点到目标节点的最短路，但是其访问的节点数很多。而最好优先搜索，采用

3、离标节点的距离作为搜索的代价参考值，贪心选择最小的扩展节点，也可以获得最短路径，而且其搜索的节点数目大大减少。图1迪杰斯特拉算法图2最好优先搜索算法当地图中包含障碍物时，迪杰斯特拉算法，仍然可以获得最短路径的路径，最好优先搜索的节点尽管少，但是其不能获得最优解。图3迪杰斯特拉算法图4最好优先搜索算法而A*算法，参考了从原点到当前节点的代价值和当前节点到目标节点启发值，综合了迪杰斯特拉算法和做好优先搜索算法优点，在有障碍物和无障碍物的地图上，可以像迪杰斯特拉算法一样求得最短路径同时，同时能够像最好优先搜索一样减少搜索范围，减少搜索

4、节点的数目。图5无障碍物时A*路径规划图6有障碍物时A*路径规划算法经典的迪杰斯特拉算法可以求得最短的路径，而启发式搜索A*算法，不但可以求得最短路，而且可以使得搜索的范围大大减少，上述算法是传统的静态路径规划算法，其规划的前提条件是已经知地图的结构。A*算法属于离线事先规划，在规划完毕之后，可以沿着最优路径移动，不是在线规划，不能一边规划一边移动。A*算法的基本理论A*算法又叫做启发式搜索算法，具有悠久的历史，其启发函数f=g+h。其中g表示从原点到当前节点已经付出的代价，好表示从当前节点到目标节点的启发值。1)A*算法必须满

5、足h(x)<=h*(x)，其中h*(x)是实际的启发值，h*(x)在实际中通常是无法事先得知的，但是这个条件是很容易满足，只要满足该条件，一定能够获得最优解。2)如果最短路径长度为C*,则在算法结束前，open表中至少有一个节点n,满足f(n)<=C*.这个性质可以这样理解，因为最短路径存在，我们不妨设它为:source->a->b->c->...->n->.....->goal.且在当前时刻，路径中在节点n前的节点都在closed表中，即已经扩展了，而节点n自己在open表中（注意：算法结束前任意时刻都有这样的节点n存在）。则

6、由于该条路劲是最短路径，我们可以知道此时在open表中的n的g(n)值已经是准确值,即最小值了。而f(n)=g(n)+h(n)=g*(n)+h(n)<=g*(n)+h*(n)=C*.(最后一个式子取等号是由于n在最短路径上)有了这个性质，我们就知道，当A*算法扩展到目标节点时，必有f(goal)=g(goal)<=C*(即=C*)。否则,如果f(goal)>C*,由于目标节点是被扩展节点,则open表中其他任意其他节点t,都有f(t)>=f(goal)>C*,和性质1矛盾。3)扩展新节点时很容易出现重复节点的问题，从上面的伪代码

7、可以看出，如果新扩展节点已经存在于closed表中，且f值比表中节点的f值还要小的话，则除了更新该节点f值，还需要重新扩展该节点，这简直就是把人从棺材里拖出来。但是如果h函数满足相容性，这一步就可以省掉了。所谓相容性就是指对任意节点s1,都满足：h(s1)<=h(s2)+c(s1,s2)(其中c(s1,s2)是指从s1转移到s2的代价)有这个性质我们在不等号两边加上g(s1),则有g(s1)+h(s1)<=h(s2)+g(s1)+c(s1,s2)。如果我们此时扩展s1,而s2又是能被s1扩展的节点，则由这个式子我们得到f(s1)

8、<=f'(s2).(若s2之前就已经被扩展出了，则当前的f(s2)可能比f'(s2)小)这个式子的意义在于由当前节点进行扩展这个方案下得到的节点的f值总比当前扩展节点的f值大（子节点总比父节点费用高），而我们每次又是选择一个具有最小f值的节点进行扩展，然后让其进入closed表，这就使得，进入closed表的每个节点的f值是递增的，并且之后不可能出现比closed表中最大f值。还要小的节点被扩展出来（感觉有点问题），因此扩展出的新节点不必再拿到closed表中检查更新了。1)可以得知有如下条件成立：f(y)=g(y)+h(y)=

9、g(x)+C(x,y)+h(y)>=g(x)+h(x)即代价函数f的值是非递减的。2)下面我们来讨论一下h函数的相容性，由于C(x,y)为从x到y的实际代价，因为h的估计小于实际的代价值，h(x)