基于粒子群算法的移动机器人路径规划
目 录
摘要 I
Abstract II
1 引言 1
1.1 课题背景及意义 1
1.2 主要研究内容及关键问题 3
1.3 论文结构 3
2 机器人路径规划概述 5
2.1 路径规划的定义 5
2.2 路径规划问题的分类 5
2.3 环境建模 6
2.3.1 可视图法 6
2.3.2 栅格法 7
3 粒子群算法概述 8
3.1 粒子群算法的基本原理 8
3.2 基本粒子群算法的数学模型 9
3.2.1 对粒子个体的抽象 9
3.2.2 问题空间的描述 10
3.2.3 寻找路径的抽象 10
3.2.4 信息素挥发的抽象 10
3.2.5 启发因子的引入 10
4 基于粒子群算法的机器人路径规划 12
4.1 环境建模 12
4.2 算法的描述 13
4.3 算法的步骤 14
5 仿真实验及结果分析 17
5.1 仿真实验 17
5.2 结果分析 18
6 结束语 21
参考文献 22
致谢 23
1.2 主要研究内容及关键问题
本课题对已知的全局静态环境进行场景建模的基础上,重点研究了用于机器人全局路径规划的智能粒子群算法,为机器人寻找一条从给定的起始点到目标点的满足一定优化指标的无碰撞路径,并在此基础上,用Matlab软件进行仿真实验,验证算法的有效性和优良性能。
本课题拟解决的关键问题:
1)环境建模:采用何种方法对机器人工作环境进行建模,建立一个便于计算机进行路径规划使用的环境模型,即将机器人实际工作的物理空间抽象成算法能够处理的抽象空间;
2)路径搜索:如何应用粒子群算法编写程序,并结合信息素更新策略,以及考虑在路径搜索阶段避免陷入局部最优解等问题,更好地规划出一条无碰撞、最优路径。
1.3 论文结构
本文的主要结构如下:
第1章:阐述了本课题的背景及意义,比较了目前常用的路径规划算法,并提出基于粒子群算法对机器人路径进行规划的问题。
第2章:描述机器人路径规划的问题,介绍了机器人工作环境的建模方法。
第3章:概述粒子群算法,介绍其基本原理和工作流程,并描述了算法的数学模型。
第4章:针对前面对路径规划问题与粒子群算法的研究,将粒子群算法引入到移动机器人的路径规划中,采用栅格法对环境进行建模,并描述算法的实施步骤。
第5章:编写程序对其进行仿真实验,并分析实验结果。
第6章:对全文进行总结,给出下一步研究方向。
2.3 环境建模
环境建模的目的是建立一个便于计算机进行路径规划使用的环境模型。环境建模是机器人路径规划的重要环节,采取何种规划方法建模由环境信息的完备程度以及环境模型的形式决定,比如,机器人所处环境中障碍物的几何特点、大小、数量等都是考虑的因素。移动机器人的工作空间是一个现实的物理空间,而路径规划算法所处理的空间是环境的抽象空间,称之为环境模型。环境建模是实现物理空间到算法处理抽象空间的一个映射,路径搜索的结果,通常是以环境模型的方式表达。
下面介绍两种较为常用的环境建模方法:可视图法、栅格法。
2.3.1 可视图法
可视图法[11]是将机器人视为一点,把机器人、目标点和多边形障碍物的各个顶点进行连接,要求机器人和障碍物各顶点之间,目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线,都不能穿越障碍物,这样就形成了一张图,称之为可视图(如图2-1)。由于任意两直线的顶点都是可视的,显然移动机器人从起点沿着这些连线到达目标点的所有路径均是无碰路径。对可视图进行搜索,并利用优化算法删除一些不必要的连线以简化可视图,缩短搜索时间,最终就可以找到一条无碰最优路径。
图2-1 可视图法示意图
然而,可视图法是建立在机器人所在环境的所有的障碍物信息已知的前提下,不能用于未知障碍物和动态障碍物环境下的路径规划。本文转载自http://www.biyezuopin.vip/onews.asp?id=13720而且该方法缺乏灵活性,若障碍物过多,搜索时间会很长。另外,一旦机器人的起点和目标点发生改变,就要重新构造可视图,比较麻烦。
function m=drawTSP(Clist,BSF,bsf,p,f)
CityNum=size(Clist,1);
for i=1:CityNum-1
plot([Clist(BSF(i),1),Clist(BSF(i+1),1)],[Clist(BSF(i),2),Clist(BSF(i+1),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g');
hold on;
end
plot([Clist(BSF(CityNum),1),Clist(BSF(1),1)],[Clist(BSF(CityNum),2),Clist(BSF(1),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g');
title([num2str(CityNum),'城市TSP']);
if f==0
text(500,230,['第 ',int2str(p),' 步',' 最短距离为 ',num2str(bsf)]);
else
text(500,230,['最终搜索结果:最短距离 ',num2str(bsf)]);
end
hold off;
pause(0.05);