Преследование на плоскости (стр. 1 из 3)
Учебно-исследовательская работа
«Преследование на плоскости»
Заключается задача в очень простой вещи. Есть преследователи, один или группа, и есть некто, кто пытается от них убежать. А нам важно понять – это очень просто убегать и догонять или это можно делать множеством способов отличающихся друг от друга эффективностью. И трудно ли найти наиболее эффективный (или оптимальный) способ погони или наоборот бегства.
Прежде чем приступать к анализу рассмотрим ситуацию, которая на первый взгляд кажется простой. Пусть некоторый кусок плоскости ограждён забором в форме окружности и в этом загоне лис пытается поймать кролика который бегает несколько быстрее лиса. Очевидно, что у лиса не было бы никаких шансов, если бы кролик имел возможность бежать по прямой. В этом случае при любой стратегии поведения лиса расстояние между ними бы только увеличивалось. Стена может быть причиной по которой кролику придётся развернуться и побежать в сторону лиса и здесь для лиса возникает уникальная возможность поймать кролика.
Однако эта возможность реальна только для очень специальной формы площадки и при не очень умном поведении кролика. Но и при самой простой форме – окружности у лиса есть интересная возможность не отстать от кролика даже при существенном различии в скоростях. Покажем, как он может это осуществить.
Предварительное замечание. Цель кролика находиться как можно дальше от лиса. Из этого следует, что при необходимости смены направления кролик должен осуществлять эту перемену так, чтобы его направление движения составляло не острый угол с направлением движения лиса (иначе он начнёт сближение). Необходимость же смены направления возникает при угрозе столкновения со стенкой. Максимально тупой угол кролик может обеспечить себе, двигаясь вдоль стенки. Отсюда следует, что при заборе имеющим форму окружности оптимально для кролика бежать по окружности как можно большего радиуса, то есть вдоль стены.
Как же в этом случае вести себя лису. Предположим, что у лиса скорость в два раза меньше. Тогда если он будет бежать по окружности центр которой будет совпадать с центром окружности кролика но длина её будет в два раза меньше, то за одно и тоже время и кролик и лис оббегут полную окружность и следовательно в каждый момент времени расстояние между ними будет равно разности Rк – Rл то есть независимым от времени. Что и требовалось доказать.
Интересный вопрос. Итак, мы выяснили, что один лис может не отстать от кролика, не означает ли, что группа лисиц (и может быть даже не очень большая) в состоянии кролика поймать.
Данный пример был призван показать, что задача не тривиальна и нуждается в тщательном исследовании, которым мы далее и займёмся. А для начала сформулируем ещё раз цель исследования:
Главная цель: Выяснить, существует ли оптимальная стратегия как для убегающего, так и для догоняющего и если да то, как её построить. А оптимальная стратегия – это такая стратегия, которая гарантирует наилучший результат независимо от поведения противника
Для того чтобы построить какую-либо теорию, мы должны строго описать основные понятия и объекты, а также сформулировать какие-то основные утверждения которые будут служить аппаратом для получения нового знания.
1 Основные понятия
Игра на преследование, убегающий игрок, группа преследователей – Это основные понятия, их смысл ясен интуитивно.
Простое движение. Простым движением называется такое движение, при котором расстояние пройденное игроком является линейной функцией от времени s(t)=kt. Для тех, кто хорошо изучал физику эта формула возможно ассоциируется с равномерным, прямолинейным движением. Однако это совсем не обязательно. Данная формула может описывать движение, в котором вектор (а наша формула скалярная, а не векторная) скорости с течением времени меняет направление, но не меняет своего модуля.
Игра на преследование с простым движением. Такая игра – это игра в которой движение любого игрока – это простое движение
Решение игры. Найти решение игры – значит определить оптимальную стратегию для всех участников игры и найти оптимальное время преследования.
Оптимальное время преследования. Время T преследования называется оптимальным если выполняются следующие условия:
1. При любом поведении убегающего игрока существует способ поведения преследователей гарантирующий встречу хотя бы одного из преследователей с убегающим игроком не позже времени T.
2. Для убегающего игрока существует способ поведения, гарантирующий невозможность встречи с преследователями раньше времени T.
Гарантированное время преследования. Если для времени Т выполнено только первое из условий описанных для оптимального времени преследования, то время Т это гарантированное время преследования.
Игра с линией жизни. Пусть область, в которой происходит игра представляет собой выпуклую область. Её граница называется линией жизни, а игра соответственно игрой с линией жизни, если цель убегающего игрока – достичь линии жизни, а цель преследователей соответственно не допустить этого события.
Множество достижимости – это область плоскости каждую точку которой игрок может достичь не позже чем за время Т двигаясь по какой-либо траектории по закону простого движения.
Зоны убегания и зоны встречи. Зона убегания – это множество точек плоскости в которых для убегающего игрока есть траектория убегания от преследователей. Соответственно зона встречи – это множество точек в которых не существует траектории убегания.
2 Несколько важных утверждений
Утверждение первое: Множество достижимости представляет собой круг.
Доказательство: Ясно, что самая удаленная точка множества достижимости (удалённая от исходной) это точка до которой игрок движется по прямой. Построим множество всех прямых проходящих через исходную точку. В силу однородности свойств плоскости движение вдоль одной из этих прямых ничем не отличается от движения вдоль другой прямой из чего следует, что на каждой из прямых самая удалённая точка множества достижимости находится на одинаковом расстоянии от исходной точки. А геометрическое множество точек находящихся на одинаковом расстоянии от некоего центра называется окружностью. В свою очередь геометрическое место точек ограниченных окружностью называется кругом, что и требовалось доказать.
Утверждение второе. Пусть убегающий игрок находится в некоторой точке, которую мы назовём исходной. Построим все возможные прямые через исходную точку. Пусть далее преследователь зная направление движения убегающего игрока, движется по прямой обеспечивающей встречу за минимальной время. Тогда множество всех точек встречи представляет собой окружность.
 |
 |  |
