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

doi:10.3778/j.issn.1673-9418.2107086

Journal of Frontiers of Computer Science and Technology ›› 2022, Vol. 16 ›› Issue (12): 2820-2831.DOI: 10.3778/j.issn.1673-9418.2107086

• Artificial Intelligence • Previous Articles Next Articles

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)

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

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

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

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

摘要：

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

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

CLC Number:

TP18

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.

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

Figures/Tables 14

Fig.1 Example of grid-based environment

Fig.2 Curve of information exchange period

Fig.3 Flowchart of AHACO for path planning

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	—	—

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	—	—

Fig.4 Optimal path generated by AHACO under grid map1

Fig.5 Optimal path generated by AHACO under grid map2

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

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

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

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

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

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

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

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

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

References 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

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 24

Related Articles 15

Recommended Articles

Metrics

[1]	ZHANG Shuohang, GUO Gaizhi. Review of Multiple Traveling Salesman Model and Its Application [J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(7): 1516-1528.
[2]	ZHAO Jiabo, YOU Xiaoming, LIU Sheng. Ant Colony Algorithm Based on Price Fluctuation Strategy and Dynamic Backtracking Mechanism [J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(6): 1390-1404.
[3]	CHEN Da, YOU Xiaoming, LIU Sheng. Dual Ant Colony Algorithm Based on Backtracking Migration and Matching Learning [J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(12): 2797-2808.
[4]	CAO Kai, CHEN Yangquan, GAO Song, GAO Jiajia. Vortex Artificial-Potential-Field Guided RRT* for Path Planning of Mobile Robot [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(4): 723-732.
[5]	MENG Jingwen, YOU Xiaoming, LIU Sheng. Double Ant Colony Algorithm Based on Collaborative Mechanism and Dynamic Regulation Strategy [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(11): 2206-2221.
[6]	ZHANG Qing, LIU Xu, PENG Li, ZHU Fengzeng. Path Planning for Mobile Robots Based on JPS and Improved A* Algorithm [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(11): 2233-2240.
[7]	YIN Shaowei, PENG Li, DAI Feifei. Smooth Path Planning Based on Improved A* Ant Colony and Rolling Window Method [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(10): 1969-1979.
[8]	GUO Jia, MA Chaobin, ZHANG Shaobo, MIAO Mengmeng. Optimized Artificial Bee Colony Algorithm with Markov Chain [J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(6): 985-995.
[9]	PAN Han, YOU Xiaoming, LIU Sheng. Double-Type Ant Colony Algorithm Considering Dynamic Guidance and Neighborhood Interaction [J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(6): 1005-1016.
[10]	FENG Zhiyu, YOU Xiaoming, LIU Sheng. Hierarchical Progressive Improved Clustering Ant Colony Algorithm for Solving TSP Problems [J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(8): 1280-1294.
[11]	LIU Xinyu, TAN Liming, YANG Chunxi, ZHAI Chi. Self-Adjustable Dynamic Path Planning of Unknown Environment Based on Ant Colony-Clustering Algorithm [J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(5): 846-857.
[12]	CHAO Xiuqin, LI Wei. Feature Selection Method Optimized by Artificial Bee Colony Algorithm [J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(2): 300-309.
[13]	ZHU Hongwei, YOU Xiaoming, LIU Sheng. Heterogeneous Dual Population Ant Colony Algorithm Based on Cooperative Filtering Strategy [J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(10): 1754-1767.
[14]	ZHU Huanxiong, LIU Bo. Outlier Detection Based on Artificial Bee Colony Intelligent Technology [J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(12): 1984-1992.
[15]	XIA Kefu, LI Pengfei, CHEN Xiaoping. People Tracking of Mobile Robot Using Improved Particle Filter [J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(11): 1849-1859.