留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

并行排序蚁群算法规划仓库AGV路径研究

于军琪 李若琳 赵安军 余紫瑞 王均峰

于军琪,李若琳,赵安军, 等. 并行排序蚁群算法规划仓库AGV路径研究[J]. 机械科学与技术,2021,40(4):609-618 doi: 10.13433/j.cnki.1003-8728.20200103
引用本文: 于军琪,李若琳,赵安军, 等. 并行排序蚁群算法规划仓库AGV路径研究[J]. 机械科学与技术,2021,40(4):609-618 doi: 10.13433/j.cnki.1003-8728.20200103
YU Junqi, LI Ruolin, ZHAO Anjun, YU Zirui, WANG Junfeng. Planning Warehouse AGV Path with Parallel-ranking Ant Colony Optimization Algorithm[J]. Mechanical Science and Technology for Aerospace Engineering, 2021, 40(4): 609-618. doi: 10.13433/j.cnki.1003-8728.20200103
Citation: YU Junqi, LI Ruolin, ZHAO Anjun, YU Zirui, WANG Junfeng. Planning Warehouse AGV Path with Parallel-ranking Ant Colony Optimization Algorithm[J]. Mechanical Science and Technology for Aerospace Engineering, 2021, 40(4): 609-618. doi: 10.13433/j.cnki.1003-8728.20200103

并行排序蚁群算法规划仓库AGV路径研究

doi: 10.13433/j.cnki.1003-8728.20200103
基金项目: 国家重点研发计划(新型建筑智能化系统平台技术)项目(2017YFC0704100)、陕西省科技厅专项科研项目(2017JM6106)及校基础研究基金(JC1706)
详细信息
    作者简介:

    于军琪(1969−),教授,博士生导师,研究方向为建筑智能与节能控制技术,junqiyu@126.com

    通讯作者:

    赵安军,副教授,博士,zhao_anjun@163.com

  • 中图分类号: TP242

