单种群自适应异构蚁群算法的机器人路径规划

doi:10.3778/j.issn.1673-9418.2107086

计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (12): 2820-2831.DOI: 10.3778/j.issn.1673-9418.2107086

单种群自适应异构蚁群算法的机器人路径规划

张松灿¹^,², 孙力帆¹^,⁺(), 司彦娜¹, 普杰信¹

1.河南科技大学信息工程学院，河南洛阳 471023
2.河南科技大学电气工程学院，河南洛阳 471023

收稿日期:2021-07-22 修回日期:2021-09-29 出版日期:2022-12-01 发布日期:2021-10-18
通讯作者: +E-mail: lifan.sun@gmail.com
作者简介:张松灿（1973—），男，河南郑州人，博士研究生，主要研究方向为群智能算法、移动机器人智能控制。
孙力帆（1982—），男，河南洛阳人，博士，副教授，主要研究方向为扩展目标跟踪、信息融合。
司彦娜（1990—），女，河南郑州人，博士研究生，主要研究方向为强化学习、机器人智能控制。
普杰信（1959—），男，河南周口人，博士，教授，博士生导师，主要研究方向为智能信息处理、机器人智能控制。
基金资助:
国家自然科学基金(U1504619);国家“十三五”装备预研领域基金资助项目(61403120207);国家“十三五”装备预研领域基金资助项目(61402100203);航空科学基金资助项目(20185142003);河南省高校科技创新人才资助项目(21HASTIT030);河南省高等学校青年骨干教师资助项目(2020GGJS073);中原科技创新领军人才资助项目(194200510012)

Single-Colony Adaptive Heterogeneous Ant Colony Algorithm for Mobile Robot Path Planning

ZHANG Songcan¹^,², SUN Lifan¹^,⁺(), SI Yanna¹, PU Jiexin¹

1. School of Information Engineering, Henan University of Science & Technology, Luoyang, Henan 471023, China
2. School of Electrical Engineering, Henan University of Science & Technology, Luoyang, Henan 471023, China

Received:2021-07-22 Revised:2021-09-29 Online:2022-12-01 Published:2021-10-18
About author:ZHANG Songcan, born in 1973, Ph.D. candidate. His research interests include swarm intelligence algorithms and intelligent control of mobile robot.
SUN Lifan, born in 1982, Ph.D., associate professor. His research interests include extended target tracking and information fusion.
SI Yanna, born in 1990, Ph.D. candidate. Her research interests include reinforcement learning and intelligent control of robot.
PU Jiexin, born in 1959, Ph.D., professor, Ph.D. supervisor. His research interests include intelligent information processing and intelligent control of robot.
Supported by:
National Natural Science Foundation of China(U1504619);National “Thirteen-Five” Equipment Pre-Research Foundation of China(61403120207);National “Thirteen-Five” Equipment Pre-Research Foundation of China(61402100203);Aeronautical Science Foundation of China(20185142003);Program of Science and Technology Innovative Talents in Universities of Henan Province(21HASTIT030);Program of Young Backbone Teachers in Universities of Henan Province(2020GGJS073);Program of Leading Talents of Science and Technology Innovation in the Central Plains of China(194200510012)

摘要/Abstract

摘要：

针对多种群蚁群算法存在结构复杂、优化速度慢及适应性不足等问题，提出一种单种群自适应异构蚁群算法，并用于机器人路径规划。该算法采用单种群结构，避免多蚁群算法结构复杂的问题；种群内每只蚂蚁都有自己的控制参数，实现蚂蚁的行为异构，增加种群的多样性；在首次迭代时，仅用启发因子构建候选解，提高了初始化种群的质量；根据蚁群优化过程中种群信息熵的变化，自适应确定信息交换周期；所设计的信息交换策略将最优蚂蚁的控制参数传递给最差蚂蚁，增强最优蚂蚁的引导作用；参数突变操作有助于在更大的参数空间探索更优的控制参数，提高算法逃离局部最优的能力。仿真实验与统计检验的结果验证了所提算法的有效性、稳定性和优越性。

关键词: 蚁群算法, 种群信息熵, 移动机器人, 路径规划, 自适应信息交换周期, 状态转移规则, 参数突变

Abstract:

