B样条曲线融合蚁群算法的机器人路径规划

doi:10.11772/j.issn.1001-9081.2021060888

《计算机应用》唯一官方网站 ›› 2021, Vol. 41 ›› Issue (12): 3558-3564.DOI: 10.11772/j.issn.1001-9081.2021060888

• 第十八届中国机器学习会议(CCML 2021) • 上一篇

B样条曲线融合蚁群算法的机器人路径规划

李二超(), 齐款款

兰州理工大学电气工程与信息工程学院，兰州 730050

收稿日期:2021-05-12 修回日期:2021-06-13 接受日期:2021-07-05 发布日期:2021-12-28 出版日期:2021-12-10
通讯作者: 李二超
作者简介:齐款款（1993—），男，安徽界首人，硕士研究生，主要研究方向：移动机器人。
基金资助:
国家自然科学基金地区项目(62063019);甘肃省自然科学基金资助项目(20JR10RA152)

Robot path planning based on B-spline curve and ant colony algorithm

Erchao LI(), Kuankuan QI

College of Electrical and Information Engineering，Lanzhou University of Technology，Lanzhou Gansu 730050，China

Received:2021-05-12 Revised:2021-06-13 Accepted:2021-07-05 Online:2021-12-28 Published:2021-12-10
Contact: Erchao LI
About author:QI Kuankuan， born in 1993， M. S. candidate. His research interests include mobile robot.
Supported by:
the Fund for Less Developed Regions of National Natural Science Foundation of China(62063019);the Natural Science Foundation of Gansu Province(20JR10RA152)

摘要/Abstract

摘要：

针对蚁群算法在静态环境下全局路径规划存在无法找到最短路径、收敛速度慢、路径搜索盲目性大、拐点多等问题，提出一种改进蚁群算法。以栅格地图为机器人运行环境，对初始信息素进行非均匀分布，使路径搜索更倾向于起点和目标点的连线附近；把当前节点、下一节点和目标点的信息加入启发式函数，同时引入动态调节因子，促使启发函数在迭代前期起主导作用，而后期则加强信息素引导；引入伪随机转移策略，以减少路径选择的盲目性，加快找到最短路径；动态调整挥发系数，使得前期挥发系数大，后期较小，从而避免算法陷入早熟；在最优解的基础上，引入B样条曲线平滑策略，以进一步优化最优解，使得到的路径更短且更加平滑。对改进算法的主要参数进行敏感性分析，并对该算法的各改进环节的可行性与有效性进行了实验，而且在20×20和50×50环境下与传统蚁群算法及其他改进蚁群算法进行仿真对比，实验结果验证了改进算法的可行性、有效性和优越性。

关键词: 移动机器人, 路径规划, 蚁群算法, B样条曲线平滑策略, 栅格地图环境

Abstract:

In view of the problems of ant colony algorithm in global path planning under static environment， such as being unable to find the shortest path， slow convergence speed， great blindness of path search and many inflection points， an improved ant colony algorithm was proposed. Taking the grid map as the running environment of the robot， the initial pheromones were distributed unevenly， so that the path search tended to be near the line between the starting point and the target point； the information of the current node， the next node and the target point was added into the heuristic function， and the dynamic adjustment factor was introduced at the same time， so as to achieve the purpose of strong guidance of the heuristic function in the early stage and strengthening the guidance of pheromone in the later stage； the pseudo-random transfer strategy was introduced to reduce the blindness of path selection and speed up finding the shortest path； the volatilization coefficient was adjusted dynamically to make the volatilization coefficient larger in the early stage and smaller in the later stage， avoiding premature convergence of the algorithm； based on the optimal solution， B-spline curve smoothing strategy was introduced to further optimize the optimal solution， resulting in shorter and smoother path. The sensitivity analysis of the main parameters of the improved algorithm was conducted， the feasibility and effectiveness of each improved step of the algorithm were tested， the simulations compared with the traditional ant colony algorithm and other improved ant colony algorithms under 20×20 and 50×50 environments were given， and the experimental results verified the feasibility， effectiveness and superiority of the improved algorithm.

Key words: mobile robot, path planning, ant colony algorithm, B-spline curve smoothing strategy, grid map environment

中图分类号:

TP242

李二超, 齐款款. B样条曲线融合蚁群算法的机器人路径规划[J]. 计算机应用, 2021, 41(12): 3558-3564.

Erchao LI, Kuankuan QI. Robot path planning based on B-spline curve and ant colony algorithm[J]. Journal of Computer Applications, 2021, 41(12): 3558-3564.

图/表 13

图1 栅格地图

Fig. 1 Grid map

图2 B样条曲线平滑最优路径仿真示意图

Fig. 2 Simulation diagram of B-spline curve smoothing optimal path

