matlab移动传感器网络的持续覆盖研究(4)

菜单

一个好的路径规划方法需要满足下列指标：

1.合理性：返回的任何路径都是合理的, 即任何路径对控制机器人运动都是可执行的；

2.完备性：如果客观上存在一条从起点到达终点的无碰路径, 该算法一定能找到; 如果环境中没有路径可通行, 会报告规划失败；

3.最优性：算法规划的结果路径在某个测度(如时间、距离、能量消耗等)上是最优的；

4.实时性：规划算法的复杂度(时间需求、存储需求等)能满足机器人运动的需要；

5.环境变化适应性：算法具有适应环境动态改变的能力, 随着环境改变, 不必全部重新计算。更加快速适应新的环境；

6.满足约束：支持移动机器人运动时的完整性和非完整性运动约束[1]。

2．1 全局路径规划

全局路径规划就是已知全局环境的一种规划从起点到终点最短的路径的一种算法。其中包括环境建模和路径搜索策略两个子问题。其中环境建模的主要方法有可视图法自由空间法和栅格法等[20]。

2.1.1 可视图法

可视图法就是将移动机器人看做一点，将机器人目标点和多边形障碍物的各顶点进行连接，并保证这些直线均不与障碍物相交，这就形成了一张网络图，称为可视图。

由于任意线段的顶点都是连接在同一网络上的，从起点沿着这些线段到达目标点的所有路径都是运动物体理论上的无碰可行的路径。搜索最优路径的问题就转化为从起点到目标点，经过这些可视线段的最短距离问题。运用优化算法可以删除一些不必要的连线，可简化可视图，以缩短搜索时间。

该法在大多数情况下可以求得最短路径，但该假设忽略了移动机器人的体积大小，使得机器人经过障碍物顶点时，离障碍物太近甚至接触，并且搜索路径需要的时间长[2]。

这种方法很有可能与障碍物产生碰撞，而且很难得到最优的路径。

对于该法还有其他衍生的种类，如切线图法、Voronoi图法。

切线图，用障碍物的切线表示路径，因此可以得到从起始点到目标点的最短路径的联通图，因此移动机器人必须接近障碍物行走，其缺点是如果控制过程中产生位置误差，移动机器人发生碰撞的可能性会很高。

Voronoi图法，用尽可能远离障碍物和墙壁的线段表示路径。但是，从起始节点到目标节点的路径将会增长，好处是采用这种控制方式时，即使产生位置误差移动机器人也不会发生碰撞。

总的来数说，可视图法是相当简洁直接的路径规划方法，但是缺点也很明显。

2.1.2 拓扑法

拓扑法把地图分割成具有拓扑特征的子空间，根据彼此连通性建立拓扑网络，在网络中寻找起始点到目标点的拓扑路径，最后由拓扑路径求出几何路径。

拓扑法基本思想是降维法，就是把在高维几何空间中求路径的问题转化成为低维拓扑空间里判别连通性的问题。

优点在于利用拓扑特征大大缩小了搜索路径的算法复杂性，仅依赖于障碍物数目，且理论上是完备的，而且拓扑法通常不需要机器人的准确位置，对于位置误差带来的影响也就有了很好的抗性。

缺点是建立拓扑网络的过相当复杂，尤其是在增加障碍物时，如何有效地修改已经存在的拓扑网络还是待解决的问题。

2.1.3 栅格法

栅格法把移动机器人所在的地图分解成一系列具有二值信息的网格单元，用四叉树或八叉树来表示，并通过优化算法完成路径的搜索。

该法以栅格为单位，地图上有障碍物的地方累积值比较高，移动机器人就会采用优化算法避开地图上被量化成具有一定分辨率的栅格，栅格大小直接影响地图信息存储量大小和路径规划时间长短，栅格划分大了地图信息存储量小，路径规划时间短，但分辨率下降，在有密集障碍物的区域中发现路径的能力减弱。格划分小了地图分辨率高在密集的环境下发现路径的能力强，但地图信息存储量大，路径规划时间长。文献综述