Одна динамическая игра управления агентами в сети

Введение 3
Постановка задачи 5
Обзор литературы 6
Глава 1. Основные понятия 8
1.1 Многошаговая игра с полной информацией 8
1.2 Алгоритм Дейкстры 10
Глава 2. Постановка игры управления агентами в сети 12
2.1 Общая сетевая структура 12
2.2 Подвижный агент: дрон 13
2.3 Альтернативы и выигрыши 14
2.4 Пример игры 15
2.5 Условие существования равновесия по Нэшу 18
Глава 3. Описание программного обеспечения 21
3.1 Постановка задачи для программного обеспечения 21
3.2 Обоснование подхода к решению задачи 21
3.3 Описание архитектуры программы 22
Глава 4. Тестирование программы на примере игры двух лиц .... 23
4.1 Постановка игры 23
4.2 Результат при условии, что первым «ходит» первый игрок . 23
4.3 Результат при условии, что первым «ходит» второй игрок . . 25
4.4 Вывод 25
Заключение 27
Список литературы 28
Приложение 29
Купить

В работе введена новая постановка некооперативной многошаговой игры управления агентами в сети. Сетевая структура описывается графом, где вершинами являются агенты, а ребра определены как устойчивые связи между агентами [1]. Выигрыш каждого игрока зависит от диаметра под­графа, определенного на вершинах, принадлежащих игроку. Диаметром графа является длина кратчайшего пути между двумя наиболее удален­ными друг от друга вершинами. Диаметр графа используется для оценки максимального времени, требующегося для доставки пакета информации от одного агента к другому.
В данной работе будем предполагать, что каждый каждый игрок име­ет в своем распоряжении одного подвижного агента, который может быть расположен в любой допустимой позиции для образования нового подгра­фа. Целью каждого игрока является уменьшение диаметра результирую­щего расширенного подграфа.
Актуальность данного подхода определяется практической значимо­стью рассмотренной задачи в приложениях, связанных с самоорганизую­щимися одноранговыми мобильными сетями (MANET) [2]. MANET - сеть, без заранее определенной структуры, которая состоит из набора беспровод­ных мобильных узлов или хостов (роль которых, в данной работе, берут на себя агенты игроков). Правильная организация сети MANET играет ключевую роль в таких задачах как восстановление связи в местах при­родных катастроф (землетрясений, наводнений и т. п.), координирование действий спасательных отрядов и т. д. Одной из самых важных проблем, связанных с построением данной сети, является разумное использование ограниченных ресурсов, таких как электромагнитный спектр частот ра­диоволн, время работы аккумуляторов и т. п. Неразумное использование этих ресурсов может привести к ухудшению производительности всей сети в целом. Большая часть исследований, проведенных с применением тео­рии игр в области мобильных сетей, связано с обнаружения вредоносных или не приносящих пользу узлов. В данном же исследовании используется другой подход: рассматривается совместный сценарий поведения узлов для достижения максимальной выгоды.
Основной особенностью данного типа сетей является возможность ре­организовывать структуру сети (топологию, пути передачи данных, рас­пределение спектра и т. д.), основываясь на знаниях предыдущих этапов построения. Таким образом, с течением времени общая производительность сети (скорость доставки пакетов информации, расходы на доставку пакета и т. п.) будет расти.
Все узлы сети имеют некоторую область взаимодействия с други­ми узлами. Таким образом, последовательность узлов может образовывать канал (путь) для передачи данных. Большое количество промежуточных узлов в таком пути может отрицательно сказаться на скорости передачи данных. Или, в некоторых случаях, препятствия на пути (озера, обломки и т. п.) могут вызвать его разрыв. Одним из эффективных способов умень­шения нагрузки на канал или его восстановления является использование беспилотных летательных аппаратов - дронов.
Предметом данного исследования является поиск наилучшего места для внедренных мобильных агентов (дронов). Под наилучшим местом по­нимается такое место, что помещение туда дрона приводит к увеличению производительности сети, а именно уменьшение длины канала передачи данных [3]. В данной задаче жестко ограничено число доступных беспи­лотных летательных аппаратов. В процессе самоорганизации сеть самосто­ятельно определяет оптимальное место для помещения в него подвижного узла. В итоге, две части одного маршрута, состоящие из промежуточных неподвижных узлов, будут соединены между собой беспилотником.
Так как сеть MANET предполагает динамическую топологию: в каж­дый момент времени сеть самостоятельно определят как использовать бес­пилотник наилучшим образом, было принято решение, в качестве инстру­мента исследования, применять теорию позиционных игр [4], [5]. Особенно­стью данного класса игр является учет динамики конфликтно - управляе­мого процесса. Класс конечношаговых игр с полной информацией является одним из классов позиционных игр. Данный класс игр теоретически позво­ляет построить граф игры, наглядно демонстрирующий поведение игроков в конкретных ситуациях. Для класса конечношаговых игр вводится по­нятие абсолютного равновесия по Нэшу, что является усилением понятия равновесия по Нэшу для игр в нормальной форме.
Купить