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

УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ ИМ. В.А. ТРАПЕЗНИКОВА РАН

КОРЕПАНОВ ВСЕВОЛОД ОЛЕГОВИЧ

Метод рефлексивных разбиений в моделях коллективного поведения

Специальность: 05.13.10 - Управление в социальных и экономических системах

Автореферат диссертации на соискание ученой степени кандидата технических наук

УДК 519.876.2

- 1 ДЕК 2011

005004509

УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ ИМ. В.А. ТРАПЕЗНИКОВА РАН

УДК 519.876.2

На правах рукописи КОРЕПАНОВ ВСЕВОЛОД ОЛЕГОВИЧ

Метод рефлексивных разбиений в моделях коллективного поведения

Специальность: 05.13.10 - Управление в социальных и экономических системах

Автореферат диссертации на соискание ученой степени кандидата технических наук

Работа выполнена в Учреждении Российской академии наук Институте проблем управления им. В.А. Трапезникова РАН

Научный руководитель: - член-корреспондент РАН

Новиков Дмитрий Александрович

Официальные оппоненты: - доктор технических наук,

Бахтадзе Наталья Николаевна - кандидат технических наук, Сараев Павел Викторович

Ведущая организация: УРАН Институт проблем управления

сложными системами (ИПУСС) РАН

Защита состоится 2011 года в Ц час. на заседании

диссертационного совета Д 002.226.02 при Учреждении Российской академии наук Институте проблем управления им. В.А. Трапезникова РАН (117997 г. Москва, ул. Профсоюзная, 65)

С диссертацией можно ознакомиться в библиотеке ИПУ РАН

Автореферат разослан " ^ " Л 2011 года.

Ученый секретарь

диссертационного совета Д 002.226.02

к.т.н. '/ В.Н. Лебедев

2

Общая характеристика работы

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

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

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

Достижение поставленной цели потребовало решения следующих основных задач:

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

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

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

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

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

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

Связь с планом. Исследования по теме диссертационной работы проводились в соответствии с плановой тематикой работ ИПУ РАН в рамках координационных планов РАН.

Научная новизна. В результате проведенных исследований:

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

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

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

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

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

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

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

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

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

Личный вклад. Все основные результаты получены автором.

Апробация работы. Результаты диссертационной работы докладывались на: семинарах УРАН Института проблем управления им. В.А. Трапезникова РАН, научных конференциях Московского физико-технического института (Долгопрудный, 2008-2010), Всероссийских школах-семинарах молодых ученых «Управление большими системами» (Липецк, 2008; Пермь, 2010), XIII Международной конференции «Проблемы управления и моделирования в сложных системах» (Самара, 2011), Пятой международной конференции «Теория игр и менеджмент» (Санкт-Петербург, 2011).

Публикации. По теме диссертационной работы автором опубликовано 10 печатных работ общим объемом 12,5 печатных листов, в том числе - 4 статьи в ведущих рецензируемых журналах.

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

Основное содержание работы

Во введении обосновывается актуальность темы диссертационной работы, определяется цель исследования и описывается структура диссертации.

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

Раздел 1.1 посвящен описанию методологии моделирования информационной и стратегической рефлексии (процесса и результа-

5

та «размышлений» агента о принципах принятия решений другими агентами). Обозначим через щц представления агента /, обладающего у-м рангом рефлексии, о ранге рефлексии /-го агента. Для случая однородных агентов обозначим через д1]к представления /-го агентау-го ранга рефлексии о доле агентов, имеющих ранг к, цк = пк1п -«истинная» доля агентов к-то ранга.

Общий постулат, принимаемый практически во всех моделях рефлексивного коллективного поведения: агент некоторого ранга рефлексии «не знает» о существовании других агентов его ранга или более высоких рангов, т. е. V к >_/ ц1]к = 0, % = 1 / п.

Основания системы классификаций моделей стратегической рефлексии.

1) Множество возможных действий агента (конечно или «бесконечно» - например, отрезок 9?1).

2) Принцип выбора действий агентами нулевого ранга:

- фиксированные (априори заданные) действия, например фокальная точка;

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

-случайные в соответствии с заданным распределением (как правило, равномерным).

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

4) Распределение (объективное) агентов по рангам рефлексии:

- произвольное фиксированное;

