Jak nietrudno się domyślić wygrywa ta mysz, która zrealizuje zadanie w najkrótszym czasie. W niektórych zawodach w ostatecznej klasyfikacji brany jest pod uwagę tylko najlepszy uzyskany czas przejazdu ze startu do celu, w innych zaś doliczany jest też czas przeszukiwania labiryntu (z odpowiednią wagą, np.1/60) oraz karne sek. za dotykanie robota (ręczne poprawki).

Przykładowe rozwiązanie labiryntu (na podstawie wcześniej zbudowanej mapy):

Jeśli chodzi o konstrukcję robotycznej myszy, to jest to temat na oddzielny artykuł, gdyż pomysłów na rozwiązania mechaniczne jak i elektroniczne jest naprawdę dużo. Ograniczeniami są jedynie długość i szerokość robota (do 25 cm). Robot nie może też przeskakiwać ścian.

Wybór algorytmów dla myszy

Problem szukania wyjścia z labiryntu jest problemem dosyć starym (już w mitologii greckiej mamy wzmianki o labiryncie Minotaura), więc sposobów przeszukiwania labiryntu jest sporo.

Labirynt można potraktować jako graf. Wtedy każde pole labiryntu będzie wierzchołkiem, a otwarte przejście między polami będzie równoznaczne z krawędzią. Przypisując wszystkim krawędziom wagę równą 1 do rozwiązania problemu będziemy mogli posłużyć się dowolnym algorytmem znajdowania najkrótszej drogi pomiędzy dwoma wierzchołkami grafu.

Możemy wykorzystać m.in. algorytm:

• Minty’ego,
• Dijkstry,
• Bellmana-Forda,
• Dantzig’a,
• Bellmana-Kalaby,
• Floyda-Warshalla,
• Demoucrona.

Dokładnie wszystkich opisywać nie będę, bo nikt w swojej myszy w postaci ogólnej ich nie użyje. Jeśli ktoś jest zainteresowany szczegółami, to odsyłam do literatury związanej z teorią grafów.

---

Algorytm, na który się zdecydujemy, w dużej mierze zależy od możliwości obliczeniowych jakimi dysponuje nasz robot. Można zbudować robota, który będzie zbierał dane z labiryntu, a następnie prześle je do komputera nadzorującego, który wykona obliczenia i prześle robotowi rozwiązanie.

W tym przypadku moc obliczeniowa nie stanowi większego problemu (każdy komputer szybko poradzi sobie z labiryntem 16x16 niezależnie od tego, z którego z wymienionych wyżej algorytmów skorzystamy) jednak jeśli chcemy, aby nasz robot wziął udział w zawodach to niestety regulamin wyklucza tę opcję.

Najczęściej więc nie mamy do dyspozycji mocy obliczeniowa rzędu GHz, musimy zadowolić się kilkunastoma MHz. Pamięć operacyjna również nie jest wyrażona w GB, a w co najwyżej KB.

Pod uwagę trzeba wziąć również fakt, że oprócz obliczania optymalnej drogi procesor przez cały czas musi zbierać informacje z czujników, przetwarzać je i sterować napędem robota. Ciekawym rozwiązaniem może okazać się konstrukcja kilku procesorowa (powiedzmy dwa komunikujące się układy - jeden odpowiedzialny za sterowanie, drugi zaś stanowiący jednostkę obliczeniową).

Skoro wiemy już na co możemy sobie pozwolić pora odpowiedzieć na pytanie jak zmusić mysz do odnalezienia drogi do celu?

Metoda 1: Wall Follower

Śledzenie ściany jest najprostszą i zarazem najmniej wymagającą metodą. Każdy na pewno słyszał o regule prawej bądź lewej ręki. Jeśli nasz robot będzie się trzymał cały czas prawej (bądź lewej) ściany, to na pewno przejedzie cały labirynt (skoro przejedzie cały to na pewno osiągnie cel).

