Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!
Sesja wygasła!

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: mobile asynchronous robots

Sortuj według:

Ogranicz wyniki do:

Gathering small number of mobile asynchronous robots on ring

Koreń M.

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

2010

T. 18

325-331

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.

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.