改进蚁群和鸽群算法的机器人路径规划

doi:10.11772/j.issn.1001-9081.2020040538

计算机应用 ›› 2020, Vol. 40 ›› Issue (11): 3366-3372.DOI: 10.11772/j.issn.1001-9081.2020040538

• 应用前沿、交叉与综合 • 上一篇下一篇

改进蚁群和鸽群算法的机器人路径规划

刘昂^1,2, 蒋近^1,2, 徐克锋¹

1. 湘潭大学自动化与电子信息学院, 湖南湘潭 411105;
2. 智能计算与信息处理教育部重点实验室(湘潭大学), 湖南湘潭 411105

收稿日期:2020-04-26 修回日期:2020-06-21 出版日期:2020-11-10 发布日期:2020-07-09
通讯作者: 刘昂(1996-),男,湖北黄冈人,硕士研究生,主要研究方向:机器人路径规划、智能优化算法;liuang96@163.com
作者简介:蒋近(1979-),男,湖南湘潭人,副教授,博士,主要研究方向:智能控制、运动控制、人工智能;徐克锋(1997-),男,广西岑溪人,硕士研究生,主要研究方向:智能服务机器
基金资助:
湖南省自然科学基金资助项目（2015JJ3126）。

Robot path planning based on improved ant colony and pigeon inspired optimization algorithm

LIU Ang^1,2, JIANG Jin^1,2, XU Kefeng¹

1. School of Automation and Electronic Information, Xiangtan University, Xiangtan Hunan 411105, China;
2. Key Laboratory of Intelligent Computing and Information Processing of Ministry of Education(Xiangtan University), Xiangtan Hunan 411105, China

Received:2020-04-26 Revised:2020-06-21 Online:2020-11-10 Published:2020-07-09
Supported by:
This work is partially supported by the Natural Science Foundation of Hunan Province (2015JJ3126).

摘要/Abstract

摘要： 针对复杂环境下移动机器人路径规划中存在的迭代速度慢和路径欠优等问题，提出将全局与局部规划算法相结合的路径规划方法。首先，利用同步双向A^*算法对蚁群算法的信息素进行优化，并对蚁群算法的转移概率和信息素更新机制进行改进，从而使算法的全局寻优速度更快，缩短移动机器人的路径长度；进一步地，将静态路径用于鸽群算法的初始化；然后，利用改进的鸽群算法对移动机器人进行了局部路径规划，通过引入模拟退火准则的方法解决局部最优问题，利用对数S型传递函数对鸽群数量的步长进行优化，从而能更好地避免与动态障碍物的碰撞。最后，利用B样条曲线对路径进行平滑化和重规划。仿真结果表明，该方法在全局静态和局部动态阶段均能生成路径长度短、评价值低的平滑路径，且收敛速度快，适合移动机器人在动态复杂环境中的穿行。

关键词: 移动机器人, 路径规划, 鸽群算法, 模拟退火准则, 平滑化, 重规划

Abstract: A method was proposed by combining the global and local path planning algorithms for the problems of slow iteration and not good path in mobile robot path planning under complex environment. Firstly, the synchronous bidirectional A^* algorithm was used for the pheromone optimization of ant colony algorithm, and the transition probability and pheromone update mechanism of ant colony algorithm were improved, so that the global optimization of the algorithm was faster and the path length of the mobile robot was shortened. Furthermore, the static path was used to initialize the pigeon inspired optimization algorithm. Secondly, the improved pigeon inspired optimization algorithm was used for the local path planning of the mobile robot. The simulated annealing criteria were introduced to solve the local optimum problem, and the logarithmic S-type transfer function was used to optimize the step size of the number of pigeons, so as to better avoid the collision with dynamic obstacles. Finally, the cubic B-spline curve was used to smooth and replan the route. Simulation results indicate that the algorithm can generate smooth paths with short length and small evaluation value in both global static and local dynamic phases, and converge quickly, which is suitable for mobile robot to travel in dynamic and complex environments.

Key words: mobile robot, path planning, pigeon inspired optimization algorithm, simulated annealing criterion, smoothing, replanning

中图分类号:

TP242

刘昂, 蒋近, 徐克锋. 改进蚁群和鸽群算法的机器人路径规划[J]. 计算机应用, 2020, 40(11): 3366-3372.

LIU Ang, JIANG Jin, XU Kefeng. Robot path planning based on improved ant colony and pigeon inspired optimization algorithm[J]. Journal of Computer Applications, 2020, 40(11): 3366-3372.

参考文献

