Projekty

SwarmIntelligence

SwarmIntelligence to algorytm do przechodzenia labiryntu inspirowany zjawiskiem inteligencji rozproszonej występującej w przyrodzie. Pozornie niezorganizowane grupy, bądź stada zwierząt, są w stanie współdziałać, tworząc skomplikowane systemy obronne lub budowle. Jednostki nie komunikują się ze sobą w sposób ciągły, nie mają wyznaczonej jednostki dowodzącej, czy wcześniej określonego planu, a jedynie poprzez obserwację siebie oraz środowiska zachowują synchronizację między swoimi działaniami. Tak rozumianą współpracę można zaobserwować w przypadku ławic ryb, stad ptaków czy właśnie mrówek.

Symulowane jednostki w naszym algorytmie nazwane zostały “mrówkami”. Każda mrówka ma zestaw operacji, które może wykonać w zależności od swojego otoczenia. Każda “widzi” jedynie pole, na którym stoi, jak również cztery sąsiadujące z nim pola, jeśli pozwala na to konstrukcja labiryntu. Główną cechą mrówek jest to, że stawiają “markery”, a następnie odpowiednio na nie reagują.

Wyróżniamy trzy rodzaje markerów:

	znacznik rozgałęzienia	Kiedy mrówka dojdzie do rozgałęzienia ścieżki i wybierze następne rozgałęzienie, na jego wejściu stawia żółty marker
	znacznik stopu	Mrówka stawia go na wyjściu ze ścieżki, którą sklasyfikowała jako ślepy zaułek.
	drogowskaz, znacznik wyjścia	Mrówka stawia go na wyjściu ze ścieżki, na której znalazła koniec labiryntu.

Następnie występują zasady poruszania związane z markerami:

Jeśli żadna ścieżka nie jest oznaczona markerem, kolejna ścieżka wybierana jest losowo.
Jeśli do wyboru jest ścieżka żółta i nieoznaczona, mrówka zawsze wybiera nieoznaczoną.
Mrówka nie może wejść na ścieżkę oznaczoną znacznikiem stopu.
Mrówka może wyjść ze ścieżki oznaczonej znacznikiem stopu.
Mrówka musi wejść na ścieżkę oznaczoną znacznikiem wyjścia.

Celem algorytmu jest sprawienie, że wszystkie mrówki opuszczą labirynt.

W ramach projektu, prócz wyżej omawianego algorytmu, zostały przygotowane również:

okno aplikacji z możliwością wyświetlenia wygenerowanego labiryntu, wraz z zaznaczonym na nim najkrótszą ścieżką oraz pozycjami poszczególnych „mrówek” i związanych z nimi znacznikami,

podłączona baza danych, przechowująca wygenerowane labirynty,
rozbudowany panel ustawień, wykorzystywany do generowania labiryntu czy ustawiania parametrów algorytmu inteligencji rozproszonej,
algorytm do generowania labiryntu – generowanie labiryntu oparte jest na stosie,

algorytm służącym do znajdowania najkrótszej ścieżki w labiryncie (algorytm Lee/propagacji fal),

Jako język programowania został użyty C++17, z kompilatorem MSVC. Do utworzenia aplikacji okienkowej wykorzystano bibliotekę Qt. Do serializacji labiryntu do bazy danych posłużono się SQLite. Przy testowaniu silników liczb pseudolosowych użyto biblioteki NIST.

Kod programu można podejrzeć na naszym githubie.

Data zakończenia: 31.1.2020

Projekty

SwarmIntelligence

Autorzy