Dynamic chaotic ant colony system and its application in robot path planning
LI Juan1, YOU Xiaoming1, LIU Sheng2, CHEN Jia1
1. School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201600, China; 2. School of Management, Shanghai University of Engineering Science, Shanghai 201600, China
Abstract:To solve problems of population diversity and convergence speed when an Ant Colony System (ACS) is used to robot path planning, a dynamic chaos operator was introduced in the ACS. The dynamic chaotic ACS can balance population diversity and convergence speed. The core of dynamic chaotic ACS is that a Logistic chaotic operator was added to the traditional ACS to increase population diversity and improve the quality of the solutions. First, the chaotic operator was added to the pre-iteration to adjust the global pheromone value in the path to increase the population diversity of the algorithm, so as to avoid the algorithm to fall into the local optimal solution. Then, in the later stage, the ACS was used to ensure convergence speed of the dynamic chaotic ACS. The experimental results show that the dynamic chaotic ACS has better population diversity compared with the ACS for the robot path planning problem. The solution quality is higher and the convergence speed is faster. Compared with the Elitist Ant colony System (EAS) and the rank-based Ant System (ASrank), the dynamic chaotic ACS can balance the relationship between the quality of the solutions and the convergence speed. The dynamic chaotic ACS can find better optimal solutions even in the complex obstacle environment. The dynamic chaotic ACS can improve the efficiency of mobile robot path planning.
李娟, 游晓明, 刘升, 陈佳. 动态混沌蚁群系统及其在机器人路径规划中的应用[J]. 计算机应用, 2018, 38(1): 126-131.
LI Juan, YOU Xiaoming, LIU Sheng, CHEN Jia. Dynamic chaotic ant colony system and its application in robot path planning. Journal of Computer Applications, 2018, 38(1): 126-131.
[1] 朱大奇,颜明重.移动机器人路径规划技术综述[J].控制与决策,2010,25(7):961-967.(ZHU D Q, YAN M Z. Summary of mobile robot path planning technology[J]. Control and Decision, 2010, 25(7):961-967.) [2] 许亚.基于改进的人工势能场的移动机器人路径规划研究[J].科技展望,2016,26(33):77-78.(XU Y. Research on mobile robot path planning based on improved artificial potential field[J]. Science and Technology, 2016, 26(33):77-78.) [3] DORIGO M, MANIEZZO V, COLORNI A. The ant system:optimization by a colony of cooperating Agents[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 1996, 26(1):1-13. [4] 夏小云,周育人.蚁群优化算法的理论研究进展[J].智能系统学报,2016,11(1):27-36.(XIA X Y, ZHOU Y R. Theoretical research progress of ant colony optimization algorithm[J]. Journal of Intelligent Systems, 2016, 11(1):27-36.) [5] 李士勇.蚁群算法及其应用[M].哈尔滨:哈尔滨工业大学出版社,2004:112-126.(LI S Y. Ant Colony Algorithm and Its Application[M]. Harbin:Harbin Institute of Technology Press, 2004:112-126.) [6] THEPPHAKORN T, PONGCHAROEN P, HICKS C. An ant colony based timetabling tool[J]. International Journal of Production Economics, 2014, 149(3):131-144. [7] GHUMMAN N S, KAUR R. Dynamic combination of improved max-min and ant colony algorithm for load balancing in cloud system[C]//Proceedings of the 6th International Conference on Computing, Communication and Networking Technologies. Piscataway, NJ:IEEE, 2015:1-5. [8] BOUSSAID I, LEPAGNOT J, SIARRY P. A survey on optimization metaheuristics[J]. Information Science,2013, 237(19):82-117. [9] GANDOMI A H, YANG X-S. Chaotic bat algorithm[J]. Journal of Computational Science, 2014, 5(2):224-232. [10] JAVIDI M, HOSSEINPOURFARD R. Chaos genetic algorithm instead genetic algorithm[J]. The International Arab Journal of Information Technology, 2015, 12(2):163-168. [11] WANG Y. Application of chaos ant colony algorithm in Web service composition based on QoS[J]. International Forum on Information Technology and Applications, 2009, 172(2):25-227. [12] TAO W Q, YANG G, ZHANG J Y. Fault section locating for distribution network with DG based on improved ant colony algorithm[C]//Proceedings of the 2016 Power Electronics and Motion Control Conference. Piscataway, NJ:IEEE, 2016:1985-1989. [13] PRAKASAM A, SAVARIMUTHU N. Metaheuristic algorithms and probabilistic behaviour:a comprehensive analysis of ant colony optimization and its variants[J]. Artificial Intelligence Review, 2016, 45(1):97-130. [14] BULLNHEIMER B, HARTL R F, STRAUB C. A new rank based version of ant system-a computational study[J]. Central European Journal of Operations Research, 1999, 7(1):25-38. [15] LORENZ N. Deterministic non periodic flow[J]. AMS Journal, 1963, 20(2):130-141. [16] WANG Y, YAO M.A new hybrid genetic algorithm based on chaos and PSO[C]//Proceedings of the 2009 IEEE International Conference on Intelligent Computing and Intelligent Systems. Piscataway, NJ:IEEE, 2009:699-703. [17] SHAHRZAD S, SEYEDALI M, ANDREW L. Biogeography-based optimisation with chaos[J]. Neural Computing and Applications, 2014, 25(5):1077-1097.