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

Размещено на http://www.allbest.ru/

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

Карпов В.Э.

Предисловие

Настоящая работа является «расширенной» редакцией статьи [Карпов, 2011]. Автор счел излишним менять удачное, на его взгляд, название. Равно как и «перетасовывать» текст для того, чтобы получилась формально другая статья. Не будучи скованным страничными ограничениями формата публикации, сюда добавлены некоторые дополнительные материалы, иллюстрации и рассуждения.

1. Введение

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

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

Итак, образование сложной системы, состоящей из простых составляющих (своего рода диалектический переход количества в качество, реализация синергетического подхода, появление эмерджентности - системного эффекта, - и проч., проч.), все это безусловно приводит (должно привести) к созданию систем, обладающих следующими важнейшими особенностями:

повышение надежности (утрата части членов коллектива не влияет на работоспособность всей системы в целом).

гибкость (способность системы к реконфигурации).

потенциальная возможность развития и усложнения решаемых задач путем наращивания мощности коллектива.

Современные приложения использования коллективного поведение роботов (физических, не программных) весьма многогранны:

командная работа роботов, совместно выполняющих диагностику труднодоступных объектов,

мониторинг окружающей среды,

коллективное решение задач роботами-спасателями,

разведка и рекогносцировка (для беспилотных летательных аппаратов, роботов военного назначения),

охранные функции, патрулирование,

и т.д.

Особенно важно коллективное взаимодействие роботов тогда, когда мы имеем дело с мини- и микро-роботами. Будучи крайне ограниченными в своих возможностях, эти роботы способны решить поставленную задачу лишь при их массовом применении. Примером такого применения микророботов может служить так называемая «интеллектуальная (умная) пыль», когда с самолета сбрасывается «туча» микророботов, каждый из которых должен выполнять некоторые простейшие функции, например, сбора информации о покрываемой территории или поражения объектов противника.

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

Непредсказуемая динамика внешней среды вплоть до сознательного противодействия.

Неполнота и противоречивость знаний роботов (агентов) о состоянии внешней среды и о других участниках.

Многообразие вариантов путей достижения цели, структур коллектива, распределения ролей и т.д.

Распределенный и динамический характер планирования действий коллектива.

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

Прочие технические проблемы (архитектура сети, протоколы, операционные средства и т.д.).

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

2. Некоторые примеры систем

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

Вернемся, однако, к примерам. Начнем с исследовательских проектов.

Проект I-SWARM. В Германии (Университет Карлсруэ) разрабатываются микророботы с "коллективным мышлением". Разработка финансируется Европейским союзом. Пока роботы умеют только узнавать друг друга и придерживаться своего сообщества. По данным на 2010 г. в рамках проекта I-SWARM создано около 100 механических особей размерами чуть более 1 кв. см, часть из них предназначена для отработки механизмов коммуникации между собой. Это - мультиагентные сообщества роботов.

Multi Robot Systems. Университет Алберты в Эдмонтоне, США. Исследования коллективного поведения роботов. Грант на пять лет в размере $39,000 в год. Разработка систем из нескольких роботов (Multi Robot Systems (MRS)). Проект посвящен задачам коллективного принятия решений.

Проект SwarmBot. Американская компания iRobot (производитель, кстати, автоматизированных пылесосов), занята разработкой небольших роботов, способных сообща выполнять определенные действия. Ожидается, что роботы SwarmBot смогут объединяться в группы численностью до десяти тысяч и выполнять такие задачи, как, например, поиск мин, исследование неизвестных территорий (в том числе на других планетах), обнаружение вредных веществ и пр. Робот SwarmBot имеет форму куба с длиной ребра около 12,5 см. и построен на базе 32-разрядного микропроцессора. Для навигации в пространстве и взаимодействия с другими роботами применяются инфракрасные датчики. Коллективная работа всей "стаи" роботов определяется в соответствии с неким набором правил группового поведения.

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