图3 改进蚁群算法流程

Fig. 3 Flowchart of improved ant colony algorithm

表1 参数Q对路径长度和迭代次数的影响

Tab. 1 Influence of parameter Q on path length and iteration times

Q	最短路径长度	迭代次数均值
1	48.321 9	42.7
50	47.792 6	57.2
100	47.421 9	53.9
150	46.885 5	52.3
200	46.907 7	60.6

表2 参数［q0， q1］对路径长度和迭代次数的影响

Tab. 2 Influence of parameters ［q0，q1］ on path length and iteration times

［q₀， q₁］	最短路径长度	迭代次数均值
［0.8，0.9］	46.671 3	49.4
［0.7，0.9］	46.605 6	66.9
［0.7，0.8］	46.659 1	55.4
［0.6，0.9］	46.900 6	63.4
［0.6，0.8］	47.237 0	62.1
［0.6，0.7］	46.705 6	66.2
［0.5，0.9］	48.109 8	54.4
［0.5，0.8］	48.704 7	72.3
［0.5，0.7］	48.368 3	54.7
［0.5，0.6］	48.887 6	59.9

表3 参数［ρmin，ρmax］对路径长度和迭代次数的影响

Tab. 3 Influence of parameters ［ρmin，ρmax］ on path length and iteration times

［ $ρ m i n$ ， $ρ m a x$ ］	最短路径长度	迭代次数均值
［0.1，0.9］	46.812 7	55.9
［0.1，0.8］	46.647 0	64.7
［0.1，0.7］	46.547 0	54.6
［0.2，0.9］	46.737 0	71.6
［0.2，0.8］	46.564 2	53.0
［0.2，0.7］	46.588 4	53.5
［0.3，0.9］	46.605 6	55.7
［0.3，0.8］	46.310 6	54.8
［0.3，0.7］	46.429 9	68.2

表3 参数［ρmin，ρmax］对路径长度和迭代次数的影响

Tab. 3 Influence of parameters ［ρmin，ρmax］ on path length and iteration times

［ $ρ m i n$ ， $ρ m a x$ ］	最短路径长度	迭代次数均值
［0.1，0.9］	46.812 7	55.9
［0.1，0.8］	46.647 0	64.7
［0.1，0.7］	46.547 0	54.6
［0.2，0.9］	46.737 0	71.6
［0.2，0.8］	46.564 2	53.0
［0.2，0.7］	46.588 4	53.5
［0.3，0.9］	46.605 6	55.7
［0.3，0.8］	46.310 6	54.8
［0.3，0.7］	46.429 9	68.2

表4 参数［α，β］对路径长度和迭代次数的影响

Tab. 4 Influence of parameters ［α，β］ on path length and iteration times

［ $α$ ， $β$ ］	最短路径长度	迭代次数均值
［1，1］	47.092 6	63.1
［1， 2］	47.061 2	44.9
［1， 3］	46.800 6	54.6
［1， 4］	46.471 3	58.4
［1， 5］	46.724 8	48.0
［1， 6］	46.610 6	63.1
［1， 8］	46.564 2	56.5
［1， 10］	46.659 1	49.9
［0.8， 4］	46.822 7	58.4
［2， 4］	47.021 9	52.2

表4 参数［α，β］对路径长度和迭代次数的影响

Tab. 4 Influence of parameters ［α，β］ on path length and iteration times

［ $α$ ， $β$ ］	最短路径长度	迭代次数均值
［1，1］	47.092 6	63.1
［1， 2］	47.061 2	44.9
［1， 3］	46.800 6	54.6
［1， 4］	46.471 3	58.4
［1， 5］	46.724 8	48.0
［1， 6］	46.610 6	63.1
［1， 8］	46.564 2	56.5
［1， 10］	46.659 1	49.9
［0.8， 4］	46.822 7	58.4
［2， 4］	47.021 9	52.2

图4 20×20运行环境下不同方案的最优路径对比

Fig. 6 Comparison of optimal paths of different schemes in 20×20 running environment

图5 20×20运行环境下各算法平滑前后最优路径对比

Fig. 5 Comparison of optimal paths of each algorithm before and after smoothing in 20×20 running environment

表5 20×20运行环境下的仿真结果

Tab. 5 Simulation results in 20×20 running environment

