Ta strona używa ciasteczek (plików cookies), dzięki którym może działać lepiej. Dowiedz się więcejRozumiem i akceptuję
Kurs Raspberry Pi!Jesteś zainteresowany kursem Raspberry Pi? Wybierz najciekawsze tematy, które opiszemy »

Roboty MicroMouse – 5 metod przeszukiwania labiryntu

Programowanie 20.09.2016 marcin13021988

vintage maze structure with red arrows showing the perfect path through the mazeMicroMouse to rodzaj zawodów, w których nasz robot (mysz) ma za zadanie w jak najkrótszym czasie rozwiązać labirynt.

Rozwiązanie labiryntu, to jego przeszukanie oraz odnalezienie najkrótszej (bądź najszybszej – nie zawsze są one równoważne) drogi z kwadratu startowego (narożnik labiryntu) do jego środka.

Klasyczny labirynt złożony jest z 256 (16×16) kwadratowych elementów o wymiarach
180×180 mm oddzielonych ściankami o grubości 12 mm i wysokości 50 mm.

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 sekundy za dotykanie robota (ręczne poprawki).

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

Roboty MicroMouse opisane na forum, sprawdź przykładowe konstrukcje »

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.

W tym artykule skupię się tylko nad algorytmicznym podejściem do problemu jakiemu musi sprostać mysz znajdująca się w labiryncie.

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 16×16 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ę.

Robot musi być w pełni autonomiczny i nie może komunikować się
z nikim, ani niczym podczas pobytu w labiryncie.

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:

Zamieniając warunek oznaczony * z warunkiem oznaczonym **
otrzymamy kod wall-followera śledzącego lewą ścianę.

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ść.

Wniosek: jeśli stworzyłeś swoją mysz, to nie decyduj się na taką metodę
przeszukiwania labiryntu – robot marnuje zbyt dużo czasu (i swoich możliwości).

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.

Stosując taką metodę kodowania trywialna staje się operacja dodawania nowo odkrytych ścian do naszej mapy. Wystarczy bowiem posłużyć się zwykłą alternatywą logiczną (OR/LUB).

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 jeżeli w naszej mapie dodajemy bądź usuwamy jakąś ścianę w danym segmencie, to musimy zrobić to także w tym drugim.

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.

Rys. 2. Przykład indeksowania segmentów labiryntu – robot startuje z segmentu o numerze 0, cel zaś stanowią segmenty o numerach 119, 120, 135, 136.

Rys. 2. Przykład indeksowania segmentów labiryntu – robot startuje z segmentu o numerze 0, cel zaś stanowią segmenty o numerach 119, 120, 135, 136.

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.

Zatem wykonując obrót w lewo o 90 stopni mnożymy bajt kierunku robota razy 4 (przesuwamy jedynkę o 2 pozycje w lewo). Analogicznie, gdy robot wykona obrót w prawo o 90 stopni przesuwamy jedynkę w prawo o dwie pozycje.

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.

Rys. 3. Przykład labiryntu dającego przewagę robotom potrafiącym jeździć po przekątnych.

Rys. 3. Przykład labiryntu dającego przewagę robotom potrafiącym jeździć po przekątnych.

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.

Spotkałem się z dwiema różniącymi się implementacjami.

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,
Rys. 4ab). Krok pierwszy oraz drugi.

Rys. 4ab). Krok pierwszy oraz drugi.

  • ponownie wszystkie nieoznaczone segmenty osiągalne z segmentów oznaczonych w kroku poprzednim oznaczamy wartością o jeden większą,
Rys. 4cd). Krok trzeci oraz piąty.

Rys. 4cd). Krok trzeci oraz piąty.

  • ostatni krok powtarzamy dopóki nie zostanie oznaczony jeden z czterech segmentów docelowych (119, 120, 135 lub 136).
Rys. 4e). Krok ostatni (osiemdziesiąty piąty) – labirynt "zalany wodą".

Rys. 4e). Krok ostatni (osiemdziesiąty piąty) – labirynt „zalany wodą”.

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.

Rys. 5. Wyznaczanie najkrótszej (długość znalezionej trasy = 84).

Rys. 5. Wyznaczanie najkrótszej (długość znalezionej trasy = 84).

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.

Wystarczy więc, że robot przejedzie kierując się malejącymi wartościami
z tablicy odleglosc i labirynt rozwiązany.

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).

Drugą wersję uważam więc za znacznie lepszą do implementacji w robocie.
W dalszej części artykułu będę się odwoływał tylko do niej.

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).

Po jakimś czasie robot dotrze do celu, a w pamięci będzie miał mapę labiryntu i uzupełnioną tablicę odleglosc[]. Wystarczy wrócić na start i wykonać przejazd.

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.

W takiej sytuacji omawiana metoda jest bezsilna.
Ale warto się zastanowić, czy musi tak być? Otóż niekoniecznie…

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.

Jeśli robot spełniałby przyjęte założenia czasowe, wybierając dłuższą trasę dotarłby do celu znacznie szybciej niż jadąc trasą najkrótszą.

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*.

Zainteresowanych odsyłam do prezentacji
pt. „Planowanie drogi robota, algorytm A*” Karola Sydora.

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

