4.1. Структура и функции агента

Часть 4. Агентные системы

4.1. Структура и функции агента

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

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

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

Отличия агента от объекта:

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

2) Агент может принять на себя обязательства или отказаться от выполнения некоторой работы, мотивируя отсутствием компетентности, занятостью другой задачей и т.п.

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

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

1. Знания (knowledge) – постоянная часть знаний агента о себе, среде, других агентах, не изменяемая в процессе его функционирования.

2. Убеждения (beliefs) – переменные знания агента о себе, среде, других агентах, стимулы к изменению которых агент может получать из среды.

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

4. Обязательства (commitments) – задачи, которые агент берет на себя по просьбе (поручению) других агентов в рамках кооперативных или частных целей.

5. Намерения (intentions) – множество задач, вытекающих из обязательств и желаний агента.

Минимальный набор базовых характеристик агента

Общие формулировки	Формулировки М.Вулдриджа и Н.Дженнингса
Характеристика	Формулировка	Характеристика	Определение
Активность	Способность к организации и реализации действий	Целенаправленная активность	Способность агентов не просто реагировать на стимулы, поступающие из среды, но и целенаправленно проявлять инициативу
Целенаправленность	Наличие собственных (социальных) источников мотивации
Автономность (полуавтономность)	Относительная независимость от окружающей среды или наличие некоторой «свободы воли», зависящей от ресурсного обеспечения	Автономность	Способность функционировать без прямого вмешательства людей или компьютерных средств и осуществлять контроль над своими действиями и состояниями
Коммуникабельность	Необходимость решать задачи совместно с другими объектами, обеспечиваемая развитыми протоколами коммуникации	Общественное поведение	Способность взаимодействия с другими агентами и людьми
Реактивность	Способность воспринимать состояние среды

6. Цели (goals) – конкретное множество конечных и промежуточных состояний, которое агент принял в качестве стратегии поведения.

4.2. Архитектура агента

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

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

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

4.3. Мультиагентные системы и виртуальные организации

4.3.1. Компоненты, кооперация и конкуренция в МАС

Компоненты МАС:

1) Множество организационных единиц:

a. подмножество агентов;

b. подмножество объектов.

2) Множество задач.

3) Среда (пространство, в котором существуют агенты и объекты).

4) Множество отношений между объектами.

5) Множество действий агентов (например, операций между объектами).

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

Показатели уровня кооперации в МАС:

1. Общие:

1.1) Характер распределения задач.

1.2) Объединение различных точек зрения.

1.3) Возможность решения общей проблемы в заданное время.

2. Детальные:

2.1) Высокая степень распределения ресурсов (в т.ч., знаний).

2.2) Избегание (малая длительность) конфликтов.

2.3) Координация действий агентов.

2.4) Высокая степень запараллеливания задач, решаемых различными агентами.

2.5) Неизбыточность действий.

2.6) Устойчивость (способность МАС пережить отказ или потерю агента).

Этапы распределенного решения задач МАС:

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

2. Задачи распределяются между агентами исполнителями.

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

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

Типы конкуренции в МАС:

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

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

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

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

Кооперация = сотрудничество + координация действий + разрешение конфликтов.

4.3.2. Доска объявлений

Механизм коммуникации реализуется с помощью т.наз. доски объявлений (blackboard). Основная идея: на доске объявлений указываются все решаемые задачи и общеизвестные сведения.

Составляющие модели доски объявлений:

1. Источники знаний.

2. Структура данных, реализующая доску объявлений.

3. Управляющий компонент.

4.3.2.1. Источники знаний

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

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

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

4.3.2.2. Структура данных доски объявлений

Структура данных доски объявлений должна содержать:

- область прохождения сообщений;

- информацию о процессе решения задачи;

- состояния агентов.

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

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

4.3.2.3. Управляющий компонент

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

4.3.3. Протоколы переговоров агентов

Требования:

1. Простота.

2. Децентрализация (переговоры осуществляются напрямую, без централизованного управления).

3. Симметричность (равноправие агентов в переговорах).

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

5. Эффективность.

Построение протокола включает три шага:

1. Определение пространства возможных соглашений.

2. Введение правил взаимодействия (например, в соответствии с теорией речевых актов в терминах «предложение – контрпредложение»).

3. Задание оптимальных стратегий агентов.

Классическими методами исследования переговорных процессов являются методы теории полезности и теории игр.

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

В начале 1980-х г.г. Р. Смит разработал модель распределенного решения задач, названную им «контрактной (договорной) сетью» (contract net). В основе модели лежит простейшая идея рыночных торгов. Имеются два типа агентов: агенты-менеджеры и агенты-исполнители (покупатели). Агент-менеджер распространяет объявление о задании и определяет исходную цену, а агенты-исполнители (потенциальные) предлагают услуги со своими вариантами цен. Агент-менеджер отбирает самые выгодные для него предложения и заключает соглашение с выбранными агентами-исполнителями, которые становятся агентами-подрядчиками.

Преимущество модели договорных сетей – простота и легкость реализации. Недостатки: отсутствие продуманного механизма выбора подрядчика и высокая загрузка коммуникационных каналов.

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

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

