GEODESIC-VPC: SPATIAL PARTITIONING FOR MULTI-ROBOT COVERAGE PROBLEM

Vishnu G. Nair and K.R. Guruprasad

References

  1. [1] J. Zhong and J. Su, Robot path planning in narrow passages based on probabilistic roadmaps, International Journal of Robotics and Automation, 28(01), 2013.
  2. [2] T. Wang, C. Sabourin, and K. Madani, A novel path planning approach for multi-robot based transportation, International Journal of Robotics and Automation, 28(01), 2013.
  3. [3] B.M. Madhu and M. Sreekumar, Implementation of role assignment and fault tree analysis for multi robot interaction, International Journal of Robotics and Automation, 32(01), 2017.
  4. [4] H. Choset, Coverage for robotics–a survey of recent results, Annals of Mathematics and Artificial Intelligence, 31(1–4), 2001, 113–126.
  5. [5] E. Galceran and M. Carreras, A survey on coverage path planning for robotics, Robotics and Autonomous Systems, 61, 2013, 1258–1276.
  6. [6] J. Zhang, H. Lv, D. He, L. Huang, Y. Dai, and Z. Zhang, Discrete bioinspired neural network for complete coverage path planning, International Journal of Robotics and Automation, 32, 2017.
  7. [7] M. Batalin and G. Sukhatme, Spreading out: A local approach to multi-robot coverage, in Distributed autonomous robotic systems (Tokyo: Springer, 2006), 373–382.
  8. [8] H. Choset, Coverage of known spaces: the boustrophedon cellular decomposition, Autonomous Robots, 9, 2000, 247–253.
  9. [9] Y. Gabriely and E. Rimon, Spanning-tree based coverage of continuous areas by a mobile robot, Annals of Mathematics and Artificial Intelligence, 31, 2001, 77–98.
  10. [10] N. Hazon and G. Kaminka, On redundancy, efficiency, and roboustness in coverage for mulitple robots, Robotics and Autonomous Systems, 56, 2011, 1102–1114.
  11. [11] X. Zheng, S. Koenig, D. Kempe, and S. Jain, Multirobot forest coverage for weighted and unweighted terrain, IEEE Transactions on Robotics, 26(6), 2010, 1018–1031.
  12. [12] L. Ludwig and M. Gini, Robotic swarm dispersion using wireless intensity signals, in Distributed autonomous robotic systems (Tokyo: Springer, 2006), 135–144.
  13. [13] Z. Wilson, T. Whipple, and P. Dasgupta, Multi-robot cover- age with dynamic coverage information compression, 8th Int. Conf. on Informatics in Control, Automation and Robotics, Noordwijkerhout, Netherlands, 2011, 236–241.
  14. [14] T. Min and H. Yin, A decentralized approach for cooperative sweeping by multiple mobile robots, Proc. of Int. Conf. on Intel. Robots and Systems, Victoria, BC, Canada, 1998, 380–385.
  15. [15] S. Hert and V. Lumelsky, Polygon area decomposition for multiplerobot workspace division, International Journal of Computational Geometry & Applications, 8, 1998, 437–466.
  16. [16] M. Jager and B. Nebel, Dynamic decentralized area partitioning for cooperating cleaning robots, Proc. of IEEE Int. Conf. on Robotics and Automation, Washington, DC, USA, 2002, 3577–3582.
  17. [17] M. Schneider-Fontan and M. J. Mataric, Territorial multi-robot task division, IEEE Transactions on Robotics and Automation, 14(5), 1998, 815–822.
  18. [18] K.R. Guruprasad, Z. Wilson, and P. Dasgupta, Complete coverage of an initially unknown environment by multiple robots using voronoi partition, Proc of 2nd Int. Conf. on Adv. in Control and Opt. of Dyn. Systems, Bangalore, India, 2012.
  19. [19] S. Bhattacharya, N. Michael, and V. Kumar, Distributed coverage and exploration in unknown non-convex environments, in Distributed Autonomous Robotic Systems (Berlin: Springer, 2013), 61–75.
  20. [20] C. Caicedo-Nuez and M. Zefran, A coverage algorithm for a class of non-convex regions, Proc. of the IEEE Conf. on Decision and Control, Cancun, Mexico, 2008, 4244–4249.
  21. [21] S.P. Fekete, T. Kamphans, A. Kroller, J. Mitchell, and C. Schmidt, Exploring and triangulating a region by a swarm of robots, Proc of APPROX, LNCS, vol. 6845, 2011, 206–217.
  22. [22] I. Rekleitis, A.P. New, E.S. Rankin, and H. Choset, Efficient boustrophedon multi-robot coverage: an algorithmic approach, Annals of Mathematics and Artificial Intelligence, 52, 2008, 109–142.
  23. [23] H. Choset, Coverage of known spaces: The boustrophedon cellular decomposition, Autonomous Robots, 9(30), 2000, 247– 253.
  24. [24] K.R. Guruprasad, and P. Dasgupta, Distributed spatial partitioning of an initially unknown region for a multi-robot coverage application, Autonomous Robots and Multrobot Systems (ARMS) workshop (co-located with AAMAS 2012), Paris, France, 2012.
  25. [25] K. Hungerford, P. Dasgupta, and K.R. Guruprasad, A repartitioning algorithm to guarantee complete, non-overlapping planar coverage with multiple robots, Proc. of DARS, Daejeon, South Korea, 2014.
  26. [26] L.C.A. Pimenta, V. Kumar, R.C. Mesquita, and G.A.S. Pereira, Sensing and coverage for a network of heterogeneous robots, Proc. of the IEEE Conf. on Decision and Control, Cancun, Mexico, 2008, 3947–3952.
  27. [27] A. Breitenmoser, M. Schwager, J.-C. Metzger, R. Siegwart, and D. Rus, Voronoi coverage of non-convex environments with a group of networked robots, Proc. of IEEE Int. Conf. on Robotics and Automation, Anchorage, AK, USA, 2010, 4982–4989.
  28. [28] S.K. Lee, S.P. Fekete, and J. McLurkin, Geodesic topological voronoi tessellations in triangulated environments with multi-robot systems, Proc. of IEEE Int. Conf. on Robotics and Automation, Chicago, IL, USA, 2014.
  29. [29] A. Becker, S.P. Fekete, A. Kroller, S.K. Lee, J. McLurkin, and C. Schmidt, Triangulating unknown environments using robot swarms, Proc. of the 29th Annual ACM Symp. on Computational Geometry, Rio de Janeiro, Brazil, 2013, 345– 346.
  30. [30] M. Thanou, Y. Stergiopoulos, and A. Tzes, Distributed coverage using geodesic metric for non-convex environments, 2013 IEEE Int. Conf. on Robotics and Automation, Karlsruhe, Germany, 2013, 933–938.
  31. [31] B. Aronov, On the geodesic voronoi diagram of point sites in a simple polygon, Algorithmica, 4(1), 1989, 109–140.
  32. [32] E. Gonzalez, O. Alvarez, Y. Diaz, C. Parra, and C. Bustacara, BSA: A complete coverage algorithm, Proc. of IEEE Int. Conf. on Robotics and Automation, Barcelona, Spain, 2005, 2040–2044.
  33. [33] K.R. Guruprasad and T.D. Ranjitha, Truly complete competitive robot coverage path planning using approximate cellular decomposition, Proc. of Advances in Robotics, 2nd Int. Conf. of Robotics Society of India, Goa, India, 2015.
  34. [34] Y. Gabriely and E. Rimon, Competitive on-line coverage of grid environments by a mobile robot, Computational Geometry, 24(3), 2003, 197–224.

Important Links:

Go Back