Efficient Path Planning Algorithm for Mobile Robots Performing Floor Cleaning Like Operations

Vishnu G Nair

Abstract


In this paper, we introduce an efficient path planning algorithm designed for floor cleaning applications, utilizing the concept of Spanning Tree Coverage (STC). We operate under the assumption that the environment, i.e., the floor, is initially unknown to the robot, which also lacks knowledge regarding obstacle positions, except for the workspace boundaries. The robot executes alternating phases of exploration and coverage, leveraging the local map generated during exploration to construct a STC tree, which then guides the subsequent coverage (cleaning) phase. The extent of exploration is determined by the range of the robot's sensors. The path generation algorithms for cleaning fall within the broader category of coverage path planning (CPP) algorithms. A key advantage of this algorithm is that the robot returns to its initial position upon completing the operation, minimizing battery usage since sensors are only active during the exploration phase. We classify the proposed algorithm as an offline-online scheme. To validate the effectiveness and non-repetitive nature of the algorithm, we conducted simulations using VRep/MATLAB environments and implemented real-time experiments using Turtlebot in the ROS-Gazebo environment. The results substantiate the completeness of coverage and underscore the algorithm's significance in applications akin to floor cleaning.

Keywords


Cleaning Path; Mobile Robots; Spanning Tree Coverage; Coverage Path Planning; Exploration; Sensors; Algorithm; Completeness; Non-Overlapping Coverage.

Full Text:

PDF

References


K. L. Doty, R. R. Harrison, and I. Real, “Sweep strategies for a sensory-driven,” in Behavior-Based Vacuum Cleaning Agent, AAAI 1993 Fall Symposium Series, Instantiating Real-World Agents, Research Triangle Park, Raleigh, NC, pp. 1-6, 1993.

M. Weiss-Cohen, I. Sirotin, and E. Rave, "Lawn Mowing System for Known Areas," 2008 International Conference on Computational Intelligence for Modelling Control & Automation, pp. 539-544, 2008, doi: 10.1109/CIMCA.2008.145.

E. U. Acar, H. Choset, Y. Zhang, and M. Schervish, “Path planning for robotic demining: Robust sensor-based coverage of unstructured environments and probabilistic methods,” The International Journal of Robotics Research, vol. 22, no. 7-8, pp. 441–466, 2003.

V. J. Lumelsky, S. Mukhopadhyay, and K. Sun, “Dynamic path planning in sensor-based terrain acquisition,” IEEE Transactions on Robotics and Automation, vol. 6, no. 4, pp. 462–472, 1990.

D. Lee and M. Recce, “Quantitative evaluation of the exploration strategies of a mobile robot,” International Journal of Robotics Research, vol. 16, no. 4 pp. 413–447, 1997.

B. Yamauchi, “Frontier-based exploration using multiple robots,” Proceedings of the Second International Conference on Autonomous Agents, pp. 47–53, 1998.

B. Gonzalez and J. Latombe, “Planning robot motions for range-image acquisition and automatic 3d model construction,” Proceedings of the AAAI Fall Symposium, 1998.

Albers, Kursawe, and Schuierer, “Exploring unknown environments with obstacles,” Algorithmica, vol. 32, no. 1, pp. 123–143, 2002.

H. Choset, “Coverage for robotics–a survey of recent results,” Annals of mathematics and artificial intelligence, vol. 31, no. 1-4, pp. 113–126, 2001.

E. Galceran and M. Carreras, “A survey on coverage path planning for robotics,” Robotics and Autonomous Systems, vol. 61, no. 12, pp. 1258– 1276, 2013.

H. Choset, “Coverage of known spaces: The boustrophedon cellular decomposition,” Autonomous Robots, vol. 9, no. 3, pp. 247–253, 2000.

Y. Gabriely and E. Rimon, “Spanning-tree based coverage of continuous areas by a mobile robot,” Annals of Math and Artificial Intelligence, vol. 31, pp. 77–98, 2001.

Shnaps and E. Rimon, “Online coverage of planar environments by a battery powered autonomous mobile robot,” IEEE Transactions on Automation Science and Engineering, vol. 13, no. 2, pp. 425–436, 2016.

E. U. Acar and H. Choset, “Sensor-based coverage of unknown environments: Incremental construction of Morse decompositions,” The International Journal of Robotics Research, vol. 21, no. 4, pp. 345– 366, 2002.

