A Highly Efficient ACO-SA Algorithm for Robot Path Planning

W Li, Feng Yang, Zhibin Li, Juan Mou, Yanmei Ha, Y. Liu, Ya Qin, Peiyang Wei, Linlin Chen, Xun Deng, Tinghui Chen, Jia Liu, Jianhong Gan, Zhenzhen Hu, Yonghong Deng, Guodong Li, Qifeng SuEAI 2025 · DOI

TL;DR

This paper introduces ACO-SA, a novel algorithm that combines Ant Colony Optimization (ACO) with Simulated Annealing (SA) to significantly improve robot path planning efficiency. By integrating SA's global search capabilities into ACO's iterative process, ACO-SA achieves faster convergence and more stable, shorter paths, addressing key limitations of traditional ACO methods.

What Problem Does This Paper Address?

Efficient path planning is crucial for mobile robots operating in complex and dynamic environments. Traditional Ant Colony Optimization (ACO) algorithms, while robust and capable of finding good solutions, suffer from slow convergence and a tendency to get stuck in local optima. This makes them less suitable for real-time applications or scenarios requiring rapid adaptation. The authors aim to overcome these limitations by developing a more efficient and stable path planning algorithm.

Methods

The core of this work is the ACO-SA algorithm, which fuses two established optimization techniques:

  • Ant Colony Optimization (ACO): This metaheuristic algorithm is inspired by the foraging behavior of ants. Ants deposit pheromones on paths, and subsequent ants are more likely to follow paths with higher pheromone concentrations. This positive feedback mechanism helps in finding optimal paths. The paper uses a grid-based approach to model the environment, where each grid cell represents a state.
  • Simulated Annealing (SA): SA is a probabilistic technique for approximating the global optimum of a given function. It mimics the annealing process in metallurgy, where a material is heated and then slowly cooled to reduce defects. In optimization, SA starts with a high "temperature" allowing for exploration of the solution space (accepting worse solutions with some probability) and gradually "cools down," becoming more selective and converging towards a better solution.

The ACO-SA fusion strategy involves:

  1. Running the ACO algorithm for an iteration.
  2. Using the best path found by ACO as the initial solution for SA.
  3. Applying SA to optimize this path, leveraging its ability to escape local optima.
  4. Feeding the improved path back to the ACO algorithm to update pheromone concentrations.
  5. Dynamically adjusting the pheromone evaporation coefficient (ρ) based on the SA temperature, increasing it at high temperatures for exploration and decreasing it at lower temperatures for convergence.

Datasets

The authors used two types of environments for evaluation:

  • Training Base Map: A specific, pre-defined map representing a training environment. This map is gridded and modeled, with obstacles clearly marked.
  • Multi-modal Large Model Random Maps: Two randomly generated maps created using a "multimodal large model." These maps are designed to simulate more complex and dynamic environments with varied obstacle shapes and distributions, testing the algorithm's robustness.

Key Insights and Ideas

  • Synergistic Optimization: The combination of ACO and SA is more than just an additive approach. SA's ability to escape local optima complements ACO's iterative search, leading to a more robust and efficient exploration of the solution space.
  • Dynamic Pheromone Management: Dynamically adjusting the pheromone evaporation coefficient based on the SA temperature is a crucial innovation. This allows the algorithm to balance exploration (at high SA temperatures) and exploitation (at low SA temperatures) more effectively.
  • Practical Applicability: The algorithm is tested on realistic grid-based maps, demonstrating its potential for practical applications like intelligent detection robots.

Key Results

The ACO-SA algorithm demonstrated significant improvements over traditional ACO and other variants:

  • Convergence Speed: ACO-SA achieved an 88.9% improvement in convergence speed compared to traditional ACO and a 58.3% improvement compared to a VACO algorithm on the training base map.
  • Path Length: While the path length on the training base map remained largely unchanged, ACO-SA achieved comparable optimal paths to other algorithms.
  • Worst-Case Performance: In random map scenarios, ACO-SA's shortest path was shortened by 36.57% and 35.95% compared to the traditional ant colony algorithm in Map 1 and Map 2 respectively.
  • Convergence Epochs: ACO-SA converged in significantly fewer iterations (e.g., 7 epochs in Map 1 worst-case, 16 epochs in Map 2 worst-case) compared to traditional ACO, which often failed to converge within 100 epochs.
  • Running Time: A slight reduction in running time was observed (1.5% and 3.5% on the training base map).

Limitations and Future Work

  • Parameter Sensitivity: While the paper explores the effect of the alpha parameter, it's implied that other parameters might also influence performance, and finding optimal settings could be an ongoing task.
  • Dynamic Environments: While random maps were used, the paper acknowledges that real-world scenarios involve more complex dynamic obstacles and multi-robot collaboration.
  • Future Directions: The authors propose integrating attention-enhanced dynamic decision-making, multimodal environment modeling, and adaptive strategy optimization algorithms (like reinforcement learning) to further enhance the algorithm's capabilities for complex and changing practical applications. They also plan to explore large-scale distributed collaborative frameworks and multi-agent attention mechanisms.

Summary updated

Abstract

Intelligent algorithms continue to develop, and efficient path planning for mobile robots in complex environments relies heavily on such algorithms. This article proposes an ACO-SA path planning method that combines ant colony and simulated annealing to solve the problems of slow iteration and long computation in classical ant colony algorithms. The training base map is gridded and modeled, and the path is initially calculated and parameterized using traditional ant colony algorithms. The simulated annealing cooling mechanism is introduced to optimize the pheromone strategy, and the robustness of the algorithm is tested using a multi-modal large model random map. Simulation shows that under the map of the training base, the path length of the ACO-SA algorithm remains unchanged, and the convergence speed is improved by 88.9% and 58.3% respectively, while the running time is shortened by 1.5% and 3.5% respectively; In the worst results of the random map, the shortest path is shortened by 36.57% and 35.95% respectively compared to the traditional ant colony algorithm. This algorithm has better optimization effect and path stability, providing a practical solution for intelligent detection robot path planning.
BibTeX
@inproceedings{li2025highly,
  author = {W Li and Feng Yang and Zhibin Li and Juan Mou and Yanmei Ha and Y. LIU and Ya Qin and Peiyang Wei and Linlin Chen and Xun Deng and Tinghui Chen and Jia Liu and Jianhong Gan and Zhenzhen Hu and Yonghong Deng and Guodong Li and Qifeng Su},
  title = {{A Highly Efficient ACO-SA Algorithm for Robot Path Planning}},
  booktitle = {EAI},
  year = {2025},
  doi = {10.4108/airo.11177},
}
Figure