Курс про мегаминкс.

Сначала фан факт: я знаком с чемпионами мира по футболу. По футболу среди человекоподобных роботов. Ну и вот, по предложению этого самого чемпиона мира по футболу, Ильи Осокина, решено сделать проект по постановке мирового рекорда по скорости сборки мегаминкса (см. рис. 1).

Мегаминкс - это перестановочный пазл, похожий на кубик Рубика, но имеющий гораздо больше состояний. У него не 6, а 12 граней (это правильный додекаэдр), и у каждой грани не 4 стороны, а 5. Для обычного кубика Рубика в 2010 году было показано, что диаметр графа состояний (самый длинный кратчайший путь между состояниями) составляет 20. Для мегаминкса есть оценка снизу в 48 и сверху в 116, но точное значение человечеству пока неизвестно. Мировой рекорд по сборке кубика Рубика 3x3 человеком составляет 2,76 секунды, а роботом - 103 миллисекунды. Это вполне объяснимо, поскольку робот может и крутить, и считать существенно быстрее. Однако для мегаминкса человеческий рекорд составляет 21,99 секунды, а рекордное время сборки роботом около 8 минут. Роботы могут быть и быстрее, и сильнее людей в отдельных задачах, но в универсальности пока отстают.

В наличии имеется робот, разработанный в Лаборатории Интеллектуальных Технологий Робототехники МФТИ. Это первый в мире робот для сборки мегаминкса, в котором обеспечивается независимое вращение всех граней.

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

Теперь, куда я собственно всех приглашаю. Будет мини курс и соревнование.

Мини-курс

Формальным аппаратом для описания пазлов, подобных мегаминксу, являются группы, графы и всякие связанные штуки: графы Кэли. действия групп на графах и кое-какая наука связанная с этим. Так что теоретическая база будет изложена на мини курсе, который проведут Андроник Арутюнов, профессор ВШМ МФТИ, и Игорь Шиманогов.

В первой части курса расскажем про группы, графы и действия. Будут изучены ключевые аспекты того, как группы действуют на множествах — в частности, на графах — и как это связано с головоломками и прикладными задачами.
Определим действие группы на множестве и сразу узнаем сколькими способами можно раскрасить куб в заданное количество цветов. Потом поговорим про графы Кэли, и как это даёт наглядную геометрическую интерпретацию образующих и соотношений группы. Тут обсудим комбинаторный взгляд на алгоритмы, скорость работы и так называемое «число Бога».

В рамках второй части курса Игорь Шиманогов расскажет про классический результат вычислительной теории групп: алгоритм Шрайера-Симса. Этот алгоритм представляет интерес как один из основных способов решения произвольных перестановочных головоломок. В лекциях будет рассказана вся необходимая теория для доказательства корректности данного алгоритма. При наличии времени и желания у слушателей возможно как рассмотрение модификаций алгоритма, так и его применение к другим вопросам теории групп.

Лекциии будут проходить в очном формате, с задержкой в неделю будут выкладываться на канале Starkit Robots на youtube.

Соревнование

Мини-курс будет идти с 27 февраля в течение двух месяцев в 17:05 часов на физтехе. Аудитория будет опубликована в чате, см. ссылку в конце поста.

Для тестирования алгоритмов будет выложен в свободный доступ симулятор мегаминкса, с которым можно будет работать на Python.

В конце апреля или начале мая будет проведено оффлайн-соревнование, на котором будет определен победитель. Скорее всего, робот с этим алгоритмом будет самым быстрым в мире на тот момент.


Участвовать могут как студенты МФТИ, так и все остальные желающие. Для участия обязательно зарегистироваться в форме!

Ссылки и контакты

Форма для регистрации
Руководитель проекта: Илья Осокин tg @elijahmipt
Чат соревнования в тг: @starkitmega

Проект поддержал фонд целевого капитала.