Вообрази, что разрабатываешь алгоритм, который должен управлять группой автономных роботов. Перед тобой стоит задача: они должны прочесать окрестности, разыскать все объекты определенного типа, а затем собрать находки в одной точке. Зачем? Можешь представить, что действие происходит на другой планете и на роботов возложена важная научная миссия.
Ты пытаешься понять, как поступили бы на месте роботов обычные люди — с руками, ногами и, возможно, в скафандрах. Если у них есть голова на плечах, они не возьмутся за работу, пока не станет ясно, кто, что и как должен делать. Во-первых, каждый участник поисковой группы должен понимать, куда возвращаться с добычей. Если не договориться о точке сбора заранее, то все разбредутся в разные стороны и толку не будет. Во-вторых, необходимо четко поделить зоны ответственности. В противном случае в некоторых местах побывает сразу несколько роботов, а кое-где, очень вероятно, ни одного.
Дальше труднее. Что делать, если одна из машин свалится в пропасть и пропадет, не доведя поиски до конца? Роботы должны самостоятельно понять, что план нарушен, а затем найти замену выбывшему из игры собрату. Получается, нужен механизм, при помощи которого они будут следить друг за другом и координировать действия во время операции. Поскольку непосредственное общение каждого с каждым годится только для малочисленных групп, придется строить иерархию. А это значит, что требуется план Б на случай неприятностей с одним из лидеров. Угодить в пропасть может и он.
Поверишь ли ты, что нужная программа умещается в шесть байт, полностью реализует все необходимые для решения поставленной задачи модели поведения роботов и предусматривает все частные случаи? Как такое возможно? Дело в том, что наши рассуждения начались с неверной посылки, когда мы взяли за основу алгоритма поведение людей. Люди — никудышный пример для подражания!
Зима близко
Первые исследователи, которые работали в области искусственного интеллекта, не сразу осознали, насколько сложная проблема перед ними стоит. Они пытались моделировать человеческое мышление, отталкиваясь от формальной логики, но обнаружили, что такой подход годится лишь для шахматных программ и автоматических решателей теорем. Он не работает без четких правил и понятных абстракций, а они в реальном мире — большой дефицит.
К восьмидесятым годам прошлого века стало ясно, что эта научная область зашла в тупик и света в конце тоннеля не видно. Энтузиазм, а за ним и финансирование стали иссякать. Сейчас этот период называют «зима искусственного интеллекта».
Наступающая «зима» вынудила специалистов по робототехнике задуматься о приоритетах. Автономные роботы невозможны без искусственного интеллекта, но кто сказал, что им нужен интеллект человеческого типа? Кто сказал, что сложное поведение требует суждений, анализа и понимания, не говоря уж о сознании? Существование примитивных животных, которые порой лишены не только мозга, но даже нервных узлов, доказывает обратное.
Возьмем, к примеру, простейшие одноклеточные микроорганизмы — амебы, относящиеся к виду Dictyostelium discoideum. Строение амеб не оставляет места для наивного антропоморфизма. Что бы эти существа ни делали, они определенно не думают — им просто нечем. У них нет памяти или сознания. Внутренности амеб представляют собой суп из органических молекул — не столько биология, сколько химия. Тем не менее диктиостелиумы демонстрируют на удивление сложное поведение.
В обычной ситуации они кормятся и размножаются так же, как другие разновидности одноклеточных. Но если для амеб наступают голодные времена, все становится гораздо интереснее. Когда еды почти не остается, они начинают стремиться друг к другу и сбиваться в группы. Десятки тысяч организмов, собравшихся в одной точке, образуют клеточный слизевик — своеобразного слизня, которого можно различить даже без микроскопа. Совместными усилиями амеб слизевик ползет вперед, пока не достигает подходящего места. Там он встает на хвост и распространяет споры.
Хакер #199. Как взломали SecuROM
Механизм, который стоит за этими процессами, куда проще, чем результат. Строительство слизевика начинается с безусловной реакции одиночных организмов на внешний раздражитель. С точки зрения программиста, это одна строчка «если… то»: если амеба испытывает голод, то выделять вещество под названием циклический аденозинмонофосфат и белки-гликопротеиды. Первое вынуждает других амеб направиться к источнику «запаха», а вторые делают поверхность организма липкой. Прибывающие амебы слипаются и образуют ядро будущего слизевика. Чем больше группа, тем интенсивнее «запах» и тем выше вероятность того, что остальные амебы направятся именно в их направлении.
Диктиостелиумы не планируют строительство слизевика. Они не координируют и не контролируют действия коллектива, если комок амеб можно обозначить этим словом. Они не осознают ни что происходит, ни где они находятся. От начала и до самого конца каждая амеба действует совершенно независимо от других, следуя крайне простым правилам. Тем не менее их примитивные реакции складываются в нечто более сложное, чем каждый элемент группы в отдельности.
Наступающая «зима искусственного интеллекта» подтолкнула специалистов по робототехнике присмотреться к поведению таких существ внимательнее. Идея о том, что группы роботов могут быть способны выполнять сложные задачи, не обладая точной моделью окружающей среды и не планируя свои действия, а лишь реагируя на стимулы, полностью противоречила классическим представлениям об искусственном интеллекте. Но тридцать лет назад это перестало быть проблемой — классический подход потерпел провал.
В конце восьмидесятых новое направление исследований получило название. Американский физик Джерардо Бени, который экспериментировал с группами роботов, предложил термин «роевой интеллект», который используют до сих пор.
Плоды коллективизации
«Реальность такова, что группу роботов, с которой мы имеем дело, нельзя назвать просто группой, — объясняет Бени в научной работе, опубликованной в 1989 году. — Она обладает определенными характеристиками, которые роднят ее с роями насекомых. Мы наблюдаем децентрализацию управления и отсутствие синхронизации. Отдельные роботы просты и (почти) идентичны. Кроме того, важную роль играет еще и размер группы, то есть количество ее участников».
Важнейшее свойство роевого интеллекта — самопроизвольное возникновение коллективного поведения, не свойственного отдельным элементам роя. В амеб-диктиостелиумов не заложена программа строительства слизевика. Отдельные муравьи не знают, как организовать транспортировку тяжелых грузов. Отдельные пчелы не умеют отражать атаки гигантских шершней. Алгоритмы их действий куда проще и зачастую не требуют даже коммуникации. Однако действия всего роя, складывающиеся из примитивных действий его участников, куда сложнее и позволяют решать такие задачи, которые не под силу одиночным особям.
Классический пример коллективного поведения — образование и движение стай птиц. С человеческой точки зрения такая слаженность невозможна без иерархии. Если есть стая, значит, должен быть вожак, так ведь? Оказывается, нет. В 1986 году специалист по компьютерной графике Крейг Рейнольдс продемонстрировал, что организованное движение стаи — это неожиданно сложный результат набора простых правил, которым независимо друг от друга следуют образующие ее птицы.
Рейнольдс разработал компьютерную модель, где в трехмерном пространстве движутся однотипные компьютерные агенты — так называемые боиды. Каждый боид следует трем принципам. Во-первых, он старается держать дистанцию между собой и другими боидами. Во-вторых, боид старается двигаться примерно туда же, куда направляются его соседи. В-третьих, его влечет туда, где других боидов больше всего (но лишь до тех пор, пока это не вступает в противоречие с другими принципами).
Этих трех принципов достаточно, чтобы группа боидов сбилась в стаю исключительно натурального вида — без централизованного управления, иерархии и даже коммуникации. Стаи прекрасно работают и без этого. Более того, без этого они работают лучше. Децентрализованный алгоритм образования стаи с равной легкостью справляется с любым количеством боидов — и с очень маленьким, и с очень большим. Стаю невозможно разрушить, удалив одного из боидов, — отряд не заметит потери бойца и спокойно полетит дальше. Вдобавок стая быстро реагирует на стимулы, о существовании которых известно лишь небольшому числу участников.
Многие из этих преимуществ отмечены уже в той статье Бени, которая вводит термин «роевой интеллект». Он пишет, что роевые роботы просты, взаимозаменяемы и, в принципе, могут быть даже одноразовыми. Почему бы и нет? Ни один элемент роя не может считаться незаменимым. Выбывающих роботов тут же заменяют другие. Такая избыточность придает рою впечатляющую устойчивость к разрушительным внешним воздействиям. Многие авторы также отмечают гибкость и масштабируемость роя. Уменьшаясь и увеличиваясь в размерах, он может адаптироваться к самым различным задачам.
Тупой и еще тупее
Задача про поиск и сбор объектов, с которой мы начали, позаимствована из работы, опубликованной специалистами по робототехнике из Шеффилдского университета. Их, правда, волновали вовсе не далекие планеты, а более практический вопрос: до какой степени можно упростить и удешевить роевых роботов. Интерес понятен: строительство роботов — это в принципе недешевое занятие. Если же роботов должно быть много (а их должно быть много, иначе какой это рой?), самой важной научной миссией становится экономия.
Ученые из Шеффилда взялись за эксперименты. Можно ли обойтись без коммуникации между отдельными элементами роя? Пример боидов доказывает, что можно. Значит, роботы останутся без средств связи. Под нож идут и лишние датчики — уцелел единственный оптический сенсор на носу. Что еще не нужно? Судя по тем же амебам, не нужны мозги. Что ж, можно попробовать оставить робота без бортового компьютера.
Вот как будет работать такая машина. Оптический сенсор определяет цвет объектов, которые находятся прямо перед ним. Роботы и их потенциальная добыча окрашены по-разному, поэтому значения на выходе сенсора не требуют интерпретации. Красный — впереди добыча. Зеленый — другой робот. Белый — стены помещения, где проходит эксперимент. Каждому из этих трех цветов соответствует пара числовых значений, которые определяют скорость и направление вращения правого и левого колеса робота. Чтобы реализовать такую связь, не нужны ни вычисления, ни логические операции, ни запоминающие устройства.
Три пары скоростей — это и есть программа, целиком и полностью описывающая поведение шеффилдских роботов, те самые шесть байт, о которых мы говорили. Чтобы подобрать оптимальный набор параметров, вызывающий нужное поведение, разработчики использовали эволюционный алгоритм. Для этого они разработали компьютерную модель арены, груза и самих роботов и начали экспериментировать. Первые итерации заполняли список скоростей случайными числами. Алгоритм тестировал набор за набором и отбирал те, которым удавалось продвинуться дальше других. Их брали в качестве базы для следующего поколения — и повторяли этот процесс снова. За несколько десятков тысяч итераций алгоритм находил такую шестерку параметров, которая позволяла роботам не просто справляться с поставленной перед ними задачей, но и делать это быстро и слаженно.
Пришло время проверить, как такой подход работает на практике. Тут авторы исследования немного сжульничали: они не стали разрабатывать сверхдешевые безмозглые машины собственной конструкции, а воспользовались роботами e-puck, которых часто используют для моделирования группового поведения.
E-puck представляет собой двухколесную «шайбу» размером 7,4 на 5,5 см. Каждое колесо приводится в движение отдельным шаговым моторчиком, который подчиняется командам микроконтроллера со встроенной оперативной памятью объемом 8 Кбайт и 144 Кбайт флеша. Кроме них, в e-puck скрывается неплохая коллекция датчиков, а также цветная видеокамера — не очень качественная, но вполне работоспособная. Итоговая стоимость робота может превышать тысячу долларов. Иными словами, не вполне то, что нужно, но сгодится на роль прототипа.
Большинство датчиков не потребовалось. Видеокамера заменила оптический сенсор; по правде говоря, это даже усложнило дело: пришлось разрабатывать подпрограмму, которая ужимает картинку до горстки пикселей, а затем определяет, какой цвет преобладает. Другая подпрограмма имитировала безусловную реакцию на замеченный цвет, переключая скорости. Осталось оклеить «шайбы» зеленой бумагой и рассеять по арене красные цилиндры из пенопласта — добычу. Можно запускать.
Вот тактика роя, которую описывают пресловутые шесть байт. Сначала роботы расползаются в стороны, высматривая красные цилиндры. Найдя их, они образуют большое кольцо и начинают двигаться навстречу друг другу, толкая цилиндры перед собой. Если в стороне осталась незамеченная добыча, это не беда. Рано или поздно роботы отрываются от своего хоровода и окружают потерянные объекты. Минут через пять все будет сделано: все цилиндры собраны в одной точке, а роботы теснятся рядом с ними.
Изменение числа роботов не влияет на действенность такого метода. Если их мало, они, возможно, провозятся дольше, но результат будет тем же. Более того, в процессе экспериментов выяснилось, что даже умение различать других роботов — это роскошь. Можно обойтись и без этого. Результат не меняется, если оптический сенсор путает других роботов с добычей или же просто не видит их.
Роевая подготовка
Исследователями из Гарварда двигал тот же интерес к дешевизне и миниатюризации, но они, в отличие от коллег из Шеффилда, уже перешли от прототипов к делу. Недавно специалисты из группы по исследованиям самоорганизующихся систем при Гарвардском университете продемонстрировали рой, состоящий из 1024 элементов. Стоимость компонентов для сборки отдельных роботов, которых окрестили «килоботами», составляет всего 14 долларов.
Несмотря на миниатюрность и фантастическую дешевизну, килоботам не свойственен шеффилдский аскетизм. Их создатели исходили из того, что машинкам понадобятся «мозги», способные потянуть SDASH — уже существующий алгоритм управления коллективными роботами. Кроме того, они должны уметь двигаться вперед, разворачиваться, общаться с ближайшими соседями и оценивать, на каком расстоянии они находятся. Все эти требования также вытекают из решения использовать SDASH. Помимо этого, разработчики сочли необходимым сделать так, чтобы килоботы могли оценивать освещенность и каким-то образом демонстрировали свое внутреннее состояние (это серьезно упростит отладку).
В итоге получилось вот что. Сердцем каждого килобота стал хорошо знакомый самодельщикам микроконтроллер ATmega328 — именно он используется в Arduino Uno. Процессор работает с тактовой частотой 8 МГц и снабжен 32 Кбайт оперативной памяти. У робота нет ни колес, ни ножек: машинка ползает по гладкой поверхности со скоростью до сантиметра в секунду при помощи пары вибромоторов. На пузе килобота закреплены светодиоды и фотодиоды, передающие и принимающие световые сигналы в инфракрасном диапазоне. Они нужны для коммуникации с соседями. Кроме того, яркость замеченных ИК-импульсов позволяет с точностью до миллиметра оценить, далеко ли те находятся.
В августе 2014 года создатели килоботов показали, на что способны эти малыши. Роботы научились по команде выстраиваться, образуя собой силуэт заложенного в них изображения — без планирования, иерархии и централизованного управления. Все, что для этого нужно, — поддерживать три модели поведения. Первая: пограничное движение. Килоботы должны по возможности перемещаться вдоль края группы, никогда не отрываясь от коллектива. Вторая: градиентное построение. Килобот может испускать особый сигнал, который подхватят и передадут по цепочке его соседи. Самое первое сообщение имеет нулевое значение, но соседи увеличат его на единицу, на следующем шаге оно станет равно двум и так далее. В результате каждый узнает, далеко ли источник сигнала. Наконец, третья и последняя: локализация. Роботы оценивают расстояния до ближайших соседей и используют их как точки отсчета в локальной системе координат.
Что получается в итоге, проще показать, чем описать словами.
Дальний прицел
Если спросить у специалистов по робототехнике, зачем все это может понадобиться, чаще всего звучат примеры военно-полевого характера. И это можно понять. С одной стороны, у армии есть деньги, и она готова их тратить, не ожидая немедленного результата. DARPA и другие американские агентства подобного толка играли и продолжают играть важную роль в финансировании исследований в области искусственного интеллекта. С другой стороны, многие преимущества роевых роботов по-настоящему заметны лишь в самой недружелюбной среде — а у военных таких сред хоть отбавляй.
Военные аналитики давно обсуждают, какие возможности откроет развитие роевой робототехники. Косяки автономных подводных аппаратов будут выстраивать разведывательные сети в глубинах океана и помогать выслеживать вражеские субмарины. «Умные» мины станут автоматически перераспределяться, чтобы в минном поле не вышло прорехи, через которую просочится неприятель. Возможен, впрочем, и альтернативный вариант: гурьба асоциальных роботов, старающихся держаться подальше друг от друга, поможет избавиться от мин.
Нетрудно придумать и гражданские применения. Они, пожалуй, кажутся даже более реалистичными. Автономным автомобилям, которые разрабатывают в Google и других компаниях, было бы неплохо поучиться у общественных животных более эффективным моделям совместных действий. У людей в этой области учиться нечему: стокилометровая пробка — это вершина коллективного поведения автомобилиста. Еще одной областью применения интеллекта роя могут стать интернет вещей и миниатюрные сенсорные сети. «Умным» устройствам будущего по определению придется обходиться без внимания человека, так почему бы не делать это сообща?
Вопрос лишь в том, когда это произойдет. Компьютерные специалисты задумались о роевом мышлении тридцать лет назад, но исследования, которые они ведут, трудно назвать даже первыми шагами — речь идет скорее о планировании этих первых шагов. А раз так, нам лучше набраться терпения.