Aiming at the existent problems of complex structure, slow optimization rate and inadequate adaptability of multi-colony ant colony algorithm, a single colony adaptive heterogeneous ant colony algorithm is proposed to solve mobile robot path planning. The proposed algorithm employs a single colony to avoid the problem of complex structure of multi-ant colony algorithm. Each ant in the colony has its own control parameters to realize the hete-rogeneous behavior and increase the diversity of the population. In the first iteration, only the heuristic factor is used to construct the candidate solution, which improves the quality of the initial population. The information exchange period is adaptively determined based on the change of population information entropy to enhance the adaptability of the algorithm. The information exchange strategy transfers the control parameters of the optimal ant to the worst ant to enhance the guiding role of the optimal ant. Parameter mutation operation is helpful for exploring better algo-rithm parameters in a larger parameter space and improving the ability to escape from local optimization. The results of simulation experiments and statistical tests verify the effectiveness, stability and superiority of the pro-posed algorithm.

Key words: colony algorithm, population information entropy, mobile robot, path planning, adaptive information exchange period, state transition rule, parameter mutation

中图分类号:

TP18

张松灿, 孙力帆, 司彦娜, 普杰信. 单种群自适应异构蚁群算法的机器人路径规划[J]. 计算机科学与探索, 2022, 16(12): 2820-2831.

