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

论文摘要

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

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景及意义
• 1.2 机器人路径规划国内外研究现状
• 1.3 本文的研究内容和创新之处
• 1.3.1 研究内容
• 1.3.2 创新之处
• 1.4 论文的组织结构
• 第2章 基于栅格法的环境建模
• 2.1 常用建模方法
• 2.2 栅格法
• 2.2.1 栅格法描述
• 2.2.2 栅格法在路径规划中的应用
• 2.3 本章小结
• 第3章 基于遗传算法的机器人路径规划
• 3.1 遗传算法简介
• 3.1.1 基本原理
• 3.1.2 遗传算法的特点
• 3.2 基于遗传算法的路径规划算法
• 3.2.1 基本思想
• 3.2.2 基于遗传算法路径规划流程及实现
• 3.2.3 算法具体步骤
• 3.2.4 局限性分析
• 3.3 本章小结
• 第4章 基于环境二次划分的栅格建模方法
• 4.1 环境划分结果及其分析
• 4.2 环境二次划分
• 4.2.1 二次划分策略
• 4.2.2 二次划分步骤
• 4.3 本章小结
• 第5章 基于环境二次划分和改进遗传算法的机器人路径规划
• 5.1 环境描述及相关定义
• 5.2 基于环境二次划分和改进遗传算法的路径规划
• 5.2.1 算法策略
• 5.2.2 个体编码策略
• 5.2.3 基于保险矩阵的种群初始化方法
• 5.2.4 适应度函数
• 5.2.5 遗传操作算子
• 5.2.6 算法步骤
• 5.3 仿真实验
• 5.3.1 实验结果
• 5.3.2 实验分析
• 5.4 本章小结
• 第6章 基于环境二次划分的机器人滚动规划算法
• 6.1 基于滚动窗口路径规划的基本思想
• 6.2 环境描述及相关定义
• 6.3 基于改进滚动窗口策略的路径规划算法
• 6.3.1 算法策略
• 6.3.2 虚拟子目标的确定
• 6.3.3 基于高质量节点的滚动规划算法步骤
• 6.3.4 窗口转向机制
• 6.4 仿真实验
• 6.4.1 实验结果
• 6.4.2 实验分析
• 6.5 本章小结
• 第7章 总结与展望
• 7.1 论文的主要工作
• 7.2 研究工作的展望
• 参考文献
• 致谢
• 附录