Машина по сборке кубика рубика

MindCub3r по-русски — делаем робота, который может собрать кубик Рубика (статья обновлена)

Не так давно обзавелся набором LEGO MINDSTORMS EV3 (31313) и с удивлением обнаружил, что в русскоязычном сегменте интернета довольно мало интересных материалов и инструкций по сборке и настройке роботов из этого набора. Решил, что нужно это дело исправлять.

Эта инструкция представляет собой вольный перевод материалов с официального сайта проекта MindCub3r и дополнена опытом самостоятельной сборки этого робота, способного собрать кубик Рубика меньше чем за 2 минуты.

Подробнее о LEGO MINDSTORMS EV3 можно почитать на этом сайте.

Вот, что у нас должно получится в итоге:

MindCub3r можно построить из одного комплекта Lego Mindstorms EV3 (31313, Home Edition).

Также вам понадобится инструкция по сборке и программное обеспечение, разработанное авторами проекта.

Буквально позавчера автор проекта объявил в своем ФБ, что подправил программное обеспечение для своего робота, и теперь оно работает со «штатной» прошивкой «кирпича» 1.06Н. На главной странице проекта эта информация также уже появилась, архив MindCub3r-v1p1a.zip, содержащий, среди прочего, и обновленную версию программы, уже доступен для загрузки. Загрузка и установка блока для датчика цвета по-прежнему необходима.

Дальнейший текст статьи исправлен с учетом последних изменений на сайте проекта!

Инструкцию по сборке MindCub3r смотрим или скачиваем здесь.
Прошивку (на момент написания статьи EV3-Firmware-V1.06H.bin) для кирпича скачиваем с официального сайта LEGO MINDSTORMS здесь.
Архив MindCub3r-v1p1a.zip с файлами проекта (MindCuber-v1p1.ev3, autorun.rtf и mc3solver-v1p1.rtf) качаем тут.
Еще нам понадобится прошивка для датчика цвета, которую берем здесь. Все дело в том, что стандартные настройки этого датчика не корректно определяют цвета в режиме RGB.

После того, как вы соберете робота и скачаете себе на компьютер все необходимое, можно приступать к настройке.

Если вы еще не обновили прошивку «кирпича» первым делом устанавливаем новую версию ПО для главного блока Mindstorms EV3:

1. Запускаем программное обеспечение LEGO MINDSTORMS EV3;
2. Выбираем Инструменты — Обновление встроенного ПО;

3. В появившемся диалоговом окне нажимаем «Просмотреть», находим предварительно закаченный файл EV3-Firmware-V1.06H.bin и жмем «Открыть»;

4. В диалоговом окне в таблице «Доступные файлы встроенного ПО» выбираем EV3-Firmware-V1.06H и жмем «Загрузить». Ждем окончания загрузки;

5. Перезагружаем главный блок (выключаем и снова включаем).

Далее устанавливаем прошивку для датчика цвета:
1. В ПО LEGO MINDSTORMS EV3 открываем новый пустой проект;
2. Выбираем Инструменты — Мастер импорта блоков;

3. В появившемся диалоговом окне нажимаем «Просмотреть», находим предварительно загруженный файл ColorSensorRGB-v1.00.ev3b и жмем «Открыть»;

4. В диалоговом окне в таблице «Выбрать блоки для импорта» выбираем ColorSensorRGB-v1.00.ev3b и жмем «Импорт».

5. Для завершения установки закройте диалоговое окно и выйдите из программного обеспечения LEGO MINDSTORMS EV3.

Теперь самый ответственный момент — загрузка программы робота в кирпич:
1. Распаковываем предварительно загруженный архив MindCub3r-v1p1a.zip;

2. Запускаем ПО LEGO MINDSTORMS EV3;
3. Выбираем Файл — Открыть проект, ищем файл MindCub3r-v1p1.ev3, распакованный из архива MindCub3r-v1p1.zip и жмем «Открыть»;

4. После открытия проекта загружаем его в «кирпич». Загружаем, но НЕ ЗАПУСКАЕМ.

5. Идем в Инструменты — Обозреватель памяти (Ctrl+I);

6. Выбираем (выделяем) во вкладке «Модуль» или «SD-карта» папку проекта «MindCub3r-v1p1»;
7. Нажимаем «Загрузить»;

8. Находим файл mc3solver-v1p1.rtf, распакованный из архива MindCub3r-v1p1a.zip и нажимаем «Открыть»;
9. Еще раз нажимаем «Загрузить», предварительно убедившись, что папка проекта «MindCub3r-v1p1» все еще выделена;
10. Находим файл InstallMC3-v1p1.rbf, распакованный из архива MindCub3r-v1p1a.zip и нажимаем «Открыть»;

