| Publikationstyp: | Beitrag in wissenschaftlicher Zeitschrift |
| Art der Begutachtung: | Peer review (Publikation) |
| Titel: | Distributed computing by mobile robots : gathering |
| Autor/-in: | Cieliebak, Mark Flocchini, Paola Prencipe, Giuseppe Santoro, Nicola |
| DOI: | 10.1137/100796534 |
| Erschienen in: | SIAM Journal on Computing |
| Band(Heft): | 41 |
| Heft: | 4 |
| Seite(n): | 829 |
| Seiten bis: | 879 |
| Erscheinungsdatum: | 2012 |
| Verlag / Hrsg. Institution: | Society for Industrial and Applied Mathematics |
| ISSN: | 1095-7111 0097-5397 |
| Sprache: | Deutsch |
| Schlagwörter: | Distributed system; Gathering; Robot |
| Fachgebiet (DDC): | 004: Informatik 621.3: Elektro-, Kommunikations-, Steuerungs- und Regelungstechnik |
| Zusammenfassung: | Consider a set of n > 2 identical mobile computational entities in the plane, called robots, operating in Look-Compute-Move cycles, without any means of direct communication. The Gathering Problem is the primitive task of all entities gathering in finite time at a point not fixed in advance, without any external control. The problem has been extensively studied in the literature under a variety of strong assumptions (e.g., synchronicity of the cycles, instantaneous movements, complete memory of the past, common coordinate system, etc.). In this paper we consider the setting without those assumptions, that is, when the entities are oblivious (i.e., they do not remember results and observations from previous cycles), disoriented (i.e., have no common coordinate system), and fully asynchronous (i.e., no assumptions exist on timing of cycles and activities within a cycle). The existing algorithmic contributions for such robots are limited to solutions for n ≤ 4 or for restricted sets of initial configurations of the robots; the question of whether such weak robots could deterministically gather has remained open. In this paper, we prove that indeed the Gathering Problem is solvable, for any n > 2 and any initial configuration, even under such restrictive conditions. |
| URI: | https://digitalcollection.zhaw.ch/handle/11475/7122 |
| Volltext Version: | Publizierte Version |
| Lizenz (gemäss Verlagsvertrag): | Lizenz gemäss Verlagsvertrag |
| Departement: | School of Engineering |
| Organisationseinheit: | Institut für Informatik (InIT) |
| Enthalten in den Sammlungen: | Publikationen School of Engineering |
Dateien zu dieser Ressource:
Es gibt keine Dateien zu dieser Ressource.
Zur Langanzeige
Cieliebak, M., Flocchini, P., Prencipe, G., & Santoro, N. (2012). Distributed computing by mobile robots : gathering. SIAM Journal on Computing, 41(4), 829–879. https://doi.org/10.1137/100796534
Cieliebak, M. et al. (2012) ‘Distributed computing by mobile robots : gathering’, SIAM Journal on Computing, 41(4), pp. 829–879. Available at: https://doi.org/10.1137/100796534.
M. Cieliebak, P. Flocchini, G. Prencipe, and N. Santoro, “Distributed computing by mobile robots : gathering,” SIAM Journal on Computing, vol. 41, no. 4, pp. 829–879, 2012, doi: 10.1137/100796534.
CIELIEBAK, Mark, Paola FLOCCHINI, Giuseppe PRENCIPE und Nicola SANTORO, 2012. Distributed computing by mobile robots : gathering. SIAM Journal on Computing. 2012. Bd. 41, Nr. 4, S. 829–879. DOI 10.1137/100796534
Cieliebak, Mark, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. 2012. “Distributed computing by mobile robots : gathering.” SIAM Journal on Computing 41 (4): 829–79. https://doi.org/10.1137/100796534.
Cieliebak, Mark, et al. “Distributed computing by mobile robots : gathering.” SIAM Journal on Computing, vol. 41, no. 4, 2012, pp. 829–79, https://doi.org/10.1137/100796534.
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt, soweit nicht anderweitig angezeigt.