Главная > Математика > Дифференциальные игры
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

8.5. ПОСТРОЕНИЕ БАРЬЕРА

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

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

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

Пример 8.5.1. Рассмотрим уравнения движения

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

Примем за верхнюю полуплоскость 0), а за — ось х Ясно, что скорость точки х равна векторной сумме двух скоростей, равных по модулю и направленных в соответствии с выбором игроков. Очевидно, что над где контролирует направление движения, а под этой кривой контролирует Тогда (должна быть барьером. На ней скорости игроков равны

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

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

Начиная с этого момента будем предполагать, что 3) лежит на и отмстим три различных возможных типа барьеров.

I. Естественные барьеры. Здесь служит границей допустимой области. С этой новой точки зрения полезно пересмотреть последнее понятие.

Пусть точка на и пусть ненулевой вектор, перпендикулярный к и направленный внутрь У. Условие

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

В каждой точке этой кривой, когда каждый из игроков играет оптимально, точка х перемещается (если она перемещается) по касательной к

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

Для построения используем начальные условия: Из того, что у — перпендикуляр к и совпадает с когда 38 встречается с следует, что эти поверхности касаются друг друга. Типичный случай изображен на рис. 8.5.1, а. Здесь замкнутая кривая на есть граница допустимой области, допустимая область лежит внутри нее. Барьер касается по

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

Рис. 8.5.1. (см. скан)

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

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

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

Рис. 8.5.2.

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

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

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

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

Рис. 8.5.3.

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

Не все части барьера годятся для решения рассматриваемого вопроса. Если барьер самопересекается или пересекаются некоторые образующие его траектории, то лежащие за пересечением части следует отбросить. Так, на рис. 8.5.3, а мы отрезаем отмеченные пунктиром части барьера область захвата — заштрихованный криволинейный треугольник. Замечательный пример такого явления, встречающийся в игре «шофер-убийца», будет обсуждаться в гл. 10.

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

II. Искусственные барьеры. Предположим, что сначала мы рассматриваем случай, когда имеет допустимую область (совпадающую, возможно, с а затем несколько изменяем игру, считая, что захват теперь означает достижение точкой х некоторого определенного подмножества на допустимой области; пусть это подмножество ограничено кривой 3. Чтобы построить барьер для новой игры, попытаемся провести полупроницаемую поверхность через 3. Полученный таким образом барьер мы как раз и будем называть искусственным барьером.

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

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

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

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

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

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

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

Теорема 8.5.1. Пусть дифференциальная игра размерности 3, для которой выполняются следующие условия:

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

2. В игре одного игрока для которой уравнения движения имеют вид

а пространство игры есть имеется полупроницаемая поверхность, которую мы обозначим через 3.

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

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

4. Полупроницаемую поверхность можно построить стандартным способом (см. § 8.3) с кривой 3) в качестве начальной.

Тогда можно построить таким образом, чтобы и составляющие ее оптимальные траектории касались 3), и оптимальные значения для совпадали бы с этими значениями на в точках из

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

Пусть вектор нормали к лежащий в Обозначив

запишем условие полупроницаемости кривой

где доставляет минимум функции

Лежащий в вектор нормали к который можно использовать как начальный для есть для некоторого Обозначив

напишем условие полупроницаемости для на

Из (8.5.5) следует, что

а из (8.5.4), что

Если бы по крайней мере одно из этих неравенств было строгим, мы бы имели

что противоречит (8.5.3).

Следовательно, оба соотношения (8.5.6) представляют собой равенства. Из второго и из условия 3 мы заключаем, что при построении можно использовать вместо Из условий 1 и 3 следует, что на совпадает с на Таким образом, оптимальные траектории на и в точках их соединения одинаковы. Это означает также, что в этих точках равны, что в свою очередь обеспечивает касание.

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

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

Выполнение условия 3 обязательно. В качестве примера можно использовать упражнение 8.3.1 (считая Ясно, что можно взять Полагая получаем для Но если читатель сделал упражнение, то он знает, что на и что это отношение стремится к нулю в окрестности кривой Эта разрывность оптимального устраняет касание траекторий с и теорема здесь неверна.

Отметим, что вместе со своей границей образует полупроницаемую поверхность.

Следствие 8.5.1. Если касается границы допустимой области, то ее касаются и лежащие на оптимальные траектории.

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

Пусть минимакс достигается при В силу 3 можно считать (после выбора некоторой ветви, если это необходимо), что единственны в окрестности «стыковки» и границы допустимой области. Тогда в некоторой точке К этого множества они должны быть равны

Таким образом, в окрестности точки К на границе допустимой области мы имеем определенные Если они

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

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

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

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

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

Проблема 8.5.2. Пусть на рис. 8.5.3, б К — точка границы допустимой области, которая отделяет траектории, опускающиеся под от траекторий обычного вида. Можно ли в общем случае провести 3 через К и построить барьер-огибающую, содержащий траектории, которые продолжали бы оптимальные траектории естественного барьера?

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

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

В дальнейшем нам потребуется

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

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

Доказательство. Поскольку управление не оптимально для полупроницаемой поверхности, применяя добивается проникновения х сквозь 3 и попадания на сторону, примыкающую к области избежания захвата. Скорость х соответствует скорости для игры и направлена по касательной к Так как 3 лежит в недопустимой области, разумеется, имеет в своем распоряжении такое которое приводит к проникновению внутрь при использовании противником В силу предположения о замкнутости (§ 2.7) любая замкнутая линейная комбинация из принадлежит вектограмме для Если игрок выберет с коэффициентом, близким к 1, а с достаточно малым коэффициентом, то суммарное будет обладать нужными свойствами.

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

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

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

<< Предыдущий параграф Следующий параграф >>
Оглавление