基于双层蚁群算法和动态环境的机器人路径规划方法

doi:10.3969/j.issn.0372-2112.2019.10.019

电子学报 ›› 2019, Vol. 47 ›› Issue (10): 2166-2176.DOI: 10.3969/j.issn.0372-2112.2019.10.019

基于双层蚁群算法和动态环境的机器人路径规划方法

许凯波^1,2, 鲁海燕¹, 黄洋¹, 胡士娟¹

1. 江南大学理学院, 江苏无锡 214122;
2. 无锡市玉祁高级中学, 江苏无锡 214183

收稿日期:2017-12-20 修回日期:2019-02-13 出版日期:2019-10-25
- 作者简介:
- 许凯波 男.1992年6月出生,山西晋城人.硕士,2018年毕业于江南大学理学院应用数学专业,主要研究方向为最优化与控制.E-mail:2587073839@qq.com;鲁海燕 女.1970年出生,山东淄博人.副教授,硕士生导师,分别于1996年和2007年在浙江大学获得硕士学位和博士学位,现为江南大学理学院信息与计算科学系党支部书记,主要从事组合优化;网络优化;计算智能和机器学习及其在组合优化、计算流体力学、生物信息学中的应用等方面的研究.E-mail:luhaiyan@jiangnan.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61772013，No.61402201）; 中央高校基本科研业务费专项资金 (No.114205020513526）

Robot Path Planning Based on Double-Layer Ant Colony Optimization Algorithm and Dynamic Environment

XU Kai-bo^1,2, LU Hai-yan¹, HUANG Yang¹, HU Shi-juan¹

1. School of Science, Jiangnan University, Wuxi, Jiangsu 214122, China;
2. Wuxi Yuqi Senior High School, Wuxi, Jiangsu 214183, China

Received:2017-12-20 Revised:2019-02-13 Online:2019-10-25 Published:2019-10-25

摘要/Abstract

摘要： 针对动态环境未知时变的特点，提出一种机器人路径规划新方法.在该方法中，首先对栅格法建立的环境模型进行凸化处理，以避免机器人沿规划路径移动时陷入U型陷阱，从而加快路径规划的速度；其次，提出双层蚁群算法（DACO），在每次迭代中先用外层蚁群算法寻找一条路径，然后以该路径为基础构造一个小环境，接着在该环境下用内层蚁群算法重新寻优，若寻得的路径质量更高，则更新路径并执行本文给出的一种新型信息素二次更新策略；最后，针对环境中不同动态障碍物的体积和速度，提出三种避障策略.动态环境下，机器人先由DACO算法规划一条静态环境下从起点到终点的全局最优路径，然后从当前起点开始，通过自带传感器获取动态环境信息，并根据需要执行等待、正碰或追尾避障策略，到达新的起点.仿真实验表明，该方法可以在动态环境下实时地为移动机器人规划出一条安全且最短的路径，是求解移动机器人路径规划问题的一种切实有效的方法.

关键词: 动态障碍物, 移动机器人, 路径规划, 蚁群算法, 栅格法

Abstract: For the characteristics of being unknown and time-varying of dynamic environment,a new method for mobile robot path planning is proposed in this paper.Firstly,in this method the environment model established by the grid method is convexized in order for the robot to avoid falling into U-shaped traps when moving along the planned path and thus to speed up the path planning.Secondly,a double-layer ant colony optimization(DACO)algorithm is proposed.In each iteration of DACO algorithm,a path is found firstly by the outer ACO algorithm,then on basis of which a small environment is constructed,and then the robot re-plans path by the inner ACO algorithm in the small environment; if the newly obtained path is better,then the global optimal path is updated and a new pheromone secondary update strategy proposed in this paper is executed.At last,three kinds of obstacle avoidance strategies are put forward according to the volume and speed of different dynamic obstacles in the environment.In the dynamic environment,the robot plans a global optimal path from the starting point to the destination with respect to the static environment via the DACO algorithm,then from the current starting point,the robot acquires the dynamic environment's information by its embedded sensor and implements waiting-for-obstacle avoidance strategy,collision avoidance strategy or rear-end collision avoidance strategy when necessary,and then the robot moves to next position as a new starting point.Simulation results show that the proposed can plan a safe and shortest path for mobile robot in real time under dynamic environment and is a practical and effective method for mobile robot path planning.

Key words: dynamic obstacles, mobile robot, path planning, ant colony optimization, grid method

中图分类号:

TP301.6

许凯波, 鲁海燕, 黄洋, 胡士娟. 基于双层蚁群算法和动态环境的机器人路径规划方法[J]. 电子学报, 2019, 47(10): 2166-2176.

XU Kai-bo, LU Hai-yan, HUANG Yang, HU Shi-juan. Robot Path Planning Based on Double-Layer Ant Colony Optimization Algorithm and Dynamic Environment[J]. Acta Electronica Sinica, 2019, 47(10): 2166-2176.

参考文献

[1] 朱大奇,颜明重.移动机器人路径规划技术综述[J].控制与决策,2010,25(7):961-967. ZHU Daqi,YAN Minzhong.Survey on technology of mobile robot path planning[J].Control and Decision,2010,25(7):961-967.(in Chinese)
[2] 李宝磊,吕丹桔,张钦虎,等.基于多元优化算法的路径规划[J].电子学报,2016,44(9):2242-2247. LI Bao-lei,LÜ Dan-ju,ZHANG Qin-hu,et al.A path planner based on multivariant optimization algorithm[J].Acta Electronica Sinica,2016,44(9):2242-2247.(in Chinese)
[3] 强宁,高洁,康凤举.基于PSO和三次样条插值的多机器人全局路径规划[J].系统仿真学报,2017,29(7):1397-1404. QIANG Ning,GAO Jie,Kang Fengju.Multi-robots global path planning based on PSO algorithm and cubic spline[J].Journal of System Simulation,2017,29(7):1397-1404.(in Chinese)
[4] 杜鹏桢,唐振民,陆建峰,等.不确定环境下基于改进萤火虫算法的地面自助车辆全局路径规划方法[J].电子学报,2014,42(3):616-624. DU Peng-zhen,TANG Zhen-min,LU Jian-feng,et al.Global path planning for ALV based on improved glowworm swarm optimization under uncertain environment[J].Acta Electronica Sinica,2014,42(3):616-624.(in Chinese)
[5] 康冰,王曦辉,刘富.基于改进蚁群算法的搜索机器人路径规划[J].吉林大学学报(工学版),2014,44(4):1062-1068. KANG Bing,WANG Xihui,LIU Fu.Path planning of searching robot based on improved ant colony algorithm[J].Journal of Jilin University(Engineering and Technology Edition),2014,44(4):1062-1068.(in Chinese)
[6] 罗德林,吴顺祥.基于势场蚁群算法的机器人路径规划[J].系统工程与电子技术,2010,36(6):1277-1280. LUO Delin,WU Shunxiang.Ant colony optimization with potential field heuristic for robot path planning[J].Systems Engineering and Electronics,2010,36(6):1277-1280.(in Chinese)
[7] 刘建华,杨建国,刘华平,等.基于势场蚁群算法的移动机器人全局路径规划方法[J].农业机械学报,2015,46(9):18-27. LIU Jianhua,YANG Jianguo,LIU Huapin,et al.Robot global path planning based on ant colony optimization with artificial potential field[J].Transactions of the Chinese Society for Agricultural Machinery,2015,46(9):18-27.(in Chinese)
[8] 刘亮.基于改进蚁群算法的移动机器人路径规划[D].武汉:武汉科技大学信息学院,2007. LIU Liang.Mobile Robot'S Path Planning Based on Improved Ant Colony Algorithm[D].Wu Han:Wuhan University of Science and Technology,2007.(in Chinese)
[9] LIU Jianhua,YANG Jianguo,LIU Huaping,et al.An improved ant colony algorithm for robot path planning[J].Soft Computing,2016,21(19):1-11.
[10] 王哲,孙树栋,曹飞祥.动态环境下移动机器人路径规划的改进蚁群算法[J].机械科学与技术,2013,32(1):42-46. WANG Zhe,SUN Shudong,CAO Feixiang.An improved ant colony algorithm for mobile robot path planning under dynamic environment[J].Mechanical Science and Technology for Aerospace Engineering,2013,32(1):42-46.(in Chinese)
[11] 屈鸿,黄利伟,柯星.动态环境下基于改进蚁群算法的机器人路径规划研究[J].电子科技大学学报,2015,44(2):260-265. QU Hong,HUANG Liwei,KE Xing.Research of improved ant colony based on robot path planning under dynamic environment[J].Journal of University of Electronic Science and Technology of China,2015,44(2):260-265.(in Chinese)
[12] ZHU Qingbao,HU Jun,CAI Wenbin.A new robot navigation algorithm for dynamic unknown environments based on dynamic path re-computation and an improved scout ant algorithm[J].Applied Soft Computing,2011,11:4667-4676.
[13] 柳长安,鄢小虎,刘春阳,等.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报,2011,39(5):1220-1224. LIU Chang-an,YAN Xiao-hu,LIU Chun-yang,et al.Dynamic path planning for mobile robot based on improved ant colony optimization algorithm[J].Acta Electronica Sinica,2011,39(5):1220-1224.(in Chinese)
[14] BORENSTEIN J,KOREN Y.Histogramic in-motion mapping for mobile robot obstacle avoidance[J].IEEE Transactions on Robotics and Automation,1991,7(4):535-539.
[15] 邢焕来,潘炜,邹喜华.一种解决组合优化问题的改进型量子遗传算法[J].电子学报,2007,35(10):1999-2007. XING Huan-lai,PAN Wei,ZOU Xi-hua.A novel improved quantum genetic algorithm for combinatorial optimization problem[J].Acta Electronica Sinica,2007,35(10):1999-2007.(in Chinese)
[16] 马卫,朱庆保.求解函数优化问题的快速连续蚁群算法[J].电子学报,2008,36(11):2120-2124. MA Wei,ZHU Qing-bao.Fast continuous ant colony optimization algorithm for solving function optimization problem[J].Acta Electronica Sinica,2008,36(11):2120-2124.(in Chinese)
[17] DORIGO M,GAMBARDELLA M.Ant colonies for the traveling salesman problem[J].BioSystems,1997,43:73-81.
[18] DORIGO M,DI CARO G.Ant colony optimization:A new meta-heuristic[A].Proceedings of the 1999 Congress on Evolutionary Computation[C].USA:IEEE,1999.DOI:10.1109/CEC.1999.782657.
[19] 许凯波,鲁海燕,程毕芸,等.求解TSP的改进信息素二次更新与局部优化蚁群算法[J].计算机应用,2017,37(6):1686-1691. XU Kaibo,LU Hanyan,CHENG Biyun,et al.Ant colony optimization algorithm based on improved pheromones double updating and local optimization for solving TSP[J].Journal of Computer Application,2017,37(6):1686-1691.(in Chinese)

基于双层蚁群算法和动态环境的机器人路径规划方法

Robot Path Planning Based on Double-Layer Ant Colony Optimization Algorithm and Dynamic Environment

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	宣志玮, 毛剑琳, 张凯翔. CBS框架下面向复杂地图的低拓展度A*算法[J]. 电子学报, 2022, 50(8): 1943-1950.
[2]	段世红, 何昊, 徐诚, 殷楠, 王然. 未知环境下基于深度序列蒙特卡罗树搜索的信源导航方法[J]. 电子学报, 2022, 50(7): 1744-1752.
[3]	蒋林, 方东君, 周和文, 黄惠保. 基于射线模型的改进全局路径规划算法[J]. 电子学报, 2022, 50(3): 548-556.
[4]	孙鑫威, 纪爱敏, 陈曦晖, 林新海, 许行. 强噪声背景下动车组轴承微弱故障信号检测[J]. 电子学报, 2021, 49(11): 2217-2224.
[5]	马慧, 汤庸, 何怀文. 主存高效的公交网络路径规划索引[J]. 电子学报, 2021, 49(11): 2273-2278.
[6]	廖伟志, 夏小云, 贾小军. 基于蚁群算法的多路径覆盖测试数据生成[J]. 电子学报, 2020, 48(7): 1330-1342.
[7]	王乐乐, 眭泽智, 蒲志强, 刘振, 易建强. 一种改进RRT的多机器人编队路径规划算法[J]. 电子学报, 2020, 48(11): 2138-2145.
[8]	王秋萍, 王彦军, 戴芳. 多策略集成的樽海鞘群算法的机器人路径规划[J]. 电子学报, 2020, 48(11): 2101-2113.
[9]	王保防, 张瑞雷, 郭健, 陈庆伟. 纵向打滑状态下的轮式移动机器人编队控制[J]. 电子学报, 2017, 45(1): 206-212.
[10]	李宝磊, 吕丹桔, 张钦虎, 施心陵, 陈建华, 张榆锋. 基于多元优化算法的路径规划[J]. 电子学报, 2016, 44(9): 2242-2247.
[11]	李媛祯, 杨群, 赖尚琦, 李博涵. 一种Hadoop Yarn的资源调度方法研究[J]. 电子学报, 2016, 44(5): 1017-1024.
[12]	章刚, 陈庆奎. GCTA:一种群组命令传输算法[J]. 电子学报, 2016, 44(2): 413-419.
[13]	李琳, 应时, 赵翀, 董波. 基于蚁群算法的面向服务软件的部署优化方法[J]. 电子学报, 2016, 44(1): 123-129.
[14]	张红强, 章兢, 周少武, 曾照福, 吴亮红. 基于简化虚拟受力模型的未知复杂环境下群机器人围捕[J]. 电子学报, 2015, 43(4): 665-674.
[15]	易云飞, 蔡永乐, 董文永, 林晓东. 求解带用户满意度的多目标实时车辆路径问题的改进伊藤算法[J]. 电子学报, 2015, 43(10): 2053-2061.