基于改进遗传算法的自动导引小车路径规划及其实现平台

  • 基于改进遗传算法的自动导引小车路径规划及其实现平台已关闭评论
  • 93 views
  • A+
所属分类:AGV设计资料
摘要

针对自动导引小车全局路径规划算法收敛慢和容易陷入局部最小值的问题,结合灰狼优化算法改进传统的精英保留策略,避免了传统精英保留策略使种群多样性变差的缺点,增强了全局搜索能力;为了防止染色体上的基因聚集到小的邻域内,提出了基于染色体信息熵的自适应变异和交叉概率的改进遗传算法,其中对于与障碍物相交的染色体片段采用邻域变异算子,使染色体片段快速避开障碍物。采用MATLAB GUI工具开发出基于改进遗传算法的移动机器人路径规划平台。实验结果表明,本文所提出的改进算法和开发平台能高效并可靠地求解复杂静态环境中的移动机器人路径规划问题。

0 引言

随着现代工业的快速发展,自动导引小车( Auto- matic Guided Vehicle,AGV)已经广泛应用于诸多领域,如智能制造工厂、装配车间、物流和运输、计算机 游戏、动画制作等[ 1]。路径规划是移动机器人导航和 控制领域很重要的问题,即在一个有障碍物的环境 中,尽可能高效可靠地规划出一条与障碍物无碰撞从起始点到目标点的路径,这条路径需按一定的 指标优化,如距离最短、能耗最低、时间最短等[ 2]。 路径规划问题可以建模成有约束的优化问题,用 优化算法求解。移动机器人的路径规划问题包含 多个目标,属于多目标优化问题,一般采用罚函数 法将其转化为单目标优化问题,文献[ 3]提出了基 于可变邻域搜索的多目标进化算法,来求解移动 机器人路径规划问题,并将其按环境信息是否全 部已知分为全局路径规划(Global   Path Planning, GPP)和 局 部 路 径 规 划 (Local  Path Planning, LPP)。GPP通过已知的环境信息离线规划出一条 最优路径,而 LPP根据传感器获取的部分环境信 息在线规划局部最优路径。路径规划技术可以分 为传统方法和智能方法,传统的路径规划方法包 括可视图法[ 4]、voronoi图法[ 5]、人工势场法[ 6]、A* 算法[ 7]等;智能方法包括模糊逻辑法[ 8]、神经网络 法[ 9]、布谷鸟搜索(Cuckoo Search,CS)算法[10],蚁 群优化(Ant Colony  Optimization,ACO)算法[11]、 人工蜂群(Artificial   Bee Colony al gorithm,ABC)算 法[12]、遗传算法(Genetic Al gorithm,GA) [ 13]和粒 子群 优 化 (Particle Swarm Optimization,PSO)算 法[14]等。传统的路径规划算法求解复杂的路径规 划问题时有计算代价高、容易陷入局部最优解和 效率低等缺陷,智能优化算法容易实施、搜索能力 强,已经成功应用于求解各种复杂的高维优化 问题[15]。

移动机器人路径规划问题属于 NP-Hard问 题,问题的复杂性高,可行解的空间大,高效地求 解该问题仍然有很大的挑战,而 GA对于 NP-Hard 优化问题已被证明有很强的全局搜索能力和并行 处理特点[16],因此最近几年很多学者尝试用 GA 求解机器人路径规划问题,如文献[17]提出了基 于精英非支配排序遗传算法的多目标最优路径规 划;文献[13]提出了基于改进遗传算法与协同进 化策略的多移动机器人全局路径规划;文献[18] 利用无环图提出了基于 GA 的机器人路径规划初 始化方法。

传统的 GA种群多样性随着迭代很快变差,为 克服这一缺陷,文献[19]提出了基于种群信息熵来 控制 GA的交叉和变异概率的自适应遗传算法,克 服了根据个体适应度值来衡量种群多样性的不足, 当种群的个体差异度较小时, P c 和 P m 自动地变大 以增加种群的多样性,摆脱了局部最优困境,提高了算法的收敛速度和收敛率。本文将基于信息熵改进 的 GA应用于路径规划问题中,并考虑到局部基因 片段与障碍物相交的问题,为了使与障碍物碰撞的 基因片段避开障碍物,提出邻域变异算子,对于障碍 物相交的基因片段按一定概率在一个基因的邻域变 异。同时由于传统的精英保留策略容易使种群多样 性变差,本文结合灰狼优化算法[20 -21]来改进传统的 精英策略,使种群保持更好的多样性,增强种群的全 局搜索能力,以避免陷入局部最小值。

1 机器人工作空间建模

移动机器人工作环境包括动态环境和静态环境, 动态环境中机器人对环境没有先验知识,因此动态环 境中路径规划的主要目的是增强避障能力,同时考虑 路径长度和移动时间。本文针对的是静态环境,机器 人对工作环境信息有先验知识。假设机器人工作空 间的环境信息已知,机器人工作空间定义如下:移动 机器人工作空间 W 为由 R 2 表示的物理空间,障碍物 在工作空间 W 中的映射为障碍物空间 Oobs ,机器人与 障碍物无碰撞移动的空间为自由空间 Cf ree ,则 Oobs ∪ Cf ree = W [ 22]。

移动机器人工作空间环境地图如图1所示,为 了方便建模,将机器人作为一个质点,忽略其实际大 小, S 表示机器人起始点, G 表示机器人目标点,黑 色矩形表示障碍物,所有障碍物构成障碍物集合Oobs ,空白区域是Cf ree ,地图用矩阵表示,形式如式( 1),其中xi,yi,Widthi和Height i分别表示第 i障 碍物左下角的横坐标、纵坐标、障碍物宽度、障碍物 高度, nob 表示障碍物的总数。为方便问题的求解, 用若干网格划分机器人工作空间,所有路径片段的 端点都落在网格的中心,网格精细程度依据环境地 图复杂程度调整。

本文引入网格细化思想,第一次求解问题时网 格细化倍数设置为1,若环境地图比较复杂、求解失 败,则增加网格细化倍数,使环境地图更精细,网格 细化前后规划出的路径对比如图2(网格细化之后 的网格未画出)所示。图中:实线是网格细化前的路 径,虚线是网格细化后的路径,可以看出网格细化之 后规划出的路径更加接近理论最优解。

基于改进遗传算法的自动导引小车路径规划及其实现平台

抱歉,此资源仅限赞助会员下载,请先
注意:本站资源多为网络收集,如涉及版权问题请及时与站长联系QQ:2766242327,我们会在第一时间内与您协商解决。如非特殊说明,本站所有资源解压密码均为:agvba.com。
weinxin
微信公众号
agvba是一个分享AGV知识和agv案例视频的网站。