Задача убегания в линейных параметрических дискретных играх

Полный текст

1. Введение Дискретные игры занимают важное место в теории игр. В фундаментальной монографии основателя теории дифференциальных игр Р. Айзекса указана важность исследования дискретных игр с точки зрения их практических приложений [13, с. 65]. Источником дискретных игр являются непрерывные (континуальные) дифференциальные игры или самостоятельно возникающие в различных прикладных областях дискретные конфликтно управляемые процессы и их модели. Основные постановки задач в дифференциальных и дискретных играх изложены в [6, 13, 14]. Дискретные дифференциальные игры начали интенсивно развиваться в работах [2, 7, 10-12]. Нелинейным дискретным играм посвящены работы [1, 7, 8]. Различные стороны, особенности и приложения дискретных конфликтно управляемых процессов (игр) исследованы в [3-5, 9, 15]. В данной работе рассмотрены линейные дискретные игры с входящим в уравнения параметром, для которых получены достаточные условия убегания из любых допустимых начальных позиций. Для известной в теории дифференциальных игр задачи «Изотропные ракеты»-«Мальчик и крокодил» [6, 13] получен новый дискретный аналог, к которому применены основные результаты работы по решению задачи убегания. 2. Постановка дискретной задачи убегания 2.1. Основные определения и формулировка игровых задач. В пространстве Rn рассматривается движение вектора , которое описывается линейным дискретным уравнением: z((k + 1)τ) = A(τ)z(kτ) + B(τ)u + D(τ)v, (2.1) где- параметры, u ∈ P ⊂ Rp, v ∈ Q ⊂ Rq; P и Q - компакты, содержащие в себе начала несущих пространств (0p ∈ P, 0q ∈ Q); A(τ), B(τ) и D(τ) - матрицы размерностей n×n, n×p и n×q соответственно, зависящие от параметра. Терминальное множество M ⊂ Rn - непустое и замкнутое. Уравнение (2.1) носит описательный характер и приобретает конкретный смысл, если будут указаны правила выбора параметров. Параметр τ 0 после выбора фиксируется. Параметры u и v выбираются двумя сторонами, их традиционно называют игроками -преследователем и убегающим. Цели игроков в общем случае являются не совпадающими. Игра начинается из начальной позиции z0 ∈/ M. Убегающий игрок стремится уклонить бесконечно долго от терминального множества M дискретную траекторию z(kτ), k = 1,2,... , при любом возможном поведении преследователя. Цель преследователя - добиться включения z(kτ) ∈ M при некотором. 2.2. Пошаговый процесс убегания. Опишем более детально процесс игры. Дискретная игра убегания (2.1) проходит пошагово. На шаге 1 полагают k = 0 и фиксируется некоторое значение параметра τ > 0. Считаем, что начальная позиция z0 задана, известна обоим игрокам и z0 ∈/ M. Полагаем z(k = 0) = z0, и пусть преследующий игрок выбирает в соответствии с (2.1) произвольно свое управление u1 = u((0 + 1)τ) = u(τ) ∈ P, которое по правилам игры становится известным убегающему игроку. Убегающий игрок на основе известных ему z0 и u1 = u(τ) так строит на шаге 1 свое управление v¯1 = v((0+1)τ) = v(τ) ∈ Q, чтобы соответствующее выбранным управлениям и начальной позиции решение уравнения z = A(τ)z(0) + B(τ)u1 + D(τ)¯v1 (2.2) не принадлежало терминальному множеству M. Заметим, что уравнение (2.2) может иметь несколько решений z, тогда выберем из них по какому-нибудь правилу одно, например, лексикографическим способом [5, с. 217]. Обозначим найденное решение через z(τ), тогда, обозначив z(τ) = z1, получим, что z1 = z(τ) = A(τ)z(0) + B(τ)u1 + D(τ)¯v1. (2.3) Таким образом, в результате первого шага, точка z0 под действием выбранных игроками управлений u1 и v¯1 перейдет согласно (2.2) в положение z(τ), удовлетворяющее (2.3). Заметим, что на самом деле v¯1 = ¯v1(τ,z0,u1), т. е. убегающий игрок строит свое управление на основе знания управления преследователя, выбранного им на данном шаге, и позиции z0 (ср. [1, 2, 7, 8, 10, 11]). На шаге 2 полагают k = 1, и убегающему игроку становятся доступными позиция z(0 + τ) = z(τ) = z1 ∈/ M, полученная на шаге 1, и выбранное преследователем на этом, втором шаге, управление u2 = u(2τ) ∈ P. На их основе убегающий игрок строит свое управление v2 = v2(2τ,z1,u2) ∈ Q так, чтобы z(2τ) ∈/ M, где z2 = z(2τ) выбрано (однозначным способом) из решений уравнения z = A(τ)z(τ) + B(τ)u2 + D(τ)¯v2. (2.4) Продолжая этот процесс индуктивно, получаем, что на n-м шаге,, убегающий игрок строит свое управление так, чтобы zn-1 = z((n - 1)τ) переходило в состояние (единственное) (2.5) и выполнялось В результате изложенного описания пошагового хода игры, начинающейся из начальной позиции z0 = z(0) ∈/ M, получаем, что z0 и (2.5) порождают последовательность точек z0,z1,z2,..., не принадлежащих терминальному множеству. Для каждой точки выбирается управление, обеспечивающее переход из рассматриваемой точки в следующую (по номеру шага) точку, которая не попадает на терминальное множество. Это управление для каждой точки строится по информации о ней (полное знание позиции) и текущему управлению в рассматриваемый момент времени (шаг). Другими словами, выбор управления убегающего игрока на каждом шаге зависит от позиции системы (2.1), сложившейся на предыдущем шаге, и управления преследователя, выбираемого ЗАДАЧА УБЕГАНИЯ В ЛИНЕЙНЫХ ПАРАМЕТРИЧЕСКИХ ДИСКРЕТНЫХ ИГРАХ им на рассматриваемом шаге. В результате дискретная система (2.1) переходит из состояния zk в состояние. Перейдем к более точным формулировкам задач игроков. Будем говорить, что убегающий игрок решил задачу убегания из заданной начальной точки z0 ∈/ M при значении параметра τ > 0, если для каждой последовательности управлений можно построить такую последовательность управлений, что соответствующие решения zn уравнения (2.5) не попадают на M при всех по условиям убегания (нулевой или начальный шаг выполняется автоматически). Если уклонение возможно из любой точки z0 ∈ Rn\M, то будем говорить, что в дискретной параметрической игре (2.1) возможно убегание при заданном значении параметра. Далее, нужно определить достаточные условия, при которых пошаговый процесс (метод) убегания в игре (2.1) может быть реализован. 3. Основной результат Пусть терминальное множество задано в виде: , (3.1) где ni - заданные единичные векторы, αi - действительные числа, i = 1,2,... ,m. Обозначим . (3.2) Теорема 3.1 (об убегании). Пусть для заданного значения параметра τ > 0 множество E(τ) ⊂ M. (3.3) Тогда в дискретной игре (2.1) из любой начальной позиции z0 ∈/ M возможно убегание пошаговым способом. При этом на каждом шаге n = 1,2,3,... убегающий игрок использует информацию о состоянии позиции на предыдущем шаге zn-1 = z((n - 1)τ) и управлении u(nτ) ∈ P, которое преследователь принимает на том же n-м шаге. В результате система (2.1) переходит из позиции zn-1 ∈/ M в положение zn = z(nτ) ∈/ M и, тем самым, возможно убегание из любой начальной позиции (точки) z0 ∈/ M. Доказательство. Из условия E(τ) ⊂ M следует, что если z /∈ M, то z /∈ E(τ), значит, minmaxmax[< ni,F(τ,z,u,v) > -αi] > 0. (3.4) u v i Из (3.4) следует, что для каждого z /∈ M, u ∈ P и фиксированного τ > 0 найдется единственный вектор v¯(τ,z,u) ∈ Q такой, что хотя бы для одного номера i = 1,2,... ,m будет выполняться неравенство: < ni,F(τ,z,u,v(τ,z,u)) > -αi > 0. (3.5) Как и выше, вектор v(t,z,u) можно выбрать однозначным (лексикографическим) способом [5]. Неравенство (3.5) будет играть основную роль при выборе управления убегания в пошаговом процессе убегания от терминального множества M, заданного в виде (3.1). Пусть на первом шаге игра начинается из начальной позиции z0 = z(0) ∈/ M и преследователь выбрал u1 = u(τ) ∈ P. Тогда убегающему игроку предлагается выбрать управление v¯1 = v1(τ,z0,u1) ∈ Q таким образом, чтобы оно удовлетворяло (3.5) при каком-либо i = 1,2,... ,m, т. е.: . (3.6) Отсюда будет следовать, что z1(τ) = F(τ,z0,u1,v1) = A(τ)z(0) + B(τ)u1 + D(τ)v1. (3.7) Продолжая индуктивно (пошагово) процесс, получим следующее: на n-м шаге,, процесс убегания начинается из точки zn-1 = z((n - 1)τ) ∈/ M, и пусть преследователь на этом шаге выбрал управление un = u(nτ). Убегающий игрок на основе знания zn-1 и управления un = u(nτ) строит свое управление таким образом, чтобы выполнялось (3.6): , (3.8) откуда следует, что для точки (3.9) не выполняются условия включения в терминальное множество M. Из (3.8) и (3.9) получается, что при изложенном способе построения управления убегания на основе (3.5) точка zn(nτ) ∈/ M при всех n = 1,2,3,... , т. е. из начальной точки z0 в дискретной игре (2.1) возможно убегание. Поскольку начальная позиция z0 ∈/ M была произвольной, то убегание в дискретной игре (2.1) при заданном фиксированном параметре τ > 0 возможно. Теорема доказана. 4. Исследование дискретной игры «Изотропные ракеты»-«Мальчик и крокодил» [6, 13] 4.1. «Мальчик и крокодил» (непрерывный случай). В теории дифференциальных и дискретных игр многие игры имеют свои «персональные экзотические имена», например: «Изотропные ракеты», «Мальчик и крокодил», «Лев и человек», «Контрольный пример Понтрягина», «Полицейский автомобиль», «Дама в озере», «Волки и олень», «Успокоение-раскачка маятника» и многие другие [1, 6, 8, 13, 14]. Заметим, что не все названные игры исследованы достаточно полно в дискретном варианте [1, 8]. Возможными причинами этого являются преимущество математических методов анализа дифференциальных игр как непрерывных систем, а также недостаточно эффективный перенос результатов дифференциальных игр на соответствующие дискретные игры. Сформулируем дифференциальную игру «Мальчик и крокодил» [6], которая в книге Р. Айзекса [13] носит название «Изотропные ракеты». Пусть движение убегающего игрока («мальчик») происходит под действием ограниченной скорости, величина и направление которой могут меняться мгновенно. Движение преследователя происходит под действием ограниченной силы, направлением и величиной которой управляет преследователь. Ввиду инерционности движения преследователя, его называют «крокодилом» [6]. Математически движения игроков (x - преследователь, y - убегающий игрок) записываются в следующем виде: ; (4.1) где x,y,u,v - векторы из, точки в (3.8) означают производные по времени. Преследование считается завершенным, если в некоторый конечный момент времени будет x = y. В противном случае будем говорить, что осуществлено убегание. Замена переменных z1 = x - y, z2 = x,˙ переводит (4.1) в систему (4.2) Терминальное множество (множество точек окончания игры) определяется в виде: . (4.3) Задачей преследователя является попадание точки z(t) - решения (4.2) с помощью допустимых управлений (измеримых функций) в некоторый конечный момент времени на терминальное множество (4.3) при любом допустимом противодействии убегающего игрока, цель которого - противоположная. В такой постановке дифференциальная (непрерывная) игра (4.2)-(4.3) называется в литературе «Мальчик и крокодил», она исследовалась многими авторами [4, 6, 9, 11, 13, 14]. В теории дифференциальных игр эта игра является важным тестовым показателем эффективности применения новых методов решения задач преследования и убегания. В игре (4.2)-(4.3) «Мальчик и крокодил» активную роль будем предоставлять убегающему игроку, задачей которого является построение такого допустимого управления (измеримой функции), которое обеспечивает уклонение (убегание) от M из заданной допустимой начальной позиции на бесконечном интервале времени. ЗАДАЧА УБЕГАНИЯ В ЛИНЕЙНЫХ ПАРАМЕТРИЧЕСКИХ ДИСКРЕТНЫХ ИГРАХ 4.2. «Мальчик и крокодил» (дискретная игра с параметром). Перейдем от дифференциальной игры «Мальчик и крокодил» к ее дискретному аналогу. Этот переход, называемый в [13, с. 65] «квантизацией», можно осуществлять разными способами, некоторые из них изложены в [1]. Нами предлагается следующий способ квантизации непрерывной дифференциальной игры (4.2)-(4.3), отличный от ранее применявшихся. В начале запишем (4.2) в матричном виде: z˙(t) = Cz(t) + u(t) + v(t), (4.4) где , (4.5) O и I - нулевая и единичная матрицы порядка m, соответственно; 0m - начало Rm. Введем последовательность {tk,k = 0,1,2,3...}, tk+1 - tk = τ > 0,t0 = 0. При подстановке в уравнение (4.2) t = tk > 0, k = 1,2,3,... оно примет вид z˙(tk) = Cz(tk) + u(tk) + v(tk). (4.6) Теперь заменим в (4.6) производную ее приближенным значением: . (4.7) Замена (4.7), на наш взгляд, предпочтительнее в силу того, что в дифференциальных играх в каждый момент времени t известны, обычно, значения z(s) при которые в будущие моменты s > t не известны, так как позиция формируются двумя противоборствующими сторонами. Замена (4.7) учитывает этот факт. A(τ) = (I - τC)-1, B(τ) = τ(I - τC)-1, а u((k + 1)τ) и v((k + 1)τ) задаются на основе (4.5). Терминальное множество зададим в виде [8]: k = 0,1,2,... , (4.9) Подставляя правую часть (4.7) в уравнение (4.6), получаем дискретное уравнение с параметром типа (2.1) (ср. [1, 8, 10, 13]): z((k + 1)τ) = A(τ)z(kτ) + B(τ)[u((k + 1)τ) + v((k + 1)τ)], где (4.8) , (4.10) где- векторы, у которых только i-я координата равнаостальные координаты равны нулю; <,> - символ скалярного произведения. Терминальное множество M ограничено по первым m координатам 2m гиперплоскостями (с нормалями), по остальным m координатам ограничений не имеет. Дискретную игру (4.8)-(4.9) с терминальным множеством (4.10) будем называть дискретной игрой «Мальчик и крокодил», соответствующей (или ассоциированной) непрерывной дифференциальной игре (4.2)-(4.3). Напомним, что убегающий игрок стремится не попасть на каждом конечном шаге на M, т. е. на каждом шаге убегания хотя бы одна из координат точки z1 не должна удовлетворять неравенствам из (4.10). Для этой игры убегание будет означать непопадание на терминальное множество (4.10) на каждом шаге, и для этого достаточно невыполнения на каждом шаге одного из неравенств в (4.10). Проверим выполнимость условий теоремы 3.1 об убегании для задачи «Мальчик и крокодил» в дискретном варианте. Несложные вычисления показывают, что в (4.9) будет: . (4.12) Вычислим теперь множество E(τ) (формула (3.2)), которое для игры (4.8)-(4.10) будет выглядеть следующим образом: . (4.13) Далее, используя линейность уравнений дискретный игры (4.8), а также (4.11)-(4.12), нетрудно вычислить, что - - , (4.14) где индекс i означает номер координаты, дающей максимум в Из вида вычисленного множества E(τ) получаем, что . (4.15) Очевидно, что если выполнено квадратное неравенство ρτ2 - στ + l < 0, то из (4.13) следует, что E(τ) = ∅, и выполняется соотношение . Поэтому если параметры рассматриваемой игры l,τ,σ,ρ удовлетворяют неравенствам (4.16) то выполняются все условия теоремы 3.1 об убегании, а значит, в дискретной игре «Мальчик и крокодил» возможно убегание, реализуемое на основе пошагового метода убегания. Из (4.14) нетрудно получить различные соотношения между параметрами дискретной игры «Мальчик и крокодил», обеспечивающие возможность убегания от терминального множества M вида (4.10). Например, при фиксированных значениях параметров l, σ и ρ задача убегания в игре «Мальчик и крокодил» разрешима, если параметр где . (4.17) 5. Обсуждение результатов Отметим некоторые отличия в дискретных играх на примере «Мальчик и крокодил» в дискретном варианте. 1. Квантизация непрерывной игры «Мальчик и крокодил» приводит к двум разным уравнениям, одним из них является полученное выше уравнение (4.8) с пояснениями (4.9), которое запишется в виде: z((k + 1)τ) = (I - τC)-1{z(kτ) + τ(u((k + 1)τ) + v((k + 1)τ))}. (5.1) 2. Другое дискретное уравнение для задачи «Мальчик и крокодил» получено квантизациейв [1, с. 116] и имеет в наших обозначениях вид: z((k + 1)τ) = (I + τC)z(kτ) + B(τ)u(kτ) + D(τ)v(kτ). (5.2) Нетрудно видеть, что уравнения (4.15) и (4.16) существенно отличаются друг от друга, что приводит к необходимости аккуратно проводить квантизацию в целях получения достоверных результатов о непрерывных играх. С другой стороны, каждый из классов дискретных игр (4.15) и (4.16) можно рассматривать как самостоятельный объект, который при исследовании может дать свои собственные результаты. В заключение отметим, что уравнение (4.16) использовалось в [1] только для исследования задачи преследования.

Об авторах

Л. П. Югай

Узбекский государственный университет физической культуры и спорта

Автор, ответственный за переписку.
Email: yugailp@mail.ru
Чирчик, Узбекистан

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