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



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


TL;DR


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


Вступление


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

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

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

Hardware


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

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

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


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

image

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

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


image

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

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

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

image

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



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


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

image

Подружить 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.

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


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

image

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

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


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

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


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



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

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



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

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



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


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

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

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

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


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


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

image

Заключение


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

image

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

Комментарии (21)


  1. ice2heart
    30.09.2015 08:11

    Конструктор крутой, но цены на него не радуют.


    1. muodov
      30.09.2015 10:42

      Согласен, особенно если переводить в рубли. С другой стороны, б/у детали можно купить по гораздо более низкой цене, а если сравнить цены на FAC с другими профессиональными конструкторами, так и вообще покажется недорого.


  1. SystemXFiles
    30.09.2015 09:16
    +1

    Немного оптимизаций:

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


    А так очень хорошая работа, впечатляет. Виден потенциал для реализации быстрой сборки =)


    1. SystemXFiles
      30.09.2015 09:21

      Еще, почему бы не сделать множество калибровок в зависимости от освещения? Т.е. иметь датчик освещения, относительно него выбирать нужную калибровку? По идее и изоляция не будет нужна потом сканирующей области.


      1. ice2heart
        30.09.2015 09:43

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


        1. muodov
          30.09.2015 11:06

          Все верно, цвет внешнего освещения тоже играет роль. К тому же, оно непостоянно: что если солнце зайдет за тучи во время сканирования?
          В случае с камерой, я так полагаю, калибровок вообще не понадобится, так как нам главное различить цвета, а не идентифицировать их.


          1. ice2heart
            30.09.2015 11:09

            Я думаю баланс белого вполне реально делать. Как на роверах, расположить эталон цвета (серого), и по нему автоматически корректировать баланс.


    1. valemak
      30.09.2015 10:49
      +2

      >>> Может ошибаюсь, но разве нельзя просканировать три стороны кубика и вычислить остальные? Сканирование в два раза быстрее будет.

      Трёх сторон недостаточно. На «невидимых» гранях есть три ребёрных элемента, расположение которые вообще никак не вычисляются на основании видимых сторон. Методом исключения вычисляются расцветки этих элементов (и то — не всегда), но абсолютно нет информации на каком именно месте какой элемент находится.

      На рисунке кубик повёрнут так, что 'невидимые' стороны обращены к зрителю, неизвестные рёберные грани окрашены чёрным


      1. muodov
        30.09.2015 11:03

        Было бы круто узнать, сколько же все-таки достаточно :)


        1. valemak
          30.09.2015 11:19

          Более того — даже на трёх «видимых» сторонах ни черта, на самом деле, не видно.

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

          Что касается ребёрных двухцветных элементов, то информации только об одном из цветов уже не хватает. Из девяти видимых только три однозначно определяются.

          Здесь кубик повёрнут к зрителю своей видимой частью. Чёрным цветом помечено 6 рёберных и 3 угловых элемента, о которых нет достаточно информации для их идентификации


          1. muodov
            30.09.2015 11:33

            Но ведь далеко не все положения достижимы. Если например просканировать 5 граней, то, возможно, будет только одно достижимое состояние шестой грани. Это только гипотеза, конечно. Надо попробовать доказать.


            1. valemak
              30.09.2015 11:44
              +1

              В некоторых случаях 5 сторон может оказаться достаточно, но, как правило, — нет. Угловые и центральный на неизвестной стороне определяются однозначно, а вот ребёрные — не всегда.

              Поясню на примере. Допустим, два ребра имеют один из цветов — зелёный. При этом зелёные грани окажутся на видимых сторонах, а незелёные — на 6-й невидимой. Узнать окончательный расклад можно, только посмотрев на последнюю сторону.

              'Неизвестная' 6-я сторона на рисунке - верхняя.


            1. valemak
              30.09.2015 11:48

              >>> Но ведь далеко не все положения достижимы.

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


    1. muodov
      30.09.2015 11:02

      Спасибо за отзыв!

      Действительно, есть мнение, что сканировать все стороны не обязательно. Но мне не удалось найти математического доказательства или опровержения этого факта, или алгоритма, который позволил бы это сделать. Для следующего поколения это нужно, конечно, видимо придётся разбираться в математике. Если вы найдёте ответ, не забудьте поделиться)

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


      1. SystemXFiles
        30.09.2015 18:45

        А есть видео, где машина работает в полную мощность по скорости? Очень хотелось бы увидеть, на что она способна =)


        1. muodov
          30.09.2015 19:05

          Такого видео нет, но там ничего сверхъестественного нет. Просто результат на несколько секунд быстрее. Мы не оптимизировали движения манипуляторов по отношению друг к другу, они просто могут двигаться быстрее, примерно в два раза. При этом время на снятие показаний с фоторезисторов, конечно, не уменьшается.


  1. alhor
    30.09.2015 12:39

    на это можно смотреть бесконечно!

    В связи с этим вопрос — скорость манипуляторов ограничена принудительно? В сети был ролик, где кубик собирают в разы быстрее, на лего, кажется.

    Спасибо за зрительный экстаз :)


    1. muodov
      30.09.2015 13:21

      Не за что, мы сами тащимся :)

      Здесь мы не пытались бить рекорды скорости, это бессмысленно с таким методом сканирования. Мы не стали ставить сюда камеру, потому что было интересно отсканировать куб, используя low-end детали: фоторезисторы и светодиоды.

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


    1. Halt
      30.09.2015 16:01

      И правда, чуть-чуть быстрее :)


      1. muodov
        30.09.2015 16:13
        +1

        Ну тогда уж надо смотреть на CubeStormer 3 ;)
        Дело не в скорости, а в красоте исполнения)


        1. Halt
          30.09.2015 17:23

          Это да :) А еще у вас звук сервоприводов шаговых двигателей божественный.