ZHANG Songcan, SUN Lifan, SI Yanna, PU Jiexin. Single-Colony Adaptive Heterogeneous Ant Colony Algorithm for Mobile Robot Path Planning[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(12): 2820-2831.

图/表 14

图1 二维栅格环境示意图

Fig.1 Example of grid-based environment

图2 信息交换周期曲线

Fig.2 Curve of information exchange period

图3 自适应异构蚁群算法流程图

Fig.3 Flowchart of AHACO for path planning

表1 算法参数设置

Table 1 Parameter setting of algorithms

算法	$α$	$β$	$ρ$	$ξ$	$q 0$
MMAS	1.1	7	0.200	—	—
ACS	1.1	7	0.200	0.2	0.8
CACS	1.0	4	0.100	0.3	0.8
PS-ACO	1.0	2	0.015	—	—
AHACO	1.1	7	0.200	—	—

表1 算法参数设置

Table 1 Parameter setting of algorithms

算法	$α$	$β$	$ρ$	$ξ$	$q 0$
MMAS	1.1	7	0.200	—	—
ACS	1.1	7	0.200	0.2	0.8
CACS	1.0	4	0.100	0.3	0.8
PS-ACO	1.0	2	0.015	—	—
AHACO	1.1	7	0.200	—	—

图4 map1环境AHACO算法得到的最优路径

Fig.4 Optimal path generated by AHACO under grid map1

图5 map2环境AHACO算法得到的最优路径

Fig.5 Optimal path generated by AHACO under grid map2

表2 map1环境不同信息交换周期的实验统计结果

Table 2 Statistical results of different periods for information exchange in map1

信息交换周期	best	mean	std	fbest	rate/%
2	45.698 5	45.891 8	0.356 4	25.13	76.67
4	45.698 5	45.891 8	0.356 4	24.97	76.67
6	45.698 5	45.891 8	0.356 4	27.03	76.60
8	45.698 5	45.891 8	0.356 4	25.50	76.67
10	45.698 5	45.891 8	0.356 4	25.90	76.67
12	45.698 5	45.891 8	0.356 4	25.17	76.67
Adaptive	45.698 5	45.792 8	0.248 6	37.03	86.67

表3 map2环境不同信息交换周期的实验统计结果

Table 3 Statistical results of different periods for information exchange in map2

信息交换周期	best	mean	std	fbest	rate/%
2	73.982 8	74.671 7	0.592 2	53.63	33.33
4	73.982 8	74.605 1	0.550 7	54.57	36.67
6	73.982 8	74.605 1	0.550 7	54.03	36.67
8	73.982 8	74.605 1	0.550 7	52.73	36.67
10	73.982 8	74.605 1	0.550 7	54.00	36.67
12	73.982 8	74.605 1	0.550 7	57.70	36.67
Adaptive	73.982 8	74.384 1	0.468 8	51.43	53.33

图6 不同规模环境下AHACO算法得到的最优路径

Fig.6 Optimal path generated by AHACO in grid maps with different scales

表4 不同环境下路径规划统计结果

Table 4 Statistical results of path planning under different grid maps

Environment	Algorithm	best	mean	std	fbest	rate/%	Environment	Algorithm	best	mean	std	fbest	rate/%
map3	MMAS	29.799 0	29.909 4	0.286 4	14.97	86.67	map5	MMAS	92.526 9	95.153 4	2.267 4	35.93	10.00
	ACS	29.799 0	29.799 0	0	32.57	100.00		ACS	91.698 5	93.848 2	1.094 4	117.10	3.33
	CACS	29.799 0	29.951 8	0.296 9	38.10	76.67		CACS	95.598 0	99.154 4	1.731 9	70.17	3.33
	PS-ACO	30.627 4	32.694 9	1.689 1	16.53	10.00		PS-ACO	95.840 6	100.912 0	3.260 0	40.00	3.33
	AHACO	29.799 0	29.799 0	0	19.20	100.00		AHACO	90.041 6	92.268 9	0.910 3	79.93	6.67
map4	MMAS	58.083 3	58.102 8	0.106 9	44.30	96.67	map6	MMAS	90.468 0	92.562 0	0.813 7	37.10	3.33
	ACS	58.083 3	58.083 3	0	16.40	100.00		ACS	90.124 9	91.820 0	0.848 7	74.63	3.33
	CACS	58.083 3	59.841 4	0.855 9	61.33	6.67		CACS	94.953 3	97.408 5	1.261 2	22.00	6.67
	PS-ACO	59.497 4	63.837 5	2.038 0	19.00	3.33		PS-ACO	93.781 7	99.417 4	3.162 2	90.66	3.33
	AHACO	58.083 3	58.259 0	0.273 0	44.13	70.00		AHACO	89.296 5	91.213 9	0.824 2	66.00	3.33

图7 不同规模环境下的算法收敛曲线

Fig.7 Convergence curves of algorithms in grid maps with different scales

图8 不同规模环境下的种群信息熵曲线

Fig.8 Population information entropy curves in grid maps with different scales

表5 Wilcoxon符号秩检验结果

Table 5 Results of Wilcoxon sign rank test

地图	AHACO vs. MMAS	AHACO vs. ACS	AHACO vs. CACS	AHACO vs. PS-ACO
map3	4.55E-02 +	1.00E+00 =	1.39E-02 +	1.57E-06 +
map4	1.14E-02 +	2.70E-03 +	1.17E-05 +	1.17E-05 +
map5	6.60E-06 +	3.55E-05 +	1.73E-06 +	1.73E-06 +
map6	3.43E-05 +	3.05E-02 +	1.73E-06 +	1.73E-06 +
+/=/-	4/0/0	3/1/0	4/0/0	4/0/0

表6 Friedman检验结果

Table 6 Results of Friedman test

$p$ value	AHACO	MMAS	ACS	CACS	PS-ACO
0.006	1.625	2.750	1.625	4.000	5.000

表6 Friedman检验结果

Table 6 Results of Friedman test

$p$ value	AHACO	MMAS	ACS	CACS	PS-ACO
0.006	1.625	2.750	1.625	4.000	5.000

参考文献 24

[1]	PEYER S, RAUTENBACH D, VYGEN J. A generalization of Dijkstra’s shortest path algorithm with applications to VLSI routing[J]. Journal of Discrete Algorithms, 2009, 7(4): 377-390. DOI URL
[2]	GURUJI A K, AGARWAL H, PARSEDIYA D. Time-efficient A* algorithm for robot path planning[J]. Procedia Tech-nology, 2016, 23: 144-149.
[3]	黄鲁, 周非同. 基于路径优化D* Lite算法的移动机器人路径规划[J]. 控制与决策, 2020, 35(4): 877-884.
	HUANG L, ZHOU F T. Path planning of moving robot based on path optimization of D* Lite algorithm[J]. Control and Decision, 2020, 35(4): 877-884.
[4]	SINGH M K, PARHI D R. Path optimisation of a mobile robot using an artificial neural network controller[J]. Inter-national Journal of Systems Science, 2011, 42(1): 107-120.
[5]	KARAMI A H, HASANZADEH M. An adaptive genetic algorithm for robot motion planning in 2D complex environ-ments[J]. Computers & Electrical Engineering, 2015, 43: 317-329.
[6]	LEE H Y, SHIN H, CHAE J. Path planning for mobile agents using a genetic algorithm with a direction guided factor[J]. Electronics, 2018, 7(10): 212. DOI URL
[7]	PRADHAN S K, PARHI D R, PANDA A K. Fuzzy logic tech-niques for navigation of several mobile robots[J]. Applied Soft Computing, 2009, 9(1): 290-304. DOI URL
[8]	LI G, CHOU W. Path planning for mobile robot using self-adaptive learning particle swarm optimization[J]. Science China Information Sciences, 2018, 61(5): 052204. DOI URL
[9]	王晓燕, 杨乐, 张宇, 等. 基于改进势场蚁群算法的机器人路径规划[J]. 控制与决策, 2018, 33(10): 1775-1781.
	WANG X Y, YANG L, ZHANG Y, et al. Robot path plan-ning based on improved ant colony algorithm with poten-tial field heuristic[J]. Control and Decision, 2018, 33(10): 1775-1781.
[10]	朱佳莹, 高茂庭. 融合粒子群与改进蚁群算法的AUV路径规划算法[J]. 计算机工程与应用, 2021, 57(6): 267-273. DOI
	ZHU J Y, GAO M T. AUV path planning based on particle swarm optimization and improved ant colony optimization[J]. Computer Engineering and Applications, 2021, 57(6): 267-273. DOI
[11]	陈雄, 袁杨. 一种机器人路径规划的蚁群算法[J]. 系统工程与电子技术, 2008, 30(5): 952-955.
	CHEN X, YUAN Y. Novel ant colony optimization algori-thm for robot path planning[J]. Journal of Systems Enginee-ring and Electronics, 2008, 30(5): 952-955.
[12]	BAI J, YANG G K, CHEN Y W, et al. A model induced max-min ant colony optimization for asymmetric traveling salesman problem[J]. Applied Soft Computing, 2013, 13(3): 1365-1375. DOI URL
[13]	LEE J. Heterogeneous-ants-based path planner for global path planning of mobile robot applications[J]. International Journal of Control, Automation and Systems, 2017, 15(4): 1754-1769. DOI URL
[14]	SREEJA N, SANKAR A. A hierarchical heterogeneous ant colony optimization based approach for efficient action rule mining[J]. Swarm and Evolutionary Computation, 2016, 29: 1-12. DOI URL
[15]	张德惠, 游晓明, 刘升. 融合猫群算法的动态分组蚁群算法[J]. 计算机科学与探索, 2020, 14(5): 880-891. DOI URL
	ZHANG D H, YOU X M, LIU S. Dynamic grouping ant colony algorithm combined with cat swarm optimization[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(5): 880-891. DOI URL
[16]	ZHANG D, YOU X, LIU S, et al. Dynamic multi-role adap-tive collaborative ant colony optimization for robot path planning[J]. IEEE Access, 2020, 8: 129958-129974. DOI URL
[17]	GÜLCÜ Ş, MAHI M, BAYKAN Ö K. et al. A parallel coope-rative hybrid method based on ant colony optimization and 3-Opt algorithm for solving traveling salesman problem[J]. Soft Computing, 2018, 22(5): 1669-1685. DOI URL
[18]	万正宜, 彭玉旭. 求解旅行商问题的改进型量子蚁群算法[J]. 计算机工程与应用, 2016, 52(22): 59-63.
	WAN Z Y, PENG Y X. Improved quantum ant colony algo-rithm for traveling salesman problem[J]. Computer Enginee-ring and Applications, 2016, 52(22): 59-63.
[19]	MAHI M, BAYKAN Ö K, KODAZ H. A new hybrid met-hod based on particle swarm optimization, ant colony opti-mization and 3-opt algorithms for traveling salesman pro-blem[J]. Applied Soft Computing, 2015, 30: 484-490. DOI URL
[20]	STÜTZLE T, HOOS H H. MAX-MIN ant system[J]. Future Generation Computer Systems, 2000, 16(8): 889-914. DOI URL
[21]	张松灿, 普杰信, 司彦娜, 等. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77. DOI
	ZHANG S C, PU J X, SI Y N, et al. Adaptive improved ant colony algorithm based on population similarity and its appli-cation[J]. Computer Engineering and Applications, 2021, 57(8): 70-77.
[22]	刘广瑞, 刘军, 孔令云. 移动机器人路径规划蚁群算法及其收敛性分析[J]. 郑州大学学报(工学版), 2012, 33(2): 24-27.
	LIU G R, LIU J, KONG L Y. Ant colony algorithm of path planning for robot and its convergence analysis[J]. Journal of Zhengzhou University (Engineering Science), 2012, 33(2): 24-27.
[23]	SHUANG B, CHEN J, LI Z. Study on hybrid PS-ACO algo-rithm[J]. Applied Intelligence, 2011, 34(1): 64-73. DOI URL
[24]	DERRAC J, GARCÍA S, MOLINA D, et al. A practical tuto-rial on the use of nonparametric statistical tests as a metho-dology for comparing evolutionary and swarm intelligence algorithms[J]. Swarm and Evolutionary Computation, 2011, 1(1): 3-18. DOI URL

单种群自适应异构蚁群算法的机器人路径规划

Single-Colony Adaptive Heterogeneous Ant Colony Algorithm for Mobile Robot Path Planning

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 24

相关文章 15

编辑推荐

Metrics

[1]	张硕航, 郭改枝. 多旅行商模型及其应用研究综述[J]. 计算机科学与探索, 2022, 16(7): 1516-1528.
[2]	赵家波, 游晓明, 刘升. 结合价格波动策略与动态回溯机制的蚁群算法[J]. 计算机科学与探索, 2022, 16(6): 1390-1404.
[3]	陈达, 游晓明, 刘升. 引入特征迁移和匹配学习的双蚁型蚁群算法[J]. 计算机科学与探索, 2022, 16(12): 2797-2808.
[4]	莫亚东, 游晓明, 刘升. 融合奖惩学习策略的动态分级蚁群算法[J]. 计算机科学与探索, 2021, 15(9): 1703-1716.
[5]	曹凯, 陈阳泉, 高嵩, 高佳佳. 涡流人工势场引导下的RRT*移动机器人路径规划[J]. 计算机科学与探索, 2021, 15(4): 723-732.
[6]	孟静雯，游晓明，刘升. 结合协同机制与动态调控策略的双蚁群算法[J]. 计算机科学与探索, 2021, 15(11): 2206-2221.
[7]	张庆，刘旭，彭力，朱凤增. 融合JPS和改进A*算法的移动机器人路径规划[J]. 计算机科学与探索, 2021, 15(11): 2233-2240.
[8]	殷绍伟, 彭力, 戴菲菲. 融合改进A*蚁群和滚动窗口法的平滑路径规划[J]. 计算机科学与探索, 2021, 15(10): 1969-1979.
[9]	潘晗，游晓明，刘升. 考虑动态导向与邻域交互的双蚁型算法[J]. 计算机科学与探索, 2020, 14(6): 1005-1016.
[10]	张德惠，游晓明，刘升. 融合猫群算法的动态分组蚁群算法[J]. 计算机科学与探索, 2020, 14(5): 880-891.
[11]	冯志雨，游晓明，刘升. 分层递进的改进聚类蚁群算法解决TSP问题[J]. 计算机科学与探索, 2019, 13(8): 1280-1294.
[12]	刘新宇，谭力铭，杨春曦，翟持. 未知环境下的蚁群-聚类自适应动态路径规划[J]. 计算机科学与探索, 2019, 13(5): 846-857.
[13]	郭羽含，胡芳霞. 考虑匹配可行性的长期合乘问题建模与求解[J]. 计算机科学与探索, 2019, 13(11): 1894-1910.
[14]	朱宏伟，游晓明，刘升. 协同过滤策略的异构双种群蚁群算法[J]. 计算机科学与探索, 2019, 13(10): 1754-1767.
[15]	任珂欣，王兴伟，马连博，黄敏. 蚁群分工启发的ICN负载均衡机制[J]. 计算机科学与探索, 2018, 12(7): 1109-1116.