Свойства

«От перестановки слагаемых сумма не меняется»

α + β = β + α

Возьмём 2-а нечётких числа α и β, α + β = γ, где множество принимаемых значений будет состоять из k2 чисел Vai+Vbj с соответствующими вероятностями Pai*Pbj. Если же рассмотреть выражение β + α, оно также будет равно у, ведь условия существование наших чисел не менялось, изменилась только позиция значений чисел Vbj+Vai отсюда следует α + β = β + α.

«От перестановки множителей произведение не меняется»

α * β = β * α

Возьмём 2-а нечётких числа α и β, α * β = γ, где множество принимаемых значений будет состоять из k^2 чисел Vai+Vbj с соответствующими вероятностями Pai*Pbj. Если же рассмотреть выражение β * α, оно также будет равно у, ведь условия существование наших чисел не менялось, отсюда следует α * β = β * α.

11.Онтологии и онтологические системы: определение, назначение, структура. Виды онтологий. Отличие онтологий от баз данных. Языки представления онтологических знаний. Примеры онтологических систем.

«Онто» - греч. – «сущее».

Онтология(технический термин) – это типичная семантическая сеть. Этапы проектирования онтологий:

1)точная спецификация концептуализации;

2)формальная точная спецификация совместно используемой концептуализации знаний;

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

4)концептуализация знаний о мире, спецификация этого знания.

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

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

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

Формальность – онтология должна быть ориентирована на компьютерное представление знаний. Это исключает использование естественных языков в полной мере.

Совместное использование – отражает понятие того, что онтология описывает всеобщее знание, принятое в группе или в сообществе.

Назначение онтологий:

1)онтология описывает всеобщие знания;

2)знания предназначены для совместного использования;

3)используется онтологическое соотношение;

4)основное назначение онтологий – интеграция информации и ее представление в виде, удобном для совместного использования в целях решения разных прикладных задач. *Система Protégé.

Формальная модель онтологий:

Предполагается наличие трех констант:

О – {X, R, F}, где

X – конечное множество концептов об объектах ПО;

R – конечное множество отношение между концептами;

F – конечное множество функций интерпретаций, заданных на концептах и/или

Классификация онтологий:

1)по степени формальности;

2)по наполнению, содержимому;

3)по цели создания.

По степени формальности:

1)онтология как словарь.

О = V = {X, {ø}, {ø}}, R= ø, F = ø. Это вырожденный случай.

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

О = V^, = {X, {ø}, {F}}, R= ø, F ≠ ø. Каждому множеству Х ставится его интерпретация.

3) О = V^,, = {X, {R }, { ø }},

4)таксономии. Эта разновидность онтологий включает точное определение отношения ПОДКЛАСС-КЛАСС(обозначаемого как isA). В таких системах строго соблюдается транзитивность отношения isA: если A является подклассом класса B, то каждый подкласс класса A также является подклассом класса B. Строгая иерархия классов необходима при использовании наследования для процедуры логического вывода.

По содержимому выделяют онтологии 4х типов:

1)онтология мета-уровня (верхнего уровня). Описывают общие понятия внешнего мира – пространство, время, материя, объект, событие, процессы, действия, которые НЕ ЗАВИСЯТ от предметной области. Огромную роль играют СВОЙСТВА.

2)онтологии предметной области – понятия, свойства, объекты, отношения конкретной ПО;

3)онтология задач – процедуры, действия;

4)онтология приложений – объединенные..

Онтологии верхнего уровня, или метаонтологии, описывающие общие понятия, независимо от задач конкретного домена. Примером такой онтологии может служить WordNet [Fellbaum C., 1998]. Масштаб WordNet весьма обширный – весь английский язык с описанием каждого термина, его синонимов и гипер/гипо (более/менее) общих терминов и отношений между ними. В то же время уровень детальности в WordNet очень низкий, имеются лишь описания на естественном языке терминов, которые не могут быть поняты машиной, и зафиксированы только самые простые отношения между ними.

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

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

В качестве примера онтологии предметных областей приведем краткое описание онтологии предприятия «The Enterprise Ontology» (далее ЕО), разработанную Эденбургским университетом совместно c такими партнерами как IBM, Lloyd’s Register и др. [Uschold M., King M., 1998; TOVE Ontology Project].

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

******Много инфы тут: http://www.intuit.ru/department/expert/ontoth/2/2.html