Наиболее интенсивно подобного рода работы проводятся по линии DARPA, причем уже давно. Речь идет о таких программах, как "Распределенные робототехнические системы" (2000 г.), "Программное обеспечение для распределенных робототехнических систем" (Software for Distributed Robotics (SDR)), "Программное обеспечение автономных мобильных роботов" (Mobile Autonomous Robot Software (MARS)) и проч.

Проект DARPA-2003. В рамках проекта был создан отряд из 120 роботов. Основная задача проекта - реализация коллективного (или распределенного) решения тактических и разведывательных задач. Проект осуществлялся американской компанией Icosystems, специализирующейся на разработке программ имитации поведения живых организмов. При этом для координации действий отдельных роботов были использованы относительно простые правила поведения, основанные на локальном взаимодействии роботов. Сами роботы построены компанией I-Robot.

Проект Centibots. Пожалуй, это один из первых реальных проектов, реализующий технологии, которые позволяют организовать взаимодействие и коллективное целенаправленное поведение большого числа автономных роботов. Первая демонстрация произошла еще в 2004 году, в Сиэтле в Центре компьютерных наук и инжиниринга Пола Алена (Университет Вашингтона). Был поставлен опыт коллективной рекогносцировки помещений группой самодвижущихся роботов. Centibots - это небольшие роботы, способные работать и как единый организм, и в одиночку. Их цель - изучить закрытое помещение, составить его план и выполнить какую-нибудь задачу. У роботов нет централизованной системы управления. В алгоритм действий роботов заложены принципы "самостоятельности и инициативности", они периодически взаимодействуют между собой и в зависимости от обстоятельств автоматически перераспределяют роли.

Артиллерийская система NLOS-LS (2010 г). Корпорации Lockheed Martin и Raytheon создают артиллерийскую систему нового поколения NLOS-LS. Заряды смогут объединяться в воздухе в интеллектуальную сеть и с максимальной эффективностью поражать объекты противника, расположенные вне зоны прямой видимости. Для наведения на цель "умные" снаряды будут использовать лазерные радары и бортовое ПО распознавания. Они способны находиться в воздухе 30 минут, преодолевая за это время до 70 км. в поисках целей, и также могут использоваться как разведывательный инструмент для сбора сведений о противнике. На разработку проекта Пентагон выделил $1,1 млрд.

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

Открытый проект SwarmRobot. Проект (его ресурс - swarmrobot.org) посвящен созданию минироботов (с линейным размерами до 3 см), которые могут организовывать масштабируемые коллективы из десятков и сотен роботов (рис.1, а). Предполагается, что создаваемая элементная база позволит реализовать различного рода эффекты самоорганизации в больших коллективах.

Проект Swarmanoid. Брюссельский свободный университет (Universite Libre de Bruxelles). Основная задача проекта - исследование поведения неоднородных коллективов роботов. Авторы проекта считают, что объединение нескольких различных роботов в группы позволит расширить возможности их использования. В частности, был реализована задача, в которой коллектив из колесных роботов, летающего робота-разведчика и манипуляционного робота (рис.1, б) совместными усилиями находили объект (книгу) и манипулировали с ним. Видео с демонстрацией возможностей таких роботов получило в 2011 г. приз на конференции Conference on Artificial Intelligence AAAI-11 в Сан-Франциско.

Эволюционирующие роботы. В 2009 г. в швейцарской лаборатории Laboratory of Intelligent Systems (политехническая школа, Лозанна) были проведены исследования в области "эволюции" роботов. Эволюционировал геном робота, определяющий поведение. В экспериментах группа из 10 роботов состязалась за пищу. Роботы - это колесные платформы (т.н. s-боты) диаметром 12 и высотой 15см. (рис.1, в).

Задача роботов заключалась в поиске "источника пищи", которым являлось светящееся кольцо на одном из концов арены. На другом конце арены было более темное кольцо, которое считается "отравленным". Роботы получали очки в зависимости от того сколько времени проведут около источников пищи и/или «яда». Кроме того, роботы могли "общаться" друг с другом, посредством световых сигналов.

