MicroMouse – urocza myszka, Claude E. Shannon i popularne zawody robotów

MicroMouse to zawody dla robotów uczących się labiryntu po to, aby dotrzeć do celu i uzyskać jak najlepsze rezultaty. Historia zawodów sięga 1950 roku i drewnianej myszki Claude’a E. Shannona, która za pomocą przerobionego telefonu nauczyła się, jak pokonać labirynt i dotarła do sera.

MicroMouse to popularne zawody polegające na osiągnięciu jak najlepszych rezultatów w pokonywaniu labiryntu przez robota. Jedne z nich odbyły się w styczniu br. we Wrocławiu przy okazji XI Robotic Arena. Podczas zawodów roboty najpierw przeszukują labirynt w celu wybrania optymalnej drogi, by dotrzeć od startu do mety w jak najkrótszym czasie. W związku z tym, że maszyny te są w pełni autonomiczne, wykorzystują algorytmy AI najczęściej bazujące na przeszukiwaniu przestrzeni stanów.

Historia zawodów MicroMouse

Opisując historię idei zawodów MicroMouse, najczęściej wskazuje się robota Claude’a E. Shannona, który w 1950 roku zaprezentował uroczą myszkę pokonującą labirynt. Drewniana mysz otrzymała imię Tezeusz i nie przypominała w żaden sposób współczesnych robotów. W ówczesnych czasach niemożliwe było bowiem wykorzystanie tak dużej mocy obliczeniowej w maleńkiej myszce. Z tego powodu była one sterowana za pomocą przekaźników telefonicznych i wózka elektromagnetycznego – umieszczonego pod metalową podłogą labiryntu – który przemieszczał robota. Sama mysz została wyposażona w magnes i wąsy odbierające sygnały dotarcia do metalowej ściany, co powodowało oznaczenie takiej przestrzeni jako zamkniętą przez ścianę. Ruchome ściany powodowały, że myszka za każdym razem musiała nauczyć się nowego układu labiryntu.

W taki sposób telefon stał się podstawą do wprawienia w ruch uroczego robota zdolnego do uczenia się nowych tras w ramach labiryntu. Na mecie po dotknięciu wąsem mosiężnego „sera”, myszka uruchamiała brzęczący sygnał dźwiękowy oznajmiający sukces. Zapoczątkowała także ideę zawodów MicroMouse. Więcej można znaleźć w poniższym filmie.

Ogólne zasady zawodów MicroMouse

Zawodnicy biorący udział w MicroMouse znają wymiary labiryntu oraz ścianek, które wyznaczają trasy dla robotów. Najczęściej jest to 16 x 16 komórek o wymiarach 18 cm x 18 cm. Ścianki labiryntu mają wysokość 5 cm. Sam robot nie może przekroczyć wymiarów 16,8 cm długości oraz 16,8 cm szerokości.

Uczestnik otrzymuje określoną ilość czasu na wykonanie kilku przejazdów. Robot pokonuje labirynt i przy wykorzystaniu algorytmu przeszukującego wybiera trasę, która pozwala na dotarcie od startu do mety w jak najkrótszym czasie. Nie zawsze jest to równoznaczne z najkrótszą drogą. Może bowiem okazać się, że robot jest w stanie szybciej pokonać dłuższą trasę. 

Można to przyrównać do wyboru optymalnej drogi w przypadku przemieszczania się samochodem. Dystans do pokonania od punktu startowego do docelowego w przypadku drogi szybkiego ruchu czy obwodnicy może być dłuższy niż trasa biegnąca przez centrum miasta. W praktyce miasto wymusza ograniczenia prędkości a wąskie uliczki spowalniają ruch samochodów. Tym samym dłuższa trasa, biegnąca przez drogę szybkiego ruchu, może doprowadzić nas do celu w dużo krótszym czasie.

Podobnie sprawa wygląda w przypadku robotów. Muszą one bowiem omijać ścianki, które stanowią pewnego rodzaju przeszkody. Z tego powodu twórcy robotów wybierają często ruch po przekątnej. Robot docierając do ściany, zamiast obracać się o 90 stopni, wykonywać podjazd do przodu i znowu obracać się o 90 stopni, obraca się o 45 stopni i pokonuje tę samą trasę po przekątnej kwadratu. Zamiast ruchu o długości 2xbok kwadratu, przejeżdża trasę stanowiącą √2xbok. Oznacza to istotne skrócenie trasy.

Sztuczna inteligencja przeszukująca przestrzeń stanów podczas zawodów MicroMouse

Algorytmy przeszukujące zaliczane są do sztucznej inteligencji, która tworzy drzewa przeszukiwań. W celu pokonania drogi od startu do mety w najkrótszym czasie wykorzystywane są metody przeszukiwań przestrzeni stanów, które biorą pod uwagę koszt dotarcia do określonego wierzchołka drzewa. Oznacza to, że wykorzystują one funkcję heurystyczną (h) do określenia odległości robota w danym położeniu (wierzchołku) od mety (stanu końcowego). Każdy ruch może bowiem oddalać mysz od celu lub ją do niego przybliżać. 

Informacje na ten temat można znaleźć w poniższym filmie. Zawiera on dokładne opisy strategii i problemów, które muszą rozwiązać twórcy robotów.

Zawody MicroMouse – podsumowanie

MicroMouse to zawody, które polegają na utworzeniu robota i odpowiednim zaprogramowaniu algorytmów sztucznej inteligencji, które umożliwią mu pokonanie w najkrótszym czasie drogi od startu do mety. W dzisiejszych czasach maszyny te najczęściej nie przypominają już uroczej myszki C. E. Shannona. Jednakże to właśnie jego robot stał się pierwowzorem dla zawodów MicroMouse, które cieszą się dużą popularnością na całym świecie.