12.Агенты и МАС: определения, обобщенная структурная схема агента и МАС, области применения агентов и МАС.

Агент – это система, находящаяся в некоторой среде, воспринимающая эту среду посредством рецепторов, и воздействующая на нее посредством эффекторов (см. рис. 1).

Многоагентная система – это система, в которой поставленная задача решается за счет совместной деятельности (кооперации, противоборства) многих агентов в некоторой среде.

Рис. 1

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

- Автономность. Агент должен работать без ежесекундного вмешательства и контроля человека.

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

- Реактивность. Агент должен оперативно реагировать на изменения в среде.

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

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

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

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

- Мобильность. Это способность агента перемещаться по вычислительной сети (или в физической среде).

- Правдивость. Агент специально не сообщает неверную информацию.

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

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

Примерами агентов являются:

- компьютерные вирусы;

- интеллектуальные помощники;

- поисковые боты в сети интернет;

- некоторые персонажи компьютерных игр;

- роботы;

- и т.д.

В тоже время агентами не являются:

- объекты в классическом понимании объектно-ориентированного программирования (см. далее);

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

- мастера, планировщики и т.п.

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

1. Моделирование поведения социальных систем с целью проверки теорий, описывающих это поведение:

- для построения планов эвакуации;

- для координации действия спасателей;

- для управления движением;

- для управления различными предприятиями, организациями, городами, странами;

- для проведения социологических исследований;

- для проведения экономического моделирования рынков;

- для проведения экологических и биологических исследований;

- и т.д.

2. Задачи логистики.

3. Задачи оптимизации поточных линий.

4. Качественный поиск информации в WEB.

5. Ведение военных действий с применением боевых роботов.

6. Автономное управление космическими аппаратами.

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

Агент – это система, находящаяся в некоторой среде, воспринимающая эту среду посредством рецепторов, и воздействующая на нее посредством эффекторов.

Многоагентная система – это система, в которой поставленная задача решается за счет совместной деятельности (кооперации, противоборства) многих агентов в некоторой среде.

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

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

2. По степени определенности последствий принимаемых решений: детерминированная – если следующее состояние среды однозначно определяется предыдущим состоянием и реализуемым действием или стохастическая – иначе. (прим. солнце встало – значит сядет)

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

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

5. По плавности изменения состояний среды бывают: дискретные – если изменения происходят скачкообразно, и непрерывные – если изменения происходят плавно. (прим. дискретные – тот же светофор; непрерывные – изменение погоды)

6. По количеству находящихся в среде агентов - одноагентные и многоагентные (прим. квартира с 1 чел.; улица).

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

14.Понятие агента и МАС: определение, отличие агента от объекта и экспертной системы.

Между агентами и экспертными системами можно найти следующие различия.

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

Во-вторых, классические ЭС не способны к реактивному и проактивному поведению.

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

В свою очередь, ЭС реального времени во многом очень похожи на агентов и чаще всего отличаются от них отсутствием социального элемента поведения.

15.Варианты структурной организации агентов: структурные схемы простого рефлексного агента и агента с моделью внешней среды, сравнение функциональных возможностей.

16.Варианты структурной организации агентов: структурные схемы агента с моделью внешней среды и агента с функцией полезности, сравнение функциональных возможностей.

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

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

Простой рефлексный агент:

полностью игнорирует прошлое

работает в реальном времени

правильно функционирует в полностью наблюдаемой среде

пример: робот-пылесос

Агент с моделью внешней среды:

Не будет противоречить правилам среды.

Агент основанный на цели

Не выполняет лишних действий, а только нужные.

Агент основанный на полезности

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

Обучающийся агент

Определяет полезность не из функции полезности а сам обучается.

Критик сравнивает со стандартом и выдает оценку, в зависимости от которой вырабатываются знания.

Критик получает всю инфу с датчиков из среды.

Произв. Компонент воздействует на среду в зависимости в зависимости от знаний агента и действий генератора проблем.

Сравнение:

Простой рефлексный и с моделью внешней среды.

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

С моделью внешней среды и с функцией полезности.

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

С функцией полезности и обучающийся.

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

18.Понятие агента и МАС: определение, критерии целесообразности применения многоагентного подхода для решения задач.

Агент – это система, находящаяся в некоторой среде, воспринимающая эту среду посредством рецепторов, и воздействующая на нее посредством эффекторов (см. рис. 1).

Рис. 1