11. Закройте диалоговое окно, выйдите из программы и перезагрузите модуль.

Последний этап — устанавливаем приложение MC3 Solver на главном модуле:

2. Находим во второй вкладке папку проекта MindCub3r-v1p1 (в памяти блока или на SD-карте):

3. Выбираем файл InstallMC3-v1p1 и нажимаем на центральную кнопку модуля для установки:

4. В третьей вкладке проверяем наличие установленного приложения MC3 Solver v1p1:

5. Перезагружаем блок.

6. В третьей вкладке блока запускаем приложение «MC3 Solver v1p1» для начала работы программы mc3solver-v1p1.rtf:

Всё! MindCub3r готов к использованию!

7. Запускаем программу в первой или во второй вкладке блока:

После запуска программы робот попросит вложить кубик («Insert cube») и начнет его сканировать датчиком цвета.
После сканирования робот ненадолго задумается и начнет сборку.
Удачное решение задачи ознаменуется радостным вращением кубика.

Вот, собственно, процесс работы робота:

Выше описан идеальный сценарий, на практике же все немного хуже — датчик может не правильно определить цвета — всего робот может провести 3 (три) цикла сканирования до того, как выдаст ошибку (Scan error). После этого нужно изъять кубик и снова вложить в робота. Причиной этому может быть или низкий заряд батареи модуля или «неправильный» кубик.
У меня иногда проходило по 3-5 повторов (3 цикла сканирования и одно изъятие) прежде чем робот принимался за сборку, но результат того однозначно стоит.

Если у вас остались вопросы, задавайте их в комментариях к статье, с удовольствием на них отвечу.

Источник

Машина для сборки кубика Рубика на основе системы FAC

Не так давно мы вместе с Wilbert Swinkels закончили работу над машиной, собирающей кубик Рубика. Про нас написали в официальном блоге Raspberry Pi и мы получили массу восторженных отзывов. Тем не менее, в русскоязычном сегменте сети проект как-то остался незамеченным. Так что я решил исправить это упущение, разместив здесь переведенную и дополненную версию оригинального поста.

Под катом речь пойдет (в основном) о софтверной части этой машины, о механической части можно почитать на официальной страничке проекта (да-да, мы знаем, что она немного «олдскульна»)

Вступление

Началось все с того, что в мае этого года я совершенно случайно познакомился с Wilbert Swinkels. Я был просто потрясен, когда увидел его творения: каждый из этих механизмов, от мала до велика, можно с уверенностью назвать произведением искусства. И чем ближе рассматриваешь их устройство, тем больше поражаешься их красотой.

Разумеется, когда Вилберт предложил мне помочь ему с машиной для сборки кубика Рубика, я не раздумывал ни секунды, тем более, что к тому времени я уже обнаружил в себе страсть к цветным кубикам. На тот момент он уже работал над машиной в течение 4 (!) с лишним лет, однако софтверную часть все еще предстояло написать.

Опыта программирования под Raspberry Pi и Arduino у меня не было совсем, но в целом задача показалась мне довольно несложной. Конечно же, я ошибался 🙂

Hardware

Сама машина построена с помощью модульной системы FAC. Это что-то вроде советского конструктора, но созданного для прототипирования серьезных и сложных механизмов. Во второй половине прошлого века ее очень активно использовали в лабораториях Philips и других компаний и университетов.

К моменту моего знакомства с Вилбертом, он уже дважды пытался «оживить» машину. Оба раза за дело брались студенты Амстердамского университета, и, к сожалению, оба раза они теряли интерес к проекту после нескольких безуспешных попыток. Один из них даже защитил диплом бакалавра по этой теме, несмотря на то, что в результате машина так и не смогла собрать кубик (поднимите руку те, кто узнал здесь себя).

Микроконтроллер

Первым делом мы решили использовать Raspberry Pi вместо Arduino. Главным образом это связано с тем, что «умные» алгоритмы решения кубика Рубика требуют значительного объема памяти и процессорных мощностей. В предыдущих попытках использовался примитивный трехслойный алгоритм, но в этот раз мы решили использовать алгоритм Коцембы. Кроме того, мне не очень хотелось писать все на С (хотя частично все же пришлось).

В стандартной версии Raspberry Pi нам не хватило пинов, чтобы подключить все имеющиеся моторы, поэтому мы заказали Development Kit. Кстати, очень советую: пинов не только больше, но и расставлены они, на мой взгляд, более логично. К тому же, на этой плате два разъема для камеры вместо одного.

