Skip to main content

2020 | OriginalPaper | Buchkapitel

Multi-robot Coverage Using Voronoi Partitioning Based on Geodesic Distance

verfasst von : Vishnu G. Nair, K. R. Guruprasad

Erschienen in: Control Instrumentation Systems

Verlag: Springer Singapore

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this paper we propose Geodesic-VPC, a “partition” and “cover” strategy for a multi-robot system using Voronoi partitioning based on geodesic distance metric in the place of the usual Euclidean distance. Each robot is responsible for covering the corresponding geodesic-Voronoi cell using a single-robot coverage strategy. The proposed partitioning scheme ensures that Voronoi cells are contiguous even in the presence of obstacles. We demonstrate that if the single-robot coverage strategy is capable of providing a complete and non-repetitive coverage, then the proposed Geodesic-VPC strategy provides a complete and non-repetitive coverage. We use spanning tree-based coverage algorithm as the underlying single-robot coverage strategy for the purpose of demonstration, though any existing single-robot coverage algorithm can be used.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Choset H (2001) Coverage for robotics—a survey of recent results. Ann Math Artif Intell 31(1–4):113–126CrossRef Choset H (2001) Coverage for robotics—a survey of recent results. Ann Math Artif Intell 31(1–4):113–126CrossRef
2.
Zurück zum Zitat Galceran E, Carreras M (2013) A survey on coverage path planning for robotics. Robot Auton Syst 61:1258–1276CrossRef Galceran E, Carreras M (2013) A survey on coverage path planning for robotics. Robot Auton Syst 61:1258–1276CrossRef
3.
Zurück zum Zitat Guruprasad KR, Wilson Z, Dasgupta P (2012) Complete coverage of an initially unknown environment by multiple robots using voronoi partition. In: Proceedings of 2nd international conference on advances in control and optimization of dynamical systems Guruprasad KR, Wilson Z, Dasgupta P (2012) Complete coverage of an initially unknown environment by multiple robots using voronoi partition. In: Proceedings of 2nd international conference on advances in control and optimization of dynamical systems
4.
Zurück zum Zitat Guruprasad KR, Dasgupta P (2012) Distributed spatial partitioning of an initially unknown region for a multi-robot coverage application. In: Autonomous robots and multirobot systems (ARMS) workshop (co-located with AAMAS 2012) Guruprasad KR, Dasgupta P (2012) Distributed spatial partitioning of an initially unknown region for a multi-robot coverage application. In: Autonomous robots and multirobot systems (ARMS) workshop (co-located with AAMAS 2012)
5.
Zurück zum Zitat Hungerford K, Dasgupta P, Guruprasad KR (2014) A repartitioning algorithm to guarantee complete, non-overlapping planar coverage with multiple robots. In: Proceedings of DARS Hungerford K, Dasgupta P, Guruprasad KR (2014) A repartitioning algorithm to guarantee complete, non-overlapping planar coverage with multiple robots. In: Proceedings of DARS
6.
Zurück zum Zitat Bhattacharya S, Michael N, Kumar V (2013) Distributed coverage and exploration in unknown non-convex environments. In: Distributed autonomous robotic systems, pp 61–75 Bhattacharya S, Michael N, Kumar V (2013) Distributed coverage and exploration in unknown non-convex environments. In: Distributed autonomous robotic systems, pp 61–75
7.
Zurück zum Zitat Fekete SP, Kamphans T, Kroller A, Mitchell J, Schmidt C (2011) Exploring and triangulating a region by a swarm of robots. In: Proceedings of APPROX, LNCS, vol 6845, pp 206–217CrossRef Fekete SP, Kamphans T, Kroller A, Mitchell J, Schmidt C (2011) Exploring and triangulating a region by a swarm of robots. In: Proceedings of APPROX, LNCS, vol 6845, pp 206–217CrossRef
8.
Zurück zum Zitat Breitenmoser A, Schwager M, Metzger J-C, Siegwart R, Rus D (2010) Voronoi coverage of non-convex environments with a group of networked robots. In: Proceedings of IEEE international conference on robotics and automation, pp 4982–4989 Breitenmoser A, Schwager M, Metzger J-C, Siegwart R, Rus D (2010) Voronoi coverage of non-convex environments with a group of networked robots. In: Proceedings of IEEE international conference on robotics and automation, pp 4982–4989
9.
Zurück zum Zitat Lee SK, Fekete SP, McLurkin J (2014) Geodesic topological Voronoi tessellations in triangulated environments with multi-robot systems. In: Proceedings of IEEE international conference on robotics and automation Lee SK, Fekete SP, McLurkin J (2014) Geodesic topological Voronoi tessellations in triangulated environments with multi-robot systems. In: Proceedings of IEEE international conference on robotics and automation
10.
Zurück zum Zitat Pimenta LCA, Kumar V, Mesquita RC, Pereira GAS (2008) Sensing and coverage for a network of heterogeneous robots. In: 2008 47th IEEE conference on decision and control, pp 3947–3952 Pimenta LCA, Kumar V, Mesquita RC, Pereira GAS (2008) Sensing and coverage for a network of heterogeneous robots. In: 2008 47th IEEE conference on decision and control, pp 3947–3952
11.
Zurück zum Zitat Thanou M, Stergiopoulos Y, Tzes A (1989) On the geodesic Voronoi diagram of point sites in a simple polygon. In: Algorithmica, pp 109–140 Thanou M, Stergiopoulos Y, Tzes A (1989) On the geodesic Voronoi diagram of point sites in a simple polygon. In: Algorithmica, pp 109–140
12.
Zurück zum Zitat Aronov B (2013) Distributed coverage using geodesic metric for non-convex environments. In: 2013 IEEE international conference on robotics and automation, pp 933–938 Aronov B (2013) Distributed coverage using geodesic metric for non-convex environments. In: 2013 IEEE international conference on robotics and automation, pp 933–938
13.
Zurück zum Zitat Gabriely Y, Rimon E (2001) Spanning tree based coverage of continuous areas by a mobile robot. Ann Math Artif Intell 31:77–98 Gabriely Y, Rimon E (2001) Spanning tree based coverage of continuous areas by a mobile robot. Ann Math Artif Intell 31:77–98
14.
Zurück zum Zitat Ranjitha TD, Guruprasad KR (2015) CCSTC: a truly complete competitive spanning tree coverage algorithm for mobile robots. In: Proceedings of advances in robotics, 2nd international conference of robotics society of India. BITS Goa, India, July 2015 Ranjitha TD, Guruprasad KR (2015) CCSTC: a truly complete competitive spanning tree coverage algorithm for mobile robots. In: Proceedings of advances in robotics, 2nd international conference of robotics society of India. BITS Goa, India, July 2015
Metadaten
Titel
Multi-robot Coverage Using Voronoi Partitioning Based on Geodesic Distance
verfasst von
Vishnu G. Nair
K. R. Guruprasad
Copyright-Jahr
2020
Verlag
Springer Singapore
DOI
https://doi.org/10.1007/978-981-13-9419-5_5

Neuer Inhalt