Global path planning approach based on ant colony optimization algorithm

Abstract

Ant colony optimization (ACO) algorithm was modified to optimize the global path. In order to simulate the real ant colonies, according to the foraging behavior of ant colonies and the characteristic of food, conceptions of neighboring area and smell area were presented. The former can ensure the diversity of paths and the latter ensures that each ant can reach the goal. Then the whole path was divided into three parts and ACO was used to search the second part path. When the three parts pathes were adjusted, the final path was found. The valid path and invalid path were defined to ensure the path valid. Finally, the strategies of the pheromone search were applied to search the optimum path. However, when only the pheromone was used to search the optimum path, ACO converges easily. In order to avoid this premature convergence, combining pheromone search and random search, a hybrid ant colony algorithm(HACO) was used to find the optimum path. The comparison between ACO and HACO shows that HACO can be used to find the shortest path.

Keywords

mobile robot / ant colony optimization / global path planning / pheromone

References

[1] LiuG.-q., PengY.-q., HouX.-dan.. The ant algorithm for solving robot path planning problem[C]. Third Int Conf on Information Technology and Applications, 2005, Washington DC, IEEE Computer Society: 25-27

[2] FanX.-p., LuoX., YiS., et al.. Optimal path planning for mobile robots based on intensified ant colony optimization algorithm[C]. 2003 IEEE Int Conf on Robotics, Intelligent Systems and Signal Processing, 2003, New York, IEEE Press: 131-136

[3] Köse M. Ant colony optimization for the wall-following robot problem[EB/OL]. https://doi.org/www.computer.org/students/looking/2003fall/A5.pdf, 2003.

[4] FanX.-p., LuoX., YiS., et al.. Path planning for robots based on ant colony optimization algorithm under complex environment[J]. Control and Decision, 2004, 19(2): 166-170

[5] JinF.-h., HongB.-r., GaoQ.-ji.. Path planning for free-flying space robot using ant algorithm [J]. Robot, 2002, 24(6): 526-529

[6] ZhuQ.-bao.. Ants predictive algorithm for path planning of robot in a complex dynamic environment[J]. Chinese Journal of Computers, 2005, 28(11): 1898-1906

[7] ZhuQ.-b., ZhangY.-lan.. An ant colony algorithm based on grid method for mobile robot path planning [J]. Robot, 2005, 27(2): 132-136

[8] DorigoM., ManiezzoV., ColorniA.. 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

[9] DeneubourgJ. L., AronS., GossS., et al.. The self-organizing exploratory pattern of the argentine ant[J]. Journal of Insect Behavior, 1990, 3: 159-168

[10] GossS., AronS., DeneubourgJ. L., et al.. Self-organized shortcuts in the Argentine ant[J]. Naturwissenschaften, 1989, 76: 579-581

[11] DorigoM., CaroG. D., BrusselsB., et al.. Ant Algorithms for discrete optimization[J]. Artificial Life, 1999, 5(3): 137-172

[12] DorigoM.Optimization, learning and natural algorithm[D], 1992, Italy, Politecnico di Milano

[13] DorigoM., BonabeauE., TheraulazG., et al.. Ant algorithms and stigmergy[J]. Future Generation Computer Systems, 2000, 16: 851-871

[14] Wagner, LindenbaumM., BrucksteinA. M.. Distributed covering by ant-robots using evaporating traces[J]. IEEE Transactions on Robotics and Automation, 1999, 15(5): 918-933

[15] LamY. K., WongE. K., LooC. K.. Explicit communication in designing efficient cooperative mobile robotic system[C]. 2003 IEEE Int Conf on Robotics and Automation, 2003, Taibei, Institute of Electrical and Electronics Engineers Inc: 3869-3874