算法	路径长度				最短路径次数	本文B样条平滑路径	拐点数目				迭代次数均值	运行时间均值/s
算法	最优值	最大值	平均值	标准差	最短路径次数	本文B样条平滑路径	最小	最大	均值	标准差	迭代次数均值	运行时间均值/s
方案1	36.242 6	37.414 2	36.805 0	0.16	3	—	4	11	7.1	1.40	20.4	7.144 5
方案2	35.071 1	36.242 6	35.774 0	0.33	4	—	22	28	25.1	1.10	43.6	6.289 6
方案3	28.627 4	28.627 4	28.627 4	0.00	50	—	4	8	4.5	1.02	1.0	4.886 1
传统算法	41.414 2	61.414 2	50.199 3	4.35	1	39.241 0	13	41	28.1	5.70	5.9	10.846 7
文献［16］算法	28.627 4	30.627 4	29.485 5	0.58	9	28.377 8	4	16	8.6	2.59	4.0	4.121 4
本文算法	28.627 4	28.627 4	28.627 4	0.00	50	28.377 8	4	6	4.3	0.74	1.0	3.730 4

图6 50×50复杂环境下各算法平滑前后最优路径对比

Fig. 6 Comparison of optimal paths of each algorithm before and after smoothing in 50 × 50 complex environment

图7 50×50复杂环境下各算法收敛曲线

Fig. 7 Convergence curve of each algorithm in 50 × 50 complex environment

表6 50×50复杂环境下三种算法的仿真结果

Tab. 6 Simulation results of three algorithms in 50 × 50 complex environment

算法	路径长度				最短次数	本文B样条平滑路径	拐点数目				迭代次数均值	运行时间均值/s
算法	最优值	最大值	平均值	标准差	最短次数	本文B样条平滑路径	最小	最大	均值	标准差	迭代次数均值	运行时间均值/s
传统算法	159.899 5	333.982 8	235.697 9	42.40	1	146.179 5	102	232	155.8	30.44	52.0	23.272 0
文献［16］算法	78.083 3	98.911 7	86.409 2	3.82	1	75.956 7	34	60	44.8	5.07	57.9	20.044 6
本文算法	71.639 6	71.639 6	71.639 6	0.00	50	70.974 1	14	16	15.9	0.49	1.9	16.208 5

参考文献 16

1	杨凯，龙佳，马雪燕，等. 移动机器人改进人工势场的路径规划方法研究［J］. 现代电子技术， 2020， 43（7）：141-145.
	YANG K， LONG J， MA X Y， et al. Research on mobile robot path planning method based on improved artificial potential field ［J］. Modern Electronics Technology， 2020， 43（7）：141-145.
2	宋宇，王志明. 改进A星算法移动机器人路径规划［J］. 长春工业大学学报， 2019， 40（2）：138-141.
	SONG Y， WANG Z M. Path planning simulation based on improved A star algorithm［J］. Journal of Changchun University of Technology， 2019， 40（2）：138-141.
3	王玉，沈丹峰，李耀杰，等. 融合跳点搜索与双向蚁群算法的AGV路径规划［J］. 西安工程大学学报， 2021， 35（1）：37-43. 10.13338/j.issn.1674-649x.2021.01.006
	WANG Y， SHEN D F， LI Y J， et al. Path planning of AGV based on JPS bidirectional ant colony algorithm［J］. Journal of Xi’an Polytechnic University， 2021， 35（1）：37-43. 10.13338/j.issn.1674-649x.2021.01.006
4	刘超. 基于改进遗传算法的多无人机航路规划方法［J］. 火力与指挥控制， 2019， 44（1）：18-22. 10.3969/j.issn.1002-0640.2019.01.004
	LIU C. Method of path planning for multi-UAV based on improved genetic algorithm［J］. Fire Control and Command Control， 2019， 44（1）：18-22. 10.3969/j.issn.1002-0640.2019.01.004
5	赵开新，王东署，徐立新. 蚁群遗传算法在移动机器人路径规划中的综合应用研究［J］. 制造业自动化， 2014， 36（17）：70-72， 84. 10.3969/j.issn.1009-0134.2014.17.018
	ZHAO K X， WANG D S， XU L X. Comprehensive application of ant colony genetic algorithm in mobile robot path planning［J］. Manufacturing Automation， 2014， 36（17）：70-72， 84. 10.3969/j.issn.1009-0134.2014.17.018
6	王晓燕，杨乐，张宇，等. 基于改进势场蚁群算法的机器人路径规划［J］. 控制与决策， 2018， 33（10）：1775-1781. 10.13195/j.kzyjc.2017.0639
	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. 10.13195/j.kzyjc.2017.0639
7	刘泽，金世俊，王庆. 基于改进蚁群算法的移动机器人二维路径规划［J］. 传感器与微系统， 2020， 39（10）：149-152. 10.4028/www.scientific.net/amm.385-386.717
	LIU Z， JIN S J， WANG Q. 2D path planning of mobile robots based on improved ant colony algorithm［J］. Transducer and Microsystem Technologies， 2020， 39（10）：149-152. 10.4028/www.scientific.net/amm.385-386.717