Należy jednak zdawać sobie sprawę, że reguła ta sprawdza się tylko dla prostych labiryntów. Nie należy liczyć, że metoda pozwoli wygrać zawody, gdy labirynt będzie celowo skonstruowany tak, aby uniemożliwić znalezienie rozwiązania robotom korzystającym z tej metody (środkowy kwadrat będący celem myszy nie będzie połączony z brzegiem labiryntu) .

Rys. 1. Przykłady labiryntów, których wall-follower nie rozwiąże

Przykładowy prosty kod dla wall-followera śledzącego prawą ścianę może wyglądać następująco:

Metoda 2: Brute Force

Kolejny prosty i niezbyt wymagający algorytm wygląda następująco:

• robot jedzie przed siebie,
• gdy dojedzie do rozdroża, to losowo wybiera jedną z możliwości i jedzie dalej,
• gdy trafi na ślepą uliczkę, to wraca do ostatniego rozdroża i wybiera inną drogę,
• kroki powtarzane są do chwili osiągnięcia celu.

Stosując ten prosty algorytm robot na pewno znajdzie rozwiązanie problemu (o ile nie będzie miał narzuconego limitu czasowego). Trudno jednak oczekiwać, że znaleziona droga będzie drogą optymalną (najkrótszą).

Warto też zauważyć, że wykorzystując tę metodę należałoby zapamiętywać pewne informacje o labiryncie, np. w które części labiryntu robot już odwiedził by nie dopuścić do zapętlenia się robota i błądzenia w nieskończoność.

Mapa labiryntu w pamięci robota (ważne zagadnienie)

Zaczynając pracę nad moim robotem wpadłem na pomysł jak w pamięci mikrokontrolera zapisać mapę labiryntu. Bardzo byłem z siebie zadowolony jednak pisząc ten artykuł okazało się, że nie jestem pierwszą osobą, która wpadła na ten pomysł (co biorąc pod uwagę kilkudziesięcioletnią historię zawodów nie jest specjalnym zaskoczeniem).

Otóż mając 256-cio segmentowy labirynt potrzebujemy 256 bajtów pamięci. Cały labirynt można zapamiętać w jednowymiarowej tablicy o długości 256. Każdej z 256 komórek labiryntu odpowiada jeden bajt (aż 8 bitów!). Do zapamiętania ułożenia ścian dla danego segmentu wystarczą nam 4 bity (młodsze lub starsze – to naprawdę nie ma większego znaczenia i zależy tylko od piszącego program), zostają nam 4 wolne bity.

Jeden z nich możemy użyć jako flagę informującą, czy dany segment był już odwiedzony, czy nie. Kolejny może informować, że jest to ślepa uliczka oraz, że dany segment nie powinien być brany pod uwagę w trakcie wykonywania algorytmu obliczającego optymalne rozwiązanie.

---

Przyjmujemy np. następujący wzór określający usytuowanie ścian NESW (North-East-South-West) oraz zakładamy, że 1 – oznacza ścianę, zaś 0 – jej brak. Ponadto załóżmy, że do kodowania ułożenia ścian w danym segmencie używamy młodszych bitów danego słowa ( - - - - N E S W ).

Przykłady:

• segment |__| zostanie zakodowany : - - - - 0111
• segment |    | zostanie zakodowany : - - - - 0101
• segment |‾‾‾  zostanie zakodowany : - - - - 1001
• i tak dalej, myślę, że każdy załapał ideę.

Taki sposób kodowania ma jeszcze jedną przyjemną właściwość. Mając na początku pustą mapę, w miarę poznawania labiryntu w czasie jego przeszukiwania zachodzi konieczność ciągłego uaktualniania mapy o odkryte ściany.

Czyli kodujemy kierunki w następujący sposób:

Lub bezpieczniej (zwłaszcza, gdy mamy zamiar usuwać ściany z mapy) definiujemy sobie stałe:

Gdy dotrzemy np. do segmentu o numerze indeks, a czujniki dostarczą nam informację, że przed nami znajduje się ściana (zakładam ponadto, że znamy ułożenie robota względem labiryntu oraz, że jest on zwrócony w kierunku N – o kierunku robota względem labiryntu za chwilę) należy tę informację dodać do naszej mapy.

