基于蚁群算法的路径规划研究

论文摘要

路径规划技术已经被广泛应用于飞行器、水面舰艇、地面车辆以及机器人等导航系统。目前求解路径规划问题的主要方法有A*算法、遗传算法、人工势能场、神经网络、计算几何方法等。蚁群算法是模拟蚂蚁觅食过程的一种仿生方法，将蚁群算法用于求解路径规划问题，近年来引起了国内外研究学者的广泛关注，也取得了一定的研究成果。基本蚁群算法用于机器人路径规划容易出现早熟收敛，工作环境中障碍物分布密集时有可能规划不出合理的路径，在稀疏的连续环境下容易出现迂回搜索从而得不到最优路径。针对上述缺点，本文在基本蚁群算法的基础上提出了如下改进策略，以提高算法性能：（1）结合双蚁群算法和最大最小蚂蚁算法思想，对距离启发因子进行改进，增强目标点对蚂蚁的引导作用，避免迂回搜索；利用进化代数动态调整启发式系数α，β和信息素挥发系数ρ，避免由于信息素的决定性作用使得进化后期出现早熟收敛；（2）利用终点距离信息初始化环境信息素以避免进化早期的盲目搜索，对不可行路径上的信息素进行分段线性调整并结合路径点回退策略以避免再次产生不可行路径，对状态转移概率排序并利用轮盘赌概率性选择路径点以提高算法的全局寻优能力。利用Visual C++6.0开发二维平面路径规划的实验仿真平台，在该平台上对本文算法与基本蚁群算法和其他改进蚁群算法进行仿真测试和性能比较。仿真结果表明，与同类算法相比，本文算法在运算时间和解的质量上都有较大程度的改善，表明了改进策略的有效性和可行性。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 本课题研究背景及意义
• 1.2 国内外研究现状
• 1.2.1 主要的环境建模方法
• 1.2.2 主要的路径规划算法
• 1.3 本论文的研究的主要内容
• 1.4 论文内容安排
• 1.5 本章小结
• 第二章 基本蚁群算法
• 2.1 基本蚁群算法的原理
• 2.1.1 蚁群行为描述
• 2.1.2 蚁群算法的基本原理
• 2.2 基本蚁群算法的数学模型
• 2.3 基本蚁群算法的性能评价
• 2.4 改进的蚁群算法
• 2.4.1 带精英策略的蚁群算法
• 2.4.2 蚁群系统（Ant Colony System）
• 2.4.3 最大—最小蚂蚁系统（Max-Min Ant System, MMAS）
• 2.5 蚁群算法的应用
• 2.6 本章小结
• 第三章 基于改进双蚁群算法的机器人路径规划
• 3.1 路径规划问题的环境表示
• 3.2 问题描述
• 3.2.1 环境描述
• 3.2.2 路径规划问题
• 3.3 基本蚁群算法用于路径规划的原理
• 3.3.1 节点选择规则
• 3.3.2 信息素更新规则
• 3.3.3 单蚁群算法的算法步骤
• 3.4 改进策略
• 3.4.1 改进启发式因子
• 3.4.2 信息素更新
• 3.4.3 权值系数 α 和 β 动态调整
• 3.4.4 挥发系数动态调整
• 3.5 双蚁群算法的步骤
• 3.6 仿真结果分析
• 3.6.1 仿真实例和参数设定
• 3.6.2 仿真结果与性能比较
• 3.7 本章小结
• 第四章 复杂环境下基于改进的蚁群算法机器人路径规划
• 4.1 基本蚁群算法的原理
• 4.1.1 节点选择规则
• 4.1.2 信息素更新规则
• 4.2 蚁群算法改进策略
• 4.2.1 距离启发因子的改进
• 4.2.2 基于排序的最优性选择下一个路径栅格
• 4.2.3 信息素初始化的改进
• 4.2.4 不可行路径信息更新规则
• 4.3 蚂蚁回退策略
• 4.4 改进算法步骤
• 4.5 仿真结果分析
• 4.5.1 仿真实例和参数设定
• 4.5.2 仿真结果与性能比较
• 4.6 本章小结
• 第5章 总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 攻读硕士学位期间论文发表和参加科研的项目情况
• 致谢