Роботы могли «эволюционировать» из-за того, что каждый робот был оснащен искусственной нейронной сетью контролируемой бинарным «геномом». В ходе экспериментов эволюция роботов приводила иногда к тому, что роботы обучались даже обманывать соперников, испуская "неправильный" свет, находясь возле кормушки (чтоб не привлекать к кормушке конкурентов).



а) б) в)

Рис.1. а) Мини-роботы проекта SwarmRobot; б) роботы проекта Swarmanoid; в) s-бот

Роботы-разведчики Scout. Центр распределенной робототехники, Университет Миннесоты, США. Начало работ - 2001 г. ([Rybski a.o., 2001]).

Устройство состоит из корпуса цилиндрической формы с двумя колёсами, а также устройством для совершения прыжков - взводимой упругой пластины.

Предназначенный для разведки, робот представляет собой очень качественное с технической точки зрения устройство. Его «тактико-технические характеристики»:

Длина: 110 мм;

Диаметр: 40 мм;

Вес: 200 г;

Скорость: 30 см/с;

Привод: 2 колеса, механизм для прыжков;

Высота прыжка: до 30 см.;

Сенсоры: камера, акселерометры, энкодеры на колесах, магнетометры;

Время функционирования: в неподвижном состоянии - 120 мин., при движении на полной скорости - 70 минут, 100 прыжков;

Коммуникации: 6 каналов связи.

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

Развитием проекта стала разработка робота-разведчика Throwbot компанией ReconRobotics (2011 г.). Робот снабжен «хвостиком» для балансированного движения и антеннами. Длина робота составляет 187 мм., а вес - 0.5 кг. Для изготовления Throwbot использовались сверхпрочные материалы - титан и авиационный алюминий, которые позволяют забрасывать робота в помещение с расстояния в тридцать метров.

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

Интересно, что производство роботов Throwbot ограничено числом в 2000 экземпляров в первый год и в 8000 во второй, так как использоваться он может только специальными службами и только в особых, угрожающих жизни людей случаях.

а) б) в)

Рис. 2. Роботы-разведчики. а) робот Scout, б) пусковое устройство, в) робот Throwbot

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

Мы сознательно не говорили о робофутболе. С одной стороны, футбол роботов - это как нельзя более удачный пример коллективного взаимодействия. Более того, это направление развивается весьма успешно вот уже не одно десятилетие. Одна только ассоциация RoboCup насчитывает 5 основных и 3 дополнительные лиги. Тем не менее, робофутбол не интересен для нашего обзора в силу того, что применяемые в нем методы и решения носят частный, зачастую сугубо технический характер. Робофутбол, как направление - это реципиент, а не донор идей.

3. Методы решения

В названиях большинства приведенных выше проектов фигурирует слово swarm - рой, стая. Действительно, многие исследования черпают свое вдохновение из мира насекомых, многие из них постоянно проводят аналогии с колониями муравьев, пчел и прочих стайных животных. Но, разумеется, реализуются и исследуются и другие модели.

На сегодняшний день исследования в области коллективного поведения роботов можно разбить на следующие направления:

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

Технологии многоагентных систем (МАС).

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

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

Эволюционные методы. Основная задача - реализация эволюционным путем механизмов внутристайного (внутрироевого) взаимодействия.

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

Распределенный ИИ. Иногда, говоря о задаче коллективного поведения роботов, пытаются применять термин "распределенный искусственный интеллект" (РИИ), считая, что эта область ИИ занимается самыми общими аспектами коллективного поведения агентов. Однако (по крайней мере - сегодня), этот подход вряд ли можно считать сложившимся. В лучшем случае основу РИИ составляют результаты, полученные в теории распределенных систем, теории принятия решений и даже теории МАС. Основные же проблемы остаются по-прежнему нерешенными. Неясно, как эффективно разбивать задачу на подзадачи и распределять их между агентами, неясно, как будут синтезироваться результаты и и согласовываться решения т.п. Иными словами, РИИ может восприниматься сейчас как декларация о намерениях.

Другим близким термином является т.н. групповая робототехника.

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