-случайное (в соответствии с вероятностным распределением Пуассона qk = ег тк / к\, где г> 0 - параметр распределения Пуассона).

5) Информированность агента к-то ранга относительно общего числа (множества) агентов:

- знает множество N достоверно и считает, что эта информация является общим знанием;

-имеет свои представления относительно общего числа (множества) агентов.

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

6) Информированность агента к-го ранга относительно агентов более низких рангов (от 0 до £ - 1 включительно):

- знает достоверно (или с некоторой погрешностью);

- предполагает, что эти агенты распределены по рангам рефлексии от 0 до к - 1 включительно в соответствии с некоторым нормированным вероятностным распределением - как правило, распределением Пуассона);

- считает что все (!) остальные агенты имеют ранг к- 1.

7) Информированность агента к-го ранга относительно других агентов своего и более высоких рангов:

- считает их всех принадлежащих нулевому рангу;

- считает их всех принадлежащих к - 1-му рангу;

- предполагает, что эти агенты распределены по рангам рефлексии от 0 до к - 1 включительно в соответствии с некоторым вероятностным распределением (как правило - распределением Пуассона);

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

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

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

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

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

Вторая глава посвящена построению общей модели рефлексивного коллективного поведения и постановке задачи рефлексивного управления (разделы 2.1-2.5).

Рассмотрим множество N= {1,..., «}, состоящее из п агентов. Агент i выбирает свое действие xt е 5R1 (для простоты здесь и ниже, если не оговорено особо, считается, что ограничения на действия агентов отсутствуют). Вектор х = (хь ...,х„) е 9Г действий агентов, называемый ситуацией игры, определяет их выигрыши, задаваемые целевыми функциями F,{x), где F,{-): 9Г -> 9?1, i е N.

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

(1) Xi б BR,(x_i) = Arg max F;(y, x,), i e N,

yeiR1

где x_i = (xu ...,х/_ьд:,+ь ...,x„) e - обстановка игры для /-го агента, BR,{-) - его наилучший ответ (best response), / e N.

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

Введение определенных предположений об информированности агентов (о той информации, которой они обладают на момент выбора действий) приводит к соответствующим концепциям равновесия. Равновесием Нэша называется такой вектор действий of, что действие каждого агента i е N является наилучшим ответом на его Нэшевскую обстановку х^ :

(2)х? еВЩхЦ,).

Теория коллективного (группового) поведения исследует динамику поведения рациональных агентов при достаточно слабых предположениях относительно их информированности. Наиболее распространенной моделью динамики коллективного поведения является модель индикаторного поведения, суть которой заключается в следующем. Предположим, что каждый агент в момент времени t наблюдает действия всех агентов {х'4 },€jV, выбранные ими в предыдущий момент времени t - 1, t = 1,2,... (начальный вектор действий х° = ( ,..., х") считается заданным).

Каждый агент может рассчитать свое текущее положение цели - такое его действие у, которое максимизировало бы его целевую 8

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

(3) щ( х':') = arg max Ffy, x'J), t= 1, 2,..., / e N.

ye SR

В рамках гипотезы индикаторного поведения каждый агент в каждый момент времени будет делать «шаг» от своего предыдущего действия к текущему положению цели:

(4) х; = + у! Nx:;1)- х,м], i е N, t= 1, 2,...,

где у'. е [0; 1] - «величины шагов». Такое коллективное поведение можно условно назвать «оптимизационным», подчеркивая тем самым его отличие от игрового.

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

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

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

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

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

9

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

