Автоматический кубик Рубика, который сам себя собирает (8 фото + 2 видео)

Изобретатель из Японии, известный под псевдонимом Human Controller , изобрёл кубик Рубика, который умеет собирать себя сам.

Необычное изобретение работает за счёт моторчиков и специально написанной программы, которая решает головоломку.

Необходимые детали японский изобретатель распечатал на 3D-принтере, затем собрал кубик Рубика вместе с моторчиками и запрограммировал.

1. 
2. 
3. 

все фотографии: media.dmm-make.com

источник видео: Human Controller

источник видео: Human Controller

Новый рекорд сборки кубика Рубика: 0,38 секунды

Робот-рекордсмен, разработанный в лаборатории биомиметической роботехники Массачусетского технологического института

Есть игры, в которые ИИ обыгрывает человека. А есть такие задачи, где человек вообще не рассматривается как конкурент. Здесь роботы соревнуются только друг с другом. Сборка кубика Рубика — типичная такая задача.

В ноябре 2016 года робот компании Infineon Technologies AG установил новый мировой рекорд по сборке кубика Рубика: собрал его за 0,637 секунды, побив предыдущий рекорд 0,89 с. Но европейских инженеров превзошли студенты лаборатории биомиметической роботехники (Biomimetic Robotics Lab) Массачусетского технологического института. Их робот справился с заданием за невероятные 0,38 секунды. Это «грязное» время, которое включает в себя нажатие клавиши «Старт», распознавание изображения и вычисление последовательности действий. Непосредственно механическая часть выполнения задачи заняла примерно 335 миллисекунд. Решение задачи в программе на базе min2phase и отправка инструкций — 45 миллисекунд.

Видео в реальном времени снято явно не для человеческих глаз. Чтобы несовершенные органы чувств человека смогли зафиксировать процесс сборки, а медленный человеческий мозг осознал происходящее, требуется замедлить воспроизведение видео хотя бы в несколько десятков раз. На скорости 0,03x от реальной становится что-то понятно.

Разработчики уверены, что машина вполне способна справиться быстрее, но для этого требуется тщательная оптимизация тайминга механических движений, отснятых на высокоскоростную камеру. На видео в 0,03х скорости (замедление в 33 раза) заметно, что после каждого перемещения грани кубика по инерции двигаются туда и обратно, прежде чем окончательно остановиться. Так, поворот на 90° в реальности завершается за примерно 10 миллисекунд, но робот делает следующее движение через 15 миллисекунд. Именно в этой части можно значительно оптимизировать процесс. Но робот и так почти в два раза перекрыл предыдущий мировой рекорд, а из-за ошибок оптимизации ломался кубик или взрывались полевые транзисторы. Так что решили оставить всё как есть. Но если нужно, студенты могут «срезать» с рекорда ещё 100 миллисекунд.

В конструкции использованы следующие детали:

6 двигателей Kollmorgen ServoDisc серии U9 (четыре N9M4T с неодимовыми магнитами и два UD9-E — у них одинаковые характеристики и производительность). Два из них взяты со старого проекта механизированной руки, остальные по дешёвке куплены на eBay. К каждому двигателю прикреплён оптический датчик US Digital 2000, тоже с eBay. Хотя эти датчики обеспечивают избыточное разрешение для данного эксперимента, но их удалось купить по $14 за штуку — новые, что просто отличная цена. Правда, для прикрепления датчиков на двигатели пришлось немного повозиться.

6 специально разработанных драйверов двигателей с 12-вольтовым питанием. Здесь работают контроллеры STM32F303K8. Платы собраны на 100-вольтовых транзисторах. Но почему-то на 60 вольтах один из них дважды взорвался, когда кубик застревал. Прошивка для контроллеров.

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

2 камеры PlayStation Eye снимают по три грани каждая. Видео обрабатывается на 187 FPS под Linux с очень низкой задержкой, по сравнению с обычными веб-камерами. Эти камеры удалось купить по 7 долларов. Правда, обнаружилась проблема с чётким различием красных и оранжевых квадратов, так что студенты немного смошенничали — и закрасили оранжевые квадраты чёрной краской.

1 кубик Рубика. Один из самых дешёвых.

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

Для сборки хорошо «разобранного» кубика обычно требуется от 19 до 23 шагов. Некоторые решения складываются быстрее, чем другие (самое быстрое состоит из 21 шага). Так что если повезёт, то задача решится примерно на 30 миллисекунд быстрее.

Машина для сборки кубика Рубика на основе системы 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 групп. При этом нам не важно, в какие именно цвета раскрашен кубик, лишь бы они были различными. К сожалению, этот метод тоже пришлось «забраковать» из-за вероятностной природы алгоритмов кластеризации: они могут выдать «хороший» результат, но не гарантируют его точность.

Оба подхода имеют свои плюсы и минусы, так что в результате мы использовали нечто среднее:

1. первым делом мы делаем искусственную калибровку показаний сканера для нормализации значений. Коэффициенты получены экспериментальным путем.
2. конвертируем полученные RGB значения в HSV
3. находим квадратики белого цвета, на основе компоненты S (насыщенность)
4. искусственно увеличиваем насыщенность всех остальных квадратиков
5. проводим простую кластеризацию оставшихся цветов, сравнивая значения с центральными квадратиками.

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

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

Заключение

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

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