毕业论文移动版

深度优先搜索法于宽度优先搜索法比较相似，只不过宽度优先的Open表采用的是先进先出的队列，而深度优先的Open表采用的是先进后出的堆栈。

等代价搜索法也有一个Open表，开始时Open表中只有起始节点。每次从Open表中取出代价最小的节点，放入Closed表中，判断该节点是否为目标节点，如果是目标节点，则搜索结束；否则计算该节点的所有子节点的代价，并将所有子节点放入Open表之中。如果Open表为空，则没有解，搜索结束。文献综述

A算法考虑的是已走过的路径和距离目标节点的路的总代价。g(n)为当前走过路径的代价，h(n)为估价函数，估计节点n到目标节点的路径代价。按照如下公式，可以得出当前路径的代价估计，其中h(n)也被叫做启发函数。

在Open表中，按照f(n)的大小进行排序，选取最小的节点进行扩展，这就是A算法的基本思想。

1.3.2  基于RoadMap的方法

基于RoadMap的方法包括可视图法和Voronoi图法等。

图1.2 可视图

可视图法从1987年就被广泛应用于移动机器人寻路。在C空间中，障碍物用多边形来表示，用直线将起始点和所有C空间障碍物的顶点以及目标点相连，并且这些直线不与障碍物相交，所形成的图就是可视图。然后利用图搜索算法来找寻最优路径。

Voronoi图法用尽可能远离障碍物的路径表示弧，将起始点和目标点连起来。然后利用图搜索法来寻找最优路径。这种方法生成的路径可能不是最优路径，但是生成的路径比较安全，即使移动机器人在移动的时候产生误差，也不会碰到障碍物。并且生成的路径比较平滑，更加合理。

图1.3 Voronoi图

1.3.3  栅格法

栅格法是目前研究最广泛采用的路径规划方法之一[3]。该方法将地图分解为多个简单的区域，即栅格。由这些栅格构成一个显式的连通图，或在搜索过程中形成隐式的连通图，然后在图上搜索一条从起始栅格到目标栅格的路径[4]。按照划分方式，栅格法可以分为确切的栅格法和不确切的栅格法。

确切的栅格法[5]将机器人工作环境分解成一系列固定大小的栅格单元，环境被量化为具有一定分辨率的栅格序列。路径规划问题被转变为了寻找起始栅格和目标栅格之间最优路径的问题。确切的栅格法中，分辨率是很重要的因素，它直接影响着栅格地图的大小和路径规划的速度。来.自/优尔论|文-网www.youerw.com/

在不确切的栅格法[6]中，所有的栅格都是预定的形状，通常为矩形。如果矩形之中包含障碍物或者边界，则将矩形再次划分为四个小矩形，重复这个过程。这种分解结构称为“四叉树”，CMU已经将这种不确切的栅格法用于越野环境下的自主地面车导航，取得了很好的效果[7]。