Y. Gabriely and E. Rimon, “Competitive on-line coverage of grid environments by a mobile robot,” Computational Geometry, vol. 24, no. 3, pp. 197–224, 2003.

T. D. Ranjitha and K. R. Guruprasad, “CCSTC: A truly complete competitive spanning tree coverage algorithm for mobile robots,” Proc. of Advances in Robotics, 2nd International Conference of Robotics Society of India, 2015.

T. D. Ranjitha and K. R. Guruprasad, “Pseudo spanning tree-based complete and competitive robot coverage using virtual nodes,” IFAC Papers on Line: Proc of 4th IFAC Conference on Advances in Control and Optimization of Dynamical Systems (ACODS), 2016.

V. G. Nair and K. R. Guruprasad, “GM-VPC: An algorithm for multi-robot coverage of known spaces using generalized Voronoi partition,” Robotica, vol. 38, no. 5, pp. 845–860, 2020.

V. G. Nair and K. R. Guruprasad, “Centroidal Voronoi Partitioning using Virtual Nodes for Multi Robot Coverage,” International Journal of Engineering and Technology, vol. 7, no. 2.21, pp. 135–139, 2018.

V. G. Nair and K. R. Guruprasad, “Geodesic-VPC: Spatial Partitioning for Multi-Robot Coverage Problem,” International Journal of Robotics and Automation, vol. 33, no. 3, pp. 189–198, 2020.

V. G. Nair and K. R. Guruprasad, “2D-VPC: An Efficient Coverage Algorithm for Multiple Autonomous Vehicles,” International Journal of Control, Automation, and Systems, vol. 19, no. 8, pp. 2891–2901, 2021

V. G. Nair and K. R. Guruprasad, “Manhattan distance based Voronoi partitioning for efficient multi-robot coverage,” in Control Instrumentation Systems: Proceedings of CISCON 2018, pp. 81-90, 2020.

V. G. Nair, A. Rag, K. P. Jayalakshmi, M. V. Dileep, and K. R. Guruprasad, “Cooperative Online Workspace Allocation in the Presence of Obstacles for Multi-robot Simultaneous Exploration and Coverage Path Planning Problem,” International Journal of Control, Automation and Systems, vol. 21, pp- 2338–2349, 2023.

K. R. Jensen-Nau, T. Hermans, and K. K. Leang, “Near-Optimal Area-Coverage Path Planning of Energy-Constrained Aerial Robots with Application in Autonomous Environmental Monitoring,” in IEEE Transactions on Automation Science and Engineering, vol. 18, no. 3, pp. 1453-1468, July 2021.

R. I. Mukhamediev et al., “Coverage Path Planning Optimization of Heterogeneous UAVs Group for Precision Agriculture,” in IEEE Access, vol. 11, pp. 5789-5803, 2023.

X. -X. Shao, Y. -J. Gong, Z. -H. Zhan, and J. Zhang, “Bipartite Cooperative Coevolution for Energy-Aware Coverage Path Planning of UAVs,” in IEEE Transactions on Artificial Intelligence, vol. 3, no. 1, pp. 29-42, Feb. 2022.

T. Yang, J. V. Miro, M. Nguyen, Y. Wang, and R. Xiong, “Template-Free Non-revisiting Uniform Coverage Path Planning on Curved Surfaces,” in IEEE/ASME Transactions on Mechatronics, vol. 28, no. 4, pp. 1853-1861, Aug. 2023.

M. Hassan and D. Liu, “PPCPP: A Predator–Prey-Based Approach to Adaptive Coverage Path Planning,” in IEEE Transactions on Robotics, vol. 36, no. 1, pp. 284-301, Feb. 2020.

J. Lu, B. Zeng, J. Tang, T. L. Lam, and J. Wen, “TMSTC*: A Path Planning Algorithm for Minimizing Turns in Multi-Robot Coverage,” in IEEE Robotics and Automation Letters, vol. 8, no. 8, pp. 5275-5282, Aug. 2023.

J. Chen, C. Du, Y. Zhang, P. Han, and W. Wei, “A Clustering-Based Coverage Path Planning Method for Autonomous Heterogeneous UAVs,” in IEEE Transactions on Intelligent Transportation Systems, vol. 23, no. 12, pp. 25546-25556, Dec. 2022.

