Application of Heuristic Integration Ant Colony Optimization in Path Planning

Authors: Zeyu Zhang, Guisheng Yin, Ziying Zhang, Liguo Zhang

Abstract:

This paper mainly studies the path planning method based on ant colony optimization (ACO), and proposes heuristic integration ant colony optimization (HIACO). This paper not only analyzes and optimizes the principle, but also simulates and analyzes the parameters related to the application of HIACO in path planning. Compared with the original algorithm, the improved algorithm optimizes probability formula, tabu table mechanism and updating mechanism, and introduces more reasonable heuristic factors. The optimized HIACO not only draws on the excellent ideas of the original algorithm, but also solves the problems of premature convergence, convergence to the sub optimal solution and improper exploration to some extent. HIACO can be used to achieve better simulation results and achieve the desired optimization. Combined with the probability formula and update formula, several parameters of HIACO are tested. This paper proves the principle of the HIACO and gives the best parameter range in the research of path planning.

Keywords: Ant colony optimization, heuristic integration, path planning

Digital Object Identifier (DOI): doi.org/1

References:

[1] Dorigo, Marco, G. D. Caro, and L. M. Gambardella. “Ant Algorithms for Discrete Optimization.” Artificial Life 5.2(1999):137-172.
[2] Stutzle, Macro Dorigo, Thomas. Ant Colony Optimization. Bradford Company, 2004.
[3] Dorigo, Marco, and C. Blum. “Ant colony optimization theory: A survey.” Theoretical Computer Science 344.2-3(2005):243-278.
[4] Dorigo, Marco, M. Birattari, and Thomas Stützle. “Ant Colony Optimization.” IEEE Computational Intelligence Magazine 1.4(2006):28-39.
[5] Yang, Qiang, et al. “Adaptive Multimodal Continuous Ant Colony Optimization.” IEEE Transactions on Evolutionary Computation 21.2(2017):191-205.
[6] Thomas Stützle, and Holger H. Hoos. “MAX–MIN Ant System.” Future Generation Computer Systems 16.8(2000):889-914.
[7] Alaya, Ines, C. Solnon, and K. Ghedira. “Ant Colony Optimization for Multi-Objective Optimization Problems.” ICTAI IEEE Computer Society, 2007.
[8] Dorigo, M., and L. M. Gambardella. “Ant colony system: a cooperative learning approach to the traveling salesman problem.” IEEE Transactions on Evolutionary Computation 1996:53-66.
[9] Ye, Ke, et al. “Ant-colony algorithm with a strengthened negative-feedback mechanism for constraint-satisfaction problems.” Information Sciences 406-407(2017):29-41.
[10] Ning, Jiaxu, et al. “A best-path-updating information-guided ant colony optimization algorithm.” Information Sciences 433-434(2018):142-162.
[11] Salimans, Tim, et al. “Evolution Strategies as a Scalable Alternative to Reinforcement Learning.” (2017).