В отличие от известных распределённых робототехнических систем, ГР подчёркивает необходимость большого количества роботов, а также предполагает масштабируемость, например, с использованием только локальной связи.

Важным аспектом ГР является ее техническая направленность: создание конструкции роботов, систем управления, механизмов взаимодействия. При этом принципиальными факторами в ГР являются миниатюризация и стоимость. Это - основные проблемы в создании больших групп роботов, поэтому простоте каждого члена команды в ГР уделяется особое внимание.

Забегая вперед, отметим, что именно принцип "простоты" робота является самым слабым местом ГР. Проблема как раз состоит в том, что члены стаи - это очень и очень непростые по своей структуре, поведению и возможностям организмы.

И, наконец, встречается термин коллективный интеллект, который появился в середине 1980-х годов в социологии при изучении процесса коллективного принятия решений. Коллективный интеллект определяется как способность группы находить решения задач более эффективные, чем лучшее индивидуальное решение в этой группе.

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

3.1 Формальные модели коллективного поведения

Автоматные модели. В 60-е гг. 20 века сформировалась школа, изучающая различные модели поведения на основе конечных автоматов. Основным тезисом являлось: любое достаточно сложное поведение слагается из совокупности простых поведенческих актов [Цетлин, 1969]. Яркими представителями этого направления являются ее основоположник М.Л. Цетлин, В.И. Варшавский, В.Л. Стефанюк, Д.А. Поспелов и др.

Характерно, что первая работа, в которой был впервые предложен и использован термин "коллективное поведение автоматов", была опубликована еще в 1963 году.

Исследуя разнообразные формы поведения, начиная от условно-рефлекторного, и заканчивая моделями коллективного поведения, был создан теоретический фундамент для описания коллективного взаимодействия объектов самой разной природы.

В рамках коллективного поведения автоматов рассматривались задачи распределения ресурсов между участниками, особенности организации однородных коллективов, поведение неоднородных структур (вводился ранг рефлексии участников) и т.п.

Решались также задачи синхронизации взаимодействия членов коллектива (автоматов). Именно на базе подобных моделей был создан фундамент сотовой связи (задача о коллективе радиостанций, которым надо "договариваться" между собой о мощности своих сигналов) [Стефанюк, 2004], [Стефанюк и др., 1967]. Именно эти модели и методы (см., например, [Варшавский и др., 1984], [Гаазе-Раппопорт и др., 1987]) стали основой для построения многих децентрализованных коллективных систем, моделей индивидуального и коллективного поведения.

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

Современные стандарты сотовой связи подразумевают наличие т.н. базовых станций, которые берут на себя функции централизованного управления, в т.ч. - и регулировку мощности сигналов. Однако предложенная в [Стефанюк, 2004], [Стефанюк и др., 1967] схема взаимодействия радиостанция является принципиально децентрализованной, самоорганизующейся. А это является принципиальным моментом для организации той же самой пресловутой «умной» пыли или интеллектуальных сенсорных сетей. Дело в том, что для этих систем наиболее актуальной проблемой является сбалансированность энергоресурса.

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

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

Рис.3. Иллюстрация к задаче о поливе участков

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

Тем не менее, где в явном виде применялась теория коллективного поведения автоматов для реализации коллективного поведения роботов автору, к сожалению, неизвестно. Сослаться можно, пожалуй, на [Карпов и др., 2005]. В этой работе рассматривалась задача поведения двух роботов (роботы серии «АМУР»), которые могли обмениваться друг с другом накопленным опытом. Опыт приобретался при функционировании роботов в различных средах, а механизмом, реализующим обучение на базе условно-рефлекторного поведения, были конечные стохастические автоматы.

Рис.4. Роботы серии «АМУР». Объединение матриц вероятностей действия

Клеточные автоматы. Иногда встречаются утверждения, что теоретическим и методологическим базисом коллективного поведения роботов может служить теория клеточных автоматов. Более того, сама теория клеточных автоматов родилась в каком-то смысле из робототехники. В свое время фон Нейман пытался решить задачу о роботе, собирающего другого робота (т.н. кинематическая модель).

