动态环境下的实时路径规划算法的研究及实现

论文摘要

路径规划的研究是机器人研究领域中的一个经典问题,贯穿了整个机器人的发展史。伴随着时代的发展,对移动机器人的路径规划发展有了新的要求。为了更好的适应实际生产生活中的需要,动态环境下的路径规划成为了路径规划研究的一个重点,热点。本文旨在研究动态环境下具有实时性和高效性的路径规划方案,提高机器人对动态环境的适应力,使得在复杂环境下依然可以准确高效的进行寻路。并对传统路径规划问题所存在的一些焦点问题进行深入研究,给出解决方案。最后通过延伸,将路径规划问题与虚拟现实数字展示平台相结合,对当前游戏中的一些应用加以分析并实现。本文的研究方法是从一般到特殊,从大体概括到深入探讨,从基本理论到扩展延伸。首先从发展背景开始,介绍了路径规划问题国内外已有的研究成果,从全局路径规划和局部路径规划对路径规划问题进行分类,分别列举说明。再从智能路径规划和传统路径规划的角度粗略介绍几类应用广泛的方案。着重介绍了人工势场法,蚁群算法和粒子群算法,以及游戏中常用的A*算法。最后结合三维数字仿真平台进行相关演示。本文的主要成果及创新点有以下几点:1)基于三维数字展示平台,实现了群体全局路径规划以及局部避障策略;2)提出将A*算法与矢量法相结合的方法,减少了A*算法启发式搜索的复杂度,一定程度上解决了因距离增加而效率急剧下降的问题。并结合滚动窗口法给出A*算法的实现;3)在蚁群算法的基础上提出基于回退法的遗传算法与蚁群算法相结合的算法,很好的解决了蚁群算法存在的“死锁”问题,克服了局部最优问题;4)提出动态编程下的AI,将脚本技术与AI智能相关进行结合,通过实践,完成智能个体从起点到终点响应AI触发条件的寻路;最后针对本文一些研究的难点盲点,提出对路径规划问题未来的展望,以便为后来的研究带来新的思维和启示。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 路径规划问题的发展概况及现状
• 1.1.1 传统路径规划问题综述
• 1.1.2 衍生路径规划问题综述
• 1.2 智能机器人路径规划的初步探讨
• 1.2.1 全局路径规划
• 1.2.2 局部路径规划
• 1.3 路径规划的研究现状以及发展趋势
• 1.4 本论文的选题和主要内容
• 第二章 动态环境下的路径规划
• 2.1 动态虚拟环境
• 2.2 人工势场法
• 2.2.1 动态人工势场法
• 2.2.2 局部最小值问题
• 2.3 蚁群算法
• 2.3.1 蚁群算法模型与原理
• 2.3.2 基于栅格法的蚁群算法
• 2.3.3 基于交叉变异的蚁群算法
• 2.3.4 蚁群算法的“死锁”现象
• 2.3.5 回退法策略
• 2.3.6 动态环境下的蚁群算法
• 2.4 粒子群算法
• 2.4.1 基本粒子群算法
• 2.4.2 粒子群算法的改进
• 2.5 智能路径规划算法的分析与比较
• 2.6 本章总结
• 第三章 寻径算法的探讨及实现
• 3.1 百花齐放的寻径算法
• 3.2 寻径算法的判优
• 3.3 A*算法及其改进
• 3.3.1 A*算法简介
• 3.3.2 A*算法的深入探讨
• 3.3.3 基于A*的矢量寻路法
• 3.3.4 基于A*的矢量寻路算法描述
• 3.4 本章小结
• 第四章 虚拟游戏场景中的实际应用
• 4.1 滚动窗口下的自动寻路
• 4.1.1 滚动窗口路径规划
• 4.1.2 滚动窗口下的自动寻路仿真
• 4.2 三维虚拟场景中的群体动画及避障
• 4.2.1 动态环境下智能群体路径规划
• 4.2.2 数字展示平台下的群体动画仿真
• 4.3 动态编程下的AI 智能
• 4.3.1 动态脚本语言
• 4.3.2 动态脚本AI 智能的实现
• 4.4 本章小结
• 第五章 总结与展望
• 5.1 论文总结
• 5.2 创新点和主要工作
• 5.3 工作展望
• 致谢
• 参考文献
• 攻硕期间取得的研究成果