Kybernetika 50 no. 1, 19-31, 2014

Sweep coverage of discrete time multi-robot networks with general topologies

Chao ZhaiDOI: 10.14736/kyb-2014-1-0019


This paper addresses a sweep coverage problem of multi-robot networks with general topologies. To deal with environmental uncertainties, we present discrete time sweep coverage algorithms to guarantee the complete coverage of the given region by sweeping in parallel with workload partition. Moreover, the error between actual coverage time and the optimal time is estimated with the aid of continuous time results. Finally, numerical simulation is conducted to verify the theoretical results.


sweep coverage, multi-robot networks, discrete time, general topologies


93E12, 62A10


  1. J. Cortés, S. Martínez, T. Karatas and F. Bullo: Coverage control for mobile sensing network. IEEE Trans. Robotics Automat. 20 (2004), 243-255.   CrossRef
  2. T. M. Cheng and A. V. Savkin: Decentralized coordinated control of a vehicle network for deployment in sweep coverage. In: Proc. IEEE Internat. Conference on Control and Automation, Christchurch 2009.   CrossRef
  3. Q. Du, V. Faber and M. Gunzburger: Centroidal Voronoi tesseuations: applications and algorithms. SIAM Rev. 41 (1999), 637-676.   CrossRef
  4. D. W. Gage: Command control for many-robot systems. In: Proc. 19th Annual AUVS Teachnical Symposium, Huntsville 1992.   CrossRef
  5. C. W. Gear: Numerical Initial Value Problems for Ordinary Differential Equations. Prentice-Hall, Englewood Cliffs, New Jersey 1971.   CrossRef
  6. Y. Hong, J. Hu and L. Gao: Tracking control for multi-agent consensus with an active leader and variable topology. Automatica 42 (2006), 1177-1182.   CrossRef
  7. R. A. Horn and C. R. Johnson: Matrix Analysis. Cambridge University Press, Cambridge 1987.   CrossRef
  8. A. Howard, L. E. Parker and G. Sukhatme: Experiments with a large heterogeneous mobile robot team: Exploration, mapping, deployment and detection. Internat. J. Robotics Research 25 (2006), 431-447.   CrossRef
  9. J. Hu and G. Feng: Distributed tracking control of leader-follower multi-agent systems under noisy measurement. Automatica 46 (2010), 1382-1387.   CrossRef
  10. W. Ren and R. Beard: Distributed Consensus in Multi-vehicle Cooperative Control. Springer-Verlag, London 2008.   CrossRef
  11. A. Renzaglia, L. Doitsidis, A. Martinelli and E. Kosmatopoulos: Adaptive-based distributed cooperative multi-robot coverage. In: Proc. American Control Conference, San Francisco 2011.   CrossRef
  12. M. Schwager, D. Rus and J. J. E. Slotine: Decentralized, adaptive control for coverage with networked robots. Internat. J. Robotics Research 28 (2009), 357-375.   CrossRef
  13. G. Shi and Y. Hong: Global target aggregation and state agreement of nonlinear multi-agent systems with switching topologies. Automatica 45 (2009), 1165-1175.   CrossRef
  14. G. Shi, Y. Hong and K. Johansson: Connectivity and set tracking of multi-agent systems guided by multiple moving leaders. IEEE Trans. Automat. Control 57 (2012), 663-676.   CrossRef
  15. X. Wang and F. Han: Robust coordination control of switching multi-agent systems via output regulation approach. Kybernetika 47 (2012), 755-772.   CrossRef
  16. C. Zhai and Y. Hong: Decentralized sweep coverage algorithm for multi-agent systems with workload uncertainties. Automatica 49 (2013), 2154-2159.   CrossRef
  17. H. Zhang, C. Zhai and Z. Chen: A general alignment repulsion algorithm for flocking of multi-agent systems. IEEE Trans. Autom. Control 56 (2011), 430-435.   CrossRef