Введение
Мы представляем систему для интерактивного испытания поведения потенциально больших групп роботов или агентов в реальном времени с помощью контролируемого демонстрационного обучения. Для нас представляет интерес относительно «комплексное» поведение, а именно такое, которое может включать несколько внутренних состояний, позволяет применять вероятностный подход к принятию решений, тяжело повторяемо, управляется при помощи параметров, а также существует как на уровне агента, так и группы агентов.
Мы понимаем, что данная задача представляет сложность по следующим трём причинам. Во-первых, в то время как статическое повторяемое поведение агента сопряжено с проблемой потенциально высокой размерности, демонстративное обучение в реальном времени представляет лишь небольшое число примеров испытаний, которых может быть недостаточно для моделирования пространства. Во-вторых, пространство мультиагентного поведения нелегко масштабируемо: с ростом числа агентов случайная макросоставляющая, возникающая из их взаимодействий, становится всё более комплексной и труднопрогнозируемой, в результате чего исследователь вновь сталкивается с проблемой измеримости, в частности если речь идёт о группе разнородных агентов. В-третьих, эти случайные макрофеномены сопряжены с угрозой обратной проблемы для методов контролируемого обучения. Данные методы обычно требуют, чтобы агенты располагали примерами вариантов поведения в разных ситуациях на микро-уровне. При этом исследователь обычно не в курсе поступков на микро-уровне ─ он только задает вариант макро-поведения, и может в силу наличия случайной составляющей не быть осведомлён о том, какими именно действиями на микроуровне оно обеспечивалось.
Несмотря на эти трудности, мы предполагаем достичь цели. Наш подход предполагает следующие два пути: (1) осуществление декомпозиции задач вручную для изучения иерархии вариантов поведения среди агентов; (2) создание древовидной иерархии агентов. Оба этих «иерархических» механизма позволяют упростить задачу с помощью принципов разделения и конкуренции. Каждый из них подробно рассматривается ниже.
Иерархически тестируемое поведение
Вручную выстраиваем задачи в виде иерархии подзадач, и тестируем поведение в рамках каждой из них. Простые действия объединяются в более комплексные посредством надстройки. Исследователь разрабатывает функции перехода между состояниями. Декомпозиция задач позволяет перевести комплексную проблему познания в существенно более мелкие, часто тривиальные, подпроблемы, а также сократить пространство характеристик в базисе каждой из подпроблем. Наконец, поведение становится параметрически управляемо («идти в точку А» или «идти к двери») и может быть использовано в рамках разных контекстов.
Иерархии агентов
Разделим агентов на подгруппы, объединенные в древовидную иерархию с разделением агентов на основных и контролирующих (не основных). Безусловно, древовидная структура имеет недостатки, к примеру, жёсткость организации. Однако, существенным плюсом для нашего исследования является простота древовидной иерархии. Важно, что эта иерархия позволяет…К примеру, мы могли бы создать многослойную иерархию, где первый уровень составили бы контролирующие агенты, у каждого из которых на попечении находилась бы небольшая группа основных агентов; второй уровень ─ агенты, заведующие группами контролирующих агентов первого уровня; и наконец во главе всего стоял бы один контролирующий агент. В процессе испытания контролирующие агенты по существу не отличаются от основных.
С нашей точки зрения, иерархии агентов и контролирующие агенты играют наиболее важную роль, когда возникает разнородность в группе (например, различные подгруппы выполняют разные задачи). Это наша конечная цель, однако пока мы работаем с однородными мультиагентными поведенческими иерархиями. Но даже в этом случае полезно разбивать группу на координирующие подгруппы.
В данной работе описан пример успешно протестированной мультиагентной коллективной задачи. Мы проводим сравнение отдельных агентов, однослойной иерархии и двухслойной иерархии. В статье представлены результаты как теоретического анализа проблемы, так и численного эксперимента.
Обзор предшествующих исследований
Наш подход касается различных подразделов литературы по мультиагентному и демонстрационному обучению. Некоторые из них обсуждаются далее.
Многое из того, что касается изучения роботов по демонстрационной литературе, может быть разделено на (1) системы, изучающие планы (к примеру, [Nicolescu, Mataric, 2002; Veeraraghavan, Veloso, 2008]) и (2) системы, изучающие политику, т.е. отклик на определенное действие компонент вектора характеристик агента, независимых от его состояния ([Bentivegna et al., 2004; Dinerstein et al., 2007; Kasper et al., 2001; Nakanishi et al., 2004]). Некоторые работы содержат модели, учитывающие состояние, к примеру, посредством скрытых Марковских моделей. Например, в [Hovland et al., 1996] состояния трактуются не как поведение, а как скрытые характеристики среды, которые исследователь пытается найти и оптимизировать. [Goldberg, Mataric, 2002] изучают переходы между состояниями в привязке к поведению, хотя сами переходы не выделяются.
Декомпозиция задач и итеративное иерархическое познание ─ естественный путь изучения многослойных структур [Stone, Veloso, 2000]. Такие подходы могут быть реализованы для изучения политики: возможно, наиболее близок нам [Saunders et al, 2006], изучающий последовательности и итеративную политику в привязке к предшествующим периодам вне анализа состояния. Планы также могут быть структурированы и изучаться итеративно сходным образом [Nicolescu, Mataric, 2002].
Одна из ключевых задач, поставленных в данной работе ─ применение контролируемого демонстрационного обучения к мультиагентным моделям. Как отмечается в [Panait, Luke, 2005], методы контролируемого (управляемого) обучения не очень широко распространены в мультиагентных случаях: львиная доля литературы базируется на таких методах, как стохастическая оптимизация или обучение методом проб и ошибок. Среди этих управляемых методов многие попадают в категорию моделирования агентов, где последние изучают друг друга, а не задачу, выданную им демонстратором. К примеру, в отмеченной статье [Stone, Veloso, 2000] управляемая задача («оценка местоположения») обоснованно описана посредством агентного моделировани, тогда как для полной задачи мультиагентного обучения («выбор местоположения») использован метод проб и ошибок. Мультиагентное обучение может также быть достигнуто посредством доверительного оценивания вместо метода проб и ошибок [Cherova, 2009].
Поведение агентов
В нашем мире каждый агент обучен набору из одного или больше вариантов поведения. Каждое из поведений представлено в форме иерархии с конечным числом состояний-автоматов в форме машин Мура (Moore machines). Каждый автомат представляет собой n-мерное пространство 
, определенное следующим образом:
-
─ набор состояний в автомате. Среди других он включает стартовое состояние S1, а также ноль или несколько состояний-флагов. В момент времени t активно в точности одно состояние St. Рассматриваются внутренние состояния автомата, а не состояния мира, т.к. ситуация в мире не моделируется. -
─ набор базовых (жёстко заданных) поведений. Каждое состояние ассоциируется в равной степени с базовым поведением или другим автоматом из 
, при условии, что возврат не допускается. -
─ набор наблюдаемых характеристик окружающей среды. В любое заданное время каждая характеристика имеет численное значение. Объединенные значения F в момент t формируют вектор характеристик среды 
. -
─ функция перехода, преобразующая текущее состояние St и текущий вектор характеристик 
в новое состояние St+1. -
Мы обобщаем модель со свободными переменными (параметрами)
, отвечающими за базовые варианты поведения и характеристики. Каждое поведение Bi заменяем на 
, а характеристику Fi ─ на 
. И изменение функции перехода, и реализация поведения базируются на базовых требованиях (целях), заданных свободными переменными.
Автомат стартует в своем начальном состоянии S1, whose behavior simply idles. Будучи в состоянии St, с каждым шагом во времени автомат делает запрос в адрес функции перехода об определении следующего состояния St+1, переходит в это состояние, и если , прекращает осуществлять поведение, присущее состоянию St, и приступает к поведению в соответствии с St+1. Происходит генерация поведения в состоянии St+1, и если оно само по себе представляет автомат, процесс генерации доходит до автомата. Характеристики могут описывать как внутренние, так и внешние условия; могут быть торообразными («углом к цели»), продолжительными («расстояние до цели»), категориальными или логическими («цель видима»).
Назначение флагового состояния в том, чтобы просто выставить флаг на автомате, обозначив, что тот воспринимает условие как верное. Два очевидных условия должны быть исполнены или потерпеть неудачу, однако могут возникнуть и другие. Флаги на автомате появляются как оптимальные характеристики родительского автомата. К примеру, флаг «сделано» может быть использован родительским автоматом для отдаления от текущего автомата, т.к. тот идентифицирует задачу как завершенную.
Поведениям или характеристикам могут быть присвоены один или несколько параметров: вместо поведения, например, «подойди к мячу», создается поведение «подойти к А» (goTo(A)), где А не специфицируется. Иначе говоря, характеристика может быть определена не как «расстояние до мяча», а как distanceTo(B). Если автомат использует такое поведение или характеристику, его параметры должны быть обусловлены специфической целью (такой, как, к примеру, «мяч» или «ближайшее препятствие») или родительским автоматом более высокого уровня.
Испытание поведения для одного агента
Мы разрабатываем «комплексное» агентское поведение, сначала вручную проводя его декомпозицию к виду иерархии N более мелких поступков, затем испытывая последовательно каждый из этих поступков пока методом надстройки не будет сконструирован «комплексный» вариант. Начнём с библиотеки поведений, состоящей из базовых (жёстко заданных) поступков, доступных агенту. Члены поведенческой библиотеки формируют доступные состояния нового поведения, в отношении которого в настоящий момент проводится испытание. Каждый раз, когда поведение до конца изучено, оно попадает в поведенческую библиотеку и становится доступно в виде состояния для новых испытаний.
Рисунок 1: Структуры, использованные в ходе экспериментов. Верхний ряд ─ полностью распределенная структура, где каждый агент следует одинаковым идентичным вариантам одного и того же поведения (и библиотеки поведений). В центре ─ простая одноуровневая иерархическая структура, где агенты сгруппированы к одному ряду контролирующих агентов. Нижний ряд ─ простая двухуровневая иерархическая структура, где контролирующие агенты первого уровня сгруппированы к различным контролирующим агентам второго уровня. Все агенты, относящиеся к данному контролирующему агенту, следуют одинаковому поведению, хотя текущее состояние этого поведения может варьироваться в зависимости от текущей ситуации в подгруппе, прикрепленной к данному агенту.
Для тестирования поведения агент помещается в режим тренировки, в рамках которого он воспроизводит именно те варианты поведения, которые назначил ему пользователь. Каждый раз, когда пользователь направляет агента на исполнение нового поступка, агент фиксирует тренировочный пример: вектор из трёх показателей 
, где 
─ это текущее поведение, 
─ текущий набор характеристик, 
─ новое желаемое поведение. Если поведение 
должно осуществиться единовременно, дополнительные примеры не фиксируются. В противном случае, пример фиксируется в форме 
и интерпретируется так: «если я выполняю 
, и состояние мира наступает 
, продолжать выполнять 
». Вектор характеристик специфицируется пользователем из библиотеки определенных ранее, но задаваемых параметрически характеристик, соответствующих задаче.
После некоторого времени управления агентом пользователь переключается в режим тестирования, в котором изучается конечное поведение автомата. В то время как состояния автомата фиксированы (они свободно соотносятся с поведениями из библиотеки), в процессе тренировки выявляются функции перехода автомата из состояния в состояние. Чтобы изучить функцию перехода для заданного состояния Si и соответствующего ему поведения Bi, мы берем все зафиксированные примеры из формы 
, сокращаем их до 
, которые формируют точки 
с пометками 
для классификационного алгоритма. В настоящий момент наш классификационный алгоритм представлен деревом решений в стиле С4.5 с вероятностными краевыми узлами , однако вместо него может быть использован практически любой иной. Результирующие классификации формируют функции перехода для автомата. Неиспользованные состояния сокращаются, и автомат сохраняется в библиотеке. Наконец, если изучаемый автомат использует параметризуемое поведение или характеристики, каждый параметр необходимо согласовывать с целью («ближайший мяч») или параметром самого автомата.
В процессе режима тестирования агент в интерактивном режиме реализует тестируемое поведение в присутствии пользователя. Если пользователь фиксирует непредсказуемое поведение, он может включиться в любое время, немедленно переводя агента снова в режим тренировки, и поправить действие, добавляя дополнительные примеры во вновь открытый режим тестирования. Более детальное обсуждение одноагентной модели см. в [Luke and Ziparo, 2010; Sullivan et al, 2010].
Однородные мультиагентные иерархии
Мы бы хотели бы изучить не только поведение одного агента, но и коллектива из многих агентов. Очевидный (распространенный) подход присвоить всем агентам одинаковое поведение на последнем этапе. Альтернативынй централизованный подход заключается в том, чтобы определить единственного контролирующего агента ответственным за всех вспомогательных агентов. Все вспомогательные агенты имеют в своих библиотеках одинаковые варианты поведения; у контролирующего агента отдельная собственная библиотека поведений ─ и базовых, и полученных в процессе изучения автоматов. Базовые варианты поведения контролирующего агента не управляют им, а вместо этого соотносятся с уникальными поступками из библиотек вспомогательных агентов. Когда контролирующий агент переходит к новому базовому поведению, вспомогательные агенты немедленно приступают к реализации соответствующего ему поведения из этих библиотек.
Наша структура промежуточная: мы определяем иерархию контролирующих агентов. Базовые агенты сгруппированы в подгруппы, каждая из которых управляется контролирующим агентом первого уровня; затем различные контролирующие агенты первого уровня группируются в подгруппы вспомогательных агентов по отношению к контролирующим агентам второго уровня, и так далее до уровня агентов m. В точности так же, как базовые агенты придерживаются одинакового поведения, поведение контролирующих агентов заданного уровня единообразно. Настоящая структура иерархии (число уровней, число агентов на одного контролера и т.д.) заранее специфицируется пользователем.
После тренировки базовых агентов в обычном режиме можно потренировать контролирующих агентов вначале первого, затем второго уровня и т.д. Тренировка контролирующих агентов по существу такая же, как и базовых: пользователь направляет контролирующего агента к реализации различных поступков (которые, в свою очередь, являются причиной действий вспомогательных агентов), которые добавляют примеры в базу данных, по которой изучаются функции перехода. В то время как базовое поведение контролирующего агента определено, каков его набор характеристик? Мы предполагаем, что, в отличие от базового агента, контролирующий агент на сформирован: его характеристики происходят из статистических результатов его вспомогательных агентов: к примеру, «базовый агент в моей группе убит (или не убит)», или «все мои вспомогательные агенты передают сигнал «сделано» (или «не сделано»)», или «средняя Y позиция базовых агентов в моей группе». Очевидно, как базовые поведения и характеристики агента, выбор характеристик, доступных контролирующему агенту, зависит о конкретных обстоятельств.
Демонстрация: поиск коробок
Мы применили мультиагентные однородные иерархии к процессу симуляции проблемы поиска коробок: агенты охотятся за коробками, затем направляя их в известные им хранилища. Коробки случайным образом распределены в среде. После сбора новая коробка появляется в среде случайным образом. Среда имеет размер 200х200 и состоит из различных круглых «коробок» и 50 агентов. Агенты перемещаются на 0.1 единицу за один шаг времени. Во всех экспериментах использованы 10 коробок, каждая 5 единиц в диаметре. Некоторые коробки переносятся 5 агентами, остальными – 25-ю. Если коробка достаточно близка к необходимому расположению, она фиксируется как «сохраненная»: тогда она вновь перемещается в новое случайное место , а все агенты от неё дистанцируются.
Декомпозиция поведения агентов
Рисунок 2: представление системы в действии (фотография элемента среды). Большие серые круги представляют собой коробки, крестик в середине – их хранилище. Заметим, что если агенты, толкающие коробку в левой части рисунка принадлежат одной и той е подгруппе, то коробку внизу рисунка передвигают агенты из различных подгрупп.
Мы вручную провели декомпозицию и испытание поведения агентов следующим образом:
-
Базовые характеристики агентов: DistanceTo(X), DirectionTo(X), ICanSeeABox, IAmAttachedToABox, Done. Первые две характеристики параметризированы либо к явным коробкам, либо к расположению хранилища. Последняя характеристика была актуальна вместе с флагом «сделано». Предел видимости коробок – 10 единиц пространства
-
Базовые характеристики агентов: Forward, RotateLeft, RotateRight, GrabBox, ReleaseBox, ReleaseBoxAndFinish, Done. ReleaseBox и Done сопросовждаются флажком «сделано» и немедленно возвращаются в стартовое состояние. Так же дело обстоит и с ReleaseBoxAndFinish, с тем только исключением, что может быть установлен также флажок «завершено», если агент зафиксирован контролером как базовый. Перенесение коробок осуществляется на расстояние 5 единиц.
-
Используя Forward, RotateLeft и RotateRight, было проведено испытание поведения Wander.
-
Используя Forward, RotateLeft и RotateRight, а также DistanceTo(X), DirectionTo(X), в режиме тренировки находится поведение GoTo(X), преследующее заданную цель.
-
Используя GoTo(X), GrabBox, ReleaseBoxAndFinish и DistanceTo(X), в режиме тренировки находится поведение ReturnWithBox, толкающее коробку к хранилищу и дистанцирующее агента от неё в случае близости к дому.
-
Используя Wander и ReturnWithBox, в режиме тренировки Forage, простая декомпозиция верхнего уровня с поиском коробок и перетаскиванием их к хранилищу.
Если агенты действуют сами по себе (контролирующий агент отсутствует), поведение высшего уровня будет описываться как Forage. В случае наличия контролирующего агента 1-го уровня, текущее поведение агента определяется контролером.
Эксперименты
Мы рассматривали три структуры:
(1) 50 независимых агентов;
(2) Частично распределенная группа из 10 независимых контролирующих агентов первого уровня, каждому из которых подконтрольна подгруппа из 5 агентов;
(3) Два независимых контролирующих агента второго уровня, каждому из которых подконтрольны 5 контролирующих агентов первого уровня, каждый из которых, в свою очередь, возглавляет подгруппу из 5 агентов.
Графическое представление использованной структуры представлено рисунком 1.
Мы провели два эксперимента. В ходе первого эксперимента мы, во-первых, стремились показать, что при помощи простой иерархии можно представить группу независимых агентов; а в-вторых, что поведения, изучаемые в этом эксперименте, хорошо соотносятся с жёстко заданными 5-кратными вариантами поведения. В ходе второго эксперимента нашей целью было показать, что двухуровневая иерархия агентов «перекрывает» одноуровневую.
Продолжительность каждого эксперимента составила 100 000 тактов времени, каждая из попыток включала 100 независимых прогонов. Значимые различия в результатах для 100 000 тактов времени зафиксированы на 95%-м уровне значимости, согласно двухстороннему t-тесту с коррекцией Бонферрони (Bonferroni correction).
Рисунок 3: Среднее число коробок, собранных во время первого эксперимента
Рисунок 4: Среднее число коробок, собранных во время второго эксперимента
Заключение
Мы продемонстрировали контролируемое обучение на базе демонстрационной системы изучения рекуррентного мультиагентного поведения в форме иерархии автоматов. Наша конечная цель – достичь полной гетерогенности агентов. На пути к достижению мы провели декомпозицию задач, занялись изучением простого поведения, последовательно объединяя варианты поведения в системы, пока не достигли желаемого результата.
Такой вариант решения задачи позволили снизить её размерность, сделав доступным решение более комплексных проблем несмотря на ограниченность базы примеров действий для тренировки.
Кроме того, нами была создана иерархия, позволяющая объединять независимых агентов в независимые небольшие группы.
Более подробно модель описана в статье "Keith Sullivan and Sean Luke. 2011. Multiagent Supervised Training with Agent Hierarchies and Manual Behavior Decomposition. In Proceedings of the IJCAI 2011 Workshop on Agents Learning Interactively from Human Teachers (ALIHT)".
© Могилат Анастасия