Ant Colony Path Planning Based on Non-uniform Modeling of Complex Environment
BU Xinping1, SU Hu1, ZOU Wei1, WANG Peng1, ZHOU Hai2
1. Research Center of Precision Sensing and Control, Institute of Automation, Chinese Academy of Sciences, Beijing 100190, China;
2. Research Center of Laser Fusion, Chinese Academy of Engineering Physics, Mianyang 621900, China
卜新苹, 苏虎, 邹伟, 王鹏, 周海. 基于复杂环境非均匀建模的蚁群路径规划[J]. 机器人, 2016, 38(3): 276-284.DOI: 10.13973/j.cnki.robot.2016.0276.
BU Xinping, SU Hu, ZOU Wei, WANG Peng, ZHOU Hai. Ant Colony Path Planning Based on Non-uniform Modeling of Complex Environment. ROBOT, 2016, 38(3): 276-284. DOI: 10.13973/j.cnki.robot.2016.0276.
Abstract:For a large auxiliary robot working in complex environment, an improved ant colony algorithm based on non-uniform environment modeling is proposed to search feasible paths. In the process of environment modeling, convex projection is firstly conducted to calculate the obstacle area of each environment obstacle on the projection plane. Then, the obstacles are extended by using the concept of the Minkowski sum, and a grid model of the environment is non-uniformly constructed based on the linear quadtree method. During path planning, an improved ant colony algorithm is adopted to search feasible paths of the vehicle. In order to improve performance, the pheromone update mechanisms of the max-min ant system (MMAS) and ant colony system (ACS) algorithms are fused, some target distance based and obstacle distance based heuristic search methods are used in grid selection, and a fitness function suitable for the constructed environment model is designed. Finally, the method is experimentally verified in the target area of a large laser facility, and the result shows that it can efficiently plan the vehicle path in complex environment in the presence of obstacles. Further, comparison experiments are also well conducted to demonstrate the superior performance of the proposed method in convergence and adaptability comparing with the basic ant colony algorithm.
[1] 李磊,叶涛,谭民,等.移动机器人技术研究现状与未来 [J].机器人,2005,24(5):475-480.Li L, Ye T, Tan M, et al. Present state and future development of mobile robot technology research[J]. Robot, 2002, 24(5): 475-480.
[2] Lozano-Perez T, Wesley M A. An algorithm for planning collision-free paths among polyhedral obstacles[J]. Communications of the ACM, 1979, 22(10): 560-570.
[3] Brooks R A. Solving the find-path problem by good representation of free space[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1983, 13(2): 190-197.
[4] Alajlan M, Koubaa A, Chaari I, et al. Global path planning for mobile robots in large-scale grid environments using genetic algorithms[C]//International Conference on Individual and Collective Behaviors in Robotics. Piscataway, USA: IEEE, 2013: 1-8.
[5] 谭民,徐德,候增广,等.先进机器人控制[M].北京:高等教育出版社,2007.Tan M, Xu D, Hou Z G, et al. Advanced robot control[M]. Beijing: Higher Education Press, 2007.
[6] Alexopoulos C, Griffin P M. Path planning for a mobile robot[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1992, 22(2): 318-322.
[7] Fan D K, Shi P. Improvement of Dijkstra's algorithm and its application in route planning[C]//7th International Conference on Fuzzy Systems and Knowledge Discovery. Piscataway, USA: IEEE, 2010: 1901-1904.
[8] Dorigo M, Maniezzo V, Colorni A. Ant system: Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1996, 26(1): 29-41.
[9] Zhou Y R. Runtime analysis of an ant colony optimization algorithm for TSP instances[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(5): 1083-1092.
[10] Tsutsui S, Liu L C. Solving quadratic assignment problems with the cunning ant system[C]//IEEE Congress on Evolutionary Computation. Piscataway, USA: IEEE, 2007: 173-179.
[11] Garai G, Debbarman S, Biswas T. An efficient ant colony optimization algorithm for function optimization. A guided search technique for high and low dimensional functions[C]//IEEE Congress on Evolutionary Computation. Piscataway, USA: IEEE, 2013: 2345-2351.
[12] Juang C F, Hsu C H. Reinforcement ant optimized fuzzy controller for mobile-robot wall-following control[J]. IEEE Transactions on Industrial Electronics, 2009, 56(10): 3931-3940.
[13] Dorigo M, Gambardella L M. Ant colony system: A cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.
[14] Stutzle T, Hoos H H. MAX-MIN ant system[J]. Future Generation Computer Systems, The International Journal of Escience, 2000, 16(8): 889-914.
[15] Zeng D W, He Q, Leng B, et al. An improved ant colony optimization algorithm based on dynamically adjusting ant number[C]//IEEE International Conference on Robotics and Biominetics. Piscataway, USA: IEEE, 2012: 2039-2043.
[16] Maekawa T, Noda T, Tamura S, et al. Curvature continuous path generation for autonomous vehicle using B-spline curves[J]. Computer-Aided Design, 2010, 42(4): 350-359.
[17] O'Rourke J. Computational geometry in C[M]. Cambridge, UK: Cambridge University Press, 1997.
[18] Sahni S. Data structures, algorithms, and application in C++[M]. Summit, USA: Silicon Press, 2004.