基于免疫遗传算法的AGV路径规划方法研究.doc

基于免疫遗传算法的AGV路径规划方法研究.doc基于免疫遗传算法的 AGV 路径规划方法研究【摘要】论文基于遗传学和免疫学的特点,提出了一种基于免疫遗传算法 AGV 路径规划方法。算法采用实数编码, 且采用不定长度, 定义的适应度函数具有明确的物理意义。所设计的路径规划方法具有遗传算法具有的搜索空间大等优点, 也具有免疫算法对抗原的识别、学忆和自动调节能力, 克服了遗传算法易陷入局部最优的缺陷, 进化速度也得到了提高。仿真结果证明该算法能较快地为 AGV 产生一条适应所处环境的无碰撞的最优路径。【关键词】自动导航小车;路径规划;免疫遗传算法;疫苗 1 、引言目前,为使移动机器人规划出良好的去去路径,所用的方法很多,如栅格法[1] 、势场法[2] 、可视图法[3] 等。但各种方法有其使用局限。人工智能的发展为 AGV 的路径规划提供了新思路, 产生了诸如神经网络学习法、遗传算法等方法。这些算法在一定程度上解决了 AGV 的路径规划问题, 但也有其缺陷。如神经网络学习法对于复杂环境难以数学建模, 范化能力差; 模糊法灵活性差。遗传算法在迭代过程中, 个体在进化过程中不可避免地会产生退化。受生物免疫系统的启发, 论文将免疫引入到遗传算法中, 在保留遗传算法优点的情况下, 利用待求问题的一些特征信息, 采用免疫方法所具有的识别、记忆等功能来抑制遗传算法在进化中所出现的退化现象。本文所设计的基于免疫遗传算法的 AGV 路径规划方法利用 AGV 在移动过程中的特殊信息对所选路径进行优化, 可较快地使 AGV 根据环境信息搜索一种满意的路径,提高了 AGV 路径规划的智能性。 2 、环境信息建模对 AGV 进行路径规划前, 应解决对其环境信息的描述即环境建模问题。为此,作以下假设[3] : (1) AGV 在二维平面中运动, 不考虑其高度方向的信息;(2) 规划环境的边界及其内所有障碍物( 妨碍 AGV 运动的所有物体) 用凸多边形表示。(3) 考虑到 AGV 的大小等, 对环境边界进行缩小和对障碍物进行扩大时, 其缩放量为 AGV 外形最大尺寸的一半。即 AGV 为“点机器人”。至此, AGV 的工作空间可描述为:工作平面和障碍物群{Oi|i=1 ,2… N}。具体到其个障碍物 Oi, 可描述为 Oi={ 顶点 1 坐标( xi1 , yi1 ),….. 顶点 n 坐标( xni , yni )}。为方便数据处理, 对多边形顶点沿顺时针方向编号。起点为 S, 终点为 E。工作平面可表示为矩形{( Xmin , Ymin ),( Xmax , Ymax )}。设在 AGV 的工作环境中有 n 个已知的障碍物 Oi( i=1 ,2, ... ,n), 对应的顶点数为 Si, 顶点坐标为(x(i,j),y(i,j))( j=1 ,2,… Si)。为描述 AGV 工作环境中的障碍物,采用 Dm×m 矩阵对环境信息进行描述, 其中, m 为障碍物顶点总数。定义 d(i,j )为: 3 、免疫遗传算法设计 路径编码方式采用免疫遗传算法求解最优问题的关键是对所求问题的解进行编码。编码的长度与搜索空间的大小及求解精度有直接关系,也影响算法的效率。对 AGV 进行路径规划时,传统的二进制或实数编码方式都不适用。本文设计了一种自适应变长度实数数组编码方式,即第 p代 Xp 的第 k 条染色体 Xkp 的第 j 位基