Первая версия сканера

Для считывания начальной конфигурации кубика нужно было сканирующее устройство. Идея очень проста: по очереди освещаем поверхность кубика тремя светодиодами: красным, зеленым и синим. Каждый раз замеряем отраженный свет при помощи фоточувствительного резистора. Теоретически, мы должны получить RGB-значения, которые можно использовать для распознавания цвета квадратика. От предыдущих программистов у нас остался proof-of-concept код для Arduino, который, казалось бы, даже работал при определенных условиях.

Первой проблемой, с которой мы столкнулись, было несоответствие напряжения. Как известно, логическая единица на пинах Arduino составляет 5В, в то время как у Raspberry Pi это 3.3В. К счастью, контроллеры шаговых двигателей (stepper motor driver), которые мы использовали, продолжили работать, несмотря на изменение амплитуды импульсов.

Гораздо более критичным оказалось то, что в Raspberry Pi нет аналоговых входов. Из-за этого на Raspberry нельзя просто взять и считать напряжение на фоторезисторе. Это, наверное, очевидно для тех, кто хоть раз с таким сталкивался, но я поначалу об этом даже не задумывался. Порыскав в сети в поисках решения, мы наткнулись на эту статью. В двух словах, мы добавляем в цепь конденсатор, и замеряем время, за которое он зарядится от нуля до логической единицы (это мы можем задетектить с помощью цифрового пина). Время зарядки будет пропорционально сопротивлению фоторезистора, поэтому мы можем судить о количестве света.

Этот подход не только ужасно ненадежен (считать время в питоновском скрипте на Linux с кучей фоновых процессов — неблагодарное дело), но и до невозможности долог. Для того, чтобы сгладить случайные отклонения в показаниях, приходилось производить считывание несколько раз, избавляться от выбросов, и усреднять оставшиеся значения. Тем не менее, нам-таки удалось заставить этот сканер работать:

Вторая (финальная) версия сканера

Сканер на конденсаторах работал довольно неплохо, но был уж очень медленным. На сканирование всего кубика Рубика уходило около двух минут, и к моменту завершения сканирования у зрителя уже пропадал всякий интерес. Поэтому мы решили все-таки вернуться к Arduino и купили маленькую Arduino Mini специально для управления сканером.

Подружить Arduino с Raspberry Pi оказалось невероятно просто: два провода, конвертер напряжения между ними, и вуаля — у нас есть Serial-интерфейс. А если прикрутить сверху простенький протокол Min, то и программировать это дело — одно удовольствие.

Я перенес всю логику управления сканером на Arduino. Скорость сканирования значительно возросла. Благодаря аналоговым входам, мы можем считывать напряжение напрямую с фоторезисторов, и эти значения очень точны. К тому же, так как Arduino смонтирован непосредственно на сканере, нам нужно гораздо меньше проводов от сканера к Raspberry Pi!

Алгоритм сборки

Сборка кубика Рубика с точки зрения математики — довольно трудоемкая задача. Конечно, речь идет о нахождении оптимального решения, а не «какого-нибудь». Я был удивлен, когда узнал, что число Бога (точная нижняя граница для количества ходов, необходимых для решения произвольного кубика) было найдено лишь в 2010.

В этом проекте мы хотели сократить суммарное время, необходимое для просчета решения и сборки, поэтому нам не подходили ни простой трехслойный алгоритм (он работает быстро, но выдает решения длиной в сотню ходов), ни оптимальный алгоритм (решения короткие, но процесс просчета на Raspberry Pi занимал бы вечность). В результате мы остановились на великолепном «двухфазном» алгоритме немецкого математика Herbert Kociemba. Он способен выдавать субоптимальные решения (в среднем 20 ходов), укладываясь при этом в разумное время.

На сайте автора можно найти реализацию алгоритма на Java. Первым делом я перевел этот код на Python. Это было совсем не сложно, поскольку большая часть программы — это математические операции и перебор вариантов. Однако, я не учел, что алгоритм требует действительно много ресурсов. Нахождение решения при первом запуске заняло более минуты (!) на моем ноутбуке.

Под PyPy с включенным JIT решение заняло 1 секунду на ноутбуке, но на Raspberry Pi все еще требовало порядка минуты. После нескольких попыток ускорить работу питоновской программы (numpy, multiprocessing), я решил все же переписать алгоритм на C. Теперь решение занимает 1-2 секунды даже на Raspberry.

