Multi-robot coverage and exploration are fundamental problems in robotics. A widely used, efficient and distributable algorithm for achieving coverage of a convex environment with Euclidean metrics is that proposed by Cortes which is based on the discrete-time Lloyd’s algorithm. This algorithm is not directly applicable to general Riemannian manifolds with boundaries that are non-convex and are intrinsically non-Euclidean. In this paper we generalize the control law based on minimization of the coverage functional to such non-Euclidean spaces punctured by obstacles. We also propose a practical discrete implementation based on standard graph search-based algorithms. We demonstrate the applicability of the proposed algorithm by solving efficient coverage problems on a sphere and a torus with obstacles, and exploration problems in non-convex indoor environments.
AdamatzkyA (1996) Voronoi-like partition of lattice in cellular automata. Mathematical and Computer Modelling23: 51–66.
2.
AlexanderS (1981) Distance Geometry in Riemannian Manifolds-with-Boundary. New York: Springer, vol. 838, pp. 12–18.
3.
BergerM (2003) A Panoramic View of Riemannian Geometry. Berlin: Springer-Verlag.
4.
BhattacharyaSGhristRKumarV (2012) Multi-robot coverage and exploration in non-Euclidean metric spaces. In: 10th International workshop on the algorithmic foundations of robotics (WAFR’2012), Cambridge, USA, 13–15 June 2012, pp.245–262. Berlin: Springer.
5.
BhattacharyaSMichaelNKumarV (2010) Distributed coverage and exploration in unknown nonconvex environments. In: 10th International symposium on distributed autonomous robotics systems, Lausanne, Switzerland, 1–3 November 2010, pp. 1–14. New York: Springer.
6.
BrownKQ (1979) Voronoi diagrams from convex hulls. Information Processing Letters9: 223–228.
7.
BulloFCortésJMartínezS (2009) Distributed Control of Robotic Networks: A Mathematical Approach to Motion Coordination Algorithms. Princeton: Princeton University Press.
8.
CorcueraJMKendallWS (1998) Riemannian barycentres and geodesic convexity. Mathematical Proceedings of the Cambridge Philosophical Society127: 253–269.
9.
CormenTHSteinCRivestRLLeisersonCE (2001) Introduction to Algorithms. Cambridge, MA: McGraw-Hill.
10.
CortesJMartinezSKaratasTBulloF (2004) Coverage control for mobile sensing networks. IEEE Transactions on Robotics and Automation20: 243–255.
11.
CortésJMartinezSBulloF (2005) Spatially-distributed coverage optimization and control with limited-range interactions. ESIAM: Control, Optimisation and Calculus of Variations11: 691–719.
KlingenbergW (1959) Contributions to Riemannian geometry in the large. Annals of Mathematics69: 654–666.
20.
LaValleSM (2006) Planning Algorithms. Cambridge: Cambridge University Press.
21.
LloydSP (1982) Least squares quantization in PCM. IEEE Transactions of Information Theory28: 129–137.
22.
Lozano-PérezTWesleyMA (1979) An algorithm for planning collision-free paths among polyhedral obstacles. Communications of the ACM22: 560–570.
23.
MilnorJ (1963) Morse Theory. Princeton: Princeton University Press.
24.
MunkresJ (1999) Topology. New York: Prentice Hall.
25.
MurrayRLiZSastrySSastryS (1994) A Mathematical Introduction to Robotic Manipulation. New York: CRC Press.
26.
OhtaS (2007) Convexities of metric spaces. Geometriae Dedicata125: 225–250.
27.
PalfiaM (2011) Means in metric spaces and the center of mass. Journal of Mathematical Analysis and Applications381: 383–391.
28.
PavoneMArsieAFrazzoliEBulloF (2011) Distributed algorithms for environment partitioning in mobile robotic networks. IEEE Transactions on Automatic Control56: 1834–1848.
29.
PetersenP (2006) Riemannian Geometry. New York: Springer.
30.
PimentaLCAKumarVMesquitaRCPereiraGAS (2008) Sensing and coverage for a network of heterogeneous robots. In: IEEE conference on decision and control, Cancun, Mexico, 9–11 December 2008, pp. 3947–3952. Piscataway: IEEE Press.
31.
RimonEKoditschekD (1991) The construction of analytic diffeomorphisms for exact robot navigation on star worlds. Transactions of the American Mathematical Society327: 71–116.
32.
RimonEKoditschekD (1992) Exact robot navigation using artificial potential fields. IEEE Transactions on Robotics and Automation8: 501–518.
33.
SastryS (1999) Nonlinear Systems: Analysis, Stability and Control. New York: Springer.
34.
StachnissC (2006) Exploration and mapping with mobile robots. PhD Thesis, University of Freiburg, Germany.
35.
StachnissCGrisettiGBurgardW (2005) Information gain-based exploration using Rao-Blackwellized particle filters. In: Robotics: science and systems I (ed ThrunSSukhatmeGSSchaalS), Cambridge, USA, 8–11June2005, pp. 65–72. Cambridge: MIT Press.
36.
ThrunSBurgardWFoxD (2005) Probabilistic Robotics. Cambridge: MIT Press.
37.
VelicMMayDMoresiL (2009) A fast robust algorithm for computing discrete Voronoi diagrams. Journal of Mathematical Modelling and Algorithms8: 343–355.
38.
WolterFE (1985) Cut loci in bordered and unbordered Riemannian manfolds. PhD Thesis, Technical University of Berlin, Germany.
