Об одном альтернативном утверждении относительно исхода дифференциальной игры "наведения–уклонения" нескольких лиц в классе "контр"-стратегий

Рассмотрение позиционной дифференциальной игры "наведения-уклонения" нескольких лиц. Формализация игры в классе "контр"-стратегий, стабильные мосты. Приведение фазового вектора игры на свое целевое множество. Динамика конфликтно-управляемого объекта.

Рубрика Программирование, компьютеры и кибернетика
Вид статья
Язык русский
Дата добавления 26.04.2019
Размер файла 255,9 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Об одном альтернативном утверждении относительно исхода дифференциальной игры "наведения-уклонения" нескольких лиц в классе "контр"-стратегий

С.В. Лутманов

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

Ключевые слова: "чистые" стратегии; "контр"-стратегии; стабильный мост; теорема об альтернативе.

1. Постановка дифференциальной игры "наведения-уклонения" нескольких лиц в классе "контр"-стратегий© С. В. Лутманов, 2011

Динамика конфликтно-управляемого объекта описывается обыкновенным векторным дифференциальным уравнением

, (1.1)

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

Относительно правых частей дифференциальных уравнений (1.1) принимаются стандартные в теории дифференциальных игр предположения:

локальные условия Липшица

.

2) условия продолжимости решения

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

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

2. Формализация игры в классе "контр"- стратегий

Формализуем дифференциальную игру нескольких лиц в классе контр-стратегий.

Определение 1. Позиционной "контр"-стратегией -го игрока называется произвольная функция

,

где .

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

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

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

.

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

Пусть - согласованный набор позиционных "контр"-стратегий и - конечное разбиение отрезка времени точками .

Определение 3. Ломаной Эйлера , выходящей из позиции и порожденной набором позиционных "контр"-стратегией , назовем всякую абсолютно непрерывную функцию , удовлетворяющую дифференциальному уравнению

,

, (2.1)

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

, равномерно сходящаяся к ней на отрезке при условии .

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

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

,

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

.

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

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

.

3. Стабильные мосты

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

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

первый игрок применяет "контр"-стратегии;

второй игрок применяет "контр"-стратегии.

Определение 5. Множество будем называть -ста-бильным мостом, обрывающимся на множестве , если оно является стабильным мостом первого игрока [3], в антагонистической игре и при этом выполняется вложение

.

Дадим расшифровку приведенного определения.

Множество будет -стабильным мостом, , если для любых позиций , отображений ,

ставящих каждому вектору в соответствие набор векторов

и моментов времени , найдется такое решение дифференциального уравнения в контингенциях

для которого .

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

Лемма 1. Пусть максимальный -стабильный (-стабильный [3]) мост, обрывающийся на множестве . Тогда для любого найдется такое, что будет выполнено

.

Здесь максимальный -стабильный (-стабильный) мост, обрывающийся на множестве . Множество представляет собой замкнутую -окрестность множества .

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

,

где . Каждое из множеств замкнуто и ограничено, так как оно образовано пересечением двух замкнутых множеств, одно из которых ограничено.

Из монотонного убывания последовательности положительных чисел следует, что для любых номеров выполнено вложение . Отсюда в силу [2] выводим, что

.

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

По теореме об альтернативе [1] в игре (игре )

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

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

, .

Дадим расшифровку приведенного определения.

Множество будет -стабильным мостом, , если для любых позиций , отображений ,

ставящих каждому набору векторов

в соответствие вектор , и моментов времени найдется такое решение дифференциального уравнения в контингенциях

, для которого .

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

4. Экстремальное прицеливание

Пусть замкнутое множество.

Определение 8. "Контр"тратегия -го игрока называется экстремальной к множеству , если она является экстремальной стратегий первого игрока к множеству в игре

.

Дадим расшифровку приведенного определения. Полагаем

.(4.1)

В случае когда точек , доставляющих в (4.1), более одной, берется любая из них.

"Контр"-стратегия будет экстремальной к множеству , если

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

произвольный вектор из множества .

Лемма 2. Пусть замкнутый -стабильный (-стабильный) мост в дифференциальной игре "наведения-уклонения" нескольких лиц, "контр"-стратегия ("чистая" стратегия [3]) является экстремальной к множеству и . Тогда для всякого движения , () будет выполнено включение для всех , если при всех .

