Микромышиные бега — самая быстрая гонка по лабиринту [Veritasium]
[музыка] Это крошечная рыба, мышь проходит лабиринт всего за 6 секунд. Каждый год люди со всего мира участвуют в самой старой гонке робототехники. Цель проста: как можно быстрее пройти лабиринт. Второй пришел к финишу с отставанием 20 миллисекунд. Сейчас это очень жесткое соревнование. Кто-то посмотрел на моего робота и сказал: "Да ты спятил! Откуда столько напряжения? За что вы боретесь? Почёт, наверное". О-о [аплодисменты].
В 1952 году математик Клод Шеннон сконструировал электронную мышь, способную искать выход из лабиринта, и назвал ее Тесей. Сообразительность мышки обеспечивал встроенный в сам лабиринт простейший компьютер на основе телефонных реле. Мышь была просто магнитом на колесиках, которые притягивали к себе электромагниты, включаемые с помощью этих реле. Сейчас Тесей следует лабиринту методом проб и ошибок, найдя правильный путь, микромыш регистрирует информацию о нем в памяти.
В дальнейшем Тесей можно будет помещать в любую точку знакомого ему лабиринта, и он дойдет до конца, ни разу не сбившись с пути. Часто упоминает среди первых примеров машинного обучения. Один из директоров Google недавно заявил: "Тесей был главным вдохновением для развития". Спустя 25 лет издатели журнала института инженеров электротехники и электроники узнали о соревнованиях для электронных мышей или лемауз, электроника так оно называлось. Они пришли в восторг: "Неужели это были преемники Тесея?".
Но в процессе перевода стерлись некоторые детали: мыши оказались игрушками на батарейках, а не роботами, демонстрирующими разумное поведение. Но издатели не унывали и решили сами устроить соревнования, которые хотели. В 1977 институт объявил об удивительных микромышленных бегах. Записались больше 6.000 участников, это число быстро сокращалось: мало кому сопутствовал успех. Два года спустя до финала дошли всего 15 участников.
Но к этому моменту соревнования уже привлекли внимание публики, благодаря чему транслировались по всей стране в вечерних новостях. Идея, не зря показалась издателям интересной, новости о микромышах разошлись по свету. [музыка] [музыка] Я участвовал в японском турнире в прошлом году, там я выиграл в категории малых размеров. В этом году я усовершенствовал ту модель, которая в прошлый раз принесла мне победу. Даже те, кто уверенно лидирует в гонке, присмотритесь, когда они запускают своих мышей: они еле кнопки находят, потому что нервы просто зашкаливают.
Да, чтобы ни было: обычные скачки, автогонки или такие машины и бега, если в вас есть хоть чуточка духа соперничества, вам хочется победить. Похоже, у Цуномии Сан немного нервничает, как и обычные мыши: эти маленькие роботы должны бегать сами. Никакого подключения к интернету, GPS или дистанционного управления. Помогать, если они где-нибудь застрянут, тоже нельзя. Вычислительные мощности, моторчики, датчики, батарейки должны поместиться в корпус размером максимум 25 на 25 сантиметров.
На высоту робота ограничений нет, но перелезать или перелетать препятствия нельзя, и никакого топлива: ракетный двигатель, к сожалению, не поставить. [музыка] Лабиринт представляет собой квадрат, примерно 3 на 3 метра, разделенный на коридоры шириной всего 18 см. В 2009 году добавили еще одну категорию: малых размеров, составляет всего 9 см. Планировка лабиринта становится [музыка]. Соревнования большой тройки — японская, тайваньская и американская — обычно дают на изучение лабиринта 7 или 10 минут, и мыши могут пройти путь от старта до финиша только пять раз.
Если мышь слишком долго изучает лабиринт, будут штраф. Логично, большинство мышей следует одной стратегии: за первый заход они внимательно изучают лабиринты, ищут лучший путь к цели, стараясь не тратить слишком много времени. Остальные попытки уходят на то, чтобы как можно быстрее пройти уже известный путь. Может показаться, что пройти лабиринт не так уж сложно, но у робота всего несколько инфракрасных сенсоров вместо глаз, и изнутри лабиринт выглядит совсем не так понятно, как сверху.
Однако, чтобы пройти лабиринт, глаза не нужны: если вести рукой по одной стене, рано или поздно вы доберетесь до цели. В большинстве лабиринтов именно так и рассуждали некоторые участники самых ранних забегов. В первом же соревновании победила мышь, которая шла по лабиринту. После чего следующий вариант: изучить каждый закоулок. Оказавшись в тупике или петле, мышь может вернуться к последнему разветвлению и пойти в другую сторону.
Если робот повернул налево и это был неверный ход, он возвращается, идет направо. Это такой подход очень упорной мыши: она уверенно идет вперед до тех пор, пока есть хоть какой-то путь дальше. Такой способ назовем его поиском глубину. Рано или поздно приведет мышь к цели. Проблема в том, что путь у нее будет, скорее всего, не самый короткий. Робот возвращается только если возникает необходимость, так легко упустить отворот на более быстрый путь.
Есть другой похожий подход — поиск вширь. Он как раз позволяет найти самый короткий путь. На пересечении коридоров мышь сначала идет в одну сторону, а когда доходит до следующей развилки, возвращается назад и проверяет, куда бы повел альтернативный путь, и лишь потом идет дальше. Мышь изучает все доступные варианты, но для этого ей приходится несколько десятков раз проходить одни и те же участки.
Не быстрее ли будет просто обойти весь лабиринт? Идея не так уж плоха: дотошная мышка может изучить все 256 ячеек в лабиринте, заглянуть за каждый поворот и в каждый угол и точно установить самый популярный способ прохождения лабиринта. Отличается от всех перечисленных этот алгоритм, известен под названием заливка. Согласно ему мышка отправляется в лабиринт полный оптимизма, настолько, что во время первой попытки его изучить она считает, что стен нет вообще.
Она намечает самый короткий путь и направляется к цели. Естественно, потом она упирается в стену, которой нет на ее карте, отмечает препятствие и прокладывает новый кратчайший маршрут, бежит, обновляет маршрут, бежит, обновляет и так далее. Но все это время стремится к цели. По сути, микромышь на своей карте отмечает расстояние от каждой ячейки в лабиринте до своей цели и затем двигается по ним от большего числа к меньшему. Попадая в тупик, робот обновляет значение ячеек и продолжает следовать новым кратчайшим путем. Именно этот принцип следовать пути с наименьшим сопротивлением дал название алгоритму.
Представьте, мы как будто заливаем лабиринт и ориентируемся на самый быстрый поток. Достигнув цели, микромышь исключает все лишние участки и получает верный маршрут, но остается вероятность, что он не самый короткий. Возможно, мышь просто не нашла тот самый быстрый путь, который нужен для победы. Да, этот подход не гарантирует, что лучший путь получится найти с первой попытки, но так как мышам необходимо вернуться на старт перед следующим проходом, обратный путь можно использовать для поиска нового, может быть, более короткого пути через лабиринт. Таким образом, если робот ищет кратчайший маршрут и на пути к цели, и обратно, вполне вероятно, что он его найдет, а в ненужной части лабиринта даже не заглянет.
Получается, что для микромышей заливка — это разумный и практичный способ находить самый короткий путь в лабиринте. Едва стало понятно, что это возможно, лучшая стратегия едва стали доступны нужные для этого микроконтроллеры и сенсоры, некоторые решили, что будущее определилось окончательно и бесповоротно. Как писали в одной статье в конце 1980-х: "С соревнованиями проблема была решена, и никаких новых вопросов не появилось".
В 2017 на соревнованиях в Японии бронзовый и серебро заняли мыши, которые, обнаружив кратчайший путь к цели, прошли его за 7.4 секунды. Но красная комета, мышь, с которой выступала победила Масакцу Уцаномию, вела себя совсем по-другому: вот самый короткий путь к цели — им шли все роботы. А вот маршрут, по которому продвигалась Красная комета, оказался на 5.5 метров длиннее.
Ну вот в чем дело: для победы вам не нужен самый короткий путь. Вам нужен самый быстрый. Поисковой алгоритм красной кометы определил, на каком маршруте меньше поворотов, которые замедляют мышь. Получилось, что более длинный путь может привести к цели быстрее, и роба-мышь рискнула это проверить. Красная комета обошла соперников на 1.31 секунды.
Сейчас мыши-участники, а чистоту иногда поведение мышей сложно предсказать. В системе моей мыши "Бака" она застывает каждый раз, когда сохраняет маршрут в памяти. Она бегает по лабиринту уже 4 минуты, если "Бак" проявится, моему участию конец. Нельзя сказать, что микромыши — отработанный материал. Дело не только в программном обеспечении или в конструкции, а сразу и в том, и в другом — это задачка робототехники.
Красная комета победила не потому, что у нее был более совершенный алгоритм или моторчики побыстрее, вся прелесть заключалась в том, как её мозг и тело взаимодействовали между собой. Оказалось, что разобраться в лабиринте вообще не проблема, с этим никаких проблем не было. Главные вопросы: навигация и скорость. С каждым годом роботы становятся меньше, быстрее и легче. Пространство для доработки ещё много.
В Японии небольшая группа активистов конструирует мышей размером с четверг, они умещаются на монетку. Прошло 50 лет. [музыка] [аплодисменты] Уже не в первый раз какие-нибудь соревнования пытаются списать со счетов прыжки в высоту. С 1896 года были Олимпийским видом спорта: участники оттачивали разные техники. Но чем дальше, тем меньше это давало результата.
Но как только использование матов стало повсеместным, все изменилось. В 1968 году Дик Фосбери первым из олимпийских спортсменов после прыжка развернулся спиной вперед. Сейчас так делают почти все прыгуны, а назвали такой метод "фосбери флоп". Если бы микромышей правда забросили в 1980-х, то там бы не случились свои "фосбери флопы".
Два дополнения, которые в корне изменили принцип работы этих роботов — спорт, где участникам можно прицепить всё, что только захочешь, открыл для инноваций. Итак, случился довольно рано, технологии тут были ни при чем. Это был скорее нестандартный подход, а точнее нестандартный поворот. Раньше все мыши поварали вот так, всё изменилось, когда собрали Mighty 3.
Майти Маус 3 первым научилась срезать углы по диагонали. Вы это видите? Вот это да! Оказалось, что это гораздо удобнее, чем мы себе представляли. Это настолько классно, что теперь в лабиринтах часто делают коридоры по диагонали. Может попасться лабиринт, где это не надо, но в целом проходить диагонали — это плюс. Чтобы мыши ездили по диагонали, храму пришлось сделать менее 11 см для малых размеров, аж до 5 см. Также поменялись по и сенсоры.
Прямой коридор — это не сложно: расстояние от стены измеряет инфракрасные датчики, и главное — оставаться по центру. Но диагонали требуют совершенно нового алгоритма, который будет вести мышь, как будто у неё шоры на глазах. Обычно, когда двигаешься вдоль стены, её видно постоянно, и по расстоянию легко понять, если ты уходишь не туда. При движении по диагонали видно только, как стены на тебя набегают, а если хоть чуть-чуть сбиться с курса, задеть угол гораздо страшнее, чем проехать боком по стене до сих пор.
Но взамен, вместо рваного движения с резкими поворотами, мы получаем плавное и быстрое. [музыка] [аплодисменты] Почти любая современная микромышь сделана так, чтобы проходить углы по диагонали. Эта стратегия открыла новое поле возможностей. Примерно в то же время менялся подход к прохождению поворотов: вместо того, чтобы останавливаться каждый раз, мыши научились двигаться по дуге.
А как только к этому добавилось движение по диагонали, резко возросло количество возможных поворотов. Лабиринт перестал быть набором из прямых углов. С новыми возможностями маневров количество возможных маршрутов стало значительно больше, и результаты невероятно радовали. Там, где раньше мы наблюдали отрывистое движение с остановками, появились плавные изгибы. Полностью изменились конструкции: то, как роботы прокладывали себе путь.
Доступные технологии год за годом развивались: большие неповоротливые манипуляторы, которые раньше нащупывали стены, сменились миниатюрными инфракрасными сенсорами. Вместо шаговых двигателей заняли электромоторы с кодовыми датчиками. Двигатели постоянного тока миниатюрные, но дают больше энергии, так что есть смысл их использовать. Ещё нам понадобилось сервоуправление, обратная связь, чтобы двигатель делал то, что надо.
Лучше ориентироваться в пространстве помогли гироскопы: если носить такую штуку с собой, это как компас. За это на самом деле спасибо мобильным телефонам: технологии дают нам принципиально новые решения. Все повороты контролирует гироскоп, и не приходится каждый раз их высчитывать. Несмотря на эти усовершенствования, самой большой физической проблемой для микромышей десятки лет никто не занимался.
Можно заметить, что почти у каждого участника соревнований с собой есть скотч. Если вы знаете, что искать, то увидите скотч везде. Нужен он не для того, чтобы чинить роботов или приматывать отвалившиеся части, а для того, чтобы между раундами очищать колеса от пыли.
При таких скоростях, поворачивая на больших скоростях, необходимо, чтобы центростремительная сила ускоряла вас в направлении поворота. Чем быстрее едет машина, тем большая сила нужна, чтобы не сойти с курса. Единственное, что обеспечивает центростремительную силу на дороге — это трение, которое определяется двумя факторами: дорога выталкивает машину вверх (вертикальная сила) и этому умножаем на статический коэффициент трения — это трение шины и поверхности трассы.
Поэтому на поворотах гоночной трассы делают под наклоном: угол позволяет машинам поворачивать при меньшем трении, потому что часть вертикальной силы направлена внутрь и за счёт этого увеличивает необходимую центростремительную силу. Если расположить часть трассы на повороте под достаточно крутым уклоном, для поворота вообще трения не понадобится. Той части вертикальной силы, которая направлена внутрь, хватит, чтобы центростремительные силы удержали машину на трассе.
Микромыши мало чем отличаются в этом смысле, но никаких уклонов и поворотов у них нет. Роботы становились быстрее, к началу 2000 проблемы было уже не скорости, её контроль. Центр тяжести пришлось опускать ниже, а на поворотах замедляться, чтобы не врезаться в стену и не перевернуться. Практически как угодно, чтобы решить эту проблему.
Итак, второй "фосбери флоп" в мире микромышей — это доработки. Впервые появилась Мокома 08, и никто не воспринял её всерьез. Вы, вероятно, тоже ничего особенного сейчас не видите, ничего страшного. Но попробуйте прислушаться: это не микрорёв моторчика. Это пропеллер. Как мы помним, перелетать через стены нельзя, но никто не запрещал с помощью пропеллера прижать робота к полу, чтобы избежать скольжения.
Да! И вот он на моей памяти первым прикрутил к мыши пропеллер. Это был канальный вентилятор. Затея была в том, чтобы посильнее прижать мышь к поверхности, к ней ещё юбку добавили. Но это ничем особенно не помогло — уж простите, я так считаю. Суть в том, чтобы внутрь попадало как можно меньше воздуха. Это как с пылесосом: если закрыть трубу, нагрузка на мотор падает, обороты возрастают, а напряжение электроцепи уменьшается.
Но если воздуха слишком много, то напряжение возрастает. Это моторы квадрокоптеров очень прожорливые. При размерах микромышей, прижимного вентилятора, часто собранного из запчастей маленького дрона, достаточно, чтобы создать направленную в пять раз больше веса. Ого, хорошо впечатляет! А сколько весит сама мышка? Около 130 граммов. Если прислушаетесь, не знаю, возьмет ли ваш микрофон, но слышу: вот мотор замедляется из-за нагрузки.
При таком большом трении современные микромыши проходят повороты, создавая центростремительную силу до 6G, как болиды формулы-1. Вентиляторы улучшили контроль, что позволило расширить границы максимальной скорости. Гипотетически разгон у неё лучше, чем у Tesla Roadster, просто недолго. Они могут носиться по лабиринту со скоростью 7 метров в секунду, быстрее, чем бегает большинство людей. [аплодисменты] [музыка]
Каждая деталь, которая сейчас считается стандартной для любой микромыши, когда-то была экспериментальной. И возможно, не за горами очередной "фосбери флоп". Четырехколесная микромышь впервые победила в Японии в 1988 году, но затем количество колёс у победителей менялось, пока через 22 года в норму снова не вошли четыре колеса.
Сейчас есть конструкция, у которых и по 6, и по 8 колёс, иногда вместо обычных ставят все направленные или снабжают мышей компьютерным зрением. Кто знает, когда случится новая смена парадигмы. Отсчёт времени пребывания в лабиринте начинается только когда робот покидает стартовый квадрат. Так что, пока никаких штрафов он не получает.
Но микромышиной гонке главное - это не количество колёс, вентиляторы или движения по диагонали. Мне кажется, это идеальное сочетание всех главных навыков, которые нужны в робототехнике: инженерии, программировании, интегрируемых системах. Всё в маленькой штучке, которую можно собрать у себя в спальне, и никаких лабораторий вам не надо. А потом думаешь: "Я тоже так могу — это совсем не сложно".
И всё! Ловушка захлопнулась. Но если втянуться... [музыка] [музыка] Сначала была просто мышка, которой нужно было пройти лабиринт. Через 50 лет это несложное, казалось бы, задачка отлично напоминает о том, что несложных задач не бывает. [музыка] Переведено и озвучено студией Vertyder.