[Algorytmy] MicroMOUSE - metody przeszukiwania labiryntu

[marcin13021988]

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

UWAGA, to tylko wstęp! Dalsza część artykułu dostępna jest na blogu.

Przeczytaj całość »

Poniżej znajdują się komentarze powiązane z tym wpisem.

[paradox91]

Ś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]

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

[Elvis]

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]

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]

Ś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]

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]

Świetny pomysł - popieram

[Treker (Damian Szymański)]

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]

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]

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]

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!

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.

[Alan_R]

Dziękuję za ten artykuł!

[memphis60raines]

Świetny artykuł. Czy ktoś z Was dysponuje zmodyfikowanym algorytmem Bellman'a?