Параллельное преследование

Аннотация

 

В данном курсовом проекте изучалась  задача простого преследования с  одним преследователем и несколькими убегающими. Указываются основные определения и рассматриваются две задачи простого преследования одним преследователем.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  1. Геометрия простого движения

 

    1.  Основные понятия  и обозначения

 

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

Простое движение. Простым движением называется такое движение, при котором расстояние пройденное игроком из начального положения, является линейной функцией от времени s(t)=ρt, где t – время, в течение которого происходило движение, s(t) – путь, пройденный игроком из начального положения, ρ – путь проходимый игроком в единицу времени, называется линейной скоростью. При простом движение ρ является постоянной и не зависит от времени.

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

Игра  на преследование с простым движением. Такая игра, в которой движение любого игрока – это простое движение

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

Решение игры. Найти решение игры – значит определить оптимальную стратегию для всех участников игры и найти оптимальное время преследования.

Оптимальное время преследования. Время преследования называется оптимальным, если выполняются следующие условия:

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

Множество достижимости – это область плоскости каждую точку, которой игрок может достичь не позже чем за время, двигаясь по какой-либо траектории по закону простого движения.

 

 

 

 

 

    1.  Множество достижимости, окружность и точка Аполлония

 

      1. Множество достижимости

 

Множество достижимости – это область плоскости каждую точку, которой игрок может достичь не позже чем за время, двигаясь по какой-либо траектории по закону простого движения.

Лемма 1. Множество достижимости игрока P представляет собой круг с центром в точке P(0) и радиусом ρt.

 

      1. Окружность и точка  Аполлония

 

Пусть преследователь P и убегающий E перемещаются по плоскости в соответствии с простым движением с постоянными линейными скоростями   ρ и σ, ρ>σ>0, и в начале игры |P(0)E(0)|=b 0.

Предположим, что игрок E, начиная с момента времени перемещается по полупрямой . Пусть игрок P зная это направление движения игрока E, начиная с момента , перемещается по некоторой прямой , обеспечивая встречу с E в точке М. Тогда должно выполнятся неравенство: ρ|E(0)M|=σ|P(0)M| (1).

Лемма 2. Геометрическое место точек M=(x, y), удовлетворяющее уравнению (1), является окружностью.

Окружность S называется окружностью Аполлония, соответствующая положениям P(0)=(0, -b) и E=(0, 0), где , .

Лемма 3. Пусть М – некоторая точка на окружности Аполлония S и игроки P и Е перемещаются по полупрямым и . Тогда для каждого t, 0<t<|E(0)M|/σ, отрезок параллелен отрезку .

Лемма 4. Пусть М – некоторая точка на окружности Аполлония S и игрок Е перемещаются по полупрямым . Тогда преследователь P не может осуществить встречу с E до момента времени |E(0)M|/σ, т.е. |E(0)M|/σ наименьшее время, за которое P может осуществить встречу с E.

 

      1. Стратегия параллельного сближения

 

Пусть преследователь P и убегающий Е перемещаются на плоскости в соответствии с простым движением с постоянными линейными скоростями ρ и σ, ρ≥σ>0. Систему координат на плоскости выберем таким образом, чтобы в момент времени t=0 игроки P и E находились в положение P(0)=(0, -b) и E=(0, 0), где b=|P(0)E(0)|>0.

Пусть игрок E, начиная с момента времени t=0, перемещается по полупрямой, т.е. с вектор скоростью , , в свою очередь игрок P, начиная с момента времени , движется с вектор скоростью , т.е. по полупрямой .

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

Если игрок Е в некоторый момент времени снова изменит направление движения, то игрок P изменит направление своего движения вышеописанным способом.

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

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

Лемма 5. Пусть ρ>σ, М некоторая точка на окружности Аполлония S и игрок Е перемещаются по полупрямым . Тогда П-стратегия предписывает для P движение по полупрямой .

Лемма 6. Пусть ρ>σ≥0; тогда для любого , , имеет место неравенство

 

  1. Групповое преследование

 

    1.  Преследование двух убегающих одним игроком

 

Три точки: преследователь и преследуемые и , обладая постоянными линейными скоростями, перемещаются на плоскости, имея при этом возможность в каждый момент времени менять направление своего движения. Пусть α – линейная скорость преследователя, а – линейная скорость убегающего. Скорости игроков произвольны, и существенно лишь то, что α .

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

Пусть преследователь выбирает один из двух способов поведения:

  1. Использует правило параллельного сближения, преследует сперва , затем (стратегия );
  2. Использует правило параллельного сближения, преследует сперва , затем (стратегия );

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

Геометрическое  место точек встречи  игроков и при их движение по прямым со скоростями α и есть окружность Аполлония D:

 где - начальное местоположение игрока .

Обозначим через  местоположение преследователя в момент времени t, а через местоположение убегающего в момент времени t (k=1,2).

Предположим, что  преследует , а затем . Рассмотри случай когда, траекториями движения являются полупрямые, выходящие из , а движется в противоположную от сторону по прямой (стратегия ), где N – точка встречи P c . Определим, к какой точке окружности Аполлония должен двигаться игрок , что бы время поимки было максимальным.

Пусть – время встречи P c , - время встречи P c при параллельном сближение из позиций , тогда

 

  • время поимки преследователем P убегающих

Справедливо равенство  (рис. 1)  

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

Так как (рис. 2.) для всех точек N дуги для всех точек N дуги , то достаточно найти точку , на которой достигается

 

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

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

Задача  сводится к нахождению

 

Покажем, что  максимум достигается в точке .

Замечание. При гомотетии эллипса с центром в точке , он переходит в эллипс , причем касаются в точке . Если коэффициент гомотетии , то выпуклая область G, ограниченная , содержит , если же , то лежит вне G (если уравнение имеет вид , то уравнение эллипса имеет вид  где

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

Следовательно,  

 

достигается в точке .

Итак, |. Тогда для всех т.е. точка действительно доставляет максимум (1).

Аналогично, если P преследует , а затем , то  двигаться к точке , где . Очевидно, убегающий должен двигаться по прямой  в противоположную от P сторону.

 

Теорема. В рассмотренной игре существует ситуация равновесия. Оптимальная стратегия игрока P выбирается из условия

, а оптимальная стратегия  игрока  является программная стратегия . Значение игры равно

.

    1. Преследование трех убегающих одним игроком

 

Рассмотрим случай, когда преследователь преследует трех убегающих E= и в начале игры выбирает некоторый порядок преследования (. Пусть α – линейная скорость преследователя, а – линейная скорость убегающего. Скорости игроков произвольны, и существенно лишь то, что α .

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

Мы получили, что игрок должен двигаться к точке (пересечение окружности Аполлония и эллипса с фокусами в точках ), двигается по прямой . Как только происходит поимка игрока , игрок меняет направление своего движения. Игрок должен двигаться к точке (пересечение окружности Аполлония и эллипса с фокусами в точках ), двигается по прямой . Преследователь применяет стратегию параллельного сближения.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Литература

 

  1. Петросян Л.А., Преследование на плоскости // Петросян Л.А., Рихсеев Б.Б., – М.: Наука. Гл. ред. физ.-мат. лит., 1991. – 96 с. – (Попул. лекции по мат.; Вып. 61)
  2. Петросян Л.А., Томский Г.В. Геометрия простого преследования. М.: Наука, 1983, 140 с.

 


Параллельное преследование