Abstract
We consider the problem of multi-robot exploration and coverage in unknown non-convex environments. The contributions of the work include (1) the presentation of a distributed algorithm that computes the generalized Voronoi tessellation of non-convex environments (using a discrete representation) in real-time for use in feedback control laws; and (2) the extension of this method to entropy based metrics that allow for cooperative coverage control in unknown non-convex environments. Simulation results demonstrate the application of the control methodology for cooperative exploration and coverage in an office environment.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aronov, B.: On the geodesic voronoi diagram of point sites in a simple polygon. In: Proc. of the Sym. on Computational Geometry, pp. 39–49. ACM, New York (1987), doi: http://doi.acm.org/10.1145/41958.41963
Burgard, W., Moors, M., Stachniss, C., Schneider, F.: Coordinated multi-robot exploration. IEEE Trans. Robot. 21(3), 376–378 (2005)
Cormen, T.H., Stein, C., Rivest, R.L., Leiserson, C.E.: Introduction to Algorithms. McGraw-Hill Higher Education (2001)
Cortes, J., Martinez, S., Karatas, T., Bullo, F.: Coverage control for mobile sensing networks. IEEE Trans. Robot. Autom. 20(2), 243–255 (2004)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271 (1959)
Fox, D., Ko, J., Konolige, K., Limketkai, B., Schultz, D., Stewart, B.: Distributed multirobot exploration and mapping. Proc. of the IEEE 94(7), 1325–1339 (2006)
Howard, A., Parker, L.E., Sukhatme, G.S.: Experiments with a large heterogeneous mobile robot team: Exploration, mapping, deployment and detection. Intl. J. Robot. Research 25(5-6), 431–447 (2006)
Lloyd, S.P.: Least squares quantization in PCM. IEEE Trans. Inf. Theory 28, 129–137 (1982)
Michael, N., Fink, J., Kumar, V.: Experimental testbed for large multi-robot teams: Verification and validation. IEEE Robot. Autom. Mag. 15(1), 53–61 (2008)
Pimenta, L.C.A., Kumar, V., Mesquita, R.C., Pereira, G.A.S.: Sensing and coverage for a network of heterogeneous robots. In: Proc. of the IEEE Conf. on Decision and Control, Cancun, Mexico, pp. 3947–3952 (2008)
Preparata, F.P., Shamos, M.I.: Computational geometry: an introduction. Springer-Verlag New York, Inc., New York (1985)
Schwager, M., McLurkin, J., Rus, D.: Distributed coverage control with sensory feedback for networked robots. In: Proc. of Robot.: Sci. and Syst., Philadelphia, PA (2006)
Schwager, M., Slotine, J.E., Rus, D.: Decentralized, adaptive control for coverage with networked robots. In: Proc. of the IEEE Intl. Conf. on Robot. and Autom., Rome, Italy, pp. 3289–3294 (2007)
Stachniss, C.: Exploration and mapping with mobile robots. Ph.D. thesis, University of Freiburg, Freiburg, Germany (2006)
Stachniss, C., Grisetti, G., Burgard, W.: Information gain-based exploration using rao-blackwellized particle filters. In: Proc. of Robot.: Sci. and Syst., Cambridge, MA, pp. 65–72 (2005)
Thrun, S., Burgard, W., Fox, D.: Probabilistic Robotics (Intelligent Robotics and Autonomous Agents). The MIT Press (2005)
Wu, L., Garcia, M.A., Puig, D., Sole, A.: Voronoi-based space partitioning for coordinated multi-robot exploration. J. Physical Agents 1(1), 37–44 (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Bhattacharya, S., Michael, N., Kumar, V. (2013). Distributed Coverage and Exploration in Unknown Non-convex Environments. In: Martinoli, A., et al. Distributed Autonomous Robotic Systems. Springer Tracts in Advanced Robotics, vol 83. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32723-0_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-32723-0_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32722-3
Online ISBN: 978-3-642-32723-0
eBook Packages: EngineeringEngineering (R0)