WRÓĆ DO STRONY
GŁÓWNEJ
Nauka

Błądzące mrówki inspirują informatyków z MIT

Jak się okazuje, od mrówek możemy się wiele nauczyć – i to nie tylko w kwestii etyki pracy. Naukowcy z Computer Science and Artificial Intelligence Laboratory MIT badają mrówki, by stworzyć modele analizy sieci społecznościowych, kolektywnego wykonywania decyzji w „rojach” robotów i komunikacji w zdecentralizowanych sieciach bezprzewodowych ad hoc.

Badanie MIT potwierdziło, że mrówki szacują swoją populację w oparciu o to, jak często spotykają inne mrówki podczas losowej eksploracji swojego otoczenia. Zdolność ta zdaje się być kluczowa w wypadku szeregu czynności – w tym decydowaniu, gdzie znaleźć się ma kolejne mrowisko.

Badacze porównali środowisko mrówek do sieci. Mrówka-odkrywca zaczyna w jednym z jej węzłów (opisującym pewien wydzielony obszar), a następnie najczęściej przemieszcza się do jednego z sąsiednich. Następnie przemieszcza się do kolejnego (lub wraca – i to jest prawdopodobne) i tak dalej. Taki proces nazywany jest w technice „błądzeniem losowym”. Podczas swojej podróży, mrówka odkrywca zlicza napotkane mrówki.

Badanie porównuje błądzenie losowe do metody losowego wyboru (random sampling) – w której losowo wybiera się poszczególne węzły sieci i zlicza w nich mrówki. W obu wypadkach dokładność rośnie wraz z każdą dodatkową „próbką”. Co ciekawe, błądzenie losowe odkrywa prawdziwą gęstość populacji nemal tak szybko, jak sprawdzona metoda losowego wyboru. Jest to istotne choćby w sieciach ad hoc, gdy trzeba szybko zliczyć wszystkie pobliskie urządzenia.

By zamodelować środowisko mrówek, badacze wykorzystali strukturę grafową zbudowaną z węzłów i krawędzi – czyli liniowych segmentów łączących poszczególne węzły.

W przypadku, gdy graf nie ma zbyt wielu połączeń – gdy występuje tylko łańcuch węzłów, gdzie każdy z nich jest podłączony tylko do dwóch sąsiednich, prawdopodobna jest sytuacja, w której zbyt częste uwzględnianie danego węzła mogłoby stanowić problem („odkrywca” pozostaje zbyt długo pomiędzy dwoma węzłami). Niemniej, w przypadku sieci komunikacyjnych stosuje się jednocześnie dwóch „wędrowców” zaczynających z tego samego węzła i wyruszających w różnych kierunkach. W efekcie, błądzenie losowe, daje podobny poziom dokładności co random sampling.

Im większa liczba wędrowców, tym szybciej da się osiągnąć wynik zbliżony do prawdy. Gdyby zamiast mrówek zastosować roboty, mogłyby się wzajemnie wymieniać uzyskanymi szacunkami.

Praca zostanie zaprezentowana na Sympozjum dotyczącym obliczeń rozproszonych organizowanym przez Association for Computing Machinery. Będzie ono miało miejsce w Chicago w dniach 25-29 lipca.

[źródło i grafika: gizmag.com]