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



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

TL;DR

Для нетерпеливых, несколько ссылок:

• Официальная страничка проекта
• Реализации двухфазного алгоритма Коцембы (Python и C)
• Другие творения Вилберта
• Сайт Вилберта о системе FAC
• Официальный сайт системы FAC

Вступление

Началось все с того, что в мае этого года я совершенно случайно познакомился с 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 итерации: каждый раз мы думали, что этого будет достаточно, и каждый раз обнаруживалась очередная щель, через которую внешнее освещение попадало на фоторезистор.

Заключение

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



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