图搜索法通过利用已有的环境地图和版图中的障碍物等数据信息建立，由起点至结束点的可行路线。一般分为深度最优和广度最优二种走向。深度优先算法优先拓展搜索深度较大的节点，因此能够更迅速的获得下一个可行路径，不过深度优先算法获取的第一个路径通常是比较长的路径。而广度优先算法则优先拓展深入较小的节点，呈波形的检索方式。因此广度优先算法检索到的第一个路径通常是最短路径。

可视图法

可视图法是由Lozano-PErEz和WESlEy于1979年所创立的，是机器人全局运动计划中的典型算法。在视野法中，机器人用点来表示，阻碍物用多角形表示。把起始点S、目标点G，以及多角形阻碍物的所有顶点（设V零是各个阻碍物的顶端组成的整体）进行了综合联系，并规定起始点和阻碍物各顶部相互之间、目标点与阻碍物各顶部相互之间和各个阻碍物顶部和顶端相互之间的连接都不得通过阻碍物，即直线是"可视的"。给图中的所有边赋值，然后建立了可视地图G（V，E），并且点集V=∪{S，G}，E为每个弧段中即可视边的总和。然后釆如果用一些优化计算就找到了从开始点S到目标点G的最优预测路径，那么再经过累加并对比上述直线的距离就可以得出了从开始点到目标点的到V路径，如图所示。

因此看来，用视图法规定的避障路线重点就是建立可视图，而建立可视图的关键性问题则就是对障碍物各个顶点清晰度的确定。判断时大致包括以下二个情况，相同障碍物中间各节点间能见度的判断和各个障碍物中间顶点可见性的判断。

可视图法虽然能获得较短路线，但搜索时长过久，而且没有灵敏度，亦即一旦自动化机器人的起始点和目标地点都出现了变化，就需要重新建立可视图，相当困难。所以可视野法更适用于多边形障碍物，对圆障碍物则没有。切线图法和Voronoi图法^[12]对可视野法做出了改良。切线图法用障碍物的切线代表圆弧，所以从开始点到目标地点的最短路线的图，移动机器人需要基本完全贴近障碍物进行。其缺陷是一旦在进行监控流程中出现了位置误差，则自动机器人撞击障碍物的概率将会非常高。而Voronoi图法用尽量避开障碍物和墙壁的路线代表圆弧。这样，从启动点到目标地点的路程就会增加，在使用这个操控方法之后，虽然形成了位置误差，但移动机器人却并没有遇到障碍物。

 Dijkstra算法

Dijkstra计算由荷兰最著名的计算机物理学家艾兹赫尔.戴克斯特拉（Edsger Wybe Dijkstra）给出，通过预测从初始点至空间中任意一个点的最短距离，使其能够获取全局最佳路径。计算从开始站出发的附近4或8个站点至新开始站点的路程，然后再将新算距离的最后一点作为计算节点，计算从附近一点至新开始站点的路程，这个计算就像波阵面一样在整个距离里传输，直至抵达目标地点。这就能够算得到机器人的最短时间路程。

Dijkstra算法是一个典型的广度最大化的状态空间搜索算法，该算法能够从起始位置出发逐层一层的寻找整个自由空间，直至最后抵达目标地点。这会增加运算时间和数据量。而另一方面，依靠搜索而得到的大量数据对于机器人驾驶者来说又是毫无意义的。

Dijkstra算法所使用的正是这个贪心的方式，表示了一些数组dis来保持源点和所有节点间的最短时间，还有一组保持那些已经得到了最短路线的所有节点的集合:T。

初始化时，每个经过原点s的路径权重均被赋为0（dis[s]=0）。假定在一个顶角s有可以径直到达的所有边（s，m），则把dis[m]设为w（s，m），并且把任何任何（s无法径直抵达的）边的路径宽度均定为无穷大。在起始时间，集合T中存在顶角s。

然后，如果在dis数组选取最低位，那么这个数值就是在源点s和该值所相应的顶点之间的最短路线，同时将该点加入到T中，就OK了，此时就是一个顶点的完成。

接着，要查看自己新增加的节点是不是能够抵达其他节点，并且看看使用这个节点抵达其他点的路线距离是不是比从源点直接抵达还要短，要是有，那就需要更换这个节点在dis上的位置。

接着，再在dis中寻找最小值，并重复以上动作，直至T中包含出图的全部顶点。

A Star算法

为克服Dijkstra计算效能低下的问题，A Star计算作为一种启发式计算被引入。该计算在广度优先的基石上增加了一种估价函数。

Astar计算的核心问题就在估价函数的设计上，如下式所示:

F（n）= g（n）+ h（n）

当中g（n）为时间耗散函式，代表了从开始结点nstart到终止节点n的真实代价；H（n）又称启发函数，指示节点n到目标节点ngoal的估算价格；f（n）则指出由初始化节点经由目的节点n至目标节点的估算价格付出代价。

和Dijkstra计算相似，Astar计算也维持了一个Open列表。在Open表中节点的优先权是按照f（n）的多少来排序的，f（n）值越小，被检索到的优先权也就越高。为确保能获得最佳值，启发函数的h（n）不宜太大，不宜超过节点n到目标节点的现实付出代价；一旦h（n）=0，则可使Astar计算退化成Dijkstra计算，尽管其能提供最佳途径，但计算效率却依然较差；假设h（n）值正好小于节点n到目标节点的现实付出代价，则Astar计算所寻找的目标结点就正好是在最优预测路线上的目标节点。所以h（n）的取值影响计算的速率和准确性，常见的的取值有二点中间的欧几里得距离（Euclidean Distance）和曼哈顿间距（Manhattan Distance）等，如图所示。