Критерии целесообразности применения многоагентного подхода для решения задач

1. Возрастающее количество распределенных систем.

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

2. Увеличение степени интеграции вычислительных устройств.

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

Из пунктов 1 и 2 возникает вопрос: как обеспечить эффективность работы программного обеспечения с распределенными, высоко интегрированными системами? Ответом на него является использование многоагентного подхода.

3. Увеличение степени социальной интеграции.

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

4. Увеличение степени интеллектуальности программного обеспечения самого разного назначения.

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

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

5. Возрастающая ориентация на человека.

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

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

1. Моделирование поведения социальных систем с целью проверки теорий, описывающих это поведение:

- для построения планов эвакуации;

- для координации действия спасателей;

- для управления движением;

- для управления различными предприятиями, организациями, городами, странами;

- для проведения социологических исследований;

- для проведения экономического моделирования рынков;

- для проведения экологических и биологических исследований;

- и т.д.

2. Задачи логистики.

3. Задачи оптимизации поточных линий.

4. Качественный поиск информации в WEB.

5. Ведение военных действий с применением боевых роботов.

6. Автономное управление космическими аппаратами.

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

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

Поэтому, когда говорят о поведении агентов и характеризуют их состояние, то употребляют такие термины как:

- убеждения (B eliefs);

- желания (D esires);

- намерения (I ntention).

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

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

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

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

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

- «Она думала, что на улице холодно» - убеждение о состоянии объекта;

- «Она была убеждена, что он сделает ей предложение» - убеждение о намерениях другого;

- «Она была уверена, что он знает ее подругу» - убеждение об убеждении другого;

- «Он думал, что она хочет в Париж» - убеждение о желаниях другого.

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

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

Уровни целеустремленности (уровни рефлексии):

1. Убеждения о внешнем мире

2. Убеждения об убеждениях

3. и т.д.

20.Технологии агентно-ориентированного анализа и проектирования: классификация, технология проектирования агентов на основе концептуального анализа структур действий.

Все известные методики разработки МАС можно классифицировать следующим образом:

- базирующиеся на традиционном объектно-ориентированном проектировании и расширяющие его в сторону агентов;

- базирующиеся на методах инженерии знаний;

- базирующиеся на организационно-ориентированных представлениях;

- сочетающие в себе элементы трех выше названных классов.

Определение концептуальной модели предметной области (КМПрО):

КМПрО = {A, X, C, V(C), R, G(A), Ru}, где:

A = {a₁, a₂,... a_n} – множество имен субъектов (т.е. агентов), действующих в предметной области (ПрО);

X = {x₁, x₂,..., x_n} - множество имен объектов(пассивных ресурсов), существующих в ПрО (в среде функционирования агентов), и необходимых агентам для их деятельности, n ³ 0;

C = {c₁, c₂,... c_n} – общее множество имен свойств агентов и объектов, но каждый агент или объект описывается своим набором свойств. Например, для x _i имеем множество имен свойств

c_i = {c_i1, c_i2,..., c_im}, m ³ 0;

V(C) – множество областей значения свойств:

c_ij = { c_i_j¹, c_i_j²,..., c_i_j^k},

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

R = {r₁, r₂,... r_l} - множество имен отношений, в которые могут вступать агенты и объекты (в разных сочетаниях) моделируемой ПрО, l >= 0;

G(A) = {g₁, g₂,... g_v} - множество имен действий (процессов, принимаемых решений), которые агенты могут совершать над объектами и друг другом, v>0 (хотя бы одно действие в задачах моделирования всегда есть);

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

Объективное состояние ПрО S_ПрО представляет собой совокупность всех фактов.

Объективное состояние ПрО изменяется под влиянием действий из множества G(A) и определяется в фиксированный момент t_i времени следующим образом:

S_ПрО (t_i) = {A(t_i), X(t_i), C(t_i), R(t_i)}

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

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

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

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

· указание на компоненты действия, т.е. другие агенты или объекты ПрО, необходимые для описания условий и реализации данного действия;

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

21.Типичные проблемы («подводные камни»), с которыми сталкиваются разработчики МАС.

Проблемы использования МАС:

1) непонимание МА-подхода, его возможностей и областей применения;

2) многоагентный «фанатизм». Существует много задач, где МА-подход не нужен;

3) стремление найти универсальное решение для уникальной задачи;

4) разработчики забывают о том, что разрабатывают ПО;

