Engel Yoğun Çalışma Alanlarında Kapsama ve Geçiş Planlaması

Öz

Bu çalışma, sabit engeller içeren iki boyutlu grid tabanlı haritalarda çalışan otonom mobil robotlar için verimli bir kapsama yol planlama algoritması sunmaktadır. Önerilen yaklaşım, çalışma alanını satır tabanlı hücresel bölgelere ayırarak her hücre içinde sistematik bir tarama gerçekleştirmekte ve hücreler arası geçişleri toplam mesafeyi en aza indirmeye yönelik olarak optimize etmektedir. Hücreler arası geçişlerde doğrudan bağlantıların engellere çarpışması durumları için güvenli yol üretimi A* algoritması kullanılarak sağlanmaktadır. Ayrıca, her hücre için giriş ve çıkış yönleri geçiş maliyetine göre ayrı ayrı optimize edilmektedir. Geliştirilen algoritma, 5×5, 15×15 ve 50×50 boyutlarında üç farklı karmaşıklık seviyesine sahip haritalar üzerinde test edilmiştir. Deneysel analizlerde kapsama yoğunluğu, ortalama hücre uzunluğu, yol verimliliği ve A* geçiş oranı gibi çok boyutlu performans metrikleri hesaplanmış ve önerilen yöntemin hem kapsama başarısı hem de geçiş güvenliği açısından tutarlı sonuçlar verdiği gösterilmiştir. Bulgular, yöntemin farklı ölçeklerdeki haritalarda uygulanabilirliğini ve genişletilebilirliğini ortaya koymaktadır.

Anahtar Kelimeler

• Kapsama Planlaması
• Mobil Robotlar
• Hücre Bölütleme
• Yol Optimizasyonu
• A* Algoritması
• Engelden Kaçınma

Coverage and Transition Planning in Obstacle-Rich Workspaces

Öz

This study proposes a comprehensive and efficient algorithm for coverage path planning, specifically designed for autonomous mobile robots operating on two-dimensional grid-based maps with fixed obstacles. The suggested approach merges several established techniques into a cohesive framework, encompassing row-based cellular decomposition, A*-based safe transition planning, and the dynamic optimization of entry and exit points for each segment of coverage. This synthesis allows for the creation of thorough and secure coverage paths while minimizing redundancy. The algorithm undergoes evaluation on maps of varying intricacy (5×5, 15×15, and 50×50), and its performance is measured using various metrics, including coverage density, average cell length, A* transition rate, and overall path efficiency. Results indicate that the proposed integration-based method consistently achieves high levels of coverage and path efficiency, while ensuring safe transitions between different areas. This framework proves to be not only practically efficient but also flexible across different scales, showcasing significant potential for real-world uses such as autonomous cleaning, agricultural monitoring, and emergency rescue operations.

Anahtar Kelimeler

• Coverage Planning
• Mobile Robots
• Cell Partitioning
• Path Optimization
• A* Algorithm
• Obstacle Avoidance

Kaynakça

1. [1] Choset H., 2001. Coverage for Robotics – A Survey of Recent Results. Annals of Mathematics and Artificial Intelligence, 31(1–4), pp. 113–126.
2. [2] Galceran E., Carreras M., 2013. A Survey on Coverage Path Planning for Robotics. Robotics and Autonomous Systems, 61(12), pp. 1258–1276.
3. [3] Ma C., Zou H., An X., 2024. A Complete Coverage Path Planning Approach for an Autonomous Underwater Helicopter in Unknown Environment Based on VFH+ Algorithm. Journal of Marine Science and Engineering, 12(3), 412.
4. [4] Ni J., Gu Y., Tang G., Ke C., Gu Y., 2024. Cooperative Coverage Path Planning for Multi-Mobile Robots Based on Improved K-Means Clustering and Deep Reinforcement Learning. Electronics, 13(5), 944.
5. [5] Tieu‑Thanh Le, Phung Cong K.‑K., Thai‑Viet Dang, 2024. An Improved Coverage Path Planning for Service Robots Based on Backtracking Method. MM Science Journal, (October 2024), 063.
6. [6] Gabriely Y., Rimon E., 2001. Spanning-Tree Based Coverage of Continuous Areas by a Mobile Robot. Annals of Mathematics and Artificial Intelligence, 31(1–4), pp. 77–98.
7. [7] Yufan Huang, Man Li, Tao Zhao, 2023. A Multi‑robot Coverage Path Planning Algorithm Based on Improved DARP Algorithm. ArXiv preprint 2304.09741.
8. [8] Xu T., Zhang S., Mei T., 2022. A Hierarchical Coverage Path Planning Method for Mobile Robot Based on TSP Model. Computers and Electronics in Agriculture, 192, 106605.

9. [9] Arkin E.M., Fekete S.P., Mitchell J.S.B., 2000. Approximation Algorithms for Lawn Mowing and Milling. Computational Geometry, 17(1–2), pp. 25–50.
10. [10] Chang Y.H., Lee T.H., 2017. Modified TSP Model Based Path Planning for Complete Coverage of Mobile Robots. Journal of Intelligent & Robotic Systems, 88(1), pp. 39–51.
11. [11] Hazon N., Kaminka G.A., 2005. Redundancy, Efficiency and Robustness in Multi-Robot Coverage. Proceedings of the IEEE International Conference on Robotics and Automation, pp. 735–741.
12. [12] Koenig S., Likhachev M., 2005. Fast Replanning for Navigation in Unknown Terrain. IEEE Transactions on Robotics, 21(3), pp. 354–363.
13. [13] Stentz A., 1995. The Focused D* Algorithm for Real-Time Replanning. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 1652–1659.
14. [14] Ulusoy A., Smith S.L., Ding X., Belta C., 2013. Optimality and Robustness in Multi-Robot Path Planning with Temporal Logic Constraints. International Journal of Robotics Research, 32(8), pp. 889–911.
15. [15] Lee J., Choi H., Kim H.J., 2022. Multi-Robot Coverage Path Planning Based on Continuous Occupancy Map. Journal of Intelligent & Robotic Systems, 104(1), 13.
16. [16] Yu J., LaValle S.M., 2013. Planning Optimal Paths for Multiple Robots on Graphs. Proceedings of the IEEE International Conference on Robotics and Automation, pp. 3612–3617.
17. [17] Smith S.L., Schwager M., Rus D., 2011. Persistent Monitoring of Changing Environments Using a Robot with Limited Range Sensing. Proceedings of the IEEE International Conference on Robotics and Automation, pp. 5448–5455.
18. [18] Rizk Y., Awad M., Tunstel E., 2019. Adaptive Path Planning for Autonomous Mobile Robots: A Survey. Journal of Field Robotics, 36(4), pp. 695–718.
19. [19] Cabreira T.M., Brisolara L.B., Ferreira P.R., 2019. Survey on Coverage Path Planning with Unmanned Aerial Vehicles. Drones, 3(1), 4.
20. [20] Zeng Y., Li H., Fu C., Pan Z., 2019. Complete Coverage Path Planning for Mobile Robots with Distance Constraints. Sensors, 19(19), 4186.
21. [21] Luo C., Yang S., Krishnan M., 2015. New Potential Field Method for Obstacle Avoidance and Path Planning of Mobile Robots. IEEE International Conference on Automation Science and Engineering, pp. 486–491.
22. [22] Meng L., Liu C., Li C., Song R., 2017. Coverage Path Planning for Cleaning Robots in 3D Environments. Sensors, 17(2), 364.