Роевые алгоритмы. 
Коллективное поведение роботов. 
Желаемое и действительное

Роевые алгоритмы и методы зачастую относят к методам т.н. роевого интеллекта. Термин «роевой интеллект» (Swarm intelligence) был введен Х. Бени и В. Цзином в 1989 г. в контексте предложенной ими системы т.н. клеточных роботов. Задачей роевого интеллекта (РИ) является изучение и описание коллективного поведения децентрализованной самоорганизующейся системы, при этом методы РИ рассматривается прежде всего как некие специфические механизмы поисковой оптимизации. Большинство алгоритмов РИ относятся к классу метаэвристик.

Системы РИ состоят из множества агентов (многоагентная система), локально взаимодействующих между собой и с окружающей средой. Сами агенты обычно довольно просты, но все вместе, локально взаимодействуя, создают так называемый роевой интеллект. Примером в природе может служить колония муравьев, рой пчел, стая птиц, рыб и т. д.

Ниже представлен перечень некоторых алгоритмов РИ, названия которых хорошо отражают суть подхода к решению задач:

Муравьиный алгоритм (Ant colony optimization).

Метод роя частиц (Particle swarm optimization).

Пчелиный алгоритм (Bees algorithm).

Оптимизация передвижением бактерий (Bacterial foraging optimization).

Стохастический диффузионный поиск (Stochastic diffusion search).

Алгоритм гравитационного поиска (Gravitational search algorithm).

Алгоритм капель воды (Intelligent Water Drops algorithm).

Светляковый алгоритм (Firefly algorithm).

Характерно, что значительная часть роевых алгоритмов посвящена реализации моделей стайного поведения, и прежде всего — стайному движению. В природе стайное поведение животных эволюционно выгодно, поэтому многие виды живых организмов содержат гены роения.

Модели движения Правила передвижения роевых животных относительно просты. Эти правила позволяют множеству относительно простых элементов формировать «коллективный мозг» способный принимать решения и заставлять двигаться стаю подобно единому организму. При этом зачастую эти правила применимы и к действиям толпы людей [Инстинкт толпы, 2007].

Макромодели. Для описания движения больших масс роевых организмов вполне подходящим оказывается математический аппарат гидродинамики. По сути дела, речь идет о статистических макромоделях.

Бродячие муравьи очень быстро реагируют на запахи следов их ближайших соседей. Стоит впереди идущим муравьям приступить к формированию настилов и пешеходных дорожек, как идущие следом мгновенно подхватывают инициативу и выстилают дорожку, по которой бегут остальные. Если плотность муравьев становится слишком высокой, это служит сигналом к формированию множества мостов, дорог и переулков из тел скопившихся муравьев, чтобы другие разбежались по ним в разные стороны, не скучиваясь.

Муравьи ведут себя так, чтобы обеспечить рою максимальную скорость передвижения.

Движение саранчи. Обычно насекомые охотятся самостоятельно, но иногда молодая саранча сбивается в огромные тучи, насчитывающие миллионы особей. Когда плотность саранчи превышает некоторый пороговый уровень, насекомые внезапно начинают двигаться вместе, выравнивая движение по своему соседу.

Движение сверчков. Известны виды сверчков (например, т.н. мормонские сверчки), которые обычно живут обособленно, но иногда они собираются миллионными роями и вытягиваются в многокилометровые полосы (длиной до семи километров). Механизм образования таких протяженных полос достаточно прост. Когда мормонские сверчки не могут найти достаточно пищи, они становятся каннибалами. Каждые 17 секунд сверчки пробуют напасть на других индивидуумов своего рода. Если какой-то сверчок не убегает, он наверняка будет съеден сородичами. Поэтому сверчки и вытягиваются в длинные стаи: тот кто впереди, убегает, чтобы не быть съеденным преследующими его собратьями.

Общие механизмы роения. Рой из множества животных можно рассматривать как отдельную единицу. Действительно, стая рыб движется как одно целое. Стая птиц также движется благодаря нескольким лидерам, при этом остальные особи в стае следуют за лидерами. Схожие механизмы действуют и в человеческом социуме: движение общества определяется направлением, задаваемом несколькими лидерами.

Толпа людей [Инстинкт толпы, 2007]. Йеном Д. Казиным (Iain D. Couzin, Оксфордский университет) был проведен ряд достаточно простых экспериментов, в которых изучались модели прохождения потока информации через толпу людей. Поведение испытуемых, испытывающих две противоречащие потребности — оставаться с группой или двигаться в индивидуальном направлении — явным образом определялось поведением лидеров. В отсутствии информации о правилах действий других игроков испытуемые совершали действия, характерные для стайного движения — следования за большинством.