Справедливость данной леммы следует непосредственно из лемм 82.1, 82.2 книги [1].

Пусть система попарно непересекающихся открытых множеств.

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

,

,

где .(4.2)

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

Заметим, что в силу условия набор "контр"-стратегий игроков, экстремальный к системе множеств является согласованным.

Лемма 3. Пусть система попарно непересекающихся открытых множеств является -стабильной [3] (-стабильной). Набор "контр"-стратегий ("чистых" стратегий [3]) всех игроков экстремален к системе множеств

, и

.

Тогда для любого номера и всякого движения (движения ), будет выполнено включение

для всех , если

при всех .

Справедливость данной леммы следует непосредственно из лемм 82.1, 82.2 книги [1].

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

Определение 10. Будем говорить, что в начальной позиции "чистая" стратегия ("контр"-стратегия ) -го игрока , решает задачу наведения на целевое множество этого игрока, если для всех (для всех ) выполнено включение .

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

.

Лемма 4. Пусть выполнено условие

Тогда где максимальный -стабильный мост (-стабильный мост), обрывающийся на множестве .

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

(),

.

().

С другой стороны, справедливо вложение

().

Для любого

,

()

должно выполняться

.

Последнее невозможно, что и доказывает справедливость леммы.

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

1) существует номер , что ;

2) ,

где максимальный -стабильный (-стабильный мост), обрывающийся на множестве .

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

().

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

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

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

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

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

Список литература

1. Красовский Н.Н., Субботин А.И. Позиционные дифференциальные игры. М.: Наука, 1974. 456 с.

2. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. М.: Наука, 1976. 544 с.

3. Лутманов С.В. Об одном альтернативном утверждении относительно исхода дифференциальной игры "наведения-уклонения" нескольких лиц в классе "чистых" и "смешанных" стратегий // Вестн. Перм. ун-та. Сер. Математика. Механика. Информатика. 2011. Вып. 1(5). С.53-61.

Размещено на Allbest.ru


Подобные документы

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

    контрольная работа [716,7 K], добавлен 11.06.2011

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

    курсовая работа [629,3 K], добавлен 08.10.2014

  • Разработка компьютерной игры "Эволюция" с помощью игрового движка Unit. Сравнение критериев игры-аналога и разрабатываемой игры. Разработка графического интерфейса пользователя. Настройки камеры в редакторе Unity. Структура файла сохранения игры.

    дипломная работа [3,6 M], добавлен 11.02.2017

  • Основные подходы при создании Windows приложений. Изучение навыков работы с 2D графикой в Windows приложениях. Методы генерации псевдослучайных чисел. Разработка игры "Сапер" с расположением мин на основе нескольких методов генерации случайных чисел.

    курсовая работа [63,2 K], добавлен 18.02.2009

  • Алгоритмическое представление и описание правил игры "Эволюция". Построение диаграммы прецедентов. Разработка графического интерфейса пользователя. Реализация интерфейса в среде Unity. Структура файла сохранения игры. Проектирование поведения компьютера.

    дипломная работа [3,3 M], добавлен 18.02.2017

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

    дипломная работа [1,6 M], добавлен 27.10.2013

  • Проект игры "Ловушка", созданный при помощи языка программирования C++. Описание заголовочных файлов. Правила и цель игры "Ловушка". Отображение движущихся объектов игры на экране с помощью заголовочного файла "gameclass.h". Описание игрового процесса.

    курсовая работа [70,6 K], добавлен 14.10.2012

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

    дипломная работа [2,7 M], добавлен 27.10.2017

  • Разработка и создание игры "Змейка". Использование динамически-активных принципов языка Java. Графические объекты программы. Описание игры, правила, теоретические сведения. Классы приложения. Типы данных. Реализация. Метод. Объект. Блок-схема игры.

    курсовая работа [12,4 K], добавлен 18.06.2008

  • Исследование спецификации логической игры "Сапёр". Системное и функциональное проектирование приложения. Разработка программных модулей. Обзор классов, необходимых для создания интерфейса данного приложения. Инструменты для реализации логической игры.

    курсовая работа [1,2 M], добавлен 13.01.2016

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.