一种蚁群算法与自适应机制的路径规划算法优化

李奇才; 舒远仲; 洪宇轩

doi:10.13433/j.cnki.1003-8728.20200426

一种蚁群算法与自适应机制的路径规划算法优化

doi: 10.13433/j.cnki.1003-8728.20200426

南昌航空大学信息工程学院, 南昌 330063

基金项目:

国家自然科学基金项目 71761028

江西省教育厅科学技术研究项目 209924

详细信息

作者简介:
李奇才(1994-), 硕士研究生, 研究方向为人工智能、机器人等, 1663580500@qq.com

通讯作者:
舒远仲, 教授, 硕士生导师, lqc1663580500@163.com

中图分类号: TP24
计量
- 文章访问数: 94
- HTML全文浏览量: 53
- PDF下载量: 14
- 被引次数: 0
出版历程
- 收稿日期: 2020-10-16
- 刊出日期: 2022-07-25

Optimizing Path Planning Algorithm based on Ant Colony Algorithm and Adaptive Mechanism

School of Information Engineering, Nanchang Hangkong University, Nanchang 330063, China

摘要

摘要: 针对目前移动机器人的路径规划问题，提出一种新的自适应机制建立信息素更新策略，通过增加自适应阈值以及优化蚁群算法生成的路径，使得生成的路径符合真实运动轨迹，提高移动机器人在行走过程中对未知环境的适应性和高效性。首先建立栅格地图和输入初始信息素和设置算法参数，将蚂蚁置于起点并计算当前状态转移概率。然后将获取到的当前自适应阈值与状态转移概率进行比较，根据比较结果选择蚂蚁行走的下一节点，更新路径直到蚂蚁到达终点，直到这一代M只蚂蚁全部遍历。最后动态更新信息启发因子α、期望启发因子β和信息素，重复步骤直到迭代完成，对生成的路径进行优化处理并输出最优路径。实验和应用表明，该方法解决了移动机器人在路径规划开始时缺乏信息素的问题，加快收敛速度，更符合移动机器人行进的运动轨迹，适用于未知动态环境中移动机器人的路径规划。
- 移动机器人 /
- 蚁群算法 /
- 信息素 /
- 自适应机制 /
- 运动轨迹
Abstract: To solve the current path planning problem of a mobile robot, a new adaptive mechanism is proposed to establish the pheromone update strategy. By increasing adaptive thresholds and optimizing the path generated with the ant colony algorithm, the generated path conforms to the real motion trajectory and improves the adaptability and efficiency of a mobile robot to its unknown environment during walking. Firstly, the raster map is established, the initial pheromone is input, and the parameters of the algorithm are set. Ants are placed at the starting point and the transition probability of the current state is calculated. Then we compare the obtained current adaptive threshold with the state transition probability, select the next node for ants to walk according to comparison results and update the path until the ants reach their end point and until all the ants of this generation traverse. Finally, we dynamically update the information heuristic factor α, the expected heuristic factor β and the pheromone. We repeat these steps until the iteration is completed, optimize the generated path and output the optimal path. Experimental and application results show that the optimization method solves the lack of pheromones at the beginning of a mobile robot′s path planning, accelerates convergence speed, conforms to its motion trajectory, being suitable for the path planning of a mobile robot in its unknown dynamic environment.
- mobile robot /
- ant colony algorithm /
- pheromone /
- adaptive mechanism /
- trajectory

HTML全文

图 1 栅格图

下载: 全尺寸图片幻灯片

图 2 路径优化处理

下载: 全尺寸图片幻灯片

图 3 算法原理流程图

下载: 全尺寸图片幻灯片

图 4 优化过程

下载: 全尺寸图片幻灯片

图 5 效果对比图

下载: 全尺寸图片幻灯片

图 6 3种算法的适应度值与迭代次数关系对比

下载: 全尺寸图片幻灯片

图 7 实验过程

下载: 全尺寸图片幻灯片

表 1 实验环境中3种算法仿真结果

名称	传统蚁群算法^[14]	自适应蚁群算法^[15]	本文算法
最短长度	34.02	30.95	25.11
迭代次数	100	70	55
收敛时间/s	7.55	7.84	4.35

下载: 导出CSV

参考文献(15)