Powiadomienia o nowych, darmowych artykułach!

Załączniki

Komentarze

paradox91

18:03, 17.08.2009

#1

Świetny artykuł właśnie czegoś takiego szukałem. Rozjaśnił mi umysł w sprawie micro mouse i natchnął do budowy robota tego typu. Szkoda że w Polsce tak mało takich zawodów :-(

Decado

18:04, 17.08.2009

#2

Paradox91, wiesz o tym że jak chcesz to moge takie zorganizować?? :D Tylko zeby sie chociaz z 3-4 roboty zglosily :). A potem bedzie juz z górki

Elvis

18:09, 17.08.2009

#3

Ja chętnie na takie zawody :) Co prawda jeszcze nie mam na nie robota, ale jak termin będzie odpowiedni, to coś powinienem mieć. Może jeszcze jednego kumpla namówię, żeby tego typu robota skonstruował.

marcin13021988
Autor wpisu

18:30, 17.08.2009

#4

Cieszę się że artykuł się podobał. Ja swoją mysz miałem zamiar ukończyć najpóźniej na zawody w Bratysławie ale jeśli tylko byłyby jakieś zawody w Polsce to również się piszę.

Le_Cheque

13:39, 02.09.2009

#5

Świetny artykuł, już się biorę za naukę, by za parę lat móc zrobić takie cudo. Dodatkowo można znaleźć w internecie ciekawą animację algorytmu . Pzdrawiam

bulibulibu

18:59, 23.11.2009

#6

Jeśli będzie dalsze zainteresowanie, to Koło Naukowe Skaner z Politechniki Łódzkiej pomyśli nad organizacją tej konkurecji w Polsce, podczas SumoChallenge2010. Decyzję podejmiemy w styczniu, lutym, w zależności od zainteresowania przeprowadzeniem tej konkurencji oraz od naszych mozliwosci zapewnienia odpowiedniej infrastruktury. Zawody SumoChallenge2010 odbęda sie w kwietniu lub czerwcu 2010.

Jeśli chcecie - piszcie ;)

marcin13021988
Autor wpisu

20:34, 23.11.2009

#7

Świetny pomysł - popieram

Treker
Administrator

8:36, 20.09.2016

#8

Drobne odświeżenie artykułu (głównie formatowanie i redakcja) dzięki czemu mógł trafić na bloga :)

Roboty MicroMouse – 5 metod przeszukiwania labiryntu

deshipu

12:32, 20.09.2016

#9

Bardzo się cieszę, widząc na blogu takie artykuły. Z wielką przyjemnością przeczytałbym na ten temat więcej -- na przykład jak można optymalnie zbierać informację o ścianach labiryntu podczas pierwszego przejazdu (omijając zupełnie obszary, które na pewno są ślepymi zaułkami), albo jak trzymać informacje o ścianach bez konieczności duplikowania jej w obu sąsiadujących segmentach.

Artykuł o samych algorytmach grafowych (znajdowanie drogi, drzewa rozpinającego, kolorowania, rozłącznych obszarów, etc.) albo o metodach reprezentowania grafu w pamięci też mógłby być niezmiernie ciekawy i przydatny.

Harnas

15:56, 20.09.2016

#10

deshipu napisał/a:

jak można optymalnie zbierać informację o ścianach labiryntu podczas pierwszego przejazdu (omijając zupełnie obszary, które na pewno są ślepymi zaułkami)

Ja w moim MM zakładałem na początku labirynt całkowicie bez ścianek i co każde pole wyznaczałem najszybszą możliwą trase od nowa, z zaktualizowanymi polami. Ślepe zaułki były wtedy omijane automatycznie, po prostu nie ma szansy na to żeby biegła przez niego najszybsza trasa.

Co do reszty to akurat samo MM jest zbyt ograniczonym zastosowaniem, żeby zabawa w optymalizowanie duplikacji danych czy zabawy z grafami miały większy sens.

deshipu

17:44, 20.09.2016

#11

Harnas napisał/a:

Ja w moim MM zakładałem na początku labirynt całkowicie bez ścianek i co każde pole wyznaczałem najszybszą możliwą trase od nowa, z zaktualizowanymi polami. Ślepe zaułki były wtedy omijane automatycznie, po prostu nie ma szansy na to żeby biegła przez niego najszybsza trasa.

Chyba rozumiem, to ma sens, dzięki!

Harnas napisał/a:

Co do reszty to akurat samo MM jest zbyt ograniczonym zastosowaniem, żeby zabawa w optymalizowanie duplikacji danych czy zabawy z grafami miały większy sens.

Też nie o samo MM mi chodzi, tylko o wykorzystanie go jako pretekst do nauki. Algorytmy grafowe przydają się bardzo wielu dziedzinach, w tym dość często w robotyce. Sam przećwiczyłem wiele z nich przy okazji losowego generowania map do gier oraz później logiki dla potworów na tych mapach, ale jestem pewien, że zastosowań jest dużo więcej.

Zobacz powyższe komentarze na forum

FORBOT Damian Szymański © 2006 - 2017 Zakaz kopiowania treści oraz grafik bez zgody autora. vPRsLH.