{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T19:28:41Z","timestamp":1791919721708,"version":"4.3.4"},"reference-count":41,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Control Optim."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>Future applications in environmental monitoring, delivery of services, and transportation of goods motivate the study of deployment and partitioning tasks for groups of autonomous mobile agents. These tasks may be achieved by recent coverage algorithms, based upon the classic methods by Lloyd. These algorithms, however, rely upon critical requirements on the communication network: information is exchanged synchronously among all agents and long-range communication is sometimes required. This work proposes novel coverage algorithms that require only gossip communication, i.e., asynchronous, pairwise, and possibly unreliable communication. Which robot pair communicates at any given time may be selected deterministically or randomly. A key innovative idea is describing coverage algorithms for robot deployment and environment partitioning as dynamical systems on a space of partitions. In other words, we study the evolution of the regions assigned to each agent rather than the evolution of the agents' positions. The proposed gossip algorithms are shown to converge to centroidal Voronoi partitions under mild technical conditions. Our treatment features a broad variety of results in topology, analysis, and geometry. First, we establish the compactness of a suitable space of partitions with respect to the symmetric difference metric. Second, with respect to this metric, we establish the continuity of various geometric maps, including the Voronoi diagram as a function of its generators, the location of a centroid as a function of a set, and the widely known multicenter function studied in facility location problems. Third, we prove two convergence theorems for dynamical systems on metric spaces described by deterministic and stochastic switches.<\/jats:p>","DOI":"10.1137\/100806370","type":"journal-article","created":{"date-parts":[[2012,2,9]],"date-time":"2012-02-09T18:40:01Z","timestamp":1328812801000},"page":"419-447","source":"Crossref","is-referenced-by-count":70,"title":["Gossip Coverage Control for Robotic Networks: Dynamical Systems on the Space of Partitions"],"prefix":"10.1137","volume":"50","author":[{"given":"Francesco","family":"Bullo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ruggero","family":"Carli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paolo","family":"Frasca","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,9]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.ecolsys.32.081501.114034"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1086\/378856"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/299917.299918"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2009.2028954"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysconle.2005.04.003"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0003-3472(74)90010-4"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.874516"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0310021"},{"key":"R9","unstructured":"F. Bullo, R. Carli, and P. Frasca,\n                      Gossip Coverage Control for Robotic Networks: Dynamical Systems on the Space of Partitions\n                      , http:\/\/arxiv.org\/abs\/0903.3642 (Dec. 2009)."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"F. Bullo, J. Cort\u00e9s, and S. Mart\u00ednez,\n                      Distributed Control of Robotic Networks\n                      , Appl. Math. Ser., Princeton University Press, 2009; also available online from http:\/\/www.coordinationbook.info.","DOI":"10.1515\/9781400831470"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1109\/TRA.2004.824698"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf,\n                      Computational Geometry: Algorithms and Applications\n                      , 2nd ed., Springer, New York, 2000.","DOI":"10.1007\/978-3-662-04245-8"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Z. Drezner and H. W. Hamacher, eds.\n                      Facility Location: Applications and Theory\n                      , Springer, New York, 2001.","DOI":"10.1007\/978-3-642-56082-8"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/040617364"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144599352836"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827503428527"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"J. W. Durham, R. Carli, P. Frasca, and F. Bullo,\n                      Discrete partitioning and coverage control with gossip communication\n                      , in Proceedings of the ASME Dynamic Systems and Control Conference, Hollywood, CA, 2009, pp. 225\u2013232.","DOI":"10.1115\/DSCC2009-2593"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2008.2007179"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1109\/18.720541"},{"key":"R20","first-page":"107","volume":"41","author":"Gr\u00f6mer H.","year":"2000","journal-title":"Beitr\u00e4ge Algebra Geom.","ISSN":"https:\/\/id.crossref.org\/issn\/0138-4821","issn-type":"print"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/s11370-009-0047-6"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2004.841937"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1109\/34.824819"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"D. Kempe, A. Dobra, and J. Gehrke,\n                      Gossip-based computation of aggregate information\n                      , in Proceedings of the IEEE Symposium on Foundations of Computer Science, Washington, DC, 2003, pp. 482\u2013491.","DOI":"10.1109\/SFCS.2003.1238221"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"S. G. Krantz and H. R. Parks,\n                      Geometric Integration Theory\n                      , Birkh\u00e4user, Boston, MA, 2008.","DOI":"10.1007\/978-0-8176-4679-0"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"R27","unstructured":"D. G. Luenberger,\n                      Linear and Nonlinear Programming\n                      , 2nd ed., Addison-Wesley, Reading, MA, 1984."},{"key":"R28","unstructured":"J. MacQueen,\n                      Some methods for the classification and analysis of multivariate observations\n                      , in Proceedings of the Fifth Berkeley Symposium on Mathematics, Statistics and Probability, University of California Press, 1965-1966, pp. 281\u2013297."},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2007.908304"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/j.anbehav.2009.04.024"},{"key":"R31","unstructured":"S. B. Nadler,\n                      Hyperspaces of Sets\n                      , Monogr. Textbooks Pure Appl. Math. 49, Marcel Dekker, New York, 1978."},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2011.2112410"},{"key":"R33","unstructured":"R. T. Rockafellar,\n                      Convex Analysis\n                      , Princeton University Press, Princeton, NJ, 1970."},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1137\/1021002"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2007.910684"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1137\/060673400"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908100177"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1109\/TCST.2007.903395"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1016\/0022-5193(80)90251-9"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1986.1104412"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1137\/070710123"}],"container-title":["SIAM Journal on Control and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100806370","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:11:02Z","timestamp":1787317862000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100806370"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/100806370"],"URL":"https:\/\/doi.org\/10.1137\/100806370","relation":{},"ISSN":["0363-0129","1095-7138"],"issn-type":[{"value":"0363-0129","type":"print"},{"value":"1095-7138","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}