自动导航车 (Automated Guided Vehicles, AGV) 又名无人搬运车, 出现于20世纪50年代, 是一种自动化的无人驾驶的智能化搬运设备, 属于移动式机器人系统, 能够沿预先设定的路径行驶, 是现代工业自动化物流系统如计算机集成制造系统 (CIMS) 中的关键设备之一[1]。它具有灵活性、智能性、对恶劣环境的强适应性等特点, 可以实现运输的自动化、智能化、柔性化。随着物流系统自动化、智能化水平的提高, AGV在物流系统的应用越来越普遍[2]。
AGV的导航控制是AGV的核心技术, 而路径规划是AGV导航的重要环节之一。AGV的路径规划是按照某一性能指标搜索一条从起始状态到目标状态的最优或近似最优的无碰路径[3]。根据对环境信息知道程度的不同, 可分为环境信息完全知道的全局路径规划和环境信息完全未知或部分未知的局部路径规划及混合路径规划[4]。
传统的解决路径规划问题的方法有可视图法、自由空间法、人工势场法等[5,6]。随着智能方法的发展, 许多研究者把目光放在了基于智能方法的路径规划研究上。遗传 (算X1法-X是s) 2智+能 (Y1方-Y法s) 2的+一种 (, Xi它-具Xi-其1) 2不+ (要Yi-求Yi-1) 2适应度函数是可导或连续的、并行性、对问题的依赖程度小、在解空间进行高效启发式搜索等优点。本文以路径长短作为评判路径好坏的指标, 利用遗传算法对静态已知环境下的全局路径规划进行研究。
1 问题描述
在物流系统中应用AGV完成搬运任务, 任务中规定了AGV的起始点S, 和目标点E, 要求提前规划一条可行的无碰撞的路径, 且该条路径的总长度尽量短。该路径由起点、终点以及4个中间点Ai (0
本文就是在已知当前的物流系统布局情况和AGV小车的起始点和目标点坐标的条件下, 求解中间点的坐标, 使得路径尽量最短。
假设物流系统为一个平面仓库, 它的形状为长为18, 宽为18的矩形, 仓库的当前布局中, 存在三个矩形障碍物, 需要移动的物体起始位置为 (0, 0) , 终止位置为 (16, 16) 。
本文以路径长短作为评判路径好坏的指标, 故性能指标函数为:
基本的约束条件为:
2 环境建模
路径规划分为两个步骤, 第一步是环境建模, 第二步是求解路径。环境建模是求解路径的基础, 合理的环境表示有利于建立规划方法和选择合适的搜索算法, 最终实现较少的时间和内存开销而规划出较为满意的路径。在当前的研究中, 环境建模的方法有很多种, 如顶点法、栅格法、广义锥法、链路可视图法。
本文考虑二维空间, 采用的是直角坐标系对物流系统当前布局进行建模, 以平面仓库的一个顶点为起始点, 用 (x, y) 坐标对AGV在平面仓库中的位置进行定位, 同时把要移动的AGV等同与一个质点。
3 基于遗传算法的AGV路径规划
3.1 算法流程
遗传算法是一种基于自然选择和基因遗传学原理的优化搜索方法, 使得我们可以在计算机上模拟生物的进化过程和基因的操作。它一般包括初始种群的产 (X生E, -X交4) 2叉+, (Y变E-异Y4) 等2过程。本文的算法流程如图1所示。
3.2 初始种群的产生
本文采用典型的二进制编码方式, 这样的编码方式直接简洁。每个染色体是由4个中间点连接而成的, 其所表示的是一条可行或者不可行的路径。染色体的结构可表示为: (x1, y1) → (x2, y2) →……→ (x4, y4) 。其中, 染色体的长度是固定的, 每个中间节点由两个坐标, 每个坐标用一个4位二进制串表示, 则染色体的长度为32。通过随机函数产生初始化种群。
3.3 适应度函数的确定
路径规划, 就是要规划出一条最短的可行路径, 约束条件是路径不与障碍物碰撞。对路径优劣程度的评估就作为遗传算法中染色体的适应值。本文考虑简单的一种情况。只用路径的长短来判断路径的优劣程度。所以, 求适应度函数就是求线路的长度。另外还需判断可行路径和不可行路径, 不可行路径就是与障碍物的轮廓线有交点的路径。则适应度函数:Fitness=
显然, 适应度越小越好。
3.4 遗传算子的确定
选择算子, 采用轮盘赌选择法, 由上可知, 适应度越小被选择的概率越大。从种群中选出父体, 个体的数量保持不变。
交叉算子, 交叉是以一定的概率, 在父染色体中随机选择一个除起始点与目标点以外的转向点, 这个转向点就作为交叉点, 把整个路径分成了两个路径段。然后选择两个父代染色体, 相互交换交叉点后面的路径段, 这样就产生了两个子代染色体。在不同父代中选择不同的交叉点, 可以增加染色体长度的差异性, 并且有利于扩大解空间的范围和最优解的产生。
变异算子, 变异是以一定的概率, 除去起始点和目标点, 在路径的中间转向点中任意选取一个位置, 将该转向点的位置坐标作一次非一致性变异, 然后把当前的转向点移至新产生的转向点上, 经过变异之后就产生了一条新的路径。
然后, 把新的路径当作新的种群进行下一步的遗传操作, 依次循环往复。
4 仿真和实验结果
本文设计并实现了仿真实验, 实验的环境是visual studio2005软件开发平台, 用c#语言编写, 为一个窗体程序。如图2所示, 输入AGV的其实位置坐标和终止位置坐标, 点击“计算线路”按钮, 系统开始计算, 用红线画出每次迭代过程中计算得出的可行路径, 并用绿线表示最终计算的最优路径。
初始参数的设置为:种群的代数:500种群大小:500, 交叉概率:0.9, 变异概率:02。起点坐标为 (0, 0) , 终点坐标为 (16, 16) 运行以上代码, 得出结果如Fig.3 (b) 所示。中间点坐标中间点的坐标 (1, 2) , (2, 5) , (5, 7) (7, 6) , 最优路径长度为2 4.69。
5 结语
综合分析, 本文采用遗传算法解决了物流系统中单个AGV的路径规划问题。随机的产生初始种群, 在遗传算法的过程中考虑了选择算子, 交叉算子和变异算子。仿真实验也证实了该方法的有效性。合理的路径规划不但能够提高AGV的作业效率缩短单个作业的完成时间, 同时也能减少能耗, 从而提升整个物流系统的运作效率减少物流运作成本。
摘要：随着物流系统自动化、智能化水平的提高, AGV在物流系统的应用越来越普遍。AGV的导航是AGV的核心技术, 而路径规划是AGV导航的重要环节之一。本文应用遗传算法求解单个AGV的路径规划问题, 最后给出该算法实现的路径规划仿真和实验结果, 实验结果证实了该方法的有效性。
关键词：遗传算法,路径规划,AGV
参考文献
[1] 马幼捷, 张海涛, 邵保福, 等.电子智能化立体车库的研究现状与走向[J].电气自动化, 2008 (5) :3～6.
[2] 张辰贝西, 黄志球.自动导航车发展综述[J].中国制造业信息化, 2010 (1) :53～5 9.
[3] 范九荣, 应浩, 曾素娣.混合遗传算法的AGV路径规划的应用[J].科技信息, 2006 (8) :266～267.
[4] 王菁华, 崔世钢, 罗云林.基于Matlab的智能机器人路径规划仿真[C].2008系统仿真技术及应用学术会议论文集, 2008:298～301.
[5] L.Guibas, J.Hershberger.Computingthe visibility graph of n line segmentsin O (n2) time[J].Theoret Comput Sc., 1985, 26:13～20.
[6] Y.K.Hwang, N.Ahuja.A Potential fieldapproach to path planning[J].IEEETrans.Robot&Autom, 1992, 8 (1) :23～3 2.