Подставив это выражение в первое соотношение получаем
 |  |
ve*Ö x2+y2=vp*Ö x2+(y+b)2.
Возведём обе части в квадрат и получим
ve2* [x2+y2]=vp2*[x2+(y+b)2]
(ve2 – vp2)*x2 + (ve2 – vp2)*y2 – 2*b*vp2*y = b2*vp2
Разделим это выражение на (ve2 – vp2) сгруппируем. Получим следующее:
x2 + (y – b*vp2/(ve2 – vp2))2 = (ve*vp*b)2/(ve2 – vp2)2
Это и есть уравнение окружности, что и требовалось доказать.
Окружность Апполония и точка Апполония представляют собой очень важные объекты, имеющие самое серьёзное применение в теории преследования на плоскости. С их помощью можно оценивать различные величины, характеризующие процесс преследования и получать траектории движения игроков. Приведём в подтверждение несколько маленьких теорем.
Теорема 1: Пусть убегающий игрок и преследователь перемещаются по своим полупрямым. Их положение зависит от времени. Обозначим его через P(t), E(t) тогда любой отрезок [P(t), E(t)] параллелен отрезку [P(0), E(0)]. На рисунке внизу эти отрезки выделены:
Теорема 2: Пусть убегающий игрок движется по прямой пересекающей окружность Апполония в точке М, движение начинается из точки Е со скоростью V. Тогда преследователь не может встретится с убегающим раньше чем за время равное |EM| / V
Значение этой теоремы трудно переоценить, так как она утверждает, что окружность Апполония – это геометрическое место точек в которых происходит гарантированная встреча при оптимальном поведении обоих игроков. Не раньше и не позже. А так как оптимальное время преследования одна из главных целей анализа теории, то становится ясным, почему нужно уметь строить окружность Апполония
3 Стратегия параллельного сближения
А теперь рассмотрим пример стратегии погони. Цель стратегии параллельного сближения заключается в том, чтобы обеспечить преследователю максимальное сближение с убегающим игроком. Ниже на картинке показаны возможные траектории преследователя и убегающего игрока при использовании стратегии параллельного преследования.