Dijkstra算法移动机器人路径规划的研究

移动机器人路径规划的研究

移动机器人路径规划的目标是寻求一条从初始点到终点的路径，使得机器人

沿规划出的路径运动时不会与环境中的障碍物碰撞，其实质就是移动机器人运动过程中的导航和避碰。

路径规划是自主式移动机器人导航的基本环节之一，它是按照某一性能指标搜索一条从起始状态到目标状态的最优或近似最优的无碰路径。根据机器人对环境信息知道的程度不同，可分为两种类型：环境信息完全知道的全局路径规划和环境信息完全未知或部分未知，通过传感器在线地对机器人的工作环境进行探测，以获取障碍物的位置、形状和尺寸等信息的局部路径规划。

1全局路径规划

全局路径规划又称静态路径规划，是基于环境先验完全信息的路径规划，

是指根据环境模型找出从起始点到目标点的符合一定性能的可行或最优的路径，它涉及的基本问题是世界模型的表达和搜索策略。全局路径规划包括环境建模和路径搜索策略两个子问题。其中环境建模的主要方法有:可视图法(V-Graph)、栅格法(Grids)和拓扑法等。

2局部路径规划

局部路径规划又称动态路径规划，依赖于传感器的信息，是未知或部分未知，

即障碍物的尺寸、行状和位置等信息必须通过传感器获得。局部路径规划的主要方法有人工势场法Artificial Potential Field。遗传算法（Genetic-algorithm）、模糊逻辑算法（Fuzzy Logic Algorithm）和滚动窗口法等。

3．环境建模

移动机器人路径规划中，包括环境建模和路径搜索策略两个子问题。 移动机器人环境建模方法：可视图法（V-Graph），自由空间法（Free SpaceApproach）和栅格法（Grids）等。

可视图法把机器人看作一点，将机器人、目标点和多边形障碍物的各顶点进行组合连接，并保证这些直线均不与障碍物相交，这就形成了一张图，称为可视图。即要求机器人和障碍物各顶点之间、目标点和障碍物各顶点以及各障碍物顶点与顶点之间的连线均不能穿越障碍物,也即直线是可视的。从而搜索最优路径的问题就转化为求经过这些可视直线从起始点到目标点的最短距离问题。优化算法可以删除一些不必要的连线以简化可视图,从而缩短搜索时间,求得最短路径。可视图法能够求得最短路径，但这种方法忽略了机器人的尺寸大小，使得机器人通过障碍物顶点时离障碍物太近，甚至接触，并且搜索时间长，对于N条连线的搜索时间为TN；自由空间法应用于机器人路径规划，采用预先定义的如广义锥形和凸多边形等基本形状构造自由空间，并将自由空间表示为连通图，通过搜索连通图来进行路径规划。其优点是比较灵活，起始点和目标点的改变不会造成

连通图的重构，缺点是复杂程度与障碍物的多少成正比，且有时无法获得最短路径。

栅格法将机器人工作环境分解成一系列具有二值信息的网格单元，多采用四叉树或八叉树表示工作环境[6]，并通过优化算法完成路径搜索。该法以栅格为单位记录环境信息，环境被量化成具有一定分辨率的栅格，栅格的大小直接影响着环境信息存储量的大小和规划时间的长短。栅格划分大了，环境信息存储量小，规划时间短，但分辨率下降，在密集环境下发现路径的能力减弱；栅格划分小了，环境分辨率高，在密集环境下发现路径的能力强，但环境信息存储量大，规划时间长，可以采用改进的栅格法弥补栅格法的不足。

栅格解耦法是目前研究较为广泛的路径规划方法。该方法将机器人的工作空间解耦为多个简单的区域,一般称为栅格。栅格大多采用四叉树或八叉树来表示，然后通过优化算法在栅格图中搜索一条从起始栅格到目标栅格的路径来完成路径搜索。栅格解耦法包括确切的和不确切的两种。

确切的解耦法用来描述整个自由空间,这将使复杂环境的解耦速度变慢,其原因是许多复杂的多边形可能需要与障碍物的边界相匹配。这种方法可以保证只要起始点到目标点之间存在路径,就完全能搜索到这条路径。在不确切的解耦法中,所有的栅格都是预定的形状,为了研究方便假设全部为矩形。整个图被分割成多个较大的矩形,每个矩形之间都是连续的。如果大矩形内部包含障碍物或者边界,则又被分割成4个小矩形,对所有稍大的栅格都进行这种划分,然后在划分的最后界限内形成的小栅格间重复执行程序,直到达到解的界限为止。在进行下一层更细的划分之前,应在每一层上的起始点和目标点间找到一条路径,如果该路径满足起始点到目标点间无障碍物的要求,则停止搜索。不确切的解耦方法比确切的解耦方法在数学计算上要简单的多,因此也比较容易实现。 4路径搜索算法

