Application of Ant Colony Optimization Algorithm Based on Triangle Inequality Principle and Partition Method Strategy in Robot Path Planning

• Published in: Axioms 2023-06, Vol.12 (6), p.525
• Main Authors: Wu, Shuai, Li, Qingxia, Wei, Wenhong
• Format: Article
• Language: English
• Subjects: Algorithms; Ant colony optimization; backtracking method; Chemical partition; Convergence; Dijkstra's algorithm; Effectiveness; Energy consumption; Genetic algorithms; Heuristic; Mathematical models; Mathematical optimization; Motion; Optimization algorithms; partitioning method; path planning; Pheromones; Planning; Pseudorandom; R&D; Research & development; Robots; Searching; Shortest-path problems; Smoothness; Solution space; Strategy; triangle inequality
• ISSN: 2075-1680; 2075-1680
• DOI: 10.3390/axioms12060525

Path planning is an important area of mobile robot research, and the ant colony optimization algorithm is essential for analyzing path planning. However, the current ant colony optimization algorithm applied to the path planning of mobile robots still has some limitations, including early blind search, slow convergence speed, and more turns. To overcome these problems, an improved ant colony optimization algorithm is proposed in this paper. In the improved algorithm, we introduce the idea of triangle inequality and a pseudo-random state transfer strategy to enhance the guidance of target points and improve the search efficiency and quality of the algorithm. In addition, we propose a pheromone update strategy based on the partition method with upper and lower limits on the pheromone concentration. This can not only improve the global search capability and convergence speed of the algorithm but also avoid the premature and stagnation phenomenon of the algorithm during the search. To prevent the ants from getting into a deadlock state, we introduce a backtracking mechanism to enable the ants to explore the solution space better. Finally, to verify the effectiveness of the proposed algorithm, the algorithm is compared with 11 existing methods for solving the robot path planning problem, including several ACO variants and two commonly used algorithms (A* algorithm and Dijkstra algorithm), and the experimental results show that the improved ACO algorithm can plan paths with faster convergence, shorter path lengths, and higher smoothness. Specifically, the algorithm produces the shortest path length with a standard deviation of zero while ensuring the most rapid convergence and the highest smoothness in the case of the shortest path in four different grid environments. These experimental results demonstrate the effectiveness of the proposed algorithm in path planning.