Czy próbowaliście kiedyś ułożyć Kostkę Rubika? Dla przeciętnego człowieka jest to całkiem spore wyzwanie. Są jednak wśród nas specjaliści, którzy nie tylko potrafią samodzielnie wykonać to zadanie, ale również stworzyć robota, które zrobi je za nich!
Dima – nasz instruktor oraz opiekun Koła Projektowego zbudował i zaprogramował maszynę, która wykorzystując odpowiednie algorytmy, układa Kostkę Rubika. Przy projektowaniu inspirował się dostępną w internecie instrukcją robota Mindcub3r, którą zmodyfikował według swoich preferencji. Zmiany polegały głównie na ulepszeniu kontroli obrotów poszczególnych silników.
nn
Sam robot składa się z trzech modułów:
n
-chwytaka – jego zadaniem jest obracanie kostki w pionie
n
-koszyka – odpowiedzialnego za trzymanie kostki oraz obracanie jej w płaszczyźnie poziomej
n
-silnika z czujnikim koloru – zadaniem tego modułu jest sterowanie położeniem czujnika koloru podczas odczytywanie kolorów z poszczególnych klocków na kostce.
nn
Program do robota został napisany od zera. Dima zaczął od zaprogramowania sterowników silników. W tym kroku trzeba było stworzyć funkcje do sterowania kierunkiem i prędkością obrotu wszystkich silników oraz dokładnie określić ich pozycję za pomocą czujników (Na przykład pozycja silnika obracającego koszyk była określona za pomocą czujnika koloru). Następnym etapem było opracowanie logicznych schematów odpowiadających za konwertowanie algorytmów napisanych w nomenklaturze stosowanej w metodach układania Kostki Rubika (litery L, R, U, D, B, F oznaczają konkretne ściany kostki) na język zrozumiały dla robota, czyli spis działań, który musi wykonać, aby zrobić dany ruch.
Najważniejszym i najbardziej wymagającym zadaniem było stworzenie tak zwanej mapy kostki. Jej zadaniem było przechowywaniem aktualnych pozycji wszystkich ścianek kostki. Gdy program potrzebował informacji o położeniu kostki, korzystał z mapy i bazując na zapisanych w niej danych, mógł wykonać kolejną sekwencję ruchów.
n
Ostanim etapem było zrobienie części kodu, która odpowiadała za tworzenie oraz wysyłanie i pobieranie algorytmów do rozkładania i układania kostki. Nasz program był zaprojektowany tak, aby pseudo-losował każdy ruch. Pseudo-losowanie od zwykłego losowania różni się tym, że algorytm losowy musi się kierować pewnymi zasadami. Jest to niezbędne, ponieważ w innym przypadku program mógłby wylosować na przykład algorytm, składający się z wykonywania kilku tych samych ruchów pod rząd lub inne, niepożądane kombinacje.
nn
W przypadku znajdywania rozwiązań dla kostki, nie możemy ich znaleźć robiąc obliczenia ręcznie lub na komputerze – kostka może mieć 43*10^18 wariantów ułożenia, samodzielne wykonywanie działań zajęłoby nieprawdopodobnie dużo czasu. Lepszym rozwiązanie jest za to wysłanie mapy kostki do serwera, który ma bardzo dużą moc obliczeniową oraz wbudowany algorytm do znalezienia rozwiązania Kostki Rubika. Algorytm jest oparty o teorię grafów, dzięki temu w krótkim czasie program może znaleźć rozwiązanie i wysłać je do robota. Po otrzymaniu gotowego algorytmu, program przetwarza go na ruchy robota i krok po kroku wykonuje polecenia.
nn
Teoria grafów
n
Algorytm oparty o teorię grafów możńa sobie wyobrażić jako dużą siatkę. Każde „skrzyżowanie” oznacza oddzielną sytuację, którą możemy otrzymać na kostce rubika. Zadaniem algorytmu jest znalezienie ścieżki do pewnej sytuacji. Scieżka ta musi mieć możliwie najmniejszą wagę (czyli ilość potrzebnych ruchów do ułożenia) i właśnie łączna waga decyduje które z wielu możliwych rozwiązań jest najszybsze i najlepsze.
nnn
Poniżej przedstawiamy efekt końcowy 🙂
https://video.wixstatic.com/video/7c0141_a6d2b5eff14148d9b5957144f2c0c672/360p/mp4/file.mp4