移动机器人路径规划的方法有很多，可以说各有优缺点。同时，随着各种新方法和新技术的不断出现，不断吸收新的理论，极大的促进了机器人足球的蓬勃发展。足球机器人在静态环境下的路径规划已经比较成熟，但是在动态环境下的全局最优路径规划方法还是不太成熟，动态环境和未知环境的路径规划一直以来都是学术界研究的一个难点和重点。

4.1Dijkstra算法

由荷兰计算机科学家艾兹格·迪科斯彻发现的。算法解决的是有向图中最短路径问题。 举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离。 Dijkstra算法可以用来找到两个城市之间的最短路径。

Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。 我们以V表示G中所有顶点的集合。 每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。 我们以E所有边的集合，而边的权重则由权重函数w: E → [0, ∞]定义。 因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。 已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。 这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。

算法描述

这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时，源点s的路径长度值被赋为0（d[s]=0）， 同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有顶点v除s外d[v]= ∞）。当算法结束时，d[v]中储存的便是从s到v的最短路径，或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路径。这条路径的长度是d[u]+w(u,v)。如果这个值比目前已知的d[v]的值要小，我们可以用新值来替代当前d[v]

中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d[u]达到它最终的值的时候没条边(u,v)都只被拓展一次。

算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。

伪码

在下面的算法中,u:=Extract_Min(Q)在在顶点集Q中搜索有最小的d[u]值的顶点u。这个顶点被从集合Q中删除并返回给用户。

1 function Dijkstra(G, w, s)

2 for each vertex v in V[G] // 初始化 3 d[v] := infinity

4 previous[v] := undefined 5 d[s] := 0 6 S := empty set

7 Q := set of all vertices

8 while Q is not an empty set // Dijstra算法主体

9 u := Extract_Min(Q) 10 S := S union {u}

11 for each edge (u,v) outgoing from u

12 if d[v] > d[u] + w(u,v) // 拓展边(u,v) 13 d[v] := d[u] + w(u,v) 14 previous[v] := u

如果我们只对在s和t之间寻找一条最短路径的话，我们可以在第9行添加条件如果满足u=t的话终止程序。

现在我们可以通过迭代来回溯出s到t的最短路径

1 S := empty sequence

2 u := t

3 while defined u 4 insert u to the beginning of S 5 u := previous[u]

现在序列S就是从s到t的最短路径的顶点集.

时间复杂度

我们可以用大O符号将Dijkstra算法的运行时间表示为边数m和顶点数n的函数。 Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q,所以搜索Q中最小元素的运算(Extract-Min(Q))只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)。

对于边数少于n2稀疏图来说，我们可以用邻接表来更有效的实现Dijkstra算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点(Extract-Min)。当用到二叉堆的时候，算法所需的时间为O((m+n)log n)，斐波纳契堆能稍微提高一些性能，让算法运行时间达到O(m + n log n)。

相关问题和算法

在Dijkstra算法的基础上作一些改动，可以扩展其功能。例如，有时希望在求得最短路径的基础上再列出一些次短的路径。为此，可先在原图上计算出最短路径，然后从图中删去该路径中的某一条边，在余下的子图中重新计算最短路径。对于原最短路径中的每一条边，均可求得一条删去该边后子图的最短路径，这些路径经排序后即为原图的一系列次短路径。 OSPF（open shortest path first, 开放最短路径优先）算法是Dijkstra算法在网络路由中的一个具体实现。

与Dijkstra算法不同，Bellman-Ford算法可用于具有负花费边的图，只要图中不存在总花费为负值且从源点 s 可达的环路（如果有这样的环路，则最短路径不存在，因为沿环路循环多次即可无限制的降低总花费）。

与最短路径问题有关的一个问题是旅行商问题(traveling salesman problem)，它要求找出通过所有顶点恰好一次且最终回到源点的最短路径。该问题是NP难的；换言之，与最短路径问题不同，旅行商问题不太可能具有多项式时间算法。

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新小学教育Dijkstra算法移动机器人路径规划的研究 全文阅读和word下载服务。