A COMPARATIVE ANALYSIS OF COLLABORATIVE PATH PLANNING AND OBSTACLE AVOIDANCE ALGORITHMS FOR SWARM ROBOTS

Abstract

In this study, three different path planning and obstacle avoidance algorithms (VFH–Pure Pursuit, RRT–Pure Pursuit, and PRM–Pure Pursuit) developed for the coordinated movement of swarm robots are comparatively analyzed. The proposed methods aim for each swarm robot to independently perceive its environment, avoid obstacles, and reach a predefined target in an organized manner. Experimental studies were conducted in three different environments, each defined as 50x50 units in size, using 3, 5, and 7 robots, with a look-ahead distance (l_d) set to 0.5. In the VFH-based approach, robots react to environmental conditions in real time, while in RRT and PRM-based algorithms, pre-planned collision-free paths are used between start and goal positions. Simulation results demonstrate that as the number of robots increases, the completion time also increases; however, the PRM algorithm offers shorter and more optimized paths. Notably, the PRM–Pure Pursuit method achieved the most efficient performance with the lowest average travel distance. The findings indicate that the choice of task-specific algorithms significantly affects the performance of swarm robots and that structured, pre-planned algorithms yield more effective results in complex environments.

Keywords

• Mobile Robots
• Obstacle Avoidance
• Path Planning
• Path Tracking.
• Swarm Robotics

SÜRÜ ROBOTLARI İÇİN İŞ BİRLİĞİNE DAYALI YOL PLANLAMA VE ENGELDEN KAÇINMA ALGORİTMALARININ KARŞILAŞTIRMALI ANALİZİ

Abstract

Bu çalışmada, sürü robotlarının koordineli hareketi için geliştirilen üç farklı yol planlama ve engelden kaçınma algoritması (VFH–Pure Pursuit, RRT–Pure Pursuit ve PRM–Pure Pursuit) karşılaştırmalı olarak analiz edilmiştir. Önerilen yöntemlerde her bir sürü robotunun bağımsız olarak çevresini algılaması, engellerden kaçınması ve belirlenen hedefe organize şekilde ulaşması hedeflenmiştir. Deneysel çalışmalar, 50x50 boyutlarında tanımlanmış üç farklı ortamda; 3, 5 ve 7 robot ile, ileriye bakma mesafesi (l_d) 0.5 olarak belirlenerek gerçekleştirilmiştir. VFH tabanlı yöntemde, robotlar çevresel koşullara anlık tepki verirken, RRT ve PRM tabanlı algoritmalarda başlangıç ve hedef konumlar arasında önceden planlanmış çarpışmasız yollar kullanılmıştır. Simülasyon sonuçları; robot sayısı arttıkça tamamlanma süresinin uzadığını, ancak PRM algoritmasının daha kısa mesafeli ve optimize yollar sunduğunu göstermiştir. Özellikle PRM–Pure Pursuit yöntemi, en düşük ortalama yol mesafesiyle en verimli performansı sergilemiştir. Elde edilen bulgular, sürü robotları için görev bazlı algoritma seçimlerinin başarımı doğrudan etkilediğini ve planlı yapıdaki algoritmaların karmaşık ortamlarda daha etkili sonuçlar verdiğini ortaya koymaktadır.

Keywords

• Engelden Kaçma
• Mobil Robotlar
• Sürü Robotiği
• Yol Planlama
• Yol Takip Etme.

References

