移动机器人路径规划技术研究(3)

狭窄的通道时 ,传统的 PRM 方法的效率变的低下 ,后来提出了一种采用分阶段混合采样策略的改进的 PRM 法 ,有效的解决了这一问题. 2. 5 拓扑法

拓扑法是由清华大学研究者提出的一种路径规划算法. 其基本思想是先将规划空间分为自由空间、半自由空间和障碍空间的子空间 ,然后搜索每个子空间及与其相连的子空间 ,计算彼此之间的连通性 ,如此则建立了拓扑网络. 路径规划是在拓扑网络上搜索从起始点到目标点的最短的路径 ,即判断拓扑网络的连通性 ,从而大大减小了高维空间路径规划的难度. 用拓扑法进行路径规划 ,一般不需要移动机器人的准确位置 ,这对于机器人移动过程中产生的位姿误差有很好的包容能力 ,但建立拓扑网略的过程非常复杂 ,特别是当空间中障碍物发生改变时 ,拓扑网的重构问题有待解决.

3 局部路径规划

局部路径规划 ,又称为动态或在线路径规划 ,作业环境部分未知或完全未知 ,主要方法有:人工势场法、模糊逻辑算法、遗传算法、蚁群算法、免疫算法等. 3. 1 人工势场法

人工势场法[10]是由 Khatib 和 Krogh 提出的一种虚拟力场法. 它的基本思想是将移动机器人所处的空间虚拟称一个存在力的场地 ,并且把这种力分为引力和斥力 ,移动机器人所受的引力是由目标点产生的 ,随距离的增大而减小 ,斥力是由障碍物产生的 ,并随距离的减小而增大 ,整个势场是引力和斥力的矢量叠加. 机器人沿着“势峰”间的“势谷”前进 ,从而绕过障碍物到达目标点. 人工势场法结构简单 ,便于底层的实时控制 ,且无需大量的计算 ,自动生成较光滑的路径 ,在实时避障和平滑轨迹控制方面得到了广泛的应用 ,但也存在着以下几个方面的缺陷:存在陷阱区域;通过狭窄通道时摆动;在障碍物前震荡;动态环境适应性差;求出的路径可能不是最优路径. 为了克服上述缺陷 ,已经研

究出了一些改进方法 ,如重新定义势函数 ,减少或使之没有局部极小点;在局部极小点处引入一个“填平势场”来引导移动机器人走出局部极小点;还可以利用如模拟退火法、遗传算法、粒子群算法等搜索算法跳出局部极小点 .

3. 2 模糊逻辑算法

模糊逻辑算法是根据经验 ,通过查表来得到规划信息 ,实现局部路径规划. 由于模糊逻辑算法基于实施传感信息 ,在处理动态变化或者未知环境下的路径规划问题显示出巨大的优越性 ,具有较好的实时性 ,且克服了势场法容易产生局部极小值的问题 ,避开了传统算法中对环境信息依赖强的缺点 ,但对于模糊隶属函数以及模糊控制规则的设计 ,目前还没有系统的理论方法 ,主要靠经验 ,因此隶属函数和控制规则的设计成为实现模糊逻辑算法的关键.

3. 3 遗传算法

遗传算法是一种基于自然选择和群体遗传机理的搜索算法 ,它基于达尔文“物竞天择 ,适者生存”的进化原理 ,模拟了自然界的生存法则. 遗传算法是一种全局优化算法 ,其算法流程是:首先初始化路径种群 ,将路径个体表述为路径上一系列的点 ,并进行参数编码;然后对参数编码的字符串采用抽象出来的几个算子进行选择、复制、交叉、变异遗传操作;经过特定进化次数或者达到优化目标即停止进化 ,输出当前优的个体.遗传算法主要的优点是:

1)遗传算法是一种多线程的搜索算法 ,可同时对多个可行解进行遗传操作 ,从而产生新的可行解 ,一定程度上避免了陷入局部极小点.

2)整体搜索策略和优化计算不依赖于梯度信息 ,只需可行解目标函数的值 ,因而解决了一些其他优化算法无法解决的问题 ,避免了复杂的理论推导.遗传算法是一种多线程的搜索算法 ,可同时对多个可行解进行遗传操作. 文献[17]给出了一种基于粗糙集约简决策规则和删除冗余属性的方法 ,大大减小了遗传算法初始种群的规模 ,提高了规划效率.