1.5. ИГРЫ ПРЕСЛЕДОВАНИЯ

Много примеров игр преследования можно привести из области военного дела: торпеда и корабль, корабль и подводная лодка, ракета и бомбардировщик, танк и «джип».

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

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

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

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

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

Часто в качестве платы удается выбрать такую непрерывную величину, что она автоматически содержит в себе определенный выше дискретный критерий. Например, предположим, что нас интересует только один вопрос: может ли быть осуществлен захват? В качестве платы можно взять время захвата, причем цель сделать это время по возможности меньшим, а цель по возможности большим. Бесконечное время соответствует случаю, когда захват неосуществим. Тогда, если действует в соответствии с этим предписанием, он, конечно, достигнет своей основной цели всякий раз, когда захват осуществим. Притом он

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

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

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

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

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

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

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

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

Рис. 1.5.1.

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

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

На рис. 1.5.1 С есть область расположения объекта, который защищает от атакующего врага оба совершают простое движение с одинаковой скоростью и начинают двигаться из положения, изображенного на рисунке. Примем здесь для простоты, что захват означает совпадение точек Платой является расстояние от точки захвата до С (если захват возможен); должен максимизировать это расстояние, а

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

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

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

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

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

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

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

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

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

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

Нас интересуют два вопроса.

1. Игра качества. Когда может поймать Ясно, что если велико, I мало и не очень превышает то всегда может избежать захвата. Можно считать, например, что он делает это, просто отступая в сторону всякий раз, когда появляется угроза захвата. Ограничение кривизны траектории преследователя запрещает ему слишком резкие повороты. Он может промчаться мимо вернувшись обратно для новой попытки, может быть снова обманут тем же маневром

Задача состоит в том, чтобы определить точные условия: значения которые разграничивают эти возможности. Это будет сделано в примере 9.1 и в гл. 10.

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

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

по этой дуге, делая максимально крутой поворот вправо — до точки где его скорость направлена на Далее он движется по касательной, как показано. Соответственно движется по той же касательной, и это простое преследование продолжается вдоль прямой вплоть до свершения захвата, скажем, в точке С.

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

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

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

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

Такой тип преследования будет называться маневром разворота. Он составляет наиболее интересный с точки зрения математики аспект игры степени. Но каково точное решение и как его найти? Каковы точные оптимальные траектории Ответы на эти вопросы приведены в гл. 10.