Y. Cao, X. Cheng, and J. Mu, “Concentrated Coverage Path Planning Algorithm of UAV Formation for Aerial Photography,” in IEEE Sensors Journal, vol. 22, no. 11, pp. 11098-11111, 2022.

M. Amersdorfer and T. Meurer, “Equidistant Tool Path and Cartesian Trajectory Planning for Robotic Machining of Curved Freeform Surfaces,” in IEEE Transactions on Automation Science and Engineering, vol. 19, no. 4, pp. 3311-3323, Oct. 2022.

B. Jafari, H. Saeedi, S. Enayati, and H. Pishro-Nik, “Energy-Optimized Path Planning for Moving Aerial Base Stations: A Non User-Oriented Framework,” in IEEE Communications Letters, vol. 26, no. 3, pp. 672-676, March 2022.

J. Li, Y. Xiong, J. She, and M. Wu, “A Path Planning Method for Sweep Coverage With Multiple UAVs,” in IEEE Internet of Things Journal, vol. 7, no. 9, pp. 8967-8978, Sept. 2020.

M. Zhang, W. Cai and L. Pang, “Predator-Prey Reward Based Q-Learning Coverage Path Planning for Mobile Robot,” in IEEE Access, vol. 11, pp. 29673-29683, 2023.

A. J. Sanchez-Fernandez, L. F. Romero, G. Bandera, and S. Tabik, “VPP: Visibility-Based Path Planning Heuristic for Monitoring Large Regions of Complex Terrain Using a UAV Onboard Camera,” in IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, vol. 15, pp. 944-955, 2022.

Y. Ma et al., “C C I B A*: An Improved BA* Based Collaborative Coverage Path Planning Method for Multiple Unmanned Surface Mapping Vehicles,” in IEEE Transactions on Intelligent Transportation Systems, vol. 23, no. 10, pp. 19578-19588, Oct. 2022.

J. Xie and J. Chen, “Multiregional Coverage Path Planning for Multiple Energy Constrained UAVs,” in IEEE Transactions on Intelligent Transportation Systems, vol. 23, no. 10, pp. 17366-17381, Oct. 2022.

Z. Wang et al., “Full-Coverage Path Planning and Stable Interaction Control for Automated Robotic Breast Ultrasound Scanning,” in IEEE Transactions on Industrial Electronics, vol. 70, no. 7, pp. 7051-7061, July 2023.

P. Maini, B. M. Gonultas, and V. Isler, “Online Coverage Planning for an Autonomous Weed Mowing Robot With Curvature Constraints,” in IEEE Robotics and Automation Letters, vol. 7, no. 2, pp. 5445-5452, April 2022.

S. Papaioannou, P. Kolios, T. Theocharides, C. G. Panayiotou, and M. M. Polycarpou, “Integrated Guidance and Gimbal Control for Coverage Planning With Visibility Constraints,” in IEEE Transactions on Aerospace and Electronic Systems, vol. 59, no. 2, pp. 1276-1291, April 2023.

C. Zygowski and A. Jaekel, “Optimal path planning strategies for monitoring coverage holes in Wireless Sensor Networks,” Ad Hoc Networks, vol. 96, 2020.

Y. V. Pehlivanoglu and P. Pehlivanoglu, “An enhanced genetic algorithm for path planning of autonomous UAV in target coverage problems,” Applied Soft Computing, vol. 112, 2021.

E. Glorieux, P. Franciosa, and D. Ceglarek, “Coverage path planning with targetted viewpoint sampling for robotic free-form surface inspection,” Robotics and Computer-Integrated Manufacturing, vol. 61, 2020.

A. K. Lakshmanan et al., “Complete coverage path planning using reinforcement learning for Tetromino based cleaning and maintenance robot,” Automation in Construction, vol. 112, 2020.

P. Yao, L. Qiu, J. Qi, and R. Yang, “AUV path planning for coverage search of static target in ocean environment,” Ocean Engineering, vol. 241, 2021.

L. Shi, S. Xu, H. Liu, and Z. Zhan, “QoS-Aware UAV Coverage path planning in 5G mmWave network,” Computer Networks, vol. 175, 2020.