(5) wi(x'_i) = arg max F,(y, xV),

JXEiR1

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

Аналогично можно рассматривать агентов и более высоких рангов рефлексии. Для этого определим Е= {N0, ...,Nm} - разбиение множества агентов N, где N - множество агентов /-го ранга рефлексии, / = 0,т,т -максимальный ранг рефлексии, щ = |iV,|, i е N,

Х,=о"<' = п' Назовем Е рефлексивным разбиением.

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

Пусть задан вектор х° «начальных» действий агентов. Рассмотрим следующую динамическую модель рефлексивного принятия ими решений, помня при этом, что соответствующие выражения для одношаговой «игровой» модели могут быть получены как частный случай, в котором решения принимаются однократно при у\ = 1, / е N.

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

(6) х; = х;-' + у\ / ели= i,2,....

ю

Если рефлексирующих агентов нет (N0 = N), то в итоге все агенты пронаблюдают реализованную траекторию (х°, ..., х', ...) векторов действий агентов, определяемых (6).

Первый ранг рефлексии. Агент j, обладающий первым рангом рефлексии (/ е N{), считает всех остальных агентов обладающими нулевым рангом рефлексии и в соответствии с (6) «предсказывает» их выбор. Поэтому его собственный выбор 'хбудет ориентирован

на наилучший ответ на ту обстановку, которая с его точки зрения должна сложиться:

(7) Уу = 1х'Г1 + у) К(х1у)- lx'rl],j е Nu

Второй ранг рефлексии. Будем считать, что каждый агент j, обладающий вторым рангом рефлексии (j е Лу, знает достоверно множество Nq и считает всех агентов из множества N[ и iV2u... и Nm \ [/'} обладающими первым рангом рефлексии (отметим, что в общем случае, когда имеются несколько агентов второго и выше ранга рефлексии, данный агент ошибочно приписывает им первый ранг). В силу этого он может «прогнозировать» поведение своих оппонентов. Его выбор будет наилучшим ответом на ту обстановку, которая с его точки зрения должна сложиться:

(8) 2x'j = "х'Г1 + у> [w/x^, V/']J е Нг.

Если нет агентов выше второго ранга рефлексии, то для агента j е N2 прогнозируемой является траектория

(А...,(%, xi^un2\{j}' хшо )>•••)> а на самом деле реализуется траектория (х,..., (2х'.сЛ,2, 'хЦ , хЦ ),...).

к-й ранг рефлексии (к < т). Поведение агентов к-то ранга рефлексии описывается аналогично рассмотренным выше трем случаям (нулевого, первого и второго рангов рефлексии) с учетом следующей рефлексивной структуры агентов. Обозначим через Хд - субъективное рефлексивное разбиение - представления агента j, обладающего к-м рангом рефлексии, о разбиении всех агентов на ранги рефлексии:

к т-к-1

Агент j е Nk к-то ранга будет выбирать действия в соответствии с процедурой

(10) кх].=кх'г1 + [Wj{xLa, 'хц,...,

В «статическом» случае агент у е Л^ £-го ранга выберет действие

(И) *х;.(Х#) = агё тах х}^, 'хЦ ,...,

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

назовем рефлексивным равновесием игры .Те = {ТУ, Р,(-)геЛг, Е}. В силу введенных выше предположений о существовании и единственности наилучших ответов рефлексивное равновесие всегда существует. Отметим, что рефлексивное равновесие достаточно экзотично в том смысле, что в нем действия агентов в общем случае не являются наилучшими ответами на действия, выбираемые оппонентами.

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

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

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

Таким образом, управляемым параметром является рефлексивное разбиение агентов.

Сформулируем задачу управления в форме достижимости: пусть задано множество 3 допустимых рефлексивных разбиений; требуется найти множество Х(3) = (^^'(Е) векторов действий

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

Рассмотрим теперь собственно задачу управления. Пусть предпочтения управляющего органа - центра - описываются его действительнозначной целевой функцией Fo(Q(x')), заданной на множестве агрегированных ситуаций игры (Q: 9?" —> 9}'), т. е. F0( ): 5R1 -> 5R1. Тогда, воспользовавшись выражением (12), эффективность рефлексивного разбиения 2 можно определить как K{Y) = F0(Q(x*(Z))).

Следовательно, формально задачу рефлексивного управления (в терминах рефлексивных разбиений) можно сформулировать в виде (13) Щ) -> max .

ЕеЗ

Обозначим через Кт максимальное значение критерия эффективности в задаче (13) при фиксированном максимальном ранге рефлексии т. Сформулируем задачу о максимальном целесообразном ранге рефлексии - таком, больше которого центру (с точки зрения задачи управления в форме достижимости или/и эффективности рефлексивного управления) использовать не имеет смысла: т = min {т\т & Arg max Kw}.

w=0,1,2,...

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

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

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

Для олигополии в случае совершенной конкуренции и при дополнительных предположениях, описанных в параграфе 2.6.2, доказано Утверждение 2, качественно гласящее, что

1. Множество достижимости есть отрезок, содержащий начальную цену и экспоненциально увеличивающийся с ростом

параметра эластичности цены. Максимальный целесообразный ранг рефлексии ограничен линейной функцией от эластичности цены.

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

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

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

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

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

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

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

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

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

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

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

Глава 3 посвящена исследованию рефлексии и рефлексивного управления с помощью разработанных автором агентных имитационных моделей, описание которых приведено в разделах 3.1-3.3.

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

Были проведены два эксперимента для имитации процесса эвакуации, по условиям схожей с моделью эвакуации теоретической модели из раздела 2.6. Здание, в котором моделировалась эвакуация представлено на Рис. 1.

2а .'/ > -»-

!3 н - А * 5 6 {

Рис. 1. Пример модели здания

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

Представленное здание характерно тем, что если 99 агентов идут в ближний выход (№ 4), то одному («рефлексирующему») агенту выгодней идти в дальний выход (№ 6), поскольку все остальные агенты создадут пробку в ближнем выходе. Это условие определяет поведение рефлексивных агентов первого ранга, поскольку каждый такой агент считает всех остальных «обычными», постольку почти все они пойдут в дальний выход. Исключение составляют агенты 1-го ранга, близко расположенные к ближнему выходу - они успеют выйти в него до образования пробки.

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

I. Получение функций зависимости времени эвакуации от количества агентов для каждого выхода в отдельности (Рис. 2); подтверждение их монотонности; нахождение оптимального количества рефлексивных агентов первого ранга для минимизации времени эвакуации; ¡1. Сбор информации по поведению «обычных» агентов и

агентов 1-го ранга; ш. Получение необходимых данных для задания поведения агентов 2 ранга.

Время эвакуации для каждого выхода, равномерное распределение

60 т—---

О 20 40 60 80 100 120

Количество агентов

Рис. 2 Время эвакуации для каждого выхода при равномерном распределении агентов

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

Время эвакуации ич здаши в зависимости от количества рефлексивных агентов

50

Количество агентов 1-го ранга

100

Рис. 3 Время эвакуации из здания в зависимости от количества рефлексивных агентов 1-го и 2-го ранга

Время выхода

Количество агентов 2-го ранга

Минимум этой поверхности есть кривая АВ, которая, с учётом погрешностей, принимает постоянное значение. То есть минимум времени эвакуации достигается на целом семействе пар (количество агентов первого и второго рангов рефлексии), в т.ч. пара (57, 0), что говорит о необязательности задействования агентов второго ранга для минимизации времени эвакуации.

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

Раздел 3.5 - «Задача о диффузной бомбе» (задача о групповом проникновении через систему обороны). Пусть заданы начальные

положения (х/0), .у/0)), /= 1 ,К0, на плоскости К0 подвижных

объектов (ПО), движущихся с постоянной по модулю скоростью % Их цель - оказаться в точке с координатами (х , у ) - поразить целевой объект (ЦО). Положение /-го ПО в момент времени / > 0 обозначим через >',(/)), его скорость - через

у/О = ^(х^)2 + (_у;)2 , время первого попадания в точку (х\ у*) -

через 7}.

Имеются N неподвижных сенсоров с координатами (а„ Ьг),

/ = 1, ./У, имеющих возможность суммировать приходящие на них в один и тот же момент времени сигналы. Расстояние оту'-го ПО до /го сенсора обозначим через р,/1) = ^(ху(/)-йГ,.)2 +(у^)-Ь1)2.

В общем случае риск обнаружения у-го ПО системой сенсоров описывается следующим функционалом:

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

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

Номер вари анта Учет вероятности обнаружения Учет положений других ПО Прогноз поведения других ПО Информированность

»о Ц <и Ч О I НЕТ НЕТ НЕТ В каждый момент времени каждый ПО должен знать только свое текущее

2 § положение и положение ЦО.

т я Дополнительно к вариан-

Й ту I в каждый момент

а, <и С О о « II ДА НЕТ НЕТ времени каждый ПО должен знать оценки риска обнаружения для

о К у0г-окрестности своего

текущего положения

Дополнительно к вариан-

VI НЕТ ДА НЕТ ту I в каждый момент времени каждый ПО должен знать текущие и предыдущие координаты

всех остальных ПО.

Кооперативная модель III НЕТ ДА НЕТ Как в варианте I.

IV ДА ДА НЕТ Дополнительно к варианту II в каждый момент времени каждый ПО должен знать текущие координаты всех остальных ПО.

Рефлексивная модель V ДА ДА ДА Как в варианте IV.

Адаптивная модель «4 ПО первого типа ДА НЕТ НЕТ Как в варианте II

< N ПО второго типа | НЕТ ДА ДА Дополнительно к варианту I в каждый момент времени каждый ПО второго типа должен знать текущие координаты всех ПО первого типа.

Рассмотрим следующую имитационную модель, реализованную в среде АпуЬо^с. Выберем К0 = 100, Л" = 7, с1 = 0,25, /7 = 0.5, 8 = 0.03. Начальные положения ПО, ЦО, сенсоры и линии уровня суммарного «сигнала» изображены на Рис. 4.

й а о а 8 о о о&оооаооооайй

о

о о о №

й о

о « о о о л о

Рис. 4. Начальное расположение ПО, ЦО (звездочка), сенсоры (треугольники) и линии уровня суммарного "сигнала" (2)

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

Рис. 5. Пример результатов группового проникновения через систему обороны для варианта II

Переход от варианта I к варианту II, т.е. рост интеллектуализации ПО за счет их анализа вероятности

уничтожения в у0 т-окрестности текущего положения, существенно повышает эффективность преодоления системы обороны (например, при р = 0.5 эффективность увеличивается с 38 до 53 - примерно на 40 %)

На Рис. 6 для вариантов I и II приведены зависимости эффективности К (здесь и ниже каждая точка на графике эффективности является результатом усреднения по 200 испытаниям) количества достигших цели ПО от вероятности р уничтожения обнаруженного ПО. Естественно, с ростом вероятности уничтожения эффективность уменьшается.

Рис. 6. Зависимость эффективности К действий группы ПО от вероятности р уничтожения обнаруженного ПО для вариантов 1 (тонкая линия) и II (жирная линия)

Обозначим через К* е {0, 1, ... ,ЛГ0} число рефлексирующих агентов. График зависимости К{К) при а = 0.25 приведен на Рис. 7.

Рис. 7. Зависимость эффективности К действий группы ПО от числа рефлексирующих агентов К

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

В заключение раздела рассматривается следующий вариант информированности и «интеллектуальности» ПО.

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

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

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

Основные результаты и выводы

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

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

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

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

4. Для прикладных моделей "Олигополия Курно", "Активная экспертиза", "Транспортные потоки и модель эвакуации", "Фондовый рынок" и др. аналитически решены задачи рефлексивного управления (найдены оптимальные рефлексивные структуры) и получены оценки максимальных целесообразных рангов рефлексии.

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

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

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

Основные публикации по теме диссертации

1. КОРЕПАНОВ В.О. Реализация иерархической структуры агента II Труды 51 Всероссийской молодёжной научной конференции «Современные проблемы фундаментальных и прикладных наук». - М.: МФТИ, 2008. - 4.1 - С. 161 - 163.

2. КОРЕПАНОВ В.О. Модели движения агентов в замкнутом пространстве II Труды IV Всероссийской школы-семинара молодых учёных «Проблемы управления и информационные технологии (ПУИТ '08)». - 2008. - С. 118 - 122.

3. КОРЕПАНОВ В.О. Влияние рефлексивных агентов на транспортный поток / Труды международной научно-практ. конф. «Теория активных систем»,- М.: ИПУ РАН, 2009. - Т. II. С. 122 -125.

4. КОРЕПАНОВ В.О. Имитационные модели тактического поведения агентов И Управление большими системами. 2009. № 26. С. 145-157.

5. КОРЕПАНОВ В.О. О влиянии рефлексивных агентов с общим знанием на транспортный поток / Тр. 52-й науч. конф. МФТИ «Современные проблемы фундаментальных и прикладных наук». Ч. I. - М.: МФТИ, 2009. - Т. 2. - С. 69 - 71.

6. КОРЕПАНОВ В.О. Управление рефлексивным поведением агентов в модели олигополии Курно И Управление большими системами. 2010. № 31. С. 225 - 249.

7. КОРЕПАНОВ В.О. Модель рефлексивного группового управления в организационных системах / Труды VII молодежной школы-конференции «Управление большими системами». - Пермь: ПГТУ, 2010. Том. 1. С. 287 - 294.

8. КОРЕПАНОВ В.О., НОВИКОВ Д.А. Метод рефлексивных разбиений в моделях группового поведения и управления И Проблемы управления. 2011. № 1. С. 21-32.

9. КОРЕПАНОВ В.О, НОВИКОВ Д.А. Задача о диффузной бомбе П Проблемы управления. 2011. № 5. с. 66 - 73.

10. КОРЕПАНОВ В.О. Модели рефлексивного группового поведения и управления. - М.: ИПУ РАН, 2011. - 127 с.

Личный вклад автора в работах, опубликованных в соавторстве, заключается в следующем: в [8, 9] описан и реализован в виде имитационных моделей метод рефлексивных разбиений.

Введение.

Глава 1. Проблемы моделирования рефлексивного группового поведения

1.1. Модели информационной и стратегической рефлексии, рефлексивные игры.

1.2. Модели коллективного поведения, теория команд.

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

1.4. Модели эвакуации.

Глава 2. Метод рефлексивных разбиений в задачах коллективного поведения и управления.

2.1. Модель игровой ситуации.

2.2. Рефлексивные разбиения.

2.3. Рефлексивная модель коллективного поведения.

2.4. «Игра» однородных агентов.

2.5. Постановка задачи управления.

2.6. Прикладные модели рефлексивного коллективного поведения и управления.

Глава 3. Имитационные модели рефлексивного коллективного поведения

3.1. Система агентного имитационного моделирования.

3.2. Модели стратегического поведения.

3.3. Модели тактического поведения.

3.4. Имитационное моделирование эвакуации.

3.5. Имитационное моделирование диффузной бомбы.

Актуальность.темы. Традиционно в теоретико-игровых моделях и/или в моделях коллективного поведения используется? одно из- двух предположений о взаимной информированности агентов (ЛИР, программных и/или мобильных агентов и т.д.). Либо считается, что вся существенная информация иг принципы принятия агентами решений всем им известны, всем: известно,- что всем это известно; и т. д. до бесконечности (так называемая концепция общего знания^ используемая, например- при определении равновесия Нэша):.Либо предполагается, что каждый агент в рамках своей информированности следует некоторой: процедуре принятия индивидуальных решений и почти «не задумывается» над тем, что знают и как- ведут себя остальные агенты. Первый: подход является каноническим для теории игр, второй - для "моделей коллективного поведения. Но между двумя-.этими «крайностями» существует;достаточно большое разнообразие возможных ситуаций, в; которых; различные агенты могут обладать, различными рангами стратегической (используемой;при :принятии;;решений) рефлексии.

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

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

Достижение поставленной цели потребовало; решения следующих основных задач:

1. Разработка метода рефлексивных разбиений: для построения и анализа моделей стратегической^ рефлексии; - агентов, принимающих, коллективные решения;, ' , ■

2. Постановка и: анализ методов; решения; задачи : рефлексивного ' управленияшоведением взаимодействующих агентов.

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

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

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

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

Связь с. планом; Исследования по теме диссертационной работы проводились в соответствии с плановой тематикой работ ИПУ РАН в рамках координационных планов РАН.

Научная новизна. В результате проведенных исследований:

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

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

- с дескриптивной точки: зрения. — расширить множество ситуаций, которые в рамках модели могут быть «объяснены» как устойчивые исходы взаимодействия агентов; соответственно^ в рамках задач: управления -расширить, область управляемости;

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

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

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

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

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

Личный вклад-Все основные результаты получены автором.

Апробация работы. Результаты диссертационной работы докладывались на: семинарах УРАН Института проблем управления им. В.А. Трапезникова РАН, трижды (на конференциях № 51-53) на Всероссийской молодёжной научной конференции с международным участием «Современные проблемы фундаментальных и прикладных наук» проводимой в МФТИ, V и VI! Всероссийской школе-семинаре молодых ученых «Управление большими системами» (Липецк, 2008;Пермь, 2010), на XIII Международной конференции «Проблемы управления и моделирования в сложных системах» (Самара, 2011), Пятой международной конференции «Теория игр и менеджмент» (СТМ'2011).

Публикации. По теме диссертационной работы автором опубликовано 10 печатных работ общим объемом 12,5 печатных листов, в том числе.— 4 статьи в ведущих рецензируемых журналах.

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