A composite objective function specifically tuned for multi-robot path planning

Abstract

In swarm robotic systems, the problem of multi-robot path planning (MRPP), especially in obstacle-filled environments, presents significant challenges in terms of coordinated navigation. This work proposes a new fitness function for online MRPP in environments containing dynamic obstacles. The proposed method optimizes the collision-free paths of 20 robots using metaheuristic algorithms such as Particle Swarm Optimization (PSO), Artificial Bee Colony Optimization (ABC), Ant Colony Optimization (ACO), Genetic Algorithm (GA), and Differential Evolution (DE). The fitness function balances conflicting objectives such as proximity to the target, obstacle, and collision avoidance with other robots. Simulations have confirmed that 20 robots divided into two groups safely reach their destinations in a 100x100 unit environment containing dynamic and static obstacles. Simulations showed that the ABC algorithm achieved the best average path length (2667.01 units) in static environments, while PSO provided the fastest computation time (13.15 s). In dynamic environments, ABC again outperformed others in path length (2790.13 units), and PSO remained the fastest (17.30 s). The contributions of the work are a new fitness function, a path planning framework that improves the efficiency of metaheuristic algorithms, and demonstration of the success of the method in dynamic environments.

Keywords

• Swarm robotics
• Path planning
• Collision avoidance
• Meta-heuristic algorithms

Çoklu robot yol planlaması için özel olarak ayarlanmış bileşik bir amaç fonksiyonu

Öz

Sürü robot sistemlerinde, özellikle engellerle dolu ortamlarda çoklu robot yol planlama (ÇRYP) problemi, koordineli navigasyon açısından önemli zorluklar ortaya koymaktadır. Bu çalışma, dinamik engeller içeren ortamlarda çevrimiçi ÇRYP için yeni bir uygunluk fonksiyonu önermektedir. Önerilen yöntem, Parçacık Sürü Optimizasyonu (PSO), Yapay Arı Kolonisi Optimizasyonu (ABC), Karınca Kolonisi Optimizasyonu (ACO), Genetik Algoritma (GA) ve Diferansiyel Evrim (DE) gibi metasezgisel algoritmalar kullanarak 20 robotun çarpışmadan kaçınan yollarını optimize etmektedir. Uygunluk fonksiyonu, hedefe yakınlık, engel ve diğer robotlarla çarpışmadan kaçınma gibi çatışan hedefleri dengelemektedir. Simülasyonlar, iki gruba ayrılan 20 robotun, dinamik ve statik engeller içeren 100x100 birimlik bir ortamda hedeflerine güvenli bir şekilde ulaştığını doğrulamıştır. Simülasyonlar, ABC algoritmasının statik ortamlarda en iyi ortalama yol uzunluğunu (2667,01 birim) elde ettiğini, PSO'nun ise en hızlı hesaplama süresini (13,15 sn) sağladığını göstermiştir. Dinamik ortamlarda ise ABC, yol uzunluğu açısından (2790,13 birim) yine diğerlerinden daha iyi performans göstermiş ve PSO en hızlı algoritma olmaya devam etmiştir (17,30 sn). Çalışmanın katkıları, yeni bir uygunluk fonksiyonu, metasezgisel algoritmaların verimliliğini artıran bir yol planlama çerçevesi ve yöntemin dinamik ortamlarda başarısının gösterilmesidir.

Anahtar Kelimeler

• Sürü robotlar
• Yol planlama
• Çarpışmadan kaçınma
• Meta-sezgisel algoritmalar

References

1. Goel, R. and Gupta, P. (2020) Robotics and industry 4.0, A roadmap to industry 4.0: Smart production, Sharp Business and Sustainable Development, 157-169.
2. Gielis, J., Shankar, A., and Prorok, A. (2022) A critical review of communications in multi-robot systems, Current Robotics Reports, 3(4): 213-225.
3. Bolu, A. and Korçak, Ö. (2021) Adaptive task planning for multi-robot smart warehouse, IEEE Access, 9: 27346-27358.
4. Yu, L., Yang, E., Ren, P., Luo, C., Dobie, G., Gu, D., and Yan, X. (2019) Inspection robots in oil and gas industry: a review of current solutions and future trends. 2019 25th International Conference on Automation and Computing (ICAC), Lancaster, UK, pp. 1-6.
5. Nazarahari, M., Khanmirza, E., and Doostie, S. (2019) Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm, Expert Systems with Applications, 115: 106-120.
6. Ugwoke, K.C., Nnanna, N.A., and Abdullahi, S.E.Y. (2025) Simulation-based review of classical, heuristic, and metaheuristic path planning algorithms, Scientific Reports, 15(1): 12643.
7. Tamizi, M.G., Yaghoubi, M., and Najjaran, H. (2023) A review of recent trend in motion planning of industrial robots, International Journal of Intelligent Robotics and Applications, 7(2): 253-274.
8. Chen, R. and Gotsman, C. (2021) Efficient fastest-path computations for road maps, Computational Visual Media, 7: 267-281.

9. Rahman, M.A., Sokkalingam, R., Othman, M., Biswas, K., Abdullah, L., and Abdul Kadir, E. (2021) Nature-inspired metaheuristic techniques for combinatorial optimization problems: Overview and recent advances, Mathematics, 9(20): 2633.
10. Kennedy, J. and Eberhart, R. (1995) Particle swarm optimization. Proceedings of ICNN'95-International Conference on Neural Networks, Perth, WA, Australia, Vol. 4, pp. 1942-1948.
11. Karaboga, D. and Basturk, B. (2007) A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm, Journal of Global Optimization, 39: 459-471.
12. Dorigo, M., Birattari, M., and Stutzle, T. (2007) Ant colony optimization, IEEE Computational Intelligence Magazine, 1(4): 28-39.
13. Holland, J.H. (1992) Genetic algorithms, Scientific American, 267(1): 66-73.
14. Price, K.V., Storn, R.M., and Lampinen, J.A. (2005) Differential evolution: a practical approach to global optimization, The Differential Evolution Algorithm, 37-134.