Umożliwi to kod:

Ogólna zasada: segment = segment OR kierunek. W ten oto prosty sposób mamy aktualną mapę labiryntu. Równie proste jest usuwanie ścian z mapy (choć na chwilę obecną wydaje mi się, że nie ma potrzeby korzystania z tej możliwości – regulamin konkursowy nie dopuszcza usuwania ścian bądź jakiejkolwiek rekonfiguracji labiryntu w czasie, gdy robot przebywa w labiryncie). Wystarczy użyć tym razem koniunkcji logicznej (AND/i ). Zatem aby usunąć dodaną wcześniej ścianę:

Ogólna zasada: segment = segment AND (NOT kierunek) i robot zapomina o ścianie.

Należy pamiętać, że każda ściana w labiryncie (oprócz ścian, o których robot wie na starcie – brzeg labiryntu) jest widoczna z dwóch segmentów (tych które ściana ta rozdziela).

Zatem pełna funkcja dodająca ścianę do mapy labiryntu (na podstawie informacji uzyskanej przez mysz znajdującą się w segmencie o numerze indeks) napisana w C może wyglądać następująco:

Funkcja usuwająca ścianę wyglądałaby analogicznie (różnica byłaby tylko w operatorach bitowych no i oczywiście w nazwie funkcji).

Aby nasza mysz nie zgubiła się na mapie, którą tworzy musi jeszcze pamiętać swoją aktualną pozycję (z tym nie ma problemu – wystarczy pamiętać numer segmentu, w którym się aktualnie znajduje, czyli liczbę z zakresu 0..255 → Rys. 2.) oraz kierunek względem labiryntu, który musi aktualizować za każdym razem, gdy wykonuje obrót o 90 lub 180 stopni.

Tę ważną informację możemy również pamiętać w jednym bajcie:

Przykładowy wzór: 0W0N0E0S (***)

Przykłady:

• mysz skierowaną w danej chwili na północ możemy zakodować: 00010000,
• mysz skierowana na południe: 00000001,
• mysz skierowana na wschód: 00000100,
• mysz skierowana na zachód: 01000000.

Jeżeli budujemy robota bardziej zaawansowanego, będącego w stanie jeździć po przekątnych (niektóre labirynty mogą dawać znaczną przewagę robotom zdolnym do takich manewrów – rys. 3.) to zera we wzorze (***) można wykorzystać do zakodowania kierunków pośrednich. Jednak jeśli ktoś zaczyna dopiero zabawę z myszami, to nie powinien sobie zawracać tym głowy.

Ale wróćmy do tego co jest tematem artykułu, czyli do przeszukiwania labiryntu.

Metoda 3: metoda propagacji fali

Sposób ten, to uproszczony algorytm BELLMANA-FORDA. Jest to najczęściej używana przez zawodników metoda przeszukiwania labiryntu w poszukiwaniu najkrótszej drogi do celu. Idea jest trywialna: wlejmy do labiryntu wodę (nie dosłownie), a ona sama znajdzie drogę.

Po prostu – woda zawsze płynie po linii najmniejszego oporu – więc droga, którą woda dotrze do celu najwcześniej, jest zarazem drogą, której szukamy (najkrótszą). Wystarczy przełożyć to na język zrozumiały dla mikrokontrolera.

Metoda propagacji fali - wersja pierwsza

Załóżmy, że robot zwiedził już cały labirynt i ma utworzoną w pamięci kompletną mapkę oraz, że wrócił na start (do segmentu o indeksie 0). Jest teraz gotowy do przejazdu pomiarowego. Zależy nam by przejazd ten odbył się jak najkrótszą drogą. Przystępujemy więc do jej wyznaczenia.

Będzie do tego potrzebna pamięć – dodatkowe 256 bajtów – do utworzenia tablicy, którą możemy nazwać na przykład odległosc[256], odpowiadającej naszemu labiryntowi (jeden bajt odpowiada jednemu segmentowi – podobnie jak miało to miejsce z mapką).

