按照机器人对环境信息掌握的程度不同可将路径规划分为两类：基于环境先验完全信息的全局路径规划和基于传感器信息的局部路径规划。

1 全局路径规划算法

（1）拓扑法[4,5]

早在20世纪80年代，现中科院院士张钹教授就提出用状态空间的连通性分析来解决路径规划问题，它根据环境和运动物体的几何特点，将组成空间划分为若干区域，这些区域要求拓扑特征一致，根据彼此间的连通性建立一个拓扑网，在该图中搜索一条拓扑路径。拓扑路径的规划方法是以降维法为主要依据，就是将高维的复杂的空间几何路径求法转化为低维的比较简单的拓扑空间的辨别连通方法。这种方法的优点在于利用拓扑特征极大地缩小了搜索空间，其算法的复杂性仅与障碍物的数目有较大关系；缺点在于表示的复杂特殊性，建立拓扑网的过程相当复杂费时。在障碍物数量增加时，如何采取合理措施对拓扑网络进行修正也是亟待解决的问题。91667

（2）栅格法[4,5]

栅格法是将机器人工作的环境信息进行划分，用尺寸相同的栅格进行描述，栅格的大小以机器人自身的尺寸为准，而且机器人工作的空间内，障碍物的位置和大小保持不变。若某个栅格范围内不含任何障碍物，则称此栅格为自由栅格；反之，称作障碍栅格。自由空间和障碍物都是由栅格块表示，对障碍物和栅格有两种标记方式：直角坐标法和序号法。一般情况下，机器人工作的环境是采用四叉树或八叉树表示，栅格的一致性和规范性使得栅格空间中邻接关系的简单化。赋予每个栅格一个通行因子后，路径规划问题就变成在栅格网上寻求两个栅格节点间的最优路径问题。栅格法将环境量化成具有一定分辨率的栅格后，栅格的大小直接影响着环境信息的存储量和规划时间。栅格划分越小可以更精确地表示障碍物，但这样会使环境信息存储量增大，规划时间加长。栅格划分大时，环境信息存储量小，规划时间短，但路径的规划就不会精确。

（3）可视图法[4]

可视图法是把机器人看做一个点，然后进行合理的组合，并且将机器人与目标点、多边形障碍物各顶点相互连接。在连接的过程中，需要保证直线的可视，也就是目标点与多边形障碍物各顶点的连线和各个多边形障碍物顶点相互之间的连线不能够穿越障碍物。通过这样的方式能有效地将搜索最优路径转化成由起点到目标点间的可视直线最短距离。这种方法的好处就是能够有效地缩短路径，但在计算上忽视了机器人自身的尺寸，这在实际运行中，当机器人经过障碍物时，很容易与障碍物的距离过近或发生触碰，从而延长搜索时间。这种情况是不可控的。适当应用切线图和Voronoi图能够对可视图的方法进行完善。切线图是使用弧来表示障碍物的切线，可以使机器人从起点到目标点按最短路径运行时只接近障碍物而不会触碰到障碍物。但这个方法也存在不足，如果在控制过程中位置设置出现了偏差，便会使机器人和障碍物发生触碰。Voronoi图的原理是使用远离障碍物的路径表示弧，这种方法会使路径距离增加，位置的误差也随之增大，但同时也会减小机器人和障碍物发生触碰的概率。

（4）自由空间法[5]

自由空间法用预先定义的多边形和广义锥形等基本形状构建自由空间，并将自由空间表示成连通图，然后通过搜索连通图进行路径规划。其构造方法是：从障碍物的一个顶点开始，依次作其他顶点的链接线，删除不必要的链接线，使链接线和障碍物边界围成的每个自由空间都是面积最大的凸多边形；连接各链接线的中点而形成的网络图就是机器人可自由运动的路线。这种方法比较灵活，如果起始点和目标点的改变，连通图也不会重构，但是算法的复杂程度与障碍物的数量成正比，而且不是任何情况下都能获得最短路径。