Новые алгоритмы демонстрируют, как рой простейших роботов можно заставить работать вместе, как единое целое
В лаборатории Технологического института Джорджии физики проводят эксперименты с роботами, выглядящими так, будто они были куплены в магазине «всё по $1». Роботы не могут передвигаться в пространстве или общаться друг с другом. В основном они машут ручонками, будто перевёрнутые на спину жуки.
Но если собрать множество этих устройств вместе, можно получить нечто из ничего: они толкаются, пихаются и сцепляются друг с другом. И в результате начинают работать как одно целое.
Исследователи изучают вопрос того, как контролировать такие системы, чтобы они функционировали похожим на рой пчёл или колонию муравьёв образом: каждый индивид действует на основе одинакового набора правил, но несколько индивидов, собравшись вместе, могут демонстрировать сложное поведение без центрального управления.
«Наш подход следующий: узнать, какова простейшая вычислительная модель, необходимая для достижения этих сложных задач? – говорит Дэйна Рэндол, специалист по информатике в Джорджтехе, один из лидеров проекта. – Мы ищем элегантность и простоту».
Рэндол, как программист, подходит к задаче с точки зрения алгоритмов: какой наиболее простой набор инструкций, на основе которых могут работать отдельные единицы роя, основанный на скудных данных, которые они могут собрать, неизбежно приведёт к сложному совместному поведению, необходимому для исследователей? В прошлом ноябре Рэндол с коллегами опубликовали алгоритм, гарантирующий, что идеальный рой из частиц сможет управляемо двигаться.
Работа с такими роботами, которых учёные прозвали «смартиклы» [smarticles; smart – умный, particle – частица / прим. перев.] – часть исследований в области возможности создания и полезности самоорганизующихся роботов. Среди других подобных примеров – роботы размером с каплю, разрабатывающиеся в Колорадском университете, рои "килоботов" из Гарвардского университета и сварманоиды из бельгийской лаборатории. Во многих случаях идея состоит в том, чтобы сымитировать проявляющееся в природе явление, например, высокоорганизованное движение децентрализованной колонии муравьёв или бессознательную самопрограммирующуюся сборку молекул ДНК.
«Мы знаем, чего хотим от це��ого роя, но чтобы запрограммировать его, необходимо разобраться, что должен делать каждый из агентов по отдельности, — сказал Мелвин Гаучи, исследователь из Гарварда, занимающийся групповой робототехникой. – Самое трудное находится в промежутке между двумя этими уровнями».
Дэйна Рэндол и Дэн Голдман в лаборатории Голдмана
Берегитесь лидеров
Дэниел Голдман – физик из Джорджтеха, руководящий экспериментом со смартиклами. В основном он интересуется физикой активных гранулированных материалов, способных менять свою форму. Среди его слайдов для конференций есть момент из фильма «Человек-паук 3», демонстрирующий зарождение сверхзлодея Песочный человек – отдельные песчинки, разбросанные по пустыне, собираются в форме человека. Смартиклы – это способ Голдмана испытывать активные гранулированные материалы в лаборатории.
«Они дают нам возможность использовать геометрию для управления свойствами материала. Если расфокусировать взгляд, можно представить, что эта куча смартиклов – реальный материал», — сказал Голдман.
У смартиклов есть короткие конечности, которыми они могут махать туда-сюда. Они реагируют на свет и звук разной частоты. Их можно запрограммировать менять скорость махания конечностями в ответ на действия других смартиклов, находящихся в непосредственной близости от них.
Смартиклы ��ожно заставить выполнить несколько действий: скомпоноваться (сбиться в кучу), расшириться (распределиться) и двигаться. Эти манёвры могут служить основой для выполнения более сложных функций, но и такие задачи довольно трудно решить, поскольку смартиклы не понимают, как они расположены по отношению ко всей группе.
Чтобы понять возможности и трудности, связанные с программированием сложного поведения, зарождающегося из простых частей, стоит иметь в виду, что именно известно каждому отдельному смартиклу. Не так уж и много. Он не может видеть, у него ограничена память, и всё, что он знает о других смартиклах, с которыми он должен согласовывать действия, он узнаёт, сталкиваясь со своими непосредственными соседями.
«Представьте себе человека, находящегося на рок-концерте с закрытыми глазами», — сказал Джошуа Дэймад, аспирант по информатике из Аризонского университета, работающий над проектом смартиклов.
Одной из стратегий может быть назначение лидера, управляющего роем – но такой подход уязвим. Если лидер пострадает, откажет весь рой. Другой – дать каждому роботу в рое свою уникальную задачу, но на крупных масштабах этот подход непрактичен. «Запрограммировать 1000 роботов по отдельности практически невозможно», — сказал Джеф Дасек, исследователь из Инженерного колледжа Олина и бывший член исследовательской группы самоорганизующихся систем в Гарварде, работавший над роями подводных роботов. «Но когда каждый член группы работает по одним и тем же правилам, ваш код не меняется, вне зависимости от того, 10 у вас роботов, 1000 или 10 000».
У алгоритма для роя есть два свойства. Во-первых, он распределённый, то есть, работает по отдельности на каждой из частиц системы (как каждый кочевой муравей выполняет простейший набор действий в зависимости от информации, полученной из окружающей среды). Во-вторых, он включает элемент случайности. Это значит, что если, допустим, кочевой муравей, почувствует наличие пяти других муравьёв поблизости, то с 20% вероятностью он передвинется левее, а с 80% — правее. Алгоритмы со случайностью отличаются от детерминистских алгоритмов, в которых каждый этап полностью определяется предыдущими.
Случайность может показаться ненужной для алгоритмов – ведь реализуя процедуру, вам обычно захочется добиться определённого результата. Но случайность обладает неожиданными преимуществами для эффективности, из-за чего алгоритмы со случайностью хорошо подходят для использования в роях.
Случайные гарантии
В 2015 Голдман и Рэндол обсуждали возможность найти правила, благодаря которым смартиклы смогли бы работать совместно, как единое целое. Рэндол поняла, что поведение, к которому Голдман хотел привести рой, очень похоже на поведение идеализированных систем частиц, изучаемых в информатике.
«И я сразу подумала: Я точно знаю, что нужно сделать», — сказала Рэндол.
Для Рэндол поведение смартиклов напомнило явление, моделируемое специалистами по информатике во многих других контекстах. Один из самых известных примеров – появление сегрегированных районов. В конце 1960-х экономист Томас Шеллинг захотел понять, как происходит сегрегация по районам в отсутствии некоей центральной силы, сортирующей людей по цвету кожи. Он представил гипотетического человека, разглядывающего своих соседей и решающего вопрос о переезде на основе того, сколько соседей выглядит так же, как он. Когда человек переезжал, Шеллинг перемещал его в случайное место поселения, где повторялся алгоритмический процесс наблюдения и принятия решения. Шеллинг обнаружил, что согласно его правилам, появление сегрегации жителей практически гарантировано, даже если некоторые люди предпочитают жить в разнородных районах.
Уильям Савой, аспирант в лаборатории Голдмана
Рэндал поняла, что смартиклы в своём рое напоминают людей в модели Шеллинга. В обоих случаях отдельные единицы должны принимать решение, не зная своего положения на глобальной схеме (они знают только то, что видят в непосредственной близости). В модели Шеллинга решения можно принимать с элементом случайности – если соседи отличаются от вас, то есть вероятность, что вы переедете, и есть вероятность, что останетесь.
В 2016-м Рэндол с коллегами опубликовали работу, где описали идеализированные частицы, живущие на решётке и решающие, остаться или подвинуться в зависимости от количества наблюдаемых вокруг частиц. Принимаемые решения были вероятностными – частицы каждый раз «бросали» взвешенный кубик для выбора. Рэндолл с соавторами показали, что если правильно назначить кубику веса, то можно гарантировать возникновение плотного роя (так же, как Шеллинг мог бы доказать, что если назначить терпимость к разнообразию жителям района на нужном уровне, то сегрегация обязательно появится). Подстраивая алгоритм, они также могли гарантировать, что рой частиц двигался бы в расширенном состоянии.
Случайность алгоритма помогает частицам в рое избегать застревания в локальных уплотнениях, когда множество изолированных подгрупп скапливаются вместе, но весь рой в целом не уплотнён. Случайность гарантирует, что при появлении небольших уплотнений некоторые единицы всё же решат пер��двинуться в другое место, и процесс будет идти, пока не будет достигнуто общее уплотнение. Чтобы избежать локальных уплотнений, нужна небольшая случайность; гораздо больше её требуется, чтобы перейти из глобально сжатого состояния в расширенное.
В реальный мир
Доказать, что частицы в теоретическом мире могут, выполняя простой алгоритм, достигать определённого поведения в рое – это одно. Реализовать алгоритм в дешёвых, подверженных отказам, реальных смартиклах, щёлкающих конечностями в коробке – совсем другое.
«Наши коллеги по теории придумывают, как программировать эти штуки, но мы пока находимся в самом начале пути, и не можем заявить, что эти схемы были перенесены напрямую», — сказал Голдман.
Одна из проблем заключалась в том, чтобы заставить смартиклы двигаться совместно. Сначала, когда исследователи заключали смартиклы в ограниченном пространстве, эта группа просто случайно дёргалась. Но однажды, когда физики наблюдали это хаотическое движение, у одного из смартиклов померла батарейка. Голдман с коллегами заметили, что рой неожиданно стал двигаться в направлении неподвижной единицы. Исследователи сообщили об этой неожиданной находке теоретикам, и те ухватились за этот намёк. Работа привела к созданию новой версии алгоритма, позволяющего идеализированному рою всегда двигаться в заданном направлении.
Понемногу эксперименты, идущие в компьютере, и физические опыты сближаются. Исследователи надеются в итоге теоретически доказать, что базовый алгоритм, реализованный распространённым методом в большом рое из небольших дешёвых роботов гарантированно приведёт к желаемому поведению роя.
«Мы хотели бы добиться того состояния, в котором мы бы не просто обнаруживали какое-то явление, когда умирает батарейка, — сказал Дэймад. – Мы хотим, чтобы это было что-то из разряда намеренных достижений».