[1] 张晓莉, 杨亚新, 谢永成. 改进的蚁群算法在机器人路径规划上的应用[J]. 计算机工程与应用,2020,56(2):29-34.(ZHANG X L,YANG Y X,XIE Y C. Application of improved ant colony algorithm in robot path planning[J]. Computer Engineering and Applications,2020,56(2):29-34.)
[2] 韩明, 刘教民, 吴朔媚, 等. 粒子群优化的移动机器人路径规划算法[J]. 计算机应用,2017,37(8):2258-2263.(HAN M,LIU J M,WU S M,et al. Path planning algorithm of mobile robot based on particle swarm optimization[J]. Journal of Computer Applications,2017,37(8):2258-2263.)
[3] FAKOOR M,KOSARI A,JAFARZADEH M. Humanoid robot path planning with fuzzy Markov decision processes[J]. Journal of Applied Research and Technology,2016,14(5):300-310.
[4] 李丽娜, 郭永强, 张晓东, 等. 萤火虫算法结合人工势场法的机器人路径规划[J]. 计算机工程与应用,2018,54(20):104-109. (LI L N,GUO Y Q,ZHANG X D,et al. Path planning algorithm for robot based on firefly algorithmcombined with artificial potential field method[J]. Computer Engineering and Applications,2018, 54(20):104-109.)
[5] SHEKHAR R C,KEARNEY M,SHAMES I. Robust model predictive control of unmanned aerial vehicle using waysets[J]. Journal of Guidance, Control, and Dynamic, 2015, 38(10):1898-1907.
[6] 李文广, 孙世宇, 李建增, 等. 分段优化RRT的无人机动态航迹规划算法[J]. 系统工程与电子技术,2018,40(8):1786-1793. (LI W G,SUN S Y,LI J Z,et al. UAV dynamic path planning algorithm based on segmentated optimization RRT[J]. Systems Engineering and Electronics,2018,40(8):1786-1793.)
[7] 王生印, 龙腾, 王祝, 等. 基于即时修复式稀疏A*算法的动态路径规划[J]. 系统工程与电子技术,2018,40(12):2714-2721. (WANG S Y,LONG T,WANG Z,et al. Dynamic path planning using anytime repairing sparse A* algorithm[J]. Systems Engineering and Electronics,2018,40(12):2714-2721.)
[8] 许凯波, 鲁海燕, 黄洋, 等. 基于双层蚁群算法和动态环境的机器人路径规划方法[J]. 电子学报, 2019, 47(10):2166-2176.(XU K B,LU H Y,HUANG Y,et al. Robot path planning based on doublelayer ant colony optimization algorithm and dynamic environment[J]. Acta Electronica Sinica, 2019, 47(10):2166-2176.)
[9] 王中玉, 曾国辉, 黄勃, 等. 改进A*算法的机器人全局最优路径规划[J]. 计算机应用,2019,39(9):2517-2522.(WANG Z Y, ZENG G H,HUANG B,et al. Global optimal path planning for robots with improved A* algorithm[J]. Journal of Computer Applications,2019,39(9):2517-2522.)
[10] 丁家如, 杜昌平, 赵耀, 等. 基于改进人工势场法的无人机路径规划算法[J]. 计算机应用,2016,36(1):287-290.(DING J R, DU C P,ZHAO Y,et al. Path planning algorithm for unmanned aerial vehicles based on improved artificial potential field[J]. Journal of Computer Applications,2016,36(1):287-290.)
[11] 赵晓, 王铮, 黄程侃, 等. 基于改进A*算法的移动机器人路径规划[J]. 机器人,2018,40(6):903-910.(ZHAO X,WANG Z, HUANG C K,et al. Mobile robot path planning based on an improved A* algorithm[J]. Robot,2018,40(6):903-910.)
[12] 王维, 裴东, 冯璋. 改进A*算法的移动机器人最短路径规划[J]. 计算机应用,2018,38(5):1523-1526.(WANG W,PEI D,FENG Z. The shortest path planning for mobile robots using improved A* algorithm[J]. Journal of Computer Applications, 2018,38(5):1523-1526.)
[13] 林娜, 黄思铭, 拱长青. 基于自适应权重鸽群算法的无人机航路规划[J]. 计算机仿真,2018,35(1):38-42,125.(LIN N, HUANG S M,GONG C Q. UAV path planning based on adaptive weighted pigeon-inspired optimization algorithm[J]. Computer Simulation,2018,35(1):38-42,125.)
[14] SZCZERBA R J,GALKOWSKI P,GLICKTEIN I S,et al. Robust algorithm for real-time route planning[J]. IEEE Transactions on Aerospace and Electronic Systems,2000,36(3):869-878.
[15] LI C,DUAN H. Target detection approach for UAVs via improved pigeon-inspired optimization and edge potential function[J]. Aerospace Science and Technology,2014,39:352-360.
[16] GOEL S. Pigeon optimization algorithm:a novel approach for solving optimization problems[C]//Proceedings of the 2014 International Conference on Data Mining and Intelligent Computing. Piscataway:IEEE,2014:1-5.
[17] HART P E,NILSSON N J,RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths in graphs[J]. IEEE Transactions on Systems Science and Cybernetics,1968,4(2):100-107.
[18] 刘生伟, 马钺, 孟树峰, 等. 改进A*算法的AGV路径规划[J]. 计算机应用,2019,39(S2):41-44.(LIU S W,MA Y,MENG S F,et al. Improved A* algorithm for path planning of AGV[J]. Journal of Computer Applications,2019,39(S2):41-44.)
[19] 姜坤霖, 李美安, 张宏伟. 面向旅行商问题的蚁群算法改进[J]. 计算机应用,2015,35(S2):114-117.(JIANG K L,LI M A,ZHANG H W. Improved ant colony algorithm for travelling salesman problem[J]. Journal of Computer Applications,2015, 35(S2):114-117.)
[20] 赵克新, 黄长强, 王渊, 等. 基于混沌蚁狮算法的无人机航迹规划[J]. 飞行力学,2018,36(1):93-96.(ZHAO K X,HUANG C Q,WANG Y,et al. UAV path planning based on chaos ant lion algorithm[J]. Flight Dynamics,2018,36(1):93-96.)
[21] DUAN H,QIAO P. Pigeon-inspired optimization:a new swarm intelligence optimizer for air robot path planning[J]. International Journal of Intelligent Computing and Cybernetics,2014,7(1):24-37.
[22] 黄思铭. 基于改进鸽群算法的无人机航路规划研究[D]. 沈阳:沈阳航空航天大学,2018:16-21.(HUANG S M. Research on UAV path planning based on improved pigeons-inspired optimization algorithm[D]. Shenyang:Shenyang Aerospace University,2018:16-21.)
[23] 李俊, 汪冲, 李波, 等. 基于多策略协同作用的粒子群优化算法[J]. 计算机应用,2016,36(3):681-686.(LI J,WANG C,LI B,et al. Particle swarm optimization algorithm based on multistrategy synergy[J]. Journal of Computer Applications,2016,36(3):681-686.)
[24] 黄辰, 费继友, 刘洋, 等. 基于动态反馈A*蚁群算法的平滑路径规划方法[J]. 农业机械学报,2017,48(4):34-40,102. (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.)
[25] 张永华, 杜煜, 潘峰, 等. 基于三次B样条曲线拟合的智能车轨迹跟踪算法[J]. 计算机应用,2018,38(6):1562-1567. (ZHANG Y H,DU Y,PAN F,et al. Intelligent vehicle path tracking algorithm based on cubic B-spline curve fitting[J]. Journal of Computer Applications,2018,38(6):1562-1567.)

