Скоростная сборка кубика Рубика роботом

25. January 2016, 12:36 Занимательное, Компьютеры и ПО, Роботы, Электроника

Появился новый робот, быстро собирающий кубик Рубика – он справляется примерно за секунду (по ссылке с картинки – видео на Youtube.com):

Cube solving robot

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

Если я не путаю, то сейчас известно, что из любой конфигурации кубик (3×3) собирается не более, чем за 26 ходов, если ходом называется поворот грани на 90 градусов. При этом большинство конфигураций лежат на два-три хода ближе к собранному кубику. Для оценки точное число ходов не так важно. Примем, что типичная сложная конфигурация – 25 ходов. То есть, если поворачивать грань за 10 миллисекунд на 90 градусов, то с преобразованиями конфигурации можно уложиться в 250 мс (плюс затраты на “переключение” граней – но не будем их учитывать). 10 мс – это 9000 градусов или 25 оборотов в секунду. Сама по себе, скорость вращения не очень большая, добротный кубик её наверняка выдержит. Заметные потери времени при “миллисекундном разрешении” будут связаны с разгоном грани – отсюда и идеи с механическим зацеплением. Для немодифицированного кубика быстрый разгон при начале вращения грани составит серьёзную техническую проблему.

Работа робота сводится к определению начальной конфигурации кубика, вычислению оптимального (или близкого к оптимальному) пути из этой конфигурации к собранному кубику, выполнению ходов. Интересно, что оптимальный путь здесь не обязательно кратчайший. Дело в том, что оптимизировать нужно с учётом исполнительного механизма, а он может какие-то ходы выполнять быстрее, а какие-то – медленнее. Например, очевидно, что все повороты должны осуществляться в одну сторону, что некоторые ходы поддаются механическому “распараллеливанию”, а некоторые – нет, и так далее. Изображение кубика требуется получить только один раз, для определения начальной позиции. Причём это изображение может быть низкого разрешения и известной геометрии, так что сколь-нибудь заметного времени на передачу и распознавание не потребуется. Основное вычислительное время – поиск оптимального пути сборки. После того, как получен список ходов – он отправляется в контроллер механизма, который максимально быстро выполняет их, передавая команды исполнительным механизмам. Логично использовать простейший контроллер, а максимум вычислений проводить на управляющем компьютере: результатом работы программы будет являться набор команд на поворот валов электродвигателей, который и передаётся в контроллер (алгоритм выполнения команд должен учитывать параллельное выполнение, так что контроллеру потребуется память и логика, позволяющая одновременно управлять несколькими двигателями).

В общем, тема эта весьма интересная, а особенное техническое развитие она получает после преодоления секундного барьера. (Человеческий рекорд, кстати, чуть менее 5 секунд.)

Адрес записки: https://dxdt.ru/2016/01/25/7808/

Похожие записки:



Далее - мнения и дискуссии

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

Комментарии читателей блога: 6

  • 1 <t> // 25th January 2016, 18:05 // Читатель Jeff Zanooda написал:

    Не совсем очевидно, почему все повороты должны осуществляться в одну сторону.

    После поворота надо остановиться, иначе соседнюю грань не повернуть (а противоположную грань можно поворачивать одновременно). После остановки уже всё равно, в какую сторону следующий поворот – в ту же или в противоположную.

    К тому же шаговые двигатели умеют быстро останавливаться.

  • 2 <t> // 26th January 2016, 12:35 // Александр Венедюхин:

    Да, действительно, похоже, что так. “Односторонняя” кинематическая схема обычно эффективнее и проще, но для кубика разницы нет – так и так останавливаться.

  • 3 <t> // 27th January 2016, 00:32 // Читатель Z.T. написал:

    про 26, да: http://www.cube20.org/qtm/

  • 4 <t> // 30th January 2016, 04:21 // Читатель зашел в гости написал:

    тут две стороны проблемы. одна – решение самой задачи, т.е. вычисление необходимого набора “ходов”(вращения граней). другая – построение механического “интерфейса”, способного быстро вращать физический кубик, созданный для человеческих рук.
    Как насчет 17х17 и более? :)
    https://www.youtube.com/watch?v=SnsEobXdvzQ

  • 5 <t> // 30th January 2016, 04:22 // Читатель зашел в гости написал:

    лимит времени на написание сообщения совсем какой-то маленький стал. Или я старею?

  • 6 <t> // 30th January 2016, 15:53 // Александр Венедюхин:

    > лимит времени на написание сообщения совсем какой-то маленький стал. Или я старею?

    Не, это в плагине-каптче почему-то сбросился лимит, стал он 120 секунд, что, конечно, слишком мало. Поправил, теперь – 600.