Planning Warehouse AGV Path with Parallel-ranking Ant Colony Optimization Algorithm

  • 摘要: 针对智能仓库中的AGV路径规划问题,提出了一种基于并行排序蚁群算法的路径规划方法,该方法通过多个子蚁群之间较优蚂蚁释放的信息素交互,提高蚁群整体的搜索能力。建立以路径最短和AGV转弯次数最少为优化目标的多目标函数模型,用并行排序蚁群算法求解,再对生成的初始路径通过减少中间节点的方式进行平滑处理。在MATLAB上进行多次仿真,对比实验结果表明,该算法在进行仓库AGV路径规划时收敛速度更快,稳定性更好,且平滑处理后的路径更优。
  • 图  1  栅格坐标与栅格编号图

    图  2  单个子蚁群运行流程图

    图  3  子蚁群信息交互示意图

    图  4  路径死角状态示意图

    图  5  路径平滑处理流程图

    图  6  解的多样性曲线

    图  7  30 × 30环境中4种算法的路径规划结果图

    图  8  30 × 30环境中4种算法的收敛曲线

    图  9  35 × 35环境中4种算法的路径规划结果图

    图  10  35 × 35环境中四种算法的收敛曲线

    图  11  有无平滑处理的路径对比

    表  1  求解TSP问题时4种算法50次仿真结果

    名称ACORACOIAC[17]P-RACO
    路径
    长度
    Max3363.043189.253177.263152.51
    Min3101.323068.443076.983058.93
    Avg3161.353189.253116.513102.16
    Sd66.5928.5628.1122.01
    迭代
    次数
    Max97422819
    Min10753
    Avg17.2210.309.426.02
    Sd16.256.605.433.39
    下载: 导出CSV

    表  2  30 × 30环境中4种算法50次仿真结果

    名称ACORACOIAC[17]P-RACO
    效用函
    数值
    Max 35.278 34.456 34.987 34.067
    Min 30.726 30.712 30.352 29.872
    Avg 32.647 32.107 31.887 30.933
    Sd 1.458 1.112 1.192 0.823
    迭代
    次数
    Max 32 26 26 10
    Min 19 16 14 8
    Avg 24.58 18.44 16.72 8.72
    Sd 3.112 2.475 2.807 0.491
    下载: 导出CSV

    表  3  35 × 35环境中4种算法50次仿真结果

    名称ACORACOIAC[17]P-RACO
    效用函
    数值
    Max 48.797 44.776 48.747 42.118
    Min 40.477 40.001 38.507 38.282
    Avg 44.420 43.346 42.336 40.049
    Sd 3.147 2.208 1.965 0.968
    迭代
    次数
    Max 37 33 29 12
    Min 27 20 19 9
    Avg 31.86 24.60 23.04 10.08
    Sd 2.550 1.989 1.199 0.483
    下载: 导出CSV

    表  4  不同复杂度地图30次仿真结果对比

    名称ACORACOIAC[17]P-RACO
    20 × 20效用
    函数
    Avg27.52526.90226.63326.630
    Sd0.8780.3450.4320.159
    迭代
    次数
    Avg16.4210.2010.335.63
    Sd3.6571.8762.1030.796
    40 × 40效用
    函数
    Avg68.76363.23459.98957.97
    Sd6.0724.2343.5463.354
    迭代
    次数
    Avg36.4224.3419.4611.91
    Sd3.0941.9371.6750.907
    50 × 50效用
    函数
    Avg100.04492.98789.87981.369
    Sd6.1575.6294.9823.771
    迭代
    次数
    Avg42.8828.9839.6713.65
    Sd3.0662.3762.2561.424
    下载: 导出CSV

    表  5  路径平滑前后数据对比

    名称30 × 3035 × 35
    平滑前路径长度40.11352.598
    平滑后路径长度38.29148.249
    路径长度减少量4.5%8.3%
    平滑前转弯次数1321
    平滑后转弯次数1214
    转弯次数减少量7.6%33.3%
    下载: 导出CSV
  • [1] 梁建刚. AGV系统路径规划与调度算法研究[D]. 北京: 北京邮电大学, 2018.

    LIANG J G. Research on path planning and scheduling algorithm of AGV system[D]. Beijing: Beijing University of Posts and Telecommunications, 2018 (in Chinese).
    [2] KANG N K, SON H J, LEE S H. Modified A-star algorithm for modular plant land transportation[J]. Journal of Mechanical Science and Technology, 2018, 32(12): 5563-5571 doi: 10.1007/s12206-018-1102-z
    [3] 乐阳, 龚健雅. Dijkstra最短路径算法的一种高效率实现[J]. 武汉测绘科技大学学报, 1999, 24(3): 209-212 doi: 10.3969/j.issn.1671-8860.1999.03.005

    YUE Y, GONG J Y. An efficient implementation of shortest path algorithm based on Dijkstra algorithm[J]. Journal of Wuhan Technical University of Surveying and Mapping, 1999, 24(3): 209-212 (in Chinese) doi: 10.3969/j.issn.1671-8860.1999.03.005
    [4] 王树西, 李安渝. Dijkstra算法中的多邻接点与多条最短路径问题[J]. 计算机科学, 2014, 41(6): 217-224 doi: 10.11896/j.issn.1002-137X.2014.06.043

    WANG S X, LI A Y. Multi-adjacent-vertexes and multi-shortest-paths problem of Dijkstra algorithm[J]. Computer Science, 2014, 41(6): 217-224 (in Chinese) doi: 10.11896/j.issn.1002-137X.2014.06.043
    [5] CHEN X, KONG Y Y, FANG X, et al. A fast two-stage ACO algorithm for robotic path planning[J]. Neural Computing and Applications, 2013, 22(2): 313-319 doi: 10.1007/s00521-011-0682-7
    [6] YANG H, QI J, MIAO Y C, et al. A new robot navigation algorithm based on a double-layer ant algorithm and trajectory optimization[J]. IEEE Transactions on Industrial Electronics, 2019, 66(11): 8557-8566 doi: 10.1109/TIE.2018.2886798
    [7] 何庆, 吴意乐, 徐同伟. 改进遗传模拟退火算法在TSP优化中的应用[J]. 控制与决策, 2018, 33(2): 219-225

    HE Q, WU Y L, XU T W. Application of improved genetic simulated annealing algorithm in TSP optimization[J]. Control and Decision, 2018, 33(2): 219-225 (in Chinese)
    [8] 贾全, 张小超, 苑严伟, 等. 拖拉机自动驾驶系统上线轨迹规划方法[J]. 农业机械学报, 2018, 49(4): 36-44 doi: 10.6041/j.issn.1000-1298.2018.04.004

    JIA Q, ZHANG X C, YUAN Y W, et al. Guided trajectory planning method for tractor autopilot system[J]. Transactions of the Chinese Society for Agricultural Machinery, 2018, 49(4): 36-44 (in Chinese) doi: 10.6041/j.issn.1000-1298.2018.04.004
    [9] COUCEIRO M S, MACHADO J A T, ROCHA R P, et al. A fuzzified systematic adjustment of the robotic Darwinian PSO[J]. Robotics and Autonomous Systems, 2012, 60(12): 1625-1639 doi: 10.1016/j.robot.2012.09.021
    [10] 孔令文, 李鹏永, 杜巧玲. 基于模糊神经网络的六足机器人自主导航闭环控制系统设计[J]. 机器人, 2018, 40(1): 16-23

    KONG L W, LI P Y, DU Q L. The closed-loop control system design of hexapod robot autonomous navigation based on fuzzy neural network[J]. Robot, 2018, 40(1): 16-23 (in Chinese)
    [11] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66 doi: 10.1109/4235.585892
    [12] 金弟, 杨博, 刘杰, 等. 复杂网络簇结构探测——基于随机游走的蚁群算法[J]. 软件学报, 2012, 23(3): 451-464 doi: 10.3724/SP.J.1001.2012.03996

    JIN D, YANG B, LIU J, et al. Ant colony optimization based on random walk for community detection in complex networks[J]. Journal of Software, 2012, 23(3): 451-464 (in Chinese) doi: 10.3724/SP.J.1001.2012.03996
    [13] STÜTZLE T, HOOS H H. MAX-MIN ant system[J]. Future Generation Computer Systems, 2000, 16(8): 889-914 doi: 10.1016/S0167-739X(00)00043-1
    [14] 刘利强, 袁赣南, 戴运桃. 多蚁群伪并行优化算法[J]. 计算机工程, 2007, 33(23): 199-201 doi: 10.3969/j.issn.1000-3428.2007.23.069

    LIU L Q, YUAN G N, DAI Y T. Multi-ant colony virtual parallel optimization algorithm[J]. Computer Engineering, 2007, 33(23): 199-201 (in Chinese) doi: 10.3969/j.issn.1000-3428.2007.23.069
    [15] LIU J H, YANG J G, LIU H P, et al. An improved ant colony algorithm for robot path planning[J]. Soft Computing, 2017, 21(19): 5829-5839 doi: 10.1007/s00500-016-2161-7
    [16] 王晓燕, 杨乐, 张宇, 等. 基于改进势场蚁群算法的机器人路径规划[J]. 控制与决策, 2018, 33(10): 1775-1781

    WANG X Y, YANG L, ZHANG Y, et al. Robot path planning based on improved ant colony algorithm with potential field heuristic[J]. Control and Decision, 2018, 33(10): 1775-1781 (in Chinese)
    [17] ZHANG Y, WANG F L, FU F K, et al. Multi-AGV Path planning for indoor factory by using prioritized planning and improved ant algorithm[J]. Journal of Engineering and Technological Sciences, 2018, 50(4): 534-547 doi: 10.5614/j.eng.technol.sci.2018.50.4.6
    [18] 乔辰, 张国立. 几何加权法求解多目标规划问题[J]. 华北电力大学学报, 2011, 38(6): 107-110

    QIAO C, ZHANG G L. Geometric weighting method for solving multi-objective programming problems[J]. Journal of North China Electric Power University, 2011, 38(6): 107-110 (in Chinese)
    [19] WANG D S, YU H F. Path planning of mobile robot in dynamic environments[C]//2011 2nd International Conference on Intelligent Control and Information Processing. Harbin: IEEE, 2011.
    [20] 孙波, 姜平, 周根荣, 等. 改进遗传算法在移动机器人路径规划中的应用[J/OL]. 计算机工程与应用, 2019(2019-06-03). http://kns.cnki.Net/kcms/detail/11.2127.tp.20190530.1022.018.html.

    SUN B, JIANG P, ZHOU G R, et al. Application of improved genetic algorithm in path planning of mobile robots[J/OL]. Computer Engineering and Applications, 2019(2019-06-03). http://kns.cnki.Net/kcms/detail/11.2127.tp.20190530.1022.018.html (in Chinese).
    [21] 屈鸿, 黄利伟, 柯星. 动态环境下基于改进蚁群算法的机器人路径规划研究[J]. 电子科技大学学报, 2015, 44(2): 260-265 doi: 10.3969/j.issn.1001-0548.2015.02.017

    QU H, HUANG L W, KE X. Research of improved ant colony based robot path planning under dynamic environment[J]. Journal of University of Electronic Science and Technology of China, 2015, 44(2): 260-265 (in Chinese) doi: 10.3969/j.issn.1001-0548.2015.02.017
    [22] 黄辰, 费继友, 刘洋, 等. 基于动态反馈A*蚁群算法的平滑路径规划方法[J]. 农业机械学报, 2017, 48(4): 34-40, 102 doi: 10.6041/j.issn.1000-1298.2017.04.004

    HUANG C, FEI J Y, LIU Y, et al. Smooth path planning method based on dynamic feedback A* ant colony algorithm[J]. Transactions of the Chinese Society for Agricultural Machinery, 2017, 48(4): 34-40, 102 (in Chinese) doi: 10.6041/j.issn.1000-1298.2017.04.004
  • 加载中
图(11) / 表(5)
计量
  • 文章访问数:  337
  • HTML全文浏览量:  64
  • PDF下载量:  31
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-10-18
  • 网络出版日期:  2021-04-16
  • 刊出日期:  2021-04-16

目录

    /

    返回文章
    返回