S. W. Cho, H. J. Park, H. Lee, D. H. Shim, and S.-Y. Kim, “Coverage path planning for multiple unmanned aerial vehicles in maritime search and rescue operations,” Computers & Industrial Engineering, vol. 161, 2021.

K. Mayilvaganam, A. Shrivastava, and P. Rajagopal, “An optimal coverage path plan for an autonomous vehicle based on polygon decomposition and ant colony optimization,” Ocean Engineering, vol. 252, 2022.

H. Huang et al., “Robotic organism targets regional coverage capture path planning for marine aquafarm based on value iteration network,” Ocean Engineering, vol. 281, 2023.

E. V. V. Carmona, J. I. V. Gomez, J. C. H. Lozada, and M. A. Cruz, “Coverage path planning for spraying drones,” Computers & Industrial Engineering, vol. 168, 2022.

R. S. Nilsson and K. Zhou, “Method and bench-marking framework for coverage path planning in arable farming,” Biosystems Engineering, vol. 198, 2020.

S. Faghihi, S. Tavana, and A. H. J. de Ruiter, “Kinodynamic on-orbit inspection path planning for full-coverage inspection in close proximity of space structures,” Acta Astronautica, vol. 198, 2022.

B. Ai, M. Jia, H. Xu, J. Xu, Z. Wen, B. Li, and D. Zhang, “Coverage path planning for maritime search and rescue using reinforcement learning,” Ocean Engineering, vol. 241, 2021.

G. Chen, Y. Shen, Y. Zhang, W. Zhang, D. Wang, and B. He, “2D multi-area coverage path planning using L-SHADE in simulated ocean survey,” Applied Soft Computing, vol. 112, 2021.

Y. Ma, Y. Zhao, Z. Li, X. Yan, H. Bi, and G. Królczyk, “A new coverage path planning algorithm for unmanned surface mapping vehicle based on A-star based searching,” Applied Ocean Research, vol. 123, 2022.

S. Yang, J. Huang, X. Xiang, J. Li, and Y. Liu, “Cooperative survey of seabed ROIs using multiple USVs with coverage path planning,” Ocean Engineering, vol. 268, 2023.

S. Dogru and L. Marques, “ECO-CPP: Energy constrained online coverage path planning,” Robotics and Autonomous Systems, vol. 157, 2022.

L. M. S. Bine, A. Boukerche, L. B. Ruiz, and A. A. F. Loureiro, “A Novel Ant Colony-inspired Coverage Path Planning for Internet of Drones,” Computer Networks, vol. 235, 2023.

F. Tang, “Coverage path planning of unmanned surface vehicle based on improved biological inspired neural network,” Ocean Engineering, vol. 278, 2023.

S. Zhao and S. H. Hwang, “Complete coverage path planning scheme for autonomous navigation ROS-based robots,” ICT Express, 2023.

L. Jiao, Z. Peng, L. Xi, S. Ding, and J. Cui, “Multi-Agent Coverage Path Planning via Proximity Interaction and Cooperation,” in IEEE Sensors Journal, vol. 22, no. 6, pp. 6196-6207, 2022.

V. Bulut, “Path planning algorithm for mobile robots based on clustering-obstacles and quintic trigonometric Bézier curve,” Annals of Mathematics and Artificial Intelligence, pp. 1-22, 2023.

C. Li, C. Liu, Y. Song, and Z. Liang, “Parameter value selection strategy for complete coverage path planning based on the Lü system to perform specific types of missions,” Frontiers of Information Technology & Electronic Engineering, vol. 24, no. 2, pp. 231-244, 2023.

S. Shentu, Z. Gong, X. J. Liu, Q. Liu, and F. Xie, “Hybrid Navigation System Based Autonomous Positioning and Path Planning for Mobile Robots,” Chinese Journal of Mechanical Engineering, vol. 35, no. 1, pp. 1-13, 2022.

G. Kyprianou, L. Doitsidis, and S. A. Chatzichristofis, “Towards the Achievement of Path Planning with Multi-robot Systems in Dynamic Environments,” J. Intell. Robot. Syst., vol. 104, no. 15, 2022.

A. Singha, A. K. Ray, and A. B. Samaddar, “Neural dynamics based complete grid coverage by single and multiple mobile robots,” SN Applied Sciences, vol. 3, no. 5, p. 543, 2021.