4.4. Элементы теории агентных систем

В работе И. Шоэма «Агентно-ориентированное программирование» (начало 1990-х г.г.) был описан социальный взгляд на организацию вычислений. Социальный агент определяется четверкой:

SA = <ST, AC, SL, T>,

где ST – множество состояний;

AC – множество действий;

SL – множество социальных законов;

T – обобщенная функция переходов.

Социальный закон slÎSL есть множество ограничений sl = {<ac, st>}, т.е. недопустимых пар состояние-действие.

T: ST´AC´SLà2^ST

T удовлетворяет условиям:

а) ("stÎST, acÎAC, slÎSL) <ac, st>ÏslèT(st, ac, sl)ÌST

б) ("stÎST, acÎAC, sl₁,sl₂ÎSL) sl₁Ésl₂ èT(st, ac, sl₁)Í T(st, ac, sl₂)

Условие а означает: Если действие ac в состоянии st легитимно (не принадлежит множеству недопустимых действий), то функция переходов возвращает непустое множество, являющееся подмножеством множества состояний.

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

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

- алетическая логика (модальности «возможно» и «необходимо»);

- эпистемическая логика («известно» и «неизвестно»);

- временная логика («всегда» и «никогда»);

- доксастическая логика («верит» и «не верит»);

- оптитативная логика («желает» и «не желает»);

- и т.д.

Они могут интерпретироваться в различных возможных мирах, тогда как классическая логика интерпретируется в одном-единственном мире. Тогда убеждения агента можно представить как совокупность миров, где распределены его предпочтения. Пусть агент работает с множеством возможных миров W. Из W можно выделить подмножество W₀, на котором агент концентрирует свое внимание, исходя из своих знаний и предпочтений. Это подмножество W₀ содержит миры, совместимые с тем, что агент знает (в чем он убежден) в текущем мире wÎW. Тогда вводится отношение достижимости R:

("w₀ÎW₀)wRw₀

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

Know (a, p, s)

Believes (a, p, s)

Doubts (a, p, s)

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

Want (a, p, s)

Indif (a, p, s)

Wantstock (a, p, s)

Язык модальной логики включает в себя традиционные компоненты:

- непустое множество примитивных высказываний F;

- логические связки Ù и Ú;

- модальные операторы Bel (убежден, уверен), Des (желает), Intend (намерен);

- временные операторы.

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

K-аксиомы (аксиомы знаний):

Bel(j)ÙBel(jèf)èBel(f)

Des(j)ÙDes(jèf)èDes(f)

Intend(j)ÙIntend(jèf)èIntend(f)

G-аксиомы (аксиомы обобщения, генерализации):

├fè├Bel(f)

├fè├Des(f)

├fè├Intend(f)

D-аксиомы (аксиомы непротиворечивости):

Bel(j)èØBel(Øj)

Des(j)èØDes(Øj)

Intend(j)èØIntend(Øj)

Позитивная интроспекция (аксиома 4):

Bel(j)èBel(Bel(j))

Негативная интроспекция (аксиома 5):

ØBel(j)èBel(ØBel(j))

4.5. Технологии проектирования МАС

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

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

- уменьшение времени и стоимости передачи данных;

- расширение ограниченных локальных ресурсов;

- облегчение координации;

- выполнение асинхронных вычислений.

Проблемы использования мобильных агентов:

1) Легальность способов перемещения объектов по сети.

2) Верификация агентов (например, защита от вирусов.

3) Соблюдение прав частной собственности.

4) Сохранение конфиденциальности информации.

5) Перенаселение сети агентами.

6) Несовместимость кода агента и программно-аппаратных средств сетевой машины.

Для реализации МАС, основанных на распределенных приложениях, используются технологии DCOM, Java RMI (Remote Method Invocation), CORBA (Common Object Request Broker Architecture).

Программное средство Agent Builder (Reticular Systems) предназначено для разработки МАС на основе Java-программ, исполняемых на любо компьютере, где установлена виртуальная Java-машина (Virtual Java Machine).

Схема проектирования и реализации приложений на основе Agent Builder ToolKit.

Модель жизненного цикла создаваемых агентов включает следующие этапы:

- обработку новых сообщений;

- определение правил поведения;

- выполнение действий;

- обновление ментальной модели (ментальных свойств) в соответствии с заданными правилами;

- планирование действий.

Правила поведения в Agent Builder реализуются на специальном ОО языке RADL (Reticular Agent Definition Language) в виде конструкции When-If-Then. Составные части этого правила выполняют следующие функции:

Name <Rule Name> содержит наименование правила;

When <MessageConditions> содержит новые сообщения, полученные от других агентов;

If <Mental Conditions> сравнивает текущую ментальную модель с условиями применимости правила;

Then <Private Actions, Mental Changes, Message Actions> определяет действия, соответствующие текущим событиям, ментальной модели и состоянию внешнего окружения.

Язык RADL основывается на продукционно-фреймовом хранении знаний и данных.

Недостатком Agent Builder называют отсутствие средств явного управления логическим выводом.

Дата добавления: 2015-11-04