Drogę wyznaczamy w dwóch etapach. Etap pierwszy („wlanie wody do labiryntu” – Rys. 4.):

• oznaczamy segment startowy wartością 0,
• kolejne segmenty (sąsiadujące, a zarazem osiągalne z segmentu oznaczonego wcześniej) oznaczamy wartością 1,

• ponownie wszystkie nieoznaczone segmenty osiągalne z segmentów oznaczonych w kroku poprzednim oznaczamy wartością o jeden większą,

• ostatni krok powtarzamy dopóki nie zostanie oznaczony jeden z czterech segmentów docelowych (119, 120, 135 lub 136).

Etap drugi (wyznaczanie optymalnej drogi – Rys. 5.). Optymalna droga powstaje od końca (patrz rysunek poniżej). Zaczynając od oznaczonego segmentu docelowego przechodzimy według malejących wartości zapisanych w tablicy odległości (wartość zapisana w tej tablicy powiedzmy pod indeksem n jest odległością n-tego segmentu labiryntu od segmentu startowego) do chwili osiągnięcia segmentu o indeksie 0.

Otrzymana droga jest na pewno drogą najkrótszą (co nie oznacza najszybszą) zatem robot znając ją może wykonać swój przejazd pomiarowy.

Metoda propagacji fali - wersja druga

Postępujemy analogicznie jak w wersji pierwszej, z tą różnią, że wodę zaczynamy wlewać do labiryntu nie w segmencie startowym, a w środku labiryntu. Czyli jako pierwsze zerami oznaczamy segmenty o numerach 119, 120, 135 i 136. Następnie oznaczamy kolejne (jak w wersji pierwszej) do chwili oznaczenia segmentu o numerze 0 (startowego) – Rys. 6.

Rys. 6. Druga wersja „zalewania labiryntu wodą” – otrzymujemy rozwiązanie to samo co poprzednio (co nie jest szczególnym zaskoczeniem).

Tym razem wartości wpisane do tablicy odleglosc[] stanowić więc będą odległość jaka dzieli robota znajdującego się w danym segmencie od celu (środka labiryntu) i zauważmy, że na tym koniec.

Nie potrzebujemy drugiego etapu, robot może od razu przystąpić do przejazdu pomiarowego – numer wpisany w tablicy odleglosc[] pod indeksem 0 oznacza długość minimalnej drogi dzielącej segmentu startowego od środka labiryntu.

Druga wersja metody jest więc niczym innym tylko odwróceniem pierwszej (odwróceniem kierunku przepływu wody). Jednak daje to wielką zaletę, że nie ma wyodrębnionego drugiego etapu, czyli odczytywania optymalnej drogi. Sam przejazd stanowi niejako etap drugi (dzieje się tak dlatego, że tym razem drogę odczytujemy od początku więc, aby wystartować nie musimy czekać, aż cała trasa zostanie odczytana).

Na rysunku powyżej – Rys. 6. – widzimy, że istnieje więcej niż jedna trasa o minimalnej długości (poprzednio też miało to miejsce, ale nie zaznaczałem tego by nie zaciemniać rysunku). W takiej sytuacji – gdy mysz ma dylemat, którą trasę wybrać – najlepszym rozwiązaniem jest danie priorytetu tej opcji, która nie wymaga od robota skrętu (o ile to możliwe oczywiście) dzięki czemu oszczędzamy cenny czas.

---

Wiemy już jak znaleźć optymalną (pod względem długości) drogę do środka labiryntu. Jednak aby to uczynić, robot musi znać układ ścian w labiryncie. Z kolei w momencie, gdy robot zostaje umieszczony w labiryncie jego mapa nie zawiera żadnych ścian. Co więc w takim wypadku zrobić?

Odpowiedź jest bardzo prosta. Postępujemy dokładnie tak, jakbyśmy znali układ ścian – czyli wypełniamy labirynt (co prawda bardzo pusty na razie) wodą. W ten sposób mamy wstępną drogę.

