基于正反馈遗传算法的新型机器人路径规划方法

论文摘要

根据对环境信息掌握程度的不同,移动机器人路径规划可分为环境信息完全已知的离线全局路径规划和环境信息完全未知或部分未知的在线局部路径规划。遗传算法由于具有并行性及全局搜索能力强等特点,被引入到路径规划之中,但这些应用多采用栅格法及可视图法对环境建模,前者栅格大小难以控制,后者建模过程复杂,且对障碍物的依赖性较强,加之遗传算法的收敛速度较慢,致使路径规划的效率并不高。为此,根据遗传算法的特点,研究了一种新型的建模方法,该方法依据机器人出发点、目标点位置建立起新的坐标空间,染色体各基因位于机器人出发点及目标点连线的各等分点的垂线上,具有过程简单、容易实现的特点。为解决算法收敛速度慢的问题,借鉴蚁群算法的思想,将正反馈机制引入到遗传算法中,用一个二维矩阵记录整个环境的累积值信息,使位于累积值高的区域的基因以较低的概率参加交叉及变异运算,以使个体中的优良基因段以较高的概率遗传到下一代。仿真实验显示了此算法能够提高全局路径规划的收敛速度,且获得较优化的解。为了解决这一新建模方法使染色体各基因只能位于起始点至目标点连线各等分点的垂线上,从而可能影响某些更优路径的获得的问题,在正反馈遗传算法中,引入新型的遗传算子——添加结点算子及删除结点算子,使染色体的各基因不再仅位于起始点至目标点连线各等分点的垂线上。之后,借鉴预测控制的基本原理,结合滚动窗口法,将改进型正反馈遗传算法应用于局部路径规划当中,实现未知环境下的路径规划。最后的仿真实验显示无论在静态未知环境中还是在动态未知环境中,改进型正反馈遗传算法均能获得较优化的解。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景及意义
• 1.2 国内外研究现状
• 1.2.1 基于遗传算法的机器人路径规划
• 1.2.2 其他路径规划方法
• 1.2.3 机器人路径规划难点及发展趋势
• 1.3 本文解决的主要问题与研究内容
• 1.3.1 新型建模方法的研究
• 1.3.2 基于正反馈遗传算法的全局路径规划
• 1.3.3 改进型正反馈遗传算法的滚动路径规划
• 1.4 本课题的主要创新点
• 1.5 文章的组织结构
• 本章小结
• 第二章 基于遗传算法的机器人路径规划
• 2.1 遗传算法简介
• 2.1.1 基本原理
• 2.1.2 工作流程及实现
• 2.1.3 基本特征
• 2.2 基于遗传算法的机器人路径规划
• 2.2.1 基本思想
• 2.2.2 算法步骤
• 2.2.3 存在的主要问题及解决方向
• 本章小结
• 第三章 正反馈遗传算法路径规划
• 3.1 环境建模
• 3.2 正反馈遗传算法的基本原理
• 3.2.1 蚁群算法的正反馈思想
• 3.2.2 正反馈遗传算法的基本原理
• 3.3 基于正反馈遗传算法的路径规划
• 3.4 仿真实验
• 3.4.1 实验过程
• 3.4.2 参数选择与结果分析
• 3.5 U形大障碍物的处理
• 本章小结
• 第四章 改进型正反馈遗传算法路径规划
• 4.1 新型遗传算子的引入
• 4.2 改进型正反馈遗传算法全局路径规划
• 4.2.1 需要说明的两个问题
• 4.2.2 改进型正反馈遗传算法全局路径规划的实现
• 4.3 改进型正反馈遗传算法局部路径规划
• 4.3.1 滚动窗口方法概述
• 4.3.2 滚动路径规划的相关定义及其基本过程
• 4.3.3 滚动路径规划的具体实现
• 4.4 仿真实验
• 4.4.1 静态环境仿真
• 4.4.2 动态环境仿真
• 本章小结
• 第五章 总结
• 参考文献
• 附录1: 致谢
• 附录2: 科研情况