Однако в дальнейшем, осознав сложность создания подобного самовоспроизводящегося робота, фон Нейман разработал более абстрактную и удобную математическую модель - первую теорию клеточных автоматов. Сейчас, являясь примером классической однородной структуры [Аладьев, 2009], теория клеточных автоматов в явном виде для решения задачи коллективного поведения роботов практически не используется.

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

При этом подходе состояния системы "робот среда" задаются парами вида

,

где R(t) и S(t) - соответственно состояния робота и среды в момент времени t. Далее задаются начальные условия

Общая же постановка задачи определяется следующим образом [Каляев и др., 2009]:

Задача управления роботом R состоит в том, чтобы определить такую последовательность действий (вектор-функцию действий) A(t) на интервале времени [t₀, t_f], выполнение которых при заданных связях, начальных условиях и ограничениях обеспечивало бы экстремум функционала

Здесь g(t) - действия прочих сил, существующих в среде. Разумеется, вводятся ограничения на возможные состояния системы "робот-среда" и возможные действия робота.

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

Оптимизационный подход позволяет решать целый ряд задач, среди которых есть очень и эффектные. Например, есть такая красивая задача, как распределение целей между роботами группы, да еще в условиях заранее неизвестных противодействий противника (см. упомянутую выше артиллерийскую систему NLOS-LS или [Каляев и др., 2009]).

Если имеется M целей T₁, T₂, …, T_M и N "роботов" R₁,…,R_N и известно, что ущерб, наносимый противнику при поражении i-й цели, определяется как Y_i=F_i(P_i,n_i), где P_i - приоритет цели, а n_i - количество роботов, поразивших i-ю цель, то целевым функционалом управления группой роботов будет Y_c=Y_i. А далее цели распределяются между роботами так, чтобы, естественно, максимизировать Y_c.

Рис.5. Распределение целей T_i между «роботами» R_i

Эта задача (по крайней мере - на модельном уровне) решается достаточно хорошо. Однако следует отметить, что подобный подход слишком абстрагируется от робота, как сложного технического объекта. «Умную пыль», «умные снаряды» и им подобные распределенные системы вряд ли можно отнести к объектам исследования именно коллективного поведения роботов. Дело даже не в том, что зачастую происходит выхолащивание самого понятия робота (и роботом называют буквально все, что движется и не движется - от тележки до лифта). Дело в том, что составная часть коллектива - робот - не может быть примитивной, простой. Особь - это сложное устройство. Только тогда возможна самоорганизация. Только тогда возникают предпосылки для коллективного поведения.

3.2 Многоагентные системы

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

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

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

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

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

Теория общих намерений. Основными понятиями теории общих намерений [Cohen a.o., 1991] являются:

события - связаны с конкретным агентом или объектом внешнего мира;

убеждения - утверждения, в истинности которых агент убежден в текущий момент времени;

цели - некоторые состояния агента, которые он стремится достичь;

взаимные убеждения - складываются из убеждений группы агентов.

Для описания поведения команды агентов используются как индивидуальные, так и общие обязательства и соглашения.

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

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

Разумеется, для коллективной работы между общими и индивидуальными намерениями агента должна существовать тесная связь.

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

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

Базовые понятия теории: групповой план и индивидуальные ментальные понятия агентов. Согласование же индивидуальных действий и планов групп агентов выходит за рамки теории.

Итак, недостатком теории общих планов является отсутствие конкретизации способа построения общего плана.

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

Например, комбинированная модель [Tambe, 97] на верхнем уровне использует понятия общих обязательств и общих намерений команды агентов, взятые из теории общих намерений. При этом понятие общих намерений используется в этой теории для описания поведения команды агентов в терминах конкретных операторов, что характерно для теории общих планов.

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

Основные проблемы и ограниченность применения подобного рода теорий хорошо иллюстрируется следующими вполне конкретными и реальными ситуациями [Городецкий и др., 2011]:

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

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

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

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

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

