Performance Evaluation of Various Path Planning Methods for Robotics and Computational Geometry
DOI:
https://doi.org/10.4108/eetiot.5433Keywords:
Path planning, Computational geometry, Boustrophedon Cellular Decomposition, Spiral Coverage, Coverage Path PlanningAbstract
INTRODUCTION: In integrating Spiral Coverage into Cellular Decomposition, which combines structured grid-based techniques with flexible, quick spiral traversal, time efficiency is increased.
OBJECTIVES: In the field of robotics and computational geometry, the study proposes a comparative exploration of two prominent path planning methodologies—Boustrophedon Cellular Decomposition and the innovative Spiral Coverage. Boustrophedon coverage has limitations in time efficiency due to its back-and-forth motion pattern, which can lead to lengthier coverage periods, especially in congested areas. Nevertheless, it is useful in some situations. It is critical to address these time-related issues to make Boustrophedon algorithms more useful in practical settings.
METHODS: The research centres on achieving comprehensive cell coverage, addressing the complexities arising from confined spaces and intricate geometries. While conventional methods emphasise route optimization between points, the coverage path planning approach seeks optimal paths that maximize coverage and minimize associated costs. This study delves into the theory, practical implementation, and application of Spiral Coverage integrated with established cellular decomposition techniques.
RESULTS: Through comparative analysis, it illustrates the advantages of spiral coverage over boustrophedon coverage in diverse robotics and computational applications. The research highlights Spiral Coverage's superiority in terms of path optimization, computational efficiency, and adaptability, proposing a novel perspective into cell decomposition. The methodology integrates the Spiral Coverage concept, transcending traditional techniques reliant on grids or Voronoi diagrams. Rigorous evaluation validates its potential to enhance path planning, exemplifying a substantial advancement in robotics and computational geometry.
CONCLUSION: Our findings show that spiral coverage is on an average 45% more efficient than conventional Boustrophedon coverage. This paper set the basis for the future work on how different algorithms can traverse different shapes more efficiently.
Downloads
References
[1] De Carvalho RN, Vidal HA, Vieira P, Ribeiro MI. Complete coverage path planning and guidance for cleaning robots. InISIE'97 Proceeding of the IEEE International Symposium on Industrial Electronics 1997 Jul 7 (Vol. 2, pp. 677-682). IEEE.
[2] Huang Y, Cao Z, Hall E. Region filling operations for mobile robot using computer graphics. InProceedings. 1986 IEEE International Conference on Robotics and Automation 1986 Apr 7 (Vol. 3, pp. 1607-1614). IEEE.
[3] Hameed IA. Motion planning for autonomous landmine detection and clearance robots. In2016 International Workshop on Recent Advances in Robotics and Sensor Technology for Humanitarian Demining and Counter-IEDs (RST) 2016 Oct 27 (pp. 1-5). IEEE.
[4] Ollis M, Stentz A. First results in vision-based crop line tracking. InProceedings of IEEE International Conference on Robotics and Automation 1996 Apr 22 (Vol. 1, pp. 951-956). IEEE.
[5] Brooks R. A robust layered control system for a mobile robot. IEEE journal on robotics and automation. 1986 Mar;2(1):14-23.
[6] Gage DW. Randomized search strategies with imperfect sensors. InMobile Robots VIII 1994 Feb 1 (Vol. 2058, pp. 270-279). SPIE.
[7] Galceran E, Carreras M. A survey on coverage path planning for robotics. Robotics and Autonomous systems. 2013 Dec 1;61(12):1258-76.
[8] Choset H. Coverage of known spaces: The boustrophedon cellular decomposition. Autonomous Robots. 2000 Dec;9:247-53.
[9] Gao L, Lv W, Yan X, Han Y. Complete coverage path planning algorithm based on energy compensation and obstacle vectorization. Expert Systems with Applications. 2022 Oct 1;203:117495.
[10] Song J, Gupta S. $varepsilon^{star} $: An Online Coverage Path Planning Algorithm. IEEE Transactions on Robotics. 2018 Feb 8;34(2):526-33.
[11] Bochkarev S, Smith SL. On minimizing turns in robot coverage path planning. In2016 IEEE international conference on automation science and engineering (CASE) 2016 Aug 21 (pp. 1237-1242). IEEE.
[12] Choset H. Coverage of known spaces: The boustrophedon cellular decomposition. Autonomous Robots. 2000 Dec;9:247-53.
[13] Ntawumenyikizaba A, Viet HH, Chung T. An online complete coverage algorithm for cleaning robots based on boustrophedon motions and A* search. In2012 8th International Conference on Information Science and Digital Content Technology (ICIDT2012) 2012 Jun 26 (Vol. 2, pp. 401-405). IEEE.
[14] Hassan M, Liu D, Chen X. Squircular-CPP: A smooth coverage path planning algorithm based on squircular fitting and spiral path. In2020 IEEE/ASME International Conference on Advanced Intelligent Mechatronics (AIM) 2020 Jul 6 (pp. 1075-1081). IEEE.
[15] Van Pham H, Asadi F, Abut N, Kandilli I. Hybrid spiral STC-hedge algebras model in knowledge reasonings for robot coverage path planning and its applications. Applied Sciences. 2019 May 9;9(9):1909.
[16] Fevgas G, Lagkas T, Argyriou V, Sarigiannidis P. Coverage path planning methods focusing on energy efficient and cooperative strategies for unmanned aerial vehicles. Sensors. 2022 Feb 6;22(3):1235.
[17] Khan A, Noreen I, Habib Z. On Complete Coverage Path Planning Algorithms for Non-holonomic Mobile Robots: Survey and Challenges. J. Inf. Sci. Eng.. 2017 Jan 1;33(1):101-21.
[18] Heydari J, Saha O, Ganapathy V. Reinforcement learning-based coverage path planning with implicit cellular decomposition. arXiv preprint arXiv:2110.09018. 2021 Oct 18.
[19] Jensen-Nau KR, Hermans T, Leang KK. Near-optimal area-coverage path planning of energy-constrained aerial robots with application in autonomous environmental monitoring. IEEE Transactions on Automation Science and Engineering. 2020 Aug 31;18(3):1453-68.
[20] Kumar K, Kumar N. Region coverage-aware path planning for unmanned aerial vehicles: A systematic review. Physical Communication. 2023 Apr 18:102073.
[21] Balampanis F, Maza I, Ollero A. Area partition for coastal regions with multiple UAS. Journal of Intelligent & Robotic Systems. 2017 Dec;88:751-66.
[22] Brown S, Waslander SL. The constriction decomposition method for coverage path planning. In2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2016 Oct 9 (pp. 3233-3238). IEEE.
[23] Lin HY, Huang YC. Collaborative complete coverage and path planning for multi-robot exploration. Sensors. 2021 May 26;21(11):3709.
[24] Balampanis F, Maza I, Ollero A. Area decomposition, partition and coverage with multiple remotely piloted aircraft systems operating in coastal regions. In2016 International Conference on Unmanned Aircraft Systems (ICUAS) 2016 Jun 7 (pp. 275-283). IEEE.
[25] Wu C, Dai C, Gong X, Liu YJ, Wang J, Gu XD, Wang CC. Energy-efficient coverage path planning for general terrain surfaces. IEEE Robotics and Automation Letters. 2019 Feb 17;4(3):2584-91.
[26] Yang T, Miro JV, Lai Q, Wang Y, Xiong R. Cellular decomposition for nonrepetitive coverage task with minimum discontinuities. IEEE/ASME Transactions on Mechatronics. 2020 May 5;25(4):1698-708.
[27] Barrientos A, Colorado J, Cerro JD, Martinez A, Rossi C, Sanz D, Valente J. Aerial remote sensing in agriculture: A practical approach to area coverage and path planning for fleets of mini aerial robots. Journal of Field Robotics. 2011 Sep;28(5):667-89.
[28] Choi, Y.H., Lee, T.K., Baek, S.H. and Oh, S.Y., 2009, October. Online complete coverage path planning for mobile robots based on linked spiral paths using constrained inverse distance transform. In 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems (pp. 5788-5793). IEEE.
[29] Cabreira TM, Di Franco C, Ferreira PR, Buttazzo GC. Energy-aware spiral coverage path planning for uav photogrammetric applications. IEEE Robotics and automation letters. 2018 Jul 16;3(4):3662-8.
[30] Alfred Daniel J, Chandru Vignesh C, Muthu BA, Senthil Kumar R, Sivaparthipan CB, Marin CE. Fully convolutional neural networks for LIDAR–camera fusion for pedestrian detection in autonomous vehicle. Multimedia Tools and Applications. 2023 Feb 1:1-24.
[31] Saadallah A, Finkeldey F, Buß J, Morik K, Wiederkehr P, Rhode W. Simulation and sensor data fusion for machine learning application. Advanced Engineering Informatics. 2022 Apr 1;52:101600.
[32] Velhal S, Sundaram S, Sundararajan N. A decentralized multirobot spatiotemporal multitask assignment approach for perimeter defense. IEEE Transactions on Robotics. 2022 Mar 28;38(5):3085-96.
[33] Krell E, King SA, Carrillo LR. Autonomous Surface Vehicle energy-efficient and reward-based path planning using Particle Swarm Optimization and Visibility Graphs. Applied Ocean Research. 2022 May 1;122:103125.
[34] Benos L, Sørensen CG, Bochtis D. Field deployment of robotic Systems for Agriculture in light of key safety, labor, ethics and legislation issues. Current Robotics Reports. 2022 Jun;3(2):49-56.
[35] Mezgár I, Váncza J. From ethics to standards–A path via responsible AI to cyber-physical production systems. Annual Reviews in Control. 2022 Jan 1;53:391-404.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 EAI Endorsed Transactions on Internet of Things
This work is licensed under a Creative Commons Attribution 3.0 Unported License.
This is an open-access article distributed under the terms of the Creative Commons Attribution CC BY 3.0 license, which permits unlimited use, distribution, and reproduction in any medium so long as the original work is properly cited.
