Abstract
In this paper, a dynamic workspace allocation methodology for coverage path planning using multiple robots in the presence of obstacles is presented. The entire workspace is initially partitioned using the Manhattan Voronoi partitioning method, without considering the obstacles present, and the robots execute Multi-Robot Simultaneous Exploration and Coverage (MRSimExCoverage) using the Spanning Tree Coverage (STC) algorithm and cover the workspace. A dynamic workspace re-allocation strategy to optimize the area covered by each robot, whenever obstacles are detected, so as to avoid certain obstacle-induced coverage issues is studied. Simulation experiments within the Matlab/V-rep environment are used to demonstrate and validate the performance of the proposed algorithm. Though the authors used the STC algorithm for path planning for demonstration, any suitable coverage algorithm may be used.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
V. J. Lumelsky, S. Mukhopadhyay, and K. Sun, “Dynamic path planning in sensor-based terrain acquisition,” IEEE Transactions on Robot and Automation, vol. 6, no. 4, pp. 462–472, 1990).
B. Yamauchi, “Frontier-based exploration using multiple robots,” Proc. of the Second International Conference on Autonomous Agents, Minneapolis, Minnesota, USA, pp. 47–53, 1998.
V. R. Jisha and D. Ghose, “Frontier based goal seeking for robots in unknown environments,” Journal of Intel and Robot Systems, vol. 67, pp. 229–254, 2012.
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.
D. C. Guastella, L. Cantelli, G. Giammello, C. D. Melita, G. Spatino, and G. Muscato, “Complete coverage path planning for aerial vehicle flocks deployed in outdoor environments,” Computers & Electrical Engineering, vol. 75, pp. 189–201, 2019.
P. Maini, K. Sundar, M. Singh, S. Rathinam, and P. B. Sujit, “Cooperative aerial-ground vehicle route planning with fuel constraints for coverage applications,” IEEE Transactions on Aerospace and Electronic Systems, vol. 55, no. 6, pp. 3016–3028, 2019.
H. Choset, “Coverage of known spaces: The boustrophedon cellular decomposition,” Autonomous Robots, vol. 9, pp. 247–253, 2000.
Y. Gabriely and E. Rimon, “Competitive on-line coverage of grid environments by a mobile robot,” Computational Geometry, vol. 24, pp. 197–224, 2003.
N. Agmon, N. Hazon, and G. A. Kaminka, “The giving tree: Constructing trees for efficient offine and online multi-robot coverage,” Annals of Math and Artificial Intelligence, vol. 52, pp. 143–168, 2008.
X. Zheng, S. Jain, S. Koenig, and D. Kempe, “Multi-robot forest coverage,” Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Edmonton, AB, Canada, pp. 3852–3857, 2005.
M. A. Batalin and G. S. Sukhatme, “Spreading out: A local approach to multi-robot coverage,” Proc. of the 6th International Symposium on Distributed Autonomous Robotics Systems, Fukuoka, Japan, pp. 373–382, 2002.
L. Ludwig and M. Gini, “Robotic swarm dispersion using wireless intensity signals,” Gini, M., Voyles, R. (eds), Distributed Autonomous Robotic Systems, vol 7, Springer, Tokyo, pp. 135–144, 2006.
Z Wilson, T Whipple, and P Dasgupta, “Multi-robot coverage with dynamic coverage information compression,” Proc. of the 8th International Conference on Informatics in Control Automation and Robotics, Noordwijkerhout, The Netherlands, pp. 236–241, 20011.
T. W. Min and H. K. Yin, “A decentralized approach for cooperative sweeping by multiple mobile robots,” Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems, Innovations in Theory, Practice and Applications, Victoria, BC, Canada, pp. 380–385, 1998.
S. Hert and V. Lumelsky, “Polygon area decomposition for multiple robot workspace division,” International Journal of Computational Geometry and Applications, vol. 8, pp. 437–466, 1998.
M. Jager and B. Nebel, “Dynamic decentralized area partitioning for cooperating cleaning robots,” Proc. of IEEE International Conference on Robotics and Automation, Washington, DC, USA, pp. 3577–3582, 2002.
I. Rekleitis, A. P. New, P. Rankin, E. Samuel, and H. Choset, “Efficient boustrophedon multi-robot coverage: An algorithmic approach,” Annals of Mathematics and Artificial Intelligence, vol. 52, pp. 109–142, 2008.
K. R. Guruprasad, Z. Wilson, and P. Dasgupta, “Complete coverage of an initially unknown environment by multiple robots using Voronoi partition,” Proc. of the 2nd International Confence on Advances in Control and Optimization of Dynamical Systems, 2012.
J. Song and S. Gupta, “ε⋆*: An online coverage path planning algorithm,” IEEE Transactions on Robotics, vol. 34, pp. 526–533, 2018.
V. G. Nair and K. R. Guruprasad, “Manhattan distance based Voronoi partitioning for efficient multi-robot coverage,” Shreesha, C., Gudi, R. (eds), Control Instrumentation Systems. Lecture Notes in Electrical Engineering, Springer, Manipal, India, vol. 581, pp. 81–90, 2020.
K. R. Guruprasad and T. D. Ranjitha, “ST-CTC: A spanning tree-based competitive and truly complete coverage algorithm for mobile robots,” Proc. of the 2nd International Conference of Robotics, Society of India, Goa, India, 2015.
R. E. Tarjan, “Data structures and network algorithms,” CBMS-NSF Regional Conference Series in Applied Mathematics CB44 Society for Industrial and Applied Mathematics, Philadelphia, USA, ISBN:978-0-89871-187-5, 1983.
K. R. Guruprasad and P. Dasgupta, “Distributed spatial partitioning of an initially unknown region for a multi-robot coverage application,” A. Lomuscio, P. Scerri, A. Bazzan, and M. Huhns (eds.), Proc. of the 13th International Conference on Autonomous Agents and Multiagent Systems, Paris, France, pp. 1453–1454, 2012.
H. Kurt, P. Dasgupta, and K. R. Guruprasad, “A repartitioning algorithm to guarantee complete, non-overlapping planar coverage with multiple robots,” N. Y. Chong and Y. J. Cho, (eds), Distributed Autonomous Robotic Systems, Springer Tracts in Advanced Robotics, vol. 112, pp. 33–48, 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, “MR-SimExCoverage: Multi-robot simultaneous exploration and coverage,” Computers and Electrical Engineering, vol. 88, 106680, 2020.
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.
Author information
Authors and Affiliations
Corresponding author
Additional information
Conflicts of Interests
The authors declare that there is no competing financial interest or personal relationship that could have appeared to influence the work reported in this paper. The authors have no relevant financial or non-financial interests to disclose.
Vishnu G. Nair received his Ph.D. degree from the National Institute of Technology Karnataka India. He is with the Department of Aeronautical and Automobile Engineering, Manipal Academy of Higher Education. His research interests include multi robotic systems.
Adarsh Rag S. received his Ph.D. degree from the Manipal Institute of Technology India. He is with CMR Institute of Technology, Bengaluru India. His research interests include algorithms and nanoelectronics.
Jayalakshmi K. P. is an Assistant Professor with the Department of Electronics and Communication Engineering at St. Joseph Engineering College, Mangaluru. Her research interests include digital control and artificial intelligence.
Dileep M. V. was with the Chungnam National University, Korea. His research interests include control systems and robotics.
K. R. Guruprasad received his Ph.D. degree from the Indian Institute of Science, Bengaluru, India. He is with the Department of Mechanical Engineering, IIT Kanpur India. His research interests include control engineering, robot motion planning, and multi-robotic systems and applications.
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The authors would like to thank Manipal Academy of Higher Education, Manipal, for providing with the facilities needed for the proposed research work.
Rights and permissions
About this article
Cite this article
Nair, V.G., Adarsh, R.S., Jayalakshmi, K.P. et al. Cooperative Online Workspace Allocation in the Presence of Obstacles for Multi-robot Simultaneous Exploration and Coverage Path Planning Problem. Int. J. Control Autom. Syst. 21, 2338–2349 (2023). https://doi.org/10.1007/s12555-022-0182-9
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12555-022-0182-9