Существует целый ряд формальных языков для описания взаимосвязанных потоков действий (работ). Это сети Петри, цепи процессов, управляемых событиями (Event-Driven Process Chain), сети потоков работ (Workflow Net) и т.д. Общие недостатки существующих формальных языков связаны с тем, что ни один из них не обладает выразительными возможностями, необходимыми для спецификации планов командного поведения агентов. В той или иной степени для этих языков характерно:

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

ограничения на возможности обмена сообщениями и ряд других;

слабые возможности по описанию временных аспектов, в частности, временной синхронизации процессов и игнорирование продолжительности процессов во времени;

отсутствие возможности выбора альтернативного сценария поведения в реальном времени, если такая необходимость возникла.

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

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

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

Исполнение сценария командной работы есть пошаговый процесс исполнения частично упорядоченной во времени последовательности действий.

Для описания сценарных баз знаний разработан специальный язык описания процессов, который построен на основе существующих языков описания сложных процессов ("потоков работ"), разработанных для описания бизнес-процессов. При этом каждое сложное действие представляется синтаксической структурой сценарной базы знаний. На рис.6, а приведен простой пример синтаксической модели сценарной базы знаний. Здесь определено множество возможных вариантов для достижения цели X₄ из начального состояния X₁: (A₁ A₃ A₄), (A₂ A₃ A₄), (A₃ A₂ A₄), (A₃ A₁ A₄) и (A₃ A₅).

Пример системы. В [Городецкий, 2010] описана командная работа подводных роботов при охране припортовой зоны подводного пространства.

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

Каждый АПР имеет средства обнаружения подводных объектов и средства их активного зондирования с целью идентификации типа (мина, пловец, безопасный объект и др.). Если АПР обнаруживает неизвестный объект, то он формирует команду (используя протокол общих намерений) для его более глубокого совместного исследования. АПР принимают на себя обязательства и соглашения, а также договариваются о зонах и ракурсах съемки объекта. Затем в течение какого-то времени АПР команды автономно решают задачи, принимают локальные решения и пересылают их АПР-инициатору.

На рис.6, б приведен фрагмент сценарной базы знаний для командной работы АПР по идентификации обнаруженного неизвестного объекта (сценарий "Идентификация объекта").

а) б)

Рис. 6. а) пример синтаксической модели сценарной базы знаний; б) фрагмент сценарной базы знаний "Идентификация объекта"

Итак, говоря о технологии МАС применительно к задаче коллективного управления роботами, можно сделать следующие выводы:

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

Основной упор делается на описание сценариев взаимодействия роботов как агентов.

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

3.3 Имитационные модели

В этом направлении за основу берутся модели биологических объектов (своего рода бионическая парадигма). Считается, что получение адекватных моделей тех же насекомых позволит реализовать естественным образом и их стайное (роевое) поведение.

Однако проблема состоит в том, что насекомые - очень непростой объект для исследований. Например, нервные клетки муравьев и пчел - любимых объектов для подражания - малы по размеру и трудны для изучения. А главное, этих нервных клеток очень много. Если центральная нервная система такого простого объекта, как виноградная улитка, содержит около 10 тыс. нейронов, то у муравьев общее количество нейронов - порядка 1 млн. При этом изучение той же улитки также сопряжено с большими сложностями. В основном опыты проводятся на командных нейронах (нейронах оборонительного рефлекса и мотонейронах) [Карпенко и др., 2003].

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

Более того, системный подход даже к клеточной нейробиологии осуществляется в основном "сверху-вниз": от поведения к мозгу, от целого мозга к отдельному нейрону. Отправной точкой в исследованиях клеточных механизмов является именно поведение.

Муравей, повторим, - это один из основных "источников вдохновения" в исследованиях коллективного поведения. Однако на самом деле муравей - это одни из наиболее неудачных примеров для изучения коллективных форм. Он слишком сложен.

Муравей

