Введение

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

Кроме упомянутой классификации, динамические игры, согласно [1], разделяются на игры качества и игры степени. В играх качества представляет интерес два исхода игры. Например, требуется определить, могут ли преследователи захватить цель до определенного момента времени или нет. Отметим, что задачи преследования со многими участниками изучались в [3,4] как игры качества. В играх степени требуется построить оптимальные стратегии игроков, для которых достигается минимакс функции платы. В настоящей работе задача преследования в пределах одной группы рассматривается как игра степени.

Оценки сложности дискретных игр преследования изложены в работе [5]. Среди таких игр имеются NP-трудные, NP-трудные в сильном смысле (определения этих понятий имеются в работе [6]), а также задачи, допускающие решение за время, ограниченное полиномом или даже линейной функцией от длины описания игры.

В данной работе изучается сложность непрерывных задач преследования, в которых число преследователей и число преследуемых больше одного. Критерий качества -это время окончания игры, т. е. время захвата всех целей. Движения игроков считаются простыми, при этом предполагается, что максимальная скорость каждого преследователя превосходит максимальную скорость любого убегающего. Каждому преследователю разрешается захватить не более одного убегающего. Множество преследователей разбивается на группы, причем для каждой цели создается одна группа [4]. В любой момент времени группы могут быть переформированы. После захвата цели вся группа вместе с целью выбывают из игры. Все цели должны быть захвачены. Требуется найти оптимальный состав групп, т. е. такой, для которого момент захвата последней цели минимален. В каждой группе преследователи и убегающий игрок применяют оптимальные или близкие к ним стратегии движения; такого рода стратегии изучались в работах [1,[7][8][9][10][11].

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

Преследование одного убегающего

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

) ( 0 t X находится преследуемый игрок E, а в точках ) (t X i находятся преследующие его игроки i P , k i , , 2 , 1   . Обозначим ) (t V i скорости игроков, k i , , 2 , 1 , 0   (нулевое значение индекса i относится к игроку E); здесь i V -двумерные векторы. Игра начинается в момент времени 0  t . Уравнения движения игроков имеют вид i i V X   , k i , , 2 , 1 , 0   . (1)

Будем считать, что выполняются ограничения

   i i w V , k i , , 2 , 1 , 0   ,( 2 )

где i w -максимальная величина скорости,

w w  0 , k i , , 2 , 1   . (3)Стратегию игрока i можно определить как функцию   ) ( , t I t S i , где ) (t I -информация, доступная игроку в момент t. Значением этой функции является управление ) (t V i ; игрок i вычисляет свое управление по формуле   ) ( , t I t S V i i 

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

 ) (t X u   ) ( , ), ( ), ( 1 0 t X t X t X k   -фазовый вектор, содержащий координаты игроков, зависящие от времени. Управления ) (t V i вычисляются по формулам   ) ( , ) ( 0 0 t X t S t V u  , (4)   ) ( ), ( , ) ( 0 t V t X t S t V u i i  , k i , , 2 , 1   .( 5 )

Используя уравнения (1), ( 4), (5), приходим к системе дифференциальных уравнений  ,

) ( , ) ( 0 0 t X t S t X u   (6)   )) ( , ( ), ( , ) ( 0 t X t S t X t S t X u u i i   , k i , , 2 , 1   , (7) T t   0 , 0 ) 0 ( u u X X  ;( 8     t S S X T u , ), 0 ( 0 . Обозначим   k V V V V , , , 2 1   управление преследования, соответствующее стратегии S.

Предположим, преследуемый объект и преследователи применяют оптимальные стратегии

 0 S и  S .

Получающиеся при этом управления назовем парой оптимальных управлений   [1] (раздел 6.8). Для произвольных значений k задачи оптимального преследования изучаются в работах [8,11] .

  V V , 0 . В случае 2  k оптимальные управления  0 V и  V указаны в работеРассмотримQ -замкнутый круг Аполлония, соответствующий окружности i A . Тогда 2 1 Q Q Q  

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

Q X   -наиболее удаленная точка от точки 0 X из множества Q, т. е. для каждого Q X  справедливо неравенство 0 0 X X X X     .

Обозначим  0 S стратегию убегающего игрока, которая состоит в том, что он двигается равномерно и прямолинейно с максимальной скоростью по направлению к точке

 X . До момента времени, равного 0 0 w X X   , захват произойти не может, поэтому 0 0 w X X t    

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

0 0 w X X   , откуда следует неравенство 0 0 w X X t     . Из двух последних неравенств вытекает соотношение 0 0 w X X t     .

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

 X , обозначим  0 V . Управление преследователей, при котором они движутся равномерно и прямолинейно с максимальной скоростью по направлению к той же точке  X , обозначим  V . Пара     V V , 0 -пара оптимальных управлений. Пример. Рассмотрим пример игры с двумя преследователями. Пусть в начальный момент времени игрок E находится в точке   0 , 0 , преследователи 1 P и 2 P находятся в точках   0 , 1  и   0 , 1 , соответственно (рисунок). Предположим, окружности Аполлония 1 A и 2 A пересекаются в двух точках  X и  1 X . В начальный момент времени центры окружностей 1 A и 2 A лежат на оси абсцисс. Точки  X и  1

X расположены симметрично относительно оси абсцисс, множество

2 1 Q Q Q   представляет собой часть плоскости, которая ограничена дугами   1 1 X a X и   X b X 2 1 . Среди точек множества Q точки  X и  1 X наиболее удалены от убегающего игрока.

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

X * y P 1 P 2 E x X 1 * A 2 A 1 -1 a 1 a 2 b 1 b 2 1

Рисунок. Пример игры с двумя преследователями Разобьем промежуток времени игры ] , 0 [ T на конечное число непересекающихся промежутков. Пусть на некоторых из этих промежутков все игроки двигаются с максимальными скоростями прямолинейно по направлению к точке  X , а на остальных промежутках двигаются с максимальными скоростями прямолинейно по направлению к точке

 1 X . С течением времени окружности Аполлония 1 A и 2 A , а также их точки пересечения  X и  1

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

0 w X 

, последняя величина представляет собой оптимальное время преследования.

Задача оптимизации групп преследования  m i , , 2 , 1   ,   n j i , , 2 , 1 , 0   . Если 0  i j , i -й преследователь не принимает участия в погоне. Обозначим ) (J t j  оптимальное время преследования в j-й группе (относящейся к j-й цели). Пусть натуральное число ) (J k j

равно количеству преследователей в j-й группе. Задачу оптимизации групп преследования можно записать следующим образом:

min, ) ( max ,..., 2 , 1 J j n j J t    (10) ) 2 ( ) 1 ( ) ( j j j k J k k   , n j , , 2 , 1   ; (1 1  ij ij n j i x c (12) 1 1    n i ij x , n j , , 2 , 1   , (1 3

)

1 1    n j ij x , n i , , 2 , 1   , (1 4 )} 1 , 0 {  ij x ; ( 1 5 ) здесь   j i ij ij w w d с 0 1   , минимум ищется по переменным ij x .

Если в задаче (12)-( 15) коэффициенты целевой функции выбрать по формуле

  2 0 1 2 j i ij ij w w d с  

, то множество оптимальных решений не изменится. При этом новые коэффициенты ij с являются рациональными числами. В таком случае для задачи (12)-( 15) существуют полиномиальные алгоритмы решения [12], т. е. задача принадлежит классу P.

NP-трудность задачи оптимизации групп преследования

Для доказательства NP-трудности задачи ОГП рассмотрим ее частный случай. Считаем, что число преследователей вдвое превышает число убегающих, т. е. n m 2  , при этом для каждого убегающего должны быть назначены ровно два преследователя,

  j j k k , n j , , 2 , 1   . Пусть все n убегающих сосредоточены в начале координат, n преследователей находятся в точке   0 , 1  , еще n преследователей сосредоточены в точке   0 , 1 .2 ) 2 ( ) 1 (

Считаем, что для любых двух преследователей Задачу ОГП (10), (11)

в рассматриваемом частном случае запишем в виде min, ) ( max ) ( ,..., 2 , 1 J j n j J t J F     (16) 2 ) (  J k j , n j ,..., 2 , 1  . (1                        , 1 , 1                            . 1 2 , 1 2 2 2 2 2 0 2 2 1 2 2 0 2 j j j j j j j j j j w x X w X w x X w X 

Решая последнюю систему двух линейных уравнений с двумя неизвестными

2  j X и j x , получаем   2 0 2 2 2 1 2 0 2 2 2 j j j j j w w w w X     . Поэтому         2 0 2 2 j j j w X J t   2 0 2 2 2 1 2 2 j j j w w w   . Следовательно, задачу ОГПП можно записать в виде   min, 2 2 max 2 0 2 2 2 1 ,..., 2 , 1 J j j j n j w w w     2 ) (  J k j , n j , , 2 , 1   , или   max, 2 min 2 0 2 2 2 1 ,..., 2 , 1 J j j j n j w w w     (18) 2 ) (  J k j , n j , , 2 , 1   . (1 9 )

Задача ОГПП в форме (18), (19) имеет вариант распознавания, в котором вопрос можно сформулировать следующим образом: существует ли допустимый вектор J такой, что выполняются неравенства Теорема 2. Задача ОГП является NP-трудной в сильном смысле. Теорема 1 и 2 легко выводятся из соответствующих теорем работы [13]. Из теоремы 2 можно сделать выводы о том, какие методы следует применять для решения задачи ОГП. В отличие от некоторых частных случаев, один из которых рассмотрен в разделе 2, в общем случае задача ОГП не может быть решена полиномиальным или псевдополиномиальным алгоритмом (при условии P  NP). Для решения подобных задач применяются методы ветвей и границ, методы случайного поиска с локальной оптимизацией, эвристические алгоритмы.

M w w w j j j    2 0 2 2 2 1 2 , n j , ,2 , 1  

Методы оптимизации групп преследования и результаты численных экспериментов

В работе [14] для оптимизации групп преследования построены конкретные версии метода ветвей и границ и метода случайного поиска с локальной оптимизацией.

Здесь подробно рассмотрим метод случайного поиска с локальной оптимизацией. Метод состоит из таких шагов. Из результатов экспериментов можно сделать вывод о высокой точности и скорости метода случайного поиска с локальной оптимизацией даже при значительных размерностях решаемых задач ОГП.

Заключение

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

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

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

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