P. Tirandazi, A. Rahiminasab, and M. J. Ebadi, “An efficient coverage and connectivity algorithm based on mobile robots for wireless sensor networks,” Journal of Ambient Intelligence and Humanized Computing, pp. 1-23, 2022.

B. Xu et al., “High-efficiency inspecting method for mobile robots based on task planning for heat transfer tubes in a steam generator,” Frontiers of Mechanical Engineering, vol. 18, no. 2, pp. 1-15, 2023.

D. An, Y. Mu, Y. Wang, B. Li, and Y. Wei, “Intelligent Path Planning Technologies of Underwater Vehicles: a Review,” Journal of Intelligent & Robotic Systems, vol. 107, no. 2, p. 22, 2023.

K. Sridharan, P. McNamee, Z. N. Ahmadabadi, and J. Hudack, “Online search of unknown terrains using a dynamical system-based path planning approach,” Journal of Intelligent & Robotic Systems, vol. 106, no. 1, p. 21, 2022.

S. Ganesan, S. K. Natarajan, and J. Srinivasan, “A global path planning algorithm for mobile robot in cluttered environments with an improved initial cost solution and convergence rate,” Arabian Journal for Science and Engineering, vol. 47, no. 3, pp. 3633-3647, 2022.

J. Mao, X. Hu, L. Zhang, X. He, and M. Milford, “A bio-inspired goal-directed visual navigation model for aerial mobile robots,” Journal of Intelligent & Robotic Systems, vol. 100, pp. 289-310, 2020.

J. K. Verma and V. Ranga, “Multi-robot coordination analysis, taxonomy, challenges and future scope,” Journal of intelligent & robotic systems, vol. 102, pp. 1-36, 2021.

X. Zhang, Y. Huang, S. Wang, W. Meng, G. Li, and Y. Xie, “Motion planning and tracking control of a four-wheel independently driven steered mobile robot with multiple maneuvering modes,” Frontiers of Mechanical Engineering, vol. 16, pp. 504-527, 2021.

L. Wang, Z. Wang, M. Liu, Z. Ying, N. Xu, and Q. Meng, “Full coverage path planning methods of harvesting robot with multi-objective constraints,” Journal of Intelligent & Robotic Systems, vol. 106, no. 1, p. 17, 2022.

L. Chang, L. Shan, C. Jiang, and Y. Dai, “Reinforcement based mobile robot path planning with improved dynamic window approach in unknown environment,” Autonomous Robots, vol. 45, pp. 51-76, 2021.

W. Pawgasame and K. Wipusitwarakun, “Mobile sensor patrol path planning in partially observable border regions,” Applied Intelligence, pp. 1-21, 2021.

K. C. Huang, F. L. Lian, C. T. Chen, C. H. Wu, and C. C. Chen, “A novel solution with rapid Voronoi-based coverage path planning in irregular environment for robotic mowing systems,” International Journal of Intelligent Robotics and Applications, vol. 5, no. 4, pp. 558-575, 2021.

A. Hentout, A. Maoudj, and M. Aouache, “A review of the literature on fuzzy-logic approaches for collision-free path planning of manipulator robots,” Artificial Intelligence Review, vol. 56, no. 4, pp. 3369-3444, 2023.

J. I. Vasquez-Gomez, M. Marciano-Melchor, L. Valentin, and J. C. Herrera-Lozada, “Coverage path planning for 2d convex regions,” Journal of Intelligent & Robotic Systems, vol. 97, pp. 81-94, 2020.

H. Taheri and Z. C. Xia, “SLAM; definition and evolution,” Engineering Applications of Artificial Intelligence, vol. 97, p. 104032, 2021.




DOI: https://doi.org/10.18196/jrc.v5i1.20035

Refbacks

  • There are currently no refbacks.


Copyright (c) 2024 Vishnu G Nair

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

 

Journal of Robotics and Control (JRC)

P-ISSN: 2715-5056 || E-ISSN: 2715-5072
Organized by Peneliti Teknologi Teknik Indonesia
Published by Universitas Muhammadiyah Yogyakarta in collaboration with Peneliti Teknologi Teknik Indonesia, Indonesia and the Department of Electrical Engineering
Website: http://journal.umy.ac.id/index.php/jrc
Email: jrcofumy@gmail.com

Kuliah Teknik Elektro Terbaik