[1]	王帅军, 胡立坤, 王一飞. 基于改进D^算法的室内移动机器人路径规划[J]. 计算机工程与设计, 2020, 41(4): 1118-1124 https://www.cnki.com.cn/Article/CJFDTOTAL-SJSJ202004036.htm WANG S J, HU L K, WANG Y F. Path planning of indoor mobile robot based on improved D^ algorithm[J]. Computer Engineering and Design, 2020, 41(4): 1118-1124 (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-SJSJ202004036.htm
[2]	SUGANTHI P H, SUBHA M K. Path navigation in ACO using mobile robot[J]. Journal of Trend in Scientific Research and Development, 2019, 3(3): 164-169
[3]	杨成林, 田书林, 龙兵, 等. 基于启发式图搜索的最小测点集优选新算法[J]. 仪器仪表学报, 2008, 29(12): 2497-2503 doi: 10.3321/j.issn:0254-3087.2008.12.007 YANG C L, TIAN S L, LONG B, et al. New minimum test point set selection algorithm based on heuristic graph search[J]. Chinese Journal of Scientific Instrument, 2008, 29(12): 2497-2503 (in Chinese) doi: 10.3321/j.issn:0254-3087.2008.12.007
[4]	FU B, CHEN L, ZHOU Y T, et al. An improved A* algorithm for the industrial robot path planning with high success rate and short length[J]. Robotics and Autonomous Systems, 2018, 106: 26-37 doi: 10.1016/j.robot.2018.04.007
[5]	郭娜, 李彩虹, 王迪, 等. 结合预测和模糊控制的移动机器人路径规划[J]. 计算机工程与应用, 2020, 56(8): 104-109 https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG202008016.htm GUO N, LI C H, WANG D, et al. Path planning of mobile robot based on prediction and fuzzy control[J]. Computer Engineering and Applications, 2020, 56(8): 104-109 (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG202008016.htm
[6]	王洪斌, 郝策, 张平, 等. 基于A^算法和人工势场法的移动机器人路径规划[J]. 中国机械工程, 2019, 30(20): 2489-2496 doi: 10.3969/j.issn.1004-132X.2019.20.012 WANG H B, HAO C, ZHANG P, et al. Path planning of mobile robots based on A^ algorithm and artificial potential field algorithm[J]. China Mechanical Engineering, 2019, 30(20): 2489-2496 (in Chinese) doi: 10.3969/j.issn.1004-132X.2019.20.012
[7]	李康顺, 徐福梅, 张文生, 等. 一种基于启发式演化算法的最优-最差蚂蚁系统[J]. 中南大学学报(自然科学版), 2010, 41(2): 609-614 https://www.cnki.com.cn/Article/CJFDTOTAL-ZNGD201002039.htm LI K S, XU F M, ZHANG W S, et al. An optimal-worst ant system based on heuristic evolutionary algorithm[J]. Journal of Central South University (Science and Technology), 2010, 41(2): 609-614 (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZNGD201002039.htm
[8]	AMARIF M, ALASHOURY I. The implicit path cost optimization in Dijkstra algorithm using hash map data structure[C]//Computer Science & Information Technology (CS & IT). 2019: 33-44
[9]	LI X L, WANG Y. Scheduling batch processing machine using max-min ant system algorithm improved by a local search method[J]. Mathematical Problems in Engineering, 2018, 2018: 3124182
[10]	王飞鹏, 谭旭杰. 求解旅行商问题的近似骨架分段蚁群优化算法[J]. 计算机工程与设计, 2019, 40(4): 1016-1021, 1105 https://www.cnki.com.cn/Article/CJFDTOTAL-SJSJ201904019.htm WANG F P, TAN X J. Approximate backbone subsection of ACO algorithm for traveling salesman problem[J]. Computer Engineering and Design, 2019, 40(4): 1016-1021, 1105 (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-SJSJ201904019.htm
[11]	ZHAO P, MA X Q, YIN X L. Research on TSP application based on improved ant colony algorithm[C]//Proceedings of 2019 the 9th International Workshop on Computer Science and Engineering. Hong Kong, China, 2019: 420-426
[12]	SARANYA C, RAO K K, UNNIKRISHNAN M, et al. Real time evaluation of grid based path planning algorithms: a comparative study[J]. IFAC Proceedings Volumes, 2014, 47(1): 766-772 doi: 10.3182/20140313-3-IN-3024.00050
[13]	INTERBLOCK D D. Patent issued for roulette game cycle optimization and methods for estimating a bet close time (USPTO 10, 629, 027)[J]. Journal of Engineering, 2020
[14]	SUGANTHI P H, SUBHA M K. Path navigation in ACO using mobile robot[J]. Journal of Trend in Scientific Research and Development, 2019, 3(3): 164-169
[15]	卜冠南, 刘建华, 姜磊, 等. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73 https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG202106009.htm BU G N, LIU J H, JIANG L, et al. Ant colony algorithm with adaptive grouping[J]. Computer Engineering and Applications, 2021, 57(6): 67-73 (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG202106009.htm