1. Ahuja, R. K., Mehlhorn, K., Orlin, J., & Tarjan, R. E. (1990). Faster algorithms for the shortest path problem. Journal of the ACM, 37(2), 213-223. https://doi.org/10.1145/77600.776158
2. Alarabi, S., Luo, C., & Santora, M. (2022). A PRM Approach to Path Planning with Obstacle Avoidance of an Autonomous Robot. 2022 8th International Conference on Automation, Robotics and Applications (ICARA), 76-80. https://doi.org/10.1109/ICARA55094.2022.9738559
3. Borenstei̇n, İ. U. J. (1998). The vector field histogram - fast obstacle avoidance for mobile robots. İeee İnternati̇onal Conference On Roboti̇cs And Automati̇on, 7(3), 278 - 288.https://doi.org/10.1109/umagd. 70.88137
4. Coppola, M., Guo, J., Gill, E., & de Croon, G. C. H. E. (2019). Provable self-organizing pattern formation by a swarm of robots with limited knowledge. Swarm Intelligence, 13(1), 59-94. https://doi.org/10.1007/s11721-019-00163-0
5. Coulter, R. Implementation of the Pure Pursuit Path Tracking Algorithm. Carnegie Mellon University, Pittsburgh, Pennsylvania, Jan 1990.
6. Çayirpunar, Ö. (t.y.). Çoklu Robot Sistemlerinde Robotlar Arası Haberleşme Ve İş Birliği Kullanılarak Arama Verimliliğinin Artırılması.
7. Dr. Lydia E. Kavraki: A Woman Making Robots Work. (2013, Ekim 14). Mental Floss. https://www.mentalfloss.com/article/53176/dr-lydia-e-kavraki-woman-making-robotswork
8. Huang, Y., Tian, Z., Jiang, Q., & Xu, J. (2020). Path Tracking Based on Improved Pure Pursuit Model and PID. 2020 IEEE 2nd International Conference on Civil Aviation Safety and Information Technology (ICCASIT, 359-364. https://doi.org/10.1109/ICCASIT50869.2020.9368694]

9. Kavraki, L. E. (2013, October 14). A woman making robots work. Mental Floss. https://www.mentalfloss.com/article/53176/dr lydia-e-kavraki-woman-making-robotswork
10. LaValle, S. M., & Kuffner, J. J. (2001). Randomized kinodynamic planning. The International Journal of Robotics Research, 20(5), 378–400. https://doi.org/10.1177/02783640122067453
11. LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.
12. Li, Y. (2021). An RRT-Based Path Planning Strategy in a Dynamic Environment. 2021 7th International Conference on Automation, Robotics and Applications (ICARA), 1-5. https://doi.org/10.1109/ICARA51699.2021.9376472
13. Lozano-Pérez, T., & Wesley, M. A. (1979). An algorithm for planning collision-free paths among polyhedral obstacles. Communications of the ACM, 22(10), 560-570. https://doi.org/10.1145/359156.359164
14. Mısır, O., & Gökrem, L. (2020). Sürü Robotları için Esnek ve Ölçeklenebilir Toplanma Davranışı Metodu. Avrupa Bilim Ve Teknoloji Dergisi100-109. https://doi.org/10.31590/ejosat.779162
15. Mısır, O., Çelı̇k, M., & Gökrem, L. (2022). Waypoint-Based Path Tracking Approach For Self-Organized Swarm Robots. Uluslararası Muhendislik Arastirma ve Gelistirme Dergisi, 14, 799-815. https://doi.org/10.29137/umagd.1118039
16. Misir, O., & Gökrem, L. (2021b). Flocking-Based Self-Organized Aggregation Behavior Method for Swarm Robotics. Iranian Journal of Science and Technology, Transactions of Electrical Engineering, 45(4), 1427-1444. https://doi.org/10.1007/s40998-021-00442-9
17. Nemec, D., Janota, A., Hruboš, M., Gregor, M., & Pirnik, R. (2017). Mutual acoustic identification in the swarm of e-puck robots. International Journal of Advanced Robotic Systems, 14, 172988141771079. https://doi.org/10.1177/1729881417710794
18. Park, J.-H., & Yoon, T.-W. (2018a). Efficient path planning using a modified PRM algorithm for a mobile robot. Journal of Institute of Control, Robotics and Systems, 24(5), 406–412.
19. Park, J.-H., & Yoon, T.-W. (2018b). Maximizing the Coverage of Roadmap Graph for Optimal Motion Planning. Complexity, 2018, e9104720. https://doi.org/10.1155/2018/9104720
20. Stormont, D.P. (2005). Autonomous rescue robot swarms for first responders. CIHSPS 2005. Proceedings of the 2005 IEEE International Conference on Computational Intelligence for Homeland Security and Personal Safety, 2005., 151-157.
21. Ulrich, I., & Borenstein, J. (1998). VFH+: reliable obstacle avoidance for fast mobile robots. Proceedings. 1998 IEEE International Conference on Robotics and Automation (Cat. No.98CH36146), 2, 1572-1577 vol.2.
22. Ulrich, I., & Borenstein, J. (1998). VFH+: Reliable Obstacle Avoidance for Fast Mobile Robots. Proceedings of the 1998 IEEE International Conference on Robotics and Automation, 1572–1577.
23. Yaşar, E. (2020). Sürü Robotların Hareket Planlamada Kullanılması. Avrupa Bilim Ve Teknoloji Dergisi(20), 24-29. https://doi.org/10.31590/ejosat.763444
24. Zheng, Y. T. Z. (2013). Research advance in swarm robotics. Defence Technology, 9(1), 18-39. https://doi.org/10.1016/j.dt.2013.03.001