8	孟冠军，陈信华，陶细佩，等. 基于混合蚁群算法的AGV路径规划［J］. 组合机床与自动化加工技术， 2021（1）：70-73.
	MENG G J， CHEN X H， TAO X P， et al. AGV path planning based on hybrid ant colony algorithm［J］. Modular Machine Tool and Automatic Processing Technique， 2021（1）：70-73.
9	曹新亮，王智文，冯晶，等. 基于改进蚁群算法的机器人全局路径规划研究［J］. 计算机工程与科学， 2020， 42（3）：564-570. 10.3969/j.issn.1007-130X.2020.03.025
	CAO X L， WANG Z W， FENG J， et al. Global path planning of robots path planning based on improved ant colony algorithm［J］. Computer Engineering and Science， 2020， 42（3）：564-570. 10.3969/j.issn.1007-130X.2020.03.025
10	王红君，徐军，赵辉，等. 基于平滑蚁群算法的机器人路径规划［J］. 燕山大学学报， 2017， 41（3）：278-282. 10.3969/j.issn.1007-791X.2017.03.012
	WANG H J， XU J， ZHAO H， et al. Mobile robot path planning based on smoothing ant colony algorithm［J］. Journal of Yanshan University， 2017， 41（3）：278-282. 10.3969/j.issn.1007-791X.2017.03.012
11	LUO Q， WANG H B， ZHENG Y， et al. Research on path planning of mobile robot based on improved ant colony algorithm［J］. Neural Computing and Applications， 2020， 32（6）：1555-1566. 10.1007/s00521-019-04172-2
12	李志锟，黄宜庆，徐玉琼. 改进变步长蚁群算法的移动机器人路径规划［J］. 电子测量与仪器学报， 2020， 34（8）：15-21.
	LI Z K， HUANG Y Q， XU Y Q. Path planning of mobile robot based on improved variable step size ant colony algorithm［J］. Journal of Electronic Measurement and Instrumentation， 2020， 34（8）：15-21.
13	胡浍冕，于修成. 基于双向搜索策略的改进蚁群路径规划算法［J］. 农业装备与车辆工程， 2019， 57（7）：9-12， 20. 10.3969/j.issn.1673-3142.2019.07.003
	HU H M， YU X C. Improved ant colony path planning algorithm based on bidirectional search strategy［J］. Agricultural Equipment and Vehicle Engineering， 2019， 57（7）：9-12， 20. 10.3969/j.issn.1673-3142.2019.07.003
14	张军明，张德祥，王硕. 基于优化蚁群算法的机器人路径规划［J］. 自动化技术与应用， 2016， 35（11）：6-10， 29. 10.1142/9789813220362_0097
	ZHANG J M， ZHANG D X， WANG S. Path planning of robot based on ant colony algorithm［J］. Techniques of Automation and Applications， 2016， 35（11）： 6-10， 29. 10.1142/9789813220362_0097
15	封声飞，雷琦，吴文烈，等. 自适应蚁群算法的移动机器人路径规划［J］. 计算机工程与应用， 2019， 55（17）：35-43. 10.3778/j.issn.1002-8331.1903-0401
	FENG S F， LEI Q， WU W L， et al. Mobile robot path planning based on adaptive ant colony algorithm［J］. Computer Engineering and Applications， 2019， 55（17）： 35-43. 10.3778/j.issn.1002-8331.1903-0401
16	赵静，汤云峰，蒋国平，等. 基于改进蚁群算法的移动机器人路径规划［J］. 南京邮电大学学报（自然科学版）， 2019， 39（6）：73-78. 10.14132/j.cnki.1673-5439.2019.06.011
	ZHAO J， TANG Y F， JIANG G P， et al. Mobile robot path planning based on improved ant colony algorithm［J］. Journal of Nanjing University of Posts and Telecommunications （Natural Science Edition）， 2019， 39（6）：73-78. 10.14132/j.cnki.1673-5439.2019.06.011

[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]	段宇君, 王耀力, 常青, 刘鑫. 改进型蚁群算法融合混沌优化的pSPIEL算法的无线传感器布局优化[J]. 计算机应用, 2020, 40(3): 793-798.
[13]	屈立成, 吕娇, 赵明, 王海飞, 屈艺华. 基于三维时空地图和运动分解的多机器人路径规划算法[J]. 计算机应用, 2020, 40(12): 3499-3507.
[14]	徐小强, 王明勇, 冒燕. 基于改进人工势场法的移动机器人路径规划[J]. 计算机应用, 2020, 40(12): 3508-3512.
[15]	童心赤, 张华军, 郭航. 多方向无人水面艇路径规划算法[J]. 计算机应用, 2020, 40(11): 3373-3378.

B样条曲线融合蚁群算法的机器人路径规划

Robot path planning based on B-spline curve and ant colony algorithm

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 16

相关文章 15

编辑推荐

Metrics