Итак, основой механизма является подражательное поведение, а движущей силой — действия лидеров.

Другим классом моделей являются формальные математические методы, описывающие локальное поведение членов коллективов (стай, роев).

Формальные методы. Речь идет о достаточно хорошо известных и проработанных методах и алгоритмах.

Говоря о моделях движения объектов, выделяются следующие базовые правила (алгоритмы), которым должны следовать эти объекты:

движение в направлении цели;

движение в направлении центра масс своих соседей;

поддержка минимально допустимого расстояния друг между другом и препятствиями.

Хорошо проработаны различного рода алгоритмы обхода препятствий и уклонения от столкновений, алгоритмы, учитывающие такие взаимоисключающие тенденции, как «отталкивание» и «притяжение» особей в стае и т. п., см., например, [Павловский и др., 2002].

Иногда даже считается, что подобные модели поведения стаи (роя, толпы) можно применить не только к движению живых существ. Правилам коллективного движения, подобным движению рыб или саранчи, подчинена работа мозговых клеток; человек принимают решение на основе множества коллективных сигналов и проч.

В целом же следует отметить, что подобного рода модели — это лишь реализация неких частных механизмов. Эти модели не претендуют, разумеется, на объяснение природы стайного поведение, предпосылки его появления или некие глубокие обобщения.

Тем не менее, на практике эти модели вполне применимы для решения частных технических задач. Иллюстрацией этому может служить, например, робот EPORO фирмы Nissan ([Nissan, 2009].

Робот EPORO. Коллектив роботов имитирует поведенческие модели стаи рыб, избегая препятствий и столкновений друг с другом и способных двигаться целенаправленно. Исследователи утверждают, что это — первая такого рода разработка в мире.

Несколько ранее, в 2008 г. той же формой был представлен робот BR23C, отличавшийся «зрением шмеля». EPORO — это развитие той же концепции «заимствования» у природы. Как BR23C, так и EPORO решают задачу движения без столкновений («инстинктивная навигация»: выявление и обход препятствий).

Как и рыбы, роботы EPORO имеют специальный сенсор — т.н. «боковую линию», роль которой играет лазерный дальномер. У рыб боковая линия — это чувствительный орган, воспринимающий движение и вибрации окружающей воды и используемый для ориентации.

Основная цель этих исследований — создание безопасных автомобилей (сам робот EPORO — это модель: высота — 60 сантиметров, вес — 13 кг.).

Разработанные методы должны позволить роботам соответствовать «трём правилам поведения рыб» :

изменять направление движения без столкновений с другими;

" путешествовать" бок о бок с остальными, сохраняя определённую дистанцию и скорость;

уметь безопасно сближаться.

а) б) Рис. 8. а) Робот EPORO. Внизу показаны варианты перегруппировки роботов на манер рыбьей стаи; б) предшественник EPORO — робот BR23C

Пример роевого алгоритма. И, наконец, приведем пример типичного роевого алгоритма — т.н. муравьиного алгоритма. Идея алгоритма — моделирование поведения муравьёв, связанного с их способностью быстро находить кратчайший путь от муравейника к источнику пищи и адаптироваться к изменяющимся условиям, находя новый кратчайший путь. Предполагается, что при своём движении муравей метит путь феромоном, и эта информация используется другими муравьями для выбора пути (хотя одно это утверждение уже вызывает массу вопросов). Это элементарное правило поведения и определяет способность муравьёв находить новый путь, если старый оказывается недоступным [МакКоннелл, 2004].

Пусть на муравьиной дороге возникает преграда. В этом случае необходимо определение нового (оптимального) пути. Дойдя до преграды, муравьи с равной вероятностью будут обходить её справа и слева. Те муравьи, которые случайно выберут кратчайший путь, будут быстрее его проходить, и за несколько передвижений он будет более обогащён феромоном. Поскольку движение муравьёв определяется концентрацией феромона, то следующие будут предпочитать именно этот путь, продолжая обогащать его феромоном до тех пор, пока этот путь по какой-либо причине не станет недоступен, см. рис. 9.

Рис. 9. Реакция на появление препятствия

