Micromouse — а ваша робомышь пройдёт лабиринт?
Возможно, вы слышали про Micromouse — конкурс для маленьких роботов-мышей, которые должны быстрее всех найти путь в центр лабиринта. Лабиринт не очень большой, его размер 32×32 квадрата (раньше было 16×16) с длиной грани 9 см. Высота стенок каждой ячейки 2,5 см, толщина — 0,6 см. Если не слышали, Cloud4Y предлагает узнать чуть больше об этом увлекательном (без шуток!) хобби.
Соревнования стали проводиться в 1970-х годах. Журнал IEEE Spectrum представил концепцию микромыши в мае 1977 года, и тогда же компания Spectrum объявила о проведении конкурса «Amazing Micromouse Competition» в 1979 году в Нью-Йорке. Из примерно 6000 первоначальных заявок на конкурс допустили 15 участников.
В 1980-х годах правила усложнили. Теперь робомышь должна была добраться до центра лабиринта, и понять это. На конкурс пришло 200 запросов, подано 100 заявок, но в финале было только 9 мышей. Sterling Mouse Ника Смита стала первой (и в том году единственной) микромышью, которая нашла центр и «поняла», что она это сделала. В 1985 году в Японии впервые прошли международные соревнования Micromouse. Первые шесть мест ожидаемо заняли японцы, и лишь седьмым был представитель Англии с мышью Enterprise.
Пример лабиринта
Если интересно, как развивались события дальше, можно посмотреть небольшую летопись (до 1992 года). Но если вкратце — к англичанам и японцам присоединились сингапурцы и канадцы, а соревнования стали проводиться в разных странах. В наше время робомыши популярны в Великобритании, США, Японии, Сингапуре, Индии, Южной Корее.
Что вообще за Micromouse такой
Мыши — это полностью автономные роботы, которые должны без посторонней помощи максимально быстро добраться из заданной точки в центральную часть лабиринта. Micromouse должна отслеживать, где она находится, обнаруживать стены во время исследования, составлять карту лабиринта и обнаруживать, что она достигла цели.
Micromouse
Модель 2015 года, победитель соревнований
Составление карты важно, ведь мышь может несколько раз пройти лабиринт, пока не найдёт оптимальный маршрут от начала до конца. И затем проходит его максимально быстро. Участникам не разрешается обновлять код своих робомышей после того, как демонстрируется схема лабиринта.
Вы могли бы подумать, что у роботизированной мыши не так много способов пройти лабиринт, но за свою почти 50-летнюю историю участники соревнований Micromouse неоднократно доказывали ошибочность этого предположения. Вот, например, свежее видео с соревнований:
Простое следование робомыши вдоль стены в первом соревновании 1977 года к 2023 году превратилось в увлекательное шоу. Изначально все роботы останавливались перед поворотом за угол, пока кто-то из участников не понял, что можно срезать углы под углом 45° и двигаться по диагонали, если робот не очень большой. Кратчайший путь не всегда самый быстрый, так как при прохождении поворотов теряется много скорости, поэтому иногда можно улучшить время, выбрав более длинный маршрут с меньшим количеством поворотов.
Обычные алгоритмы поиска оптимального маршрута используют вариации алгоритма Беллмана, алгоритма Дейкстры, алгоритма поиска A*, различных алгоритмов обхода дерева и обхода графов.
Большая скорость хороша только в том случае, если вы можете сохранить контроль, поэтому многие роботы теперь оснащены вентиляторами, которые прижимают их к поверхности лабиринта, увеличивая тягу. Это привело к скорости до 7 метров в секунду и перегрузки до 6G на поворотах.
Пример сложного японского лабиринта
Понятно, что на такой скорости даже пылинка может навредить миниатюрной робомыши, приведя к потере управления. Поэтому все участники аккуратно чистят колёса перед заездом. Многие победные заезды длятся менее 10 секунд, что требует от создателей робота множества экспериментов, позволяющих увеличить контролируемую скорость и снизить вес робомыши.
Красота Microhouse заключается в его доступности. Собрать робомышь самому — не самая сложная задача. Гораздо труднее научить робота проходить лабиринты. Но если эта тема зацепит, то оторваться будет трудно.
Спасибо за внимание!
Что ещё интересного есть в блоге Cloud4Y
→ Информационная безопасность и глупость: необычные примеры
→ NAS за шапку сухарей
→ Взлом Hyundai Tucson, часть 1, часть 2
→ Столетний язык программирования — какой он
→ 50 самых интересных клавиатур из частной коллекции