Итак, что дали 130 млн. лет эволюции этих насекомых (кстати, общая масса которых чуть больше, чем общая масса людей). В качестве примера из известных примерно 8000 видов муравьев рассмотрим наиболее распространенного в наших широтах рыжего лесного муравья из рода Formica. Рыжие лесные муравьи относятся к одной из наиболее прогрессивных групп муравьев. Далее дадим их характеристику в форме краткой справки ([Длусский, 1967], [Захаров, 1978]).

Гнездо. Купол до полутора метров высотой. Состоит из множества секций, камер, служебных и спальных помещений. Численность населения - от нескольких десятков до нескольких сотен тысяч особей.

Муравьиные тропы. Тропы ведут к кормовым участкам. Тропы ухожены. Протяженность - десятки и сотни метров, ширина - до метра. Такие дороги действуют иногда десятки лет. Совокупность троп составляет охраняемую территорию данного муравейника. Муравьи Formica свои дороги запахом не метят.

Ориентация и память. Муравьи могут ориентироваться по солнцу. Фуражир, идущий в поисках пищи по однородной местности, сохраняет постоянный угол к солнцу. Муравьи удерживают в памяти направление движения по отношению к солнцу не менее 5 дней. Муравьи-охотники ориентируются, запоминая окружающий ландшафт. Муравьи способны запомнить относительное расположение каких-либо выдающихся предметов в ландшафте (камней, палочек и т.д.) и выстраивают свой маршрут по этим ориентирам.

Центральная нервная система (ЦНС). ЦНС состоит из ряда ганглиев, связанных между собой. Наиболее важной частью является надглоточный ганглий, или "мозг" муравьев, в котором образуются временные связи. Временные связи образуются у муравьев в грибовидных телах, являющихся аналогом коры головного мозга позвоночных. Размеры грибовидных тел муравьев связаны со способностью различных видов к образованию условных рефлексов. У рабочих Formica грибовидные тела составляют 1/2 объема мозга (у пчелы, например, грибовидные тела составляют всего 1/15 размеров мозга, несмотря на то, что мозг их относительно больше).

Всего нервная система муравья содержит порядка 1 млн нейронов (из них собственно в мозгу - надглоточном ганглии) - порядка 500 тыс.шт. Мозг муравья -- это примерно 6% от общего веса тела насекомого (у человека это соотношение всего 2%).

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

Рис.7. Муравей рода Formica

1 -- глотка; 2 -- пищевод; 3 -- ядовитая железа: 4 -- надглоточный ганглий; 5 -- подглоточный ганглий; 6 -- грудные нервные узлы; 7 -- брюшная нервная цепочка.

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

Органы вкуса муравьев также расположены на жгутиках усиков, на нижней губе.

Зрение. Область точного зрения муравья не превышает 1-2 см. При этом, как и большинство "простейших", муравьи видят прежде всего не форму, а движение и цвет. Сами органы зрения представлены большими фасеточными глазами и тремя простыми глазками, функция которых пока не очень ясна.

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

Деятельность муравьев. Перечислим кратко лишь некоторые наиболее интересные виды:

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

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

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

Выращивание грибов. Муравьи некоторых видов устраивают в своих муравейниках грибные плантации для снабжения высококалорийной белковой пищей.

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

Взаимодействие муравьев.

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

Социальное поведение.

Профессии и психологические склонности. По мере роста муравьиной общины разделение функций становится все более глубоким: число профессий рабочих муравьев возрастает, а специализация каждой особи сужается (в мирмекологи это называется полиэтизмом). Основами для специализации рабочих муравьев стали их физиологическое состояние и психические наклонности. Например, более инициативные, с быстрой реакцией муравьи становятся разведчикам или охотниками, крупные - солдатами, а особи, имеющие замедленную реакцию и минимум любознательности, - обслуживающими рабочими и фуражирами. Это - т.н. кастовый полиэтизм.

Однако, и это представляется чрезвычайно важным, муравьи способны менять профессии. Например, при гибели значительной части муравьев-фуражиров, оставшиеся рабочие внутригнездовые муравьи берут на себя их работу (наблюдалось так же, как муравей-охотник неуклюже и весьма неуверенно выполняет функции няньки).

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