改进蚁群和鸽群算法的机器人路径规划

Robot path planning based on improved ant colony and pigeon inspired optimization algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李开荣, 刘爽, 胡倩倩, 唐亦媛. 基于转角约束的改进蚁群优化算法路径规划[J]. 计算机应用, 2021, 41(9): 2560-2568.
[2]	陆国庆, 孙昊. 基于随机行走的群机器人二维地图构建[J]. 计算机应用, 2021, 41(7): 2121-2127.
[3]	栾佳宁, 张伟, 孙伟, 张奥, 韩冬. 基于二维码视觉与激光雷达融合的高精度定位算法[J]. 计算机应用, 2021, 41(5): 1484-1491.
[4]	黄书召, 田军委, 乔路, 王沁, 苏宇. 基于改进遗传算法的无人机路径规划[J]. 计算机应用, 2021, 41(2): 390-397.
[5]	王家亮, 李树华, 张海涛. 基于贝叶斯估计与区域划分遍历的四轴飞行器避障路径规划算法[J]. 计算机应用, 2021, 41(2): 384-389.
[6]	魏博, 杨茸, 舒思豪, 万勇, 苗建国. 基于离子运动-人工蜂群算法的移动机器人路径规划[J]. 计算机应用, 2021, 41(2): 379-383.
[7]	李伟, 金世俊. 基于人工势场法和启发式采样的最优路径收敛方法[J]. 计算机应用, 2021, 41(10): 2912-2918.
[8]	刘思嘉, 童向荣. 基于强化学习的城市交通路径规划[J]. 计算机应用, 2021, 41(1): 185-190.
[9]	祁玄玄, 黄家骏, 曹建安. 基于改进A^*算法的无人车路径规划[J]. 计算机应用, 2020, 40(7): 2021-2027.
[10]	徐晓强, 秦品乐, 曾建朝. 基于改进粒子群优化算法的牙齿正畸路径规划方法[J]. 计算机应用, 2020, 40(7): 1938-1943.
[11]	韩雨涝, 房鼎益. 联合无线充电与数据收集的移动充电装置多目标路径规划算法[J]. 计算机应用, 2020, 40(6): 1745-1750.
[12]	屈立成, 吕娇, 赵明, 王海飞, 屈艺华. 基于三维时空地图和运动分解的多机器人路径规划算法[J]. 计算机应用, 2020, 40(12): 3499-3507.
[13]	徐小强, 王明勇, 冒燕. 基于改进人工势场法的移动机器人路径规划[J]. 计算机应用, 2020, 40(12): 3508-3512.
[14]	童心赤, 张华军, 郭航. 多方向无人水面艇路径规划算法[J]. 计算机应用, 2020, 40(11): 3373-3378.
[15]	梅伟, 赵云涛, 毛雪松, 李维刚. 基于离散灰狼算法的喷涂机器人路径规划方法[J]. 计算机应用, 2020, 40(11): 3379-3384.