Gathering small number of mobile asynchronous robots on ring

• Autorzy: Koreń M.

Warianty tytułu

PL

Problem zebrania małej ilości asynchronicznych mobilnych robotów na cyklu

• Języki publikacji: EN

Abstrakty

EN

We study a fundamental problem related to the coordination of distributed mobile entities (referred to simply as robots), namely, that of meeting at the same location in a network. In the considered scenario, a set of identical, oblivious robots, without the ability to communicate with each other, is required to gather in one node of an unlabeled, undirected ring and remain in it. The gathering point is not given in advance, and the robots have to decide where to meet only by observing their environment and performing some computations based on those observations. The studied problem has been completely solved for configurations with k > 18 robots on the ring, and surprisingly, the difficulty of the analysis is aggravated when the number of robots is small. This paper contains a complete characterization of gatherable configurations with k = 4 robots, closing an open problem posed in the literature.

PL

Problem rozważany w niniejszej pracy jest jednym z podstawowych problemów powiązanych z koordynacją rozproszonych mobilnych jednostek (nazywanych dla uproszczenia robotami). Projektant ma do dyspozycji zbiór identycznych, bezpamięciowych robotów, które nie mogą komunikować się ze sobą bezpośrednio. Muszą one zebrać się w jednym wierzchołku nieskierowanego cyklu, bez etykiet na wierzchołkach i krawędziach. Gdy roboty zbiorą się w jednym wierzchołku grafu, muszą w nim pozostać. Miejsce spotkania nie jest z góry ustalone, roboty muszą je wybrać na podstawie poczynionych obserwacji otoczenia i pewnych obliczeń bazujących na tych obserwacjach. Zadaniem projektanta jest stworzenie algorytmu dla pojedynczej jednostki, którego wykonanie na wszystkich dostępnych jednostkach doprowadzi do zebrania ich w jednym miejscu w sieci. Problem ten został całkowicie rozwiązany dla konfiguracji zawierających k > 18 robotów na cyklu, jednakże trudność analizy wzrasta dla małych ilości robotów. Niniejsza praca zawiera pełną charakteryzację zbieralnych konfiguracji zawierających k = 4 roboty, co zamyka przedstawiony w literaturze problem otwarty.

Słowa kluczowe

EN

mobile asynchronous robots

PL

mobilne roboty

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2010
• Tom: T. 18
• Strony: 325--331
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Koreń M.

• Gdansk University of Technology, Department of Algorithms and System Modeling

Bibliografia

• [1] M. Cieliebak. Gathering non-oblivious mobile robots. LATIN’04, pp. 577–588, 2004.
• [2] M. Cieliebak, P. Flocchini, G. Prencipe, N. Santoro. Solving the gathering problem. ICALP’03, pp. 1181–1196, 2003.
• [3] M. Cieliebak, G. Prencipe. Gathering autonomous mobile robots. SIROCCO’02, pp. 57–72, 2002.
• [4] P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer. Hard tasks for weak robots: The role of common knowledge in pattern formation by autonomous mobile robots. ISAAC’99, pp. 93–102, 1999.
• [5] G. Prencipe. On the feasibility of gathering by autonomous mobile robots. SIROCCO’05, pp. 246–261, 2005.
• [6] P. Flocchini, D. Ilcinkas, A. Pelc, N. Santoro. Computing without communicating: Ring exploration by asynchronous oblivious robots. OPODIS’07, pp. 105–118, 2007.
• [7] P. Flocchini, E. Kranakis, D. Krizanc, F. Luccio, N. Santoro, C. Sawchuk. Multiple mobile agent rendezvous in a ring. LATIN’04, pp. 599–608, 2004.
• [8] R. Klasing, E. Markou, A. Pelc. Gathering asynchronous oblivious mobile robots in a ring. Theoretical Computer Science, (390):27–39, 2008. Elsevier.
• [9] R. Klasing, A. Kosowski, A. Navarra. Taking advantage of symmetries: Gathering of asynchronous oblivious robots on a ring. OPODIS’08, pp. 446–462, 2008.
• [10] K. Haba, T. Izumi, Y. Katayama, N. Inuzuka, K. Wada. On Gathering Problem in a Ring for 2n Autonomous Mobile Robots. COMP’08, pp.47-54, 2008.