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