SpringerLink
Log in

Cooperative Online Workspace Allocation in the Presence of Obstacles for Multi-robot Simultaneous Exploration and Coverage Path Planning Problem

  • Regular Papers
  • Robot and Applications
  • Published:
International Journal of Control, Automation and Systems Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. 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).

    Article  Google Scholar 

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

  3. 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.

    Article  Google Scholar 

  4. 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.

    Article  Google Scholar 

  5. 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.

    Article  Google Scholar 

  6. 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.

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  9. 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.

    Article  MathSciNet  MATH  Google Scholar 

  10. 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.

  11. 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.

  12. 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.

    MATH  Google Scholar 

  13. 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.

  14. T. W. Min and H. K. Yin, “A decentralized approach for cooperative swee** 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.

  15. 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.

    Article  MathSciNet  MATH  Google Scholar 

  16. 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.

  17. 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.

    Article  MathSciNet  MATH  Google Scholar 

  18. 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.

  19. J. Song and S. Gupta, “ε⋆*: An online coverage path planning algorithm,” IEEE Transactions on Robotics, vol. 34, pp. 526–533, 2018.

    Article  Google Scholar 

  20. 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.

    Article  Google Scholar 

  21. 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.

    Google Scholar 

  22. 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.

  23. 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.

  24. H. Kurt, P. Dasgupta, and K. R. Guruprasad, “A repartitioning algorithm to guarantee complete, non-overlap** 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.

  25. 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.

    Article  Google Scholar 

  26. 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.

    Article  Google Scholar 

  27. V. G. Nair and K. R. Guruprasad, “MR-SimExCoverage: Multi-robot simultaneous exploration and coverage,” Computers and Electrical Engineering, vol. 88, 106680, 2020.

    Article  Google Scholar 

  28. 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.

    Google Scholar 

  29. 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.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Aeronautical and Automobile Engineering, Manipal Institute of Technology, Manipal Academy of Higher Education, Manipal Karnataka, 576104, India

    Vishnu G. Nair

  2. Department of Electronics and Communication Engineering, CMR Institute of Technology, Bengaluru, Karnataka, 560037, India

    Rag S. Adarsh

  3. Department of Electronics and Communication Engineering, St. Joseph Engineering College, Mangaluru, Karnataka, 575028, India

    K. P. Jayalakshmi

  4. Chungnam National University, Chungnam, Korea

    M. V. Dileep

  5. Department of Mechanical Engineering, Indian Institute of Technology, Kanpur, India

    K. R. Guruprasad

Authors
  1. Vishnu G. Nair
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rag S. Adarsh
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. K. P. Jayalakshmi
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. M. V. Dileep
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. K. R. Guruprasad
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to K. R. Guruprasad.

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

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12555-022-0182-9

Keywords

Search

Navigation