5) разработчики забывают о многопоточности;

Проблемы синхронизации работы агентов, их взаимодействия:

6) архитектура МАС плохо распараллелена;

7) стремление разработать слишком «интеллектуальных» агентов;

8) стремление разработать новую архитектуру агента;

9) всё рассматривается как агенты;

10) разрабатываемые агенты слишком свободны в своём взаимодействии.

22.Проблема кооперации агентов: необходимость кооперации, общие свойства протоколов ведения переговоров, необходимые составляющие переговорного процесса.

Необходимыми предпосылками и условиями кооперации агентов выступают:

· мотивация к объединению индивидуальных усилий;

· географическое сближение, объединение и размножение агентов;

· коммуникация;

· сотрудничество и координация действий;

· специализация;

· переговоры между агентами.

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

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

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

· простота;

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

· симметричность (все агенты являются равноправными участниками переговоров);

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

· эффективность (как по отношению к отдельным агентам, так и по отношению к их коалициям).

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

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

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

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

23.Аукционы как переговоры с целью распределения ресурсов: классификация аукционов; основные варианты проведения аукционов – английский, голландский; проблемы лжи и сговора при проведении аукционов.

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

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

На аукционе один агент играет особую роль аукционера. Только он заинтересован в повышении цены на ресурс. Все остальные агенты заинтересованы в снижении цен.

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

Аукционы открытого типа, в свою очередь, делятся на:

«английские», когда цена повышается, начиная с некоторой стартовой, и побеждает тот агент, кто предложил наибольшую цену;

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

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

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

24.Задачно-ориентированные переговоры: формализация переговорного процесса и стратегия ведение переговоров по протоколу последовательных уступок.

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

Осуществляется с помощью переговорного процесса – ЗОП (задачно-ориентированный переговор). При этом должны выполняться условия:

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

Предложение – это конкретный вариант разделения общей задачи на составляющие;

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

Результат – заключение соглашения.

Соглашение – предложение, которое устраивает все стороны, участвующие в переговорах;

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

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

Трудности:

1)определить, что может являться предметом переговоров, а что нет;

2)определить количество участников переговорного процесса.

Минимальное количество участников – 2.

Форматы: 1) один-один, 2)один-много, 3)много-много.

Примеры задач, требующих переговорного процесса:

1)согласовать перевозку грузов несколькими людьми;

2)совместное использование ресурса.

ЗОП = < T, A, C >. С = Р(T_i)

T – множество предложений;

А – множество агентов, участвующих в переговорах;

С – ценности предложений.

Рассчитывается как применение функции полезности к конкретному предложению.

Полезность – субъективная величина.

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

U^a(T_i) = P(T_a) – P(T_i) > 0.

P(T_a) – стоимость решения собственного множества задач агента;

P(T_i) – стоимость сделанного предложения(предлагаемого множества задач).

Если U^a(T_i)>0, то предложение полезно для агента «а»;

Если U^a(T_i)=0, то равноценно и принимать его нет необходимости.

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

1)На первом раунде агенты одновременно делают друг другу предложения, предложения содержат 2 подмножества задач к переговорному множеству:

-задачи для себя;

-задачи для другого.

Т1 – предложение, сделанное 1-м агентом.

Т2 – 2-м агентом.

U¹, U² – функции оценки полезности - точки зрения 1-го агента и 2-го агента.

Соглашение может быть заключено в том случае, если:

U¹(T2)>=U¹(T1) или

U²(T1)>=U²(T2)

«Чужое предложение выгоднее, чем своё».

Если выполняются оба, то какое принять – выбирается через жребий.

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

Какова должна быть стратегия поведения по этому протоколу?

1)первым предложением должно быть наиболее выгодное для себя;

2)кто должен уступать на очередном раунде? Предлагается использовать оценку готовности агента к риску возникновения конфликта (когда один агент перестает уступать, может привести к неудаче переговорного процесса).

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

Полезность агента i, которую он потеряет – разница между полезностью для его собственного предложения и предложения агента j.

deltaU^ij = Uⁱ(Ti) – Uⁱ(Tj);

risk = deltaUij/Ui(Ti) // riskⁱ = [0;1]

Чем ближе к 1, тем меньше агент теряет, идя на конфликт; чем ближе к 0 – тем больше теряет и должен идти на уступки.

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

Пример – развоз детей в школу соседями.