W kolejnym kroku robot rozpoczyna swój przejazd po wyznaczonej drodze. Za każdym razem, gdy dotrze do nieodwiedzonego jeszcze segmentu uaktualniamy mapkę ścian w pamięci i do aktualnego labiryntu ponownie wlewamy wodę (w ten sposób wyznaczymy aktualną drogę do celu).

Jak nietrudno zauważyć metoda ta wymaga dosyć częstego wlewania wody do labiryntu – jednak operacja ta (uaktualnienie 256-elementowej tablicy odległości) nie zajmuje dużo czasu. Czas ten zależy głownie od szybkości procesora w jaki jest wyposażony robot, ale na ogół powinien on być mniejszy od sekundy. Możemy więc sobie na to pozwolić na etapie eksploracji labiryntu.

Podsumowując: omawiana metoda świetnie nadaje się do szukania najkrótszej drogi w labiryncie. Wymaga ona 512 bajtów pamięci (256 na mapkę i 256 na tablicę odległości). Na uwagę zasługuje również jej prostota: po dotarciu do danego segmentu wykonujemy następujące kroki (o ile oczywiście segment ten nie jest celem):

1. uaktualniamy mapę ścian (o ile dany segment nie był jeszcze odwiedzany, jeśli był przechodzimy do kroku 3),
2. wlewamy wodę do labiryntu,
3. sprawdzamy, który z sąsiednich segmentów (osiągalny z danego – nie oddzielony ścianą) ma najmniejszą aktualną wartość odległości od celu,
4. jedziemy do tego sąsiada.

Metoda 4: przyspieszona metoda propagacji fali

Można się także zastanowić nad przyspieszeniem podanej wyżej metody. Chodzi głównie o krok 2. Przecież nie zawsze trzeba uaktualniać całą tablicę odległości (jednorazowe uaktualnienie mapy ścian, to dodanie do mapy najwyżej 3 ścian). Wystarczy więc uaktualnić tylko te wartości, które tego wymagają. Taka modyfikacja znacznie przyspieszy algorytm.

Zatem przyspieszona metoda wyglądała by tak, po dotarciu do danego segmentu:

1. uaktualniamy mapę ścian (o ile dany segment nie był jeszcze odwiedzany, jeśli był przechodzimy do kroku 3),
2. uaktualniamy wartości w tablicy odległości, ale tylko te, które tego wymagają(!),
3. sprawdzamy, który z sąsiednich segmentów (osiągalny z danego - nie oddzielony ścianą) ma najmniejszą aktualną wartość odległości od celu,
4. jedziemy do tego sąsiada.

Niektórzy mogą zapytać co to znaczy: uaktualniamy tylko te wartości które tego wymagają? Otóż jeśli dotarliśmy do jakiegoś segmentu i uaktualniliśmy mapę ścian wykonujemy następujące kroki:

1. sprawdzamy czy wartość odległości od celu dla danego segmentu jest o jeden większa od najmniejszej z wartości odległości osiągalnych sąsiadów,
2. jeśli tak – nie robimy nic (żadna aktualizacja tablicy odległości nie jest konieczna),
3. jeśli nie – modyfikujemy tą wartość tak, by warunek ten spełniała i powtarzamy procedurę dla każdego osiągalnego z danego segmentu sąsiada.

Wady przyspieszonej metody propagacji fali

Metoda propagacji fali (zarówno przyspieszona jak i nie) ma jedną wadę. Znaleziona droga jest najkrótszą, ale jak już wspominałem wcześniej, wcale nie musi być (i zwykle nie jest) najszybszą.

Dzieje się tak dlatego, że znaleziona droga mimo, że najkrótsza z możliwych, może mieć mnóstwo zakrętów. Może istnieć droga dłuższa od znalezionej, ale zawierająca mniej zakrętów oraz więcej długich odcinków prostych. Jeśli weźmiemy pod uwagę fakt, że nasza mysz szybciej pokonuje odcinki proste niż zakręty, na których jej prędkość znacznie spada (należy się z tym pogodzić), może okazać się, że jadąc dłuższą drogą można uzyskać lepszy czas.