Обе реализации алгоритма я выложил на GitHub.

Управление машиной

Следующим шагом было написать программу, которая бы управляла механической частью: двигала моторчики, учитывая передаточные числа и ограничения механизма (например, боковые держатели можно поворачивать только когда нижний находится в определенном положении, иначе он будет мешать).

Помимо основной программы, я сделал интерактивный шелл, который сэкономил мне кучу времени при отладке. В целом, в этой части не было ничего необычного с точки зрения программирования. Для отладки сканирования я генерировал результаты в виде картинок.

Сканирование и распознавание цветов

До этого момента все было интересно, но не сложно. Спустя две недели после начала работы, машина уже могла собирать кубик из заданного состояния. Оставалось только научиться считывать начальную конфигурацию кубика при помощи сканера. У нас уже была «рабочая» программа для Arduino, так что мы не ожидали никаких сюрпризов. Тем не менее, эта часть проекта оказалась самой сложной, и отняла у нас еще 2 месяца трудов.

Показания фоторезисторов

Как я писал выше, мы начали со схемы сканера с конденсаторами. Погрешность такого подхода была ужасающей, поэтому для получения юзабельных значений пришлось делать замеры несколько раз, а затем избавляться от выбросов. После этого мы получили что-то вроде этого (это результат сканирования собранного кубика в темной комнате):

Как видно, результат далек от идеала. Во-первых, значения для одного и того же цвета на разных позициях различны, поскольку фоторезисторы и светодиоды «смотрят» в немного разных направлениях. Во-вторых, некоторые цвета находятся очень близко друг к другу в цветовом пространстве, а порой и вовсе диапазоны значений пересекаются (например, оранжевый и красный иногда дают одинаковые значения). И, наконец, показания очень сильно зависят от внешнего освещения.

Наглядно погрешность сканера на конденсаторах можно увидеть на следующей диаграмме (а вообще, есть интерактивная версия здесь):

Оглядываясь назад, я удивляюсь, как нам вообще удалось заставить сканирование работать с такими результатами, хотя это и потребовало тщательной и мудреной калибровки значений, о которой речь пойдет чуть ниже.

Как я уже говорил, сканер на конденсаторах заработал, но был очень медленным. Когда мы заменили его другим, со встроенной Arduino, показания стали гораздо «кучнее» (интерактивная версия тут):

Калибровка и кластеризация показаний

Теперь, когда у нас были «сырые» RGB-показания с фоторезисторов, нужно было собственно идентифицировать цвета, чтобы подать конфигурацию кубика на вход алгоритму сборки. Здесь сразу напрашивались два различных подхода: использование цветовых интервалов и алгоритма кластеризации.

Первый подход — это решение «в лоб»: можно было экспериментальным путем определить интервалы значений для каждой стороны кубика (по сути, разбить пространство цвета на непересекающиеся области), и затем просто объединять значения по принадлежности определенному интервалу. При этом, каждую из 9 возможных позиций на грани кубика следует рассматривать отдельно. Такой метод очень просто запрограммировать, но у него есть два существенных недостатка. Во-первых, он привязывает нас к конкретным цветам, а значит мы сможем собирать только строго определенный кубик Рубика. А во-вторых, интервалы возможных значений очень сильно зависят от внешнего освещения. Более того, мы обнаружили, что, в зависимости от внешнего освещения, одно и то же показание может отвечать различным цветам.

Второй подход требует предварительной калибровки значений, чтобы один и тот же цвет давал одинаковые результаты во всех 9 позициях на грани кубика. В этом случае мы можем использовать алгоритм кластеризации для объединения значений в 6 групп. При этом нам не важно, в какие именно цвета раскрашен кубик, лишь бы они были различными. К сожалению, этот метод тоже пришлось «забраковать» из-за вероятностной природы алгоритмов кластеризации: они могут выдать «хороший» результат, но не гарантируют его точность.

Борьба с внешним освещением

Даже с хорошим алгоритмом кластеризации сканирование часто заканчивалось неудачей из-за внешних условий. Алгоритм, откалиброванный в темной комнате, не справлялся с задачей в дневных условиях, и наоборот. Более того, если внешнее освещение было очень ярким (прямой солнечный свет), сканер вообще переставал работать, так как влияние светодиодов становилось едва заметным. Вилберт проделал очень кропотливую работу над изоляцией сканера от внешнего освещения. Пришлось пройти 3 итерации: каждый раз мы думали, что этого будет достаточно, и каждый раз обнаруживалась очередная щель, через которую внешнее освещение попадало на фоторезистор.

