Centroidal Voronoi Partitioning using Virtual Nodes for MultiRobot Coverage

  • Authors

    • Vishnu G Nair
    • Guruprasad K R
    2018-04-20
    https://doi.org/10.14419/ijet.v7i2.21.11852
  • Centroidal Voronoi Configuration, Multi-robot coverage, Virtual nodes

  • Abstract

    This paper addresses the problem of Voronoi partitioning using Centroidal Voronoi configuration for a multi-robotic coverage strategy known as Voronoi Partition based Coverage (VPC) algorithm. In VPC, the area to be covered is divided into Voronoi cells and each robot covers the corresponding cell. We use the concept of Centroidal Voronoi Configuration (CVC) to achieve a more uniform load distribution among the robots in terms of the area covered. Instead of the robots moving physically into the CVC, we introduce a concept of virtual nodes, which are deployed into CVC. Once the Voronoi partition is created based on the virtual nods, the robots cover the corresponding Voronoi cells. A gradient based control law has been used for deployment of the virtual nodes. Simulation results are provided to demonstrate the proposed deployment and partitioning scheme.

     

  • References

    1. [1] P. Dasgupta, a. Munoz-melendez, and k. Guruprasad, “multirobot terrain coverage and task allocation for autonomous detection of landmines,†in proc. Of spie 8359, sensors, and command, control, communications, and intelligence (c3i), 2012.

      [2] Choset, “coverage of known spaces: the boustrophedon cellular decomposition,†autonomous robots, vol. 9, no. 3, pp. 247–253, 2000.

      [3] Galceran and m. Carreras, “a survey on coverage path planning for robotics,†robotics and autonomous systems, vol. 61, no. 12, pp.1258–1276, 2013.

      [4] M. Jager and b. Nebel, "dynamic decentralized area partitioning for cooperating cleaning robots," proceedings 2002 ieee international conference on robotics and automation (cat. No.02ch37292), 2002, pp. 3577-3582 vol.4.

      [5] Ioannis rekleitis, ai peng ,edward samuel rankin, howie choset “efficient boustrophedon multi-robot coverage: an algorithmic approach,†annals of math and artificial intelligence, vol. 52, pp. 109–142, 2008.

      [6] N. Hazon, g.a. kaminka “on redundancy, efficiency, and robustness in coverage for multiple robots,†robotics and autonomous systems, pp. 1102–1114, 2008.

      [7] N. Agmon, n. Hazon, and g.a kaminka, “the giving tree: constructing trees for efficient offline and online multi-robot coverage,†annals of math and artificial intelligence, vol. 52, no. 2-4, pp. 43–168, 2009.

      [8] X. Zheng, S. Koenig, D. Kempe, and S. Jain, “Multirobot forest coverage for weighted and unweighted terrain,†IEEE Transactions on Robotics, vol. 26, no. 6, pp. 1018–1031, 2010.

      [9] Z. Wilson, T. Whipple, and P. Dasgupta, “Multi-robot coverage with dynamic coverage information compression,†in Proc of 8th International Conference on Informatics in Control, Automation and Robotics, 2011, pp. 236–241.

      [10] D. Michel and K. McIsaac, “New path planning scheme for complete coverage of mapped areas by single and multiple robots,†in Proc of International Conference on Mechatronics and Automation (ICMA).IEEE, 2012, pp. 1233–1240.

      [11] K.R Guruprasad, Z. Wilson, and P. Dasgupta, “Complete coverage of an initially unknown environment by multiple robots using Voronoi partition,†in Proc of advances in control and optimization of dynamical systems (ACODS), 2012.

      [12] T.W Min and H.K Yin, in Proc of International Conference on Intelligent Robots and Systems, 1998, pp. 380–385.

      [13] S. Hert and V. Lumelsky, “Polygon area decomposition for multiple robot workspace division,†International Journal of Computational Geometry & Applications, vol. 8., 437—466,1998.

      [14] B. Bash and P. Desnoyers, “Exact distributed Voronoi cell computation in sensor networks,†in Proc of the Sixth IEEE/ACM Conference On Information Processing in Sensor Networks, 2007, pp. 236–243.

      [15] K.R. Guruprasad and P. Dasgupta, “Distributed Voronoi partitioning for multi-robot systems with limited range sensors,†in Proc of IEEE/RSJ International Conference on Robotics and Intelligent Systems, 2012, pp. 3546–3552.

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

      [17] Y. Gabriely and E. Rimon, “Spanning-tree based coverage of continuous areas by a mobile robot,†Annals of Mathematics

      [18] A. Okabe, B. Boots, K. Sugihara, and S. Chiu, Spatial Tessellations. Concepts and Applications of Voronoi Diagrams, 2000.

      [19] J. Cort´es, S. Mart´ınez, T. Karata, and F. Bullo, “Coverage control for mobile sensing networksâ€, IEEE Transactions on Robotics and Automation, vol 20, no. 2, 2004, pp. 243-255.

      [20] K.R. Guruprasad and D. Ghose, “Automated multi-agent search using centroidal Voronoi configurationâ€, IEEE Transactions on Automation Science and Engineering, vol 8, issue 2, April 2011, pp. 420-423.

  • Downloads

  • How to Cite

    G Nair, V., & K R, G. (2018). Centroidal Voronoi Partitioning using Virtual Nodes for MultiRobot Coverage. International Journal of Engineering & Technology, 7(2.21), 135-139. https://doi.org/10.14419/ijet.v7i2.21.11852

    Received date: 2018-04-21

    Accepted date: 2018-04-21

    Published date: 2018-04-20