Metoda 5: Kolejna modyfikacja metody Bellmana

Pomysł jest bardzo prosty: zastąpmy tablice odległości, tablicą czasu. Do tej pory w tablicy odległości przechowywaliśmy odległość danego segmentu od celu. Zamiast tej tablicy możemy w algorytmie użyć tablicy czasów (również 256 elementowej), w której zamiast odległości będzie zapisany czas jaki jest potrzebny by dotrzeć z danego segmentu labiryntu do celu.

Przyjmujemy, że przejazd z jednego segmentu do drugiego zajmuje 1 jednostkę czasu – w sytuacji, gdy robot nie musi wykonywać skrętu oraz np.: trzy razy dłużej (3 jednostki czasu) - w sytuacji, gdy musi wykonać skręt.

Następnie wartości tych używamy w trakcie wypełniania tablicy czasów. Robimy to analogicznie jak poprzednio, ale zamiast zawsze zwiększać wartość wpisywaną do kolejnych segmentów o 1, robimy to tylko, gdy dojazd do danego segmentu nie wymaga skrętu, w przeciwnym wypadku wartość wpisywaną zwiększamy o 3.

Zobaczmy jak to wygląda na przykładzie rozważanego wcześniej labiryntu – Rys. 7.

Analizując Rys. 8. widzimy, że wyznaczona tym razem trasa ma zaledwie 22 zakręty, podczas gdy trasa wyznaczona wcześniej (najkrótsza) miała tych zakrętów w najlepszym wypadku 28. Co ciekawe trasa ta jest dłuższa, ale jedynie o dwie jednostki od poprzedniej – długość tej wynosi 86, zaś poprzedniej wynosiła 84.

Wprowadzając więc niewielką modyfikację do metody Bellmana (zauważmy, że w gruncie rzeczy zmieniliśmy jedynie wagi przypisane niektórym połączeniom miedzy segmentami labiryntu) można uzyskać naprawdę świetne rezultaty.

---

UWAGA! Jeśli robot potrafi jeździć po przekątnych, w niektórych labiryntach może wykorzystywać tą umiejętność, co może dać mu przewagę nad konkurencją. Jednak, aby tę przewagę wykorzystać nie wystarczą metody omówione powyżej.

Jazda po przekątnych jest trudna – odradzałbym ją początkującym. Jeśli jednak ktoś dysponujemy zdolną myszą i zdecyduje się wykorzystać potencjał jazdy po przekątnych, to polecam dość prosty algorytm heurystyczny A*.

Podsumowanie

Na koniec chciałbym zaznaczyć bardzo ważną rzecz. Najpiękniejszą moim zdaniem cechą zawodów MicroMouse jest nieprzewidywalność – olbrzymia ilość kombinacji labiryntu skutkuje tym, że nigdy nie wiemy co czeka robota. Niektóre labirynty mogą dawać przewagę robotom, korzystającym z prostych metod, inne zaś bardziej zaawansowanym myszom.

Rolą zawodnika jest jak najlepsze przygotowanie maszyny na te niespodziewane warunki. Dlatego właśnie tak bardzo liczy się pomysłowość i umiejętność kombinowania. Każda sekunda jest cenna. Do zobaczenia na zawodach!

Źródła:
- http://www.SocietyOfRobots.com
- http://www.lboro.ac.uk/departments/el/robotics
- http://www.micromouseinfo.com
- http://www.thinklabs.in/
- http://micromouse.cannock.ac.uk
- P.Bablok, M.Jaśkowiak, P.Sieczka „Planowanie trajektorii ruchu robota mobilnego”

Autor: marcin13021988
Redakcja: Damian (Treker) Szymański
Data pierwsze publikacji na forum: 16-08-2009

algorytmy, konkurencje, mapowanie, micromouse, robot, zawody