Таким образом, будут искаться необходимые пути, при этом моделирование испарения феромона будет гарантировать, что найденное локальное оптимальное решение не будет единственным. Обобщённый муравьиный алгоритм поиска на графе представим в следующем виде ([Штовба, 2003]):

Цикл, пока не выполнены условия выхода:

Создание муравьёв (размещение на графе) Поиск решения (переход в следующую точку). Вероятность перехода из вершины i в вершину j зависит от уровня феромона в этой точке.

Обновление уровня феромона в точке (i, j). Уровень феромона может быть обновлен так:

.

где — интенсивность испарения, L_k(t) — цена текущего решения для k-го муравья, Q — цена оптимального решения, т. е. Q/L_k — феромон, откладываемый kм муравьём, использующим ребро (i, j).

Дополнительные действия (например, локальный поиск).

КонецЦикла

Проект MARS. Пожалуй, одним из первых реальных проектов, реализующих групповое поведение роботов, является MARS (Multiple Autonomous Robots), США, Пенсильванский университет.

Начало работ, судя по публикациям, относится к 2000 г. В качестве основы выбрана четырехколесная платформа Clodbuster.

Рис. 10. Робот проекта MARS

Проект был посвящен отработке методов ориентации групп мобильных автономных роботов с использованием правил ближайшего соседства. В основу этих правил положена теория связанных систем. Суть метода заключается в том, что роботы определяют свои действия по действиям, выполняемым соседями. Например, если в такой группе есть ведущий, который движется по запланированной траектории, то все остальные роботы повторяют его движения.

Ресурс проекта находится по адресу http://www.cis.upenn.edu/mars/site/platforms.htm.

(Примечание. Автору не удалось выяснить, что скрывается под термином «Теория связанных систем». Наиболее внятное упоминание об этой теории было найдено в сборнике «Успехи физических наук» за 1935 г. Кроме того, часто название этой теории встречается совместно с т.н. «Теорией биосинхронизма», что совсем повергает автора в уныние.).

Замечания к роевым и стайным методам Здесь необходимо сделать два замечания, первое из которых касается терминологии.

Стая и коллектив. Следует различать понятия коллективного и стайного управления. Коллективное управление подразумевает, что объекты, входящие в группу, имеют возможность обмениваться друг с другом информацией. В т.ч. — знают о целях и задачах, имеют сведения о составе коллектива и т. д.

Стайное управление предполагает, что члены группы не имеют, вообще говоря, информационной связи с другими объектами, могут не знать состава и характеристик прочих членов группы.

Условно различие между стаей и коллективом можно изобразить так:

Задача подражательного поведения. На самом деле, это весьма непростая задача. Реализация принципа «делай, как остальные» далеко не всегда сводится к правилам «ближайшего соседства». Это, скорее, управление на сложном поведенческом уровне.

Дело в том, что для реализации подражания неизбежно возникают следующие задачи:

Распознавание «своих», т. е. объектов для подражания.

Определение действий «своих», которым следует подражать. Иными словами, робот должен знать, что делает его окружение, т. е. распознать их действия.

Выполнение такого же действия. Здесь речь идет даже не столько о реализации действия, сколько о реализации поведенческого акта.

Таким образом, принцип «делай, как остальные» превращается в принцип «веди себя так же». Например, идти в том же направлении, что и прочие, отработать защитное поведение, поиск пищи и т. п. Особенно явно это видно у тех же муравьев. Подражательное поведение представляет собой крайне сложные комплексы действий — перенос пищи (в т.ч. — согласованные действия по транспортировке тяжелых грузов), строительство, уход, оборонительные действия и проч. Иными словами, речь идет о том, что подражательность означает запуск больших, сложных поведенческих (не только моторных) программ.

И последнее. Типичный пример стайного поведения группы роботов так или иначе сводится к следующему: «Предположим, что каждый робот может выполнять одну из двух работ и при этом может менять одну на другую. Первоначально роботы выбирают себе работу произвольно. Периодически, обмениваясь информацией с ближайшими соседями, роботы принимают решение о продолжении выполнения выбранной ими работы или о ее изменении. Если большинство ближайших соседей выполняют ту же работу, что и данный робот, то робот продолжает ее выполнять, иначе — меняет работу». А далее следуют какие-нибудь выводы, обобщения и проч. Интересно, что автоматные модели 60-х гг. оказываются гораздо глубже, интереснее и разнообразнее. Сравните, например, приведенную постановку с решением задачи о поливе участков [Варшавский и др., 1984].