В основе способности муравьев к обучению лежит хорошая память. В процессе обучения большое значение имеют реакции подражания.

Механизмы социального образования. Обмены. Основным признаком "свой-чужой" для муравьев является запах. Если же сообществу приходится делиться на обособленные группы (колонны, колонии, федерации, о чем будет сказано далее), то трофаллаксис перестанет играть свою роль. И тогда начинает работать механизм обмена - важнейшая для поддержания целостности семьи операция - регулярный обмен личинками, куколками и молодыми рабочими.

Колонны. Крупный муравейник не однороден. По достижении некоторой критической численности, "население" муравейника делится на т.н. колонны - обособленные подгруппы муравьев. У каждой колонны есть своя кормовая дорога, члены каждой колонны живут в своей секции. Будучи обособленными, колонны, тем не менее, не могут не контактировать друг с другом, чтобы не терять своей внутригнездовой общности (признаком которой является запах). Контакты эти осуществляются с помощью обменов.

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

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

Федерации. Образование колоний, - это не последняя вершина организационной структуры муравьиного сообщества. Длительный процесс образования отводков (колоний) ведет в конечном счете к перенаселению. И тогда формируются федерации - своего рода панмуравейник. Если в отдельной семье или колонии социальная регуляция колонн или входящих в колонию муравейников возникает как механизм, обеспечивающий общий рост населения, то задача федерации - ограничение общей численности муравьев в системе. Результатом регуляции в федерации является сохранение основных структурных единиц.

Федерация - высшее достижение социальной организации у муравьев. Устойчивость федерации значительно выше, чем обособленной колонии. Причем все это достигается одними и теми же средствами - обменами.

Механизмы реализации

Рассмотрим далее некоторые возможные механизмы, могущие лежащие в основе моделей деятельности муравьев.

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

Распределенный мозг. Весьма экзотической теорией, пытающейся объяснить механизм управления муравьиным сообществом, является теория распределенного мозга [Луговской, 2007]. Согласно этой теории, в муравьином сообществе существуют носители этого "распределенного мозга" - т.н. "ленивые" муравьи. Феномен "ленивых" муравьев заключается в том, что около 20% муравьиной семьи не принимает участия в трудовой деятельности. При этом ссылаются на эксперимент, проведенный в Стэнфордской лаборатории известного физика, лауреата Нобелевской премии И. Пригожина, который занимался проблемами самоорганизации и коллективной деятельности. В этом эксперименте муравьиную семью разделили на две части: в одну вошли только "ленивые" муравьи, а в другую -- "работники". Через некоторое время выяснилось, что качественный состав семей выровнялся: в семье "ленивых" муравьев только каждый пятый остался "ленивым", а остальные стали активно работать. В семье же "работников" та же пятая часть стала "ленивыми", а остальные остались "работниками". Из этого делался вывод, что, по-видимому, в каждой семье часть ее членов делегируется для хранения особо важных сегментов распределенного мозга. При этом по структуре и строению нервной системы "ленивые" муравьи не отличаются от обычных. Механизм же коммуникации внутри распределенного мозга и между мозгом и прочими членами социума является совершенно неизученным.

Центральные моторные программы. На самом деле, вместо моделирования целого ансамбля из 1 млн. нейронов можно реализовать ограниченное количество функциональных блоков (подсистема распознавания, ориентации, коммуникации, обучения, выполнения действий и т.п.). Дело не в формировании из этих блоков или подсистем хорошо известной структуры интеллектуального робота. Речь идет о реализации идеи многоуровневого иерархического управления. Эта идея применительно к построению движений была сформулирована Н.А. Бернштейном (пирамидная двигательная система) еще в 30-40-е гг. прошлого века ([Бернштейн, 1997]). По такому же принципу, используя хорошо изученный нейрофизиологами механизм центральных моторных программ, можно строить и системы управления роботами [Карпов, 2007], [Добрынин и др., 2007].

...