Заключение

Работать над этим проектом было невероятно захватывающе. Так здорово наблюдать, как на твоих глазах машина оживает, и особенно круто видеть, как она работает, оправдывая все твои усилия. Однако это не идет ни в какое сравнение с тем багажом знаний, которые удалось почерпнуть в процессе. Я и предположить не мог, что мне придется изучить тучу материалов по электронике, механике, алгебре и даже математической статистике, а по пути найти с десяток полезных утилит и библиотек. Вот почему я так счастлив, что мне представилась возможность работать над этим проектом.

Как бы то ни было, эта машина — всего лишь прототип. Мы не задавались целью побить рекорд скорости, и уж точно мы не реализовали весь потенциал механических частей. Но мы обязательно постараемся сделать это в следующей версии машины, над которой мы уже начали работу. Там для сканирования мы собираемся использовать камеру, а конструкция манипуляторов претерпела значительные изменения. Ну и конечно, если у вас есть какие-либо вопросы, предложения или советы — буду рад услышать их в комментариях.

Источник

Rubik’s Cube

Rubik’s Cube Simulator

Play with the online cube simulator on your computer or on your mobile phone.

Drag the pieces to make a face rotation or outside the cube to rotate the puzzle.

Apply a random scramble or go to full screen with the buttons.

Rubik’s Cube Solver

Calculate the solution for a scrambled cube puzzle in only 20 steps.

Set up the scramble pattern, press the Solve button and follow the instructions.

Use the color picker, apply an algorithm or use a random scramble.

How to solve the Rubik’s Cube

The beginner’s solution guide with images and easy to follow instructions.

Knowing how to solve the Rubik’s Cube is an amazing skill and it’s not so hard to learn if you are patient. You’ll realize that you don’t have to be a genius to get it done.

In this tutorial we are going to use the easiest layer-by-layer method.

White Edges

Let’s start with the white face. Try to form a plus sign on the top of the cube, matching the colors of the side stickers to the colors of the lateral centers. This step shouldn’t be too hard, try to do this without reading the examples below.

We can easily insert the edge to the top if you move it to the highlighted bottom-front spot first. Depending on where the white sticker is facing do the rotations.

When the white edge is stuck between two solved edges (last image) you can send it to the bottom layer doing this:

I used capital letters to mark the clockwise face rotations: F (front), R (right), L (left), U (up), D (down).

Turns in the opposite direction are marked with an apostrophe.

Finish The White Face

When the white edges are matching we can move on to solve the white coners.

First put the white corner that belongs to the spot marked with the upper arrow in either of the highlighted positions. Next repeat the algorithm below until the white piece comes to its desired destination.

This trick sends the piece back and forth between the top and bottom locations, twisting the corner in each step. Using this you can solve each white corner in less than 6 iterations.

At the end your cube should have a solid white face with the lateral stickers matching the lateral centers.

Center Layer

Turn your cube upside down because we don’t need to work with the white face anymore. We can insert an edge piece from the top-front position to the middle layer using a trick. Do the left or right algorithm depending on which side you have to insert the piece:

When a center layer piece is in a wrong position you can use the same trick to take it out.

You’ll have two solved layers when you finish this stage. We’re almost there.

Yellow Cross

Inspect the top of your cube. You see a yellow cross, a line, an L-shape or a dot. Our goal is to form a yellow cross.

Use this algorithm to shift from one state to the other.

Swap Edges

We have a yellow cross on the top but the edges are not in their final position. They need to match the side colors.

Use this to swap the front and left yellow edges in the top layer.

Cycle Corners

Only the yellow corners are left unsolved at this point. Now we are going to put them in their final position and we’ll rotate them in the last step.

Use the algorithm below to cycle the pieces in the direction marked with the arrows while the top-right-front piece is standing still.

Orient Corners

Everything is positioned, we just have to orient the yellow corners. We use the same algorithm that we used for solving the white corners in the second step:

This step can be confusing for most people so read the explanation very carefully and do exactly what it says!

1. Hold the cube in your hand having an unsolved yellow corner in the highlighted top-right-front position.
2. Repeat the algorithm until this piece is solved.
3. Turn the top layer to bring another unsolved piece in the highlighted position.
4. Repeat R’ D’ R D until that one is also solved.
5. Do 3 and 4 for any other unsolved yellow corner.

Important! During the process it might seem that you have messed up the whole cube but don’t worry because it will come together if you do it correctly, following the instructions.

Video Tutorial

Watch these steps being explaind in this video:

Источник