基于环境二次划分的移动机器人路径规划新算法研究

摘要

移动机器人路径规划是机器人研究领域最基本的环节之一,包括环境建模和路径搜索两个子问题。常见的栅格法由于其计算简单,易于实现和维护,已被广泛的应用于路径规划的环境建模中,但栅格粒度难以控制的缺陷一直未能得到很好的解决,为此,本文提出了以障碍物为启发信息对环境进行二次划分的栅格建模方法,较好的解决了这一问题。
　　 由于遗传算法对问题的种类有很强的鲁棒性,因此被成功的应用于求解全局已知的路径规划问题。然而传统遗传算法随机生成初始种群导致其有效性和遍历性差,同时遗传算法收敛速度慢的固有缺陷也影响规划的性能。为此,本文利用环境二次划分方法为路径搜索算法提供了优秀的环境模型；提出了以显性基因的保险矩阵为启发信息产生初始种群的新方法,提高了初始种群在搜索空间的有效性和遍历性；同时将保险矩阵作为环境知识构造适应度函数和相关遗传算子,克服了遗传算法收敛速度慢的问题,提高了路径规划的效率。计算机仿真实验结果表明,即使是在有陷阱等复杂障碍物的环境下,用本算法也能获得最优路径,与已有的同类代表性算法相比,收敛速度显著提高,效果令人满意。
　　 滚动规划是解决感知环境路径规划的经典算法,但局部路径中的多数节点在新窗口中被视为无效节点的规划策略,不仅浪费了存储空间,而且也影响了规划的实时性；另外,由于机器人视野域范围的有限性可能导致规划停滞。为此,本文提出了一种基于高质量节点和窗口转向机制的机器人滚动规划新方法。该方法对局部环境进行二次划分,为路径搜索算法提供了优秀的建模环境；搜索算法对视野域内节点从距离长短、安全程度、陷入陷阱障碍物的可能性角度进行评价并以质量值表示,选择质量值高的节点替代局部路径的完整规划,实现了当前最优选择和对陷阱障碍物预判的合理结合,在保证成功规划的同时解决了局部路径节点有效性差的问题；同时给出窗口转向新策略,解决了规划过程中由于视野域范围有限而造成的停滞现象。计算机仿真实验结果表明,该算法规划速度快,能有效的解决规划的停滞问题,是一种提高滚动规划算法实时性和有效性的方法。