Сложность задач оптимизации преследования на плоскости

Розглянуто диференційні ігри переслідування на площині, в яких для кожного втікача утворюється група переслідувачів. Доведено теореми про NP-повноту та NP-трудність задач оптимізації груп переслідування. The differential pursuit-evasion games on a plane, in which a group of pursuers is created for e...

Повний опис

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Проблемы управления и информатики
Дата:	2013
Автор:	Пашко, С.В.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2013
Теми:	Оптимальное управление и методы оптимизации
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/207612
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Сложность задач оптимизации преследования на плоскости / С.В. Пашко // Проблемы управления и информатики. — 2013. — № 3. — С. 27–39. — Бібліогр.: 13 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-207612
record_format	dspace
spelling	Пашко, С.В. 2025-10-10T13:48:19Z 2013 Сложность задач оптимизации преследования на плоскости / С.В. Пашко // Проблемы управления и информатики. — 2013. — № 3. — С. 27–39. — Бібліогр.: 13 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207612 518.9 10.1615/JAutomatInfScien.v45.i5.30 Розглянуто диференційні ігри переслідування на площині, в яких для кожного втікача утворюється група переслідувачів. Доведено теореми про NP-повноту та NP-трудність задач оптимізації груп переслідування. The differential pursuit-evasion games on a plane, in which a group of pursuers is created for every evader, are considered. The theorems about NP-completeness and NP-hardness of pursuit optimization problems are proved. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Оптимальное управление и методы оптимизации Сложность задач оптимизации преследования на плоскости Складність задач оптимізації переслідування на площині Complexity of Pursuit Optimization Problems on a Plane Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Сложность задач оптимизации преследования на плоскости
spellingShingle	Сложность задач оптимизации преследования на плоскости Пашко, С.В. Оптимальное управление и методы оптимизации
title_short	Сложность задач оптимизации преследования на плоскости
title_full	Сложность задач оптимизации преследования на плоскости
title_fullStr	Сложность задач оптимизации преследования на плоскости
title_full_unstemmed	Сложность задач оптимизации преследования на плоскости
title_sort	сложность задач оптимизации преследования на плоскости
author	Пашко, С.В.
author_facet	Пашко, С.В.
topic	Оптимальное управление и методы оптимизации
topic_facet	Оптимальное управление и методы оптимизации
publishDate	2013
language	Russian
container_title	Проблемы управления и информатики
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
format	Article
title_alt	Складність задач оптимізації переслідування на площині Complexity of Pursuit Optimization Problems on a Plane
description	Розглянуто диференційні ігри переслідування на площині, в яких для кожного втікача утворюється група переслідувачів. Доведено теореми про NP-повноту та NP-трудність задач оптимізації груп переслідування. The differential pursuit-evasion games on a plane, in which a group of pursuers is created for every evader, are considered. The theorems about NP-completeness and NP-hardness of pursuit optimization problems are proved.
issn	0572-2691
url	https://nasplib.isofts.kiev.ua/handle/123456789/207612
citation_txt	Сложность задач оптимизации преследования на плоскости / С.В. Пашко // Проблемы управления и информатики. — 2013. — № 3. — С. 27–39. — Бібліогр.: 13 назв. — рос.
work_keys_str_mv	AT paškosv složnostʹzadačoptimizaciipresledovaniânaploskosti AT paškosv skladnístʹzadačoptimízacíípereslíduvannânaploŝiní AT paškosv complexityofpursuitoptimizationproblemsonaplane
first_indexed	2025-11-25T22:49:34Z
last_indexed	2025-11-25T22:49:34Z
_version_	1850574369320861696
fulltext	© С.В. ПАШКО, 2013 Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 3 27 ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ И МЕТОДЫ ОПТИМИЗАЦИИ УДК 518.9 С.В. Пашко СЛОЖНОСТЬ ЗАДАЧ ОПТИМИЗАЦИИ ПРЕСЛЕДОВАНИЯ НА ПЛОСКОСТИ Введение Задачи преследования и убегания, занимающие одно из центральных мест в теории динамических игр, можно разделить на два класса. В задачах первого класса игроки перемещаются на некотором многообразии, например на евклидо- вой плоскости. Эти задачи принято называть непрерывными играми преследова- ния; многие их них изучены в работе [1]. В задачах второго класса игроки двига- ются по ребрам заданного графа. Впервые такие задачи, которые называются дис- кретными играми преследования, подробно рассмотрены в работе [2]. Кроме упомянутой классификации, динамические игры, согласно [1], разде- ляются на игры качества и игры степени. В играх качества представляет интерес два исхода игры. Например, требуется определить, могут ли преследователи за- хватить цель до определенного момента времени или нет. Отметим, что задачи преследования со многими участниками изучались в работах [3, 4] как игры каче- ства. В играх степени требуется построить оптимальные стратегии игроков, для которых достигается минимакс функции платы. В настоящей работе задача пре- следования в пределах одной группы рассматривается как игра степени. Следует отметить достигнутые успехи в построении роботизированных си- стем преследователей на практике, в которых несколько роботов преследуют не- которое количество целей [5]. Оценки сложности дискретных игр преследования изложены в работе [6]. Среди таких игр имеются NP-трудные, NP-трудные в сильном смысле (определе- ния этих понятий имеются в работе [7]), а также задачи, допускающие решение за время, ограниченное полиномом или даже линейной функцией от длины описа- ния игры. В данной работе изучается сложность непрерывных задач преследования, в которых число преследователей и число преследуемых больше одного. Крите- рием качества является время окончания игры, т.е. время захвата всех целей. Движения игроков считаются простыми, при этом предполагается, что макси- мальная скорость каждого преследователя превосходит максимальную скорость любого убегающего. Каждому преследователю разрешается захватить не более одного убегающего. Множество преследователей разбивается на группы, причем для каждой цели создается одна группа [3]. В любой момент времени группы мо- гут быть переформированы. После захвата цели вся группа вместе с целью выбыва- ет из игры. Все цели должны быть захвачены. Требуется найти оптимальный состав групп, т.е. такой, для которого момент захвата последней цели минимален. В каж- дой группе преследователи и убегающий игрок применяют оптимальные или близ- кие к ним стратегии движения; такого рода стратегии изучались в работах [1, 8–12]. 28 ISSN 0572-2691 В настоящей работе показано, что задача оптимизации состава групп пресле- дования является NP-трудной в сильном смысле, а некоторые ее частные случаи допускают полиномиальные по времени алгоритмы решения. 1. Преследование одного убегающего Рассмотрим задачу оптимального преследования одного убегающего группой преследователей. Пусть на плоскости в точке 0X находится преследуемый игрок E, а в точках iX находятся преследующие его игроки ,iP .,...,2,1 ki  Обозначим iV скорости игроков, ki ,...,2,1,0 (нулевое значение индекса i относится к игроку E); здесь iV — двумерные векторы. Уравнения движения игроков имеют вид ,ii VX  .,...,2,1,0 ki  (1) Будем считать, что выполняются ограничения , ii wV ,,...,2,1,0 ki  (2) где iw — максимальная величина скорости, 22 yxX  — длина вектора ).,( yxX  Кроме того, скорость iV считается кусочно-непрерывной функцией от времени. Это означает, что в каждом ограниченном временном интервале суще- ствует не больше конечного числа точек разрыва. Игрок i управляет своими координатами, выбирая в каждый момент времени скорость .iV Функция )(tVi является управлением i-го игрока. Движение, осу- ществляемое таким образом, называется простым. Игра начинается в момент вре- мени 0t и считается законченной, когда координаты одного из преследовате- лей в некоторый момент Tt  совпадают с координатами E, случай T не ис- ключается. Преследователи стремятся уменьшить время T, преследуемый стремится его увеличить. Считаем, что ,0 iww  .,...,2,1 ki  (3) Стратегию игрока i можно определить как функцию )),(,( tItSi где )(tI — информация, доступная игроку в момент t. Значением этой функции является управление );(tVi игрок i вычисляет свое управление по формуле )).(,( tItSV ii  Ниже считается, что стратегия убегающего зависит только от времени и фазового вектора, а стратегии преследователей зависят еще и от скорости убегающего игрока. Пусть ))(),...,(),(()( 10 tXtXtXtX k u  — фазовый вектор, содержащий координаты игроков, зависящие от времени. Управления )(tVi вычисляются по формулам )),(,()( 00 tXtStV u (4) )),(),(,()( 0 tVtXtStV u ii  .,...,2,1 ki  (5) Используя уравнения (1), (4), (5), приходим к системе дифференциальных уравнений )),(,()( 00 tXtStX u (6) ))),(,(),(,()( 0 tXtStXtStX uu ii  ,,...,2,1 ki  (7) ,0 Tt  ,)0( 0uu XX  (8) здесь 0uX — заданное начальное значение вектора .uX Решением системы (6)–(8) считается абсолютно непрерывная функция )),(),...,(),(()( 10 tXtXtXtX k u  Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 3 29 производная которой всюду удовлетворяет соотношениям (6), (7), за исключени- ем, быть может, конечного числа моментов времени в каждом ограниченном вре- менном отрезке. Пусть ),...,,( 21 kSSSS  — стратегия преследования. Пара стратегий убега- ния и преследования ),( 0 SS называется совместной, если существует единствен- ное решение )(tX u системы уравнений (6)–(8), причем управления ),(tVi вычис- ляемые по формулам (4), (5), являются кусочно-непрерывными функциями от t и удовлетворяют соотношениям (2). Приведенное определение совместной пары стратегий аналогично определению, данному в [9]. Пусть величина ),),0(( 0 SSXT u равна времени захвата цели, если стратегии 0S и S совместны, и равна бесконечности в противном случае. Оптимальным временем преследования назовем число ).,),0((supinf 0 0 SSXTt u SS  (9) Ясно, что из соотношений (3) следует .t Назовем стратегию S оптималь- ной стратегией преследования, если для каждой стратегии 0S выполняется неравен- ство .),),0(( 0   tSSXT u Назовем стратегию  0S оптимальной стратегией убега- ния, если для каждой стратегии S справедливо неравенство .),),0(( 0   tSSXT u Обозначим ),...,,( 21 kVVVV  управление преследования, соответствующее стра- тегии S. Предположим, преследуемый объект и преследователи применяют опти- мальные стратегии  0S и .S Получающиеся при этом управления назовем парой оптимальных управлений ).,( 0  VV В случае 2k оптимальные управления  0V и V указаны в работе [1, разд. 6.8]. Для произвольных значений k задачи оптимального преследования изучаются в [8, 9]. Рассмотрим подробнее игру с двумя преследователями, т.е. при условии .2k Обозначим iA окружность Аполлония, относящуюся к паре игроков E, ,iP .2,1i Она представляет собой геометрическое место точек, в которых могут встретиться игроки E и ,iP если они двигаются равномерно и прямолинейно с максимальными скоростями. Пусть iQ — замкнутый круг Аполлония, соответ- ствующий окружности .iA Тогда 21 QQQ  — множество таких точек плоско- сти, до которых игрок E успевает дойти не позже каждого преследователя. Внут- ренность множества Q представляет собой множество точек, до которых игрок E успевает дойти раньше любого преследователя. Пусть QX  — наиболее уда- ленная точка от точки 0X из множества Q, т.е. для каждого QX  справедливо неравенство .00 XXXX  Обозначим  0S стратегию убегающего игрока, которая состоит в том, что он двигается равномерно и прямолинейно с максимальной скоростью по направле- нию к точке .X До момента времени, равного 00 / wXX  , захват произойти не может, поэтому ./ 00 wXXt   В данной игре каждый из преследователей может применить стратегию параллельного сближения [11]. В работе [12] доказа- но, что применение каждым преследователем этой стратегии приводит к захвату цели за время, которое не превосходит величины 00 / wXX  , откуда следует неравенство ./ 00 wXXt   Из двух последних неравенств вытекает соот- ношение ./ 00 wXXt   30 ISSN 0572-2691 Управление убегающего игрока, при котором он движется равномерно и прямолинейно с максимальной скоростью по направлению к точке ,X обозна- чим .0 V Управление преследователей, при котором они движутся равномерно и прямолинейно с максимальной скоростью по направлению к той же точке ,X обозначим .V Пара ),( 0  VV является парой оптимальных управлений. Пример. Рассмотрим пример игры с двумя преследователями. Пусть в начальный момент времени игрок E находится в точке (0, 0), преследователи 1P и 2P находятся в точках )0,1( и )0,1( соответственно (рисунок). Предположим, окружности Аполлония 1A и 2A пересекаются в двух точках: X и .1 X В начальный момент времени центры окружностей 1A и 2A лежат на оси абсцисс. Точки X и  1X расположены симметрично относительно оси абс- цисс, множество 21 QQQ  представляет собой часть плоскости, которая огра- ничена дугами  11XaX и .21  XbX Среди точек множества Q точки X и  1X наиболее удалены от убегающего игрока. В этой игре имеется множество пар оптимальных управлений. Одна из таких пар приводит к тому, что все игроки двигаются прямолинейно по направлению к точке X с максимальными скоростями. Другая пара приводит к тому, что все игроки двигаются с максимальными скоростями прямолинейно по направлению к точке .1 X Разобьем промежуток времени игры [0, T] на конечное число непересекаю- щихся промежутков. Пусть на некоторых из них все игроки двигаются с макси- мальными скоростями прямолинейно по направлению к точке ,X а на остальных промежутках — с максимальными скоростями прямолинейно по направлению к точке .1 X С течением времени окружности Аполлония 1A и 2A , а также их точ- ки пересечения X и  1X изменяют свое положение. Соответствующие пары управлений также оптимальны. Если все игроки применяют описанные оптимальные управления, то в каж- дый момент времени три игрока расположены на одной прямой, и преследователи находятся по разные стороны убегающего на равных расстояниях от него. Захват цели происходит в момент времени 0/ wX  , последняя величина представляет собой оптимальное время преследования. X * y P1 P2 E x * 1X A2 A1 1 a1 a2 b1 b2 1 Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 3 31 2. Задача оптимизации групп преследования Рассмотрим задачу формирования оптимальных групп преследования в слу- чае, когда число убегающих больше одного. Пусть на плоскости имеются m пре- следователей и n убегающих, причем .1 nm Все игроки обладают простым движением, максимальная скорость каждого преследователя больше максималь- ной скорости любого убегающего. Для каждого убегающего образуется группа преследователей, которая после его захвата выбывает из игры вместе с ним. Цель считается захваченной, если ее координаты совпадают с координатами одного из преследователей, входящих в группу. Все цели должны быть захвачены. Считает- ся, что для каждой цели заданы минимальное и максимальное количества игро- ков, которые могут принадлежать группе. Требуется составить группы преследо- вания таким образом, чтобы общее время завершения игры принимало минималь- ное значение. Считаем, что в каждой группе игроки действуют следующим образом. Если существует пара оптимальных стратегий ),( 0  SS , то они применяются игроками; время захвата t вычисляется по формуле (9). Если оптимальных стратегий нет, то для любого сколь угодно малого поло- жительного числа  существует стратегия преследования S  такая, что для лю- бой стратегии уклонения 0S справедливо неравенство ;),),0(( 0  tSSXT u здесь число t определяется формулой (9). Поскольку ),,),0((sup 0 0 SSXTt u S  то существует стратегия преследования 0S  такая, что выполняется неравенство ).,),0(( 0 SSXTt u  Считаем, что применяется пара стратегий ),( 0 SS  . Так как число  можно выбрать сколь угодно близким к нулю, то в такой группе для вычисления времени захвата цели также используем формулу (9). Пусть целочисленный вектор ),...,,( 21 mjjjJ  задает распределение пре- следователей по группам. Число ij означает номер цели, которую преследует i-й преследователь, },,...,2,1{ mi .},...,2,1{ nji  Обозначим )(Jt j  оптимальное время преследования в j-й группе (относящейся к j-й цели). Пусть натуральное число )(Jk j равно количеству преследователей в j-й группе. Задачу оптимизации групп преследования можно записать следующим образом: min,)(max ,...,2,1   Jj nj Jt (10) ,)( )2()1( jjj kJkk  .,...2,1 nj  (11) Здесь )2()1( , jj kk задают соответственно минимально возможное и максимально возможное число преследователей в j-й группе. Входными данными этой задачи являются координаты на плоскости всех иг- роков в начале игры, их максимальные скорости, числа , )1( jk , )2( jk m, n. Считаем, что входные данные представляют собой целые числа; максимальные скорости и числа , )1( jk , )2( jk m, n считаются положительными. Задачу (10), (11) назовем задачей оптимизации групп преследования (ОГП). В задаче требуется найти оптимальное значение вектора J, который состоит из целых чисел. Поскольку входные данные также являются целыми числами, то уместен вопрос, какова алгоритмическая сложность задачи ОГП. Ниже доказыва- ется, что в общем случае эта задача является NP-трудной в сильном смысле. 32 ISSN 0572-2691 В некоторых частных случаях задача ОГП допускает решение за время, огра- ниченное полиномом от длины ее описания, т.е. принадлежит классу P. Рассмот- рим один из них. Предположим, число преследователей равно числу убегающих, т.е. .nm Для каждой цели должен быть назначен ровно один преследователь. Если один игрок преследует цель, то его оптимальной стратегией является дви- жение с максимальной скоростью по направлению к цели, а оптимальной страте- гией убегающего является движение с максимальной скоростью в противополож- ном от преследователя направлении. Пусть ijd — начальное расстояние между i-м преследователем и j-й целью. Оптимальное время захвата цели равно ),/( 01 jiij wwd  где jw0 и iw1 означают максимальные скорости убегающего и преследователя соответственно. Пусть булева переменная ijx принимает значение 1, если i-й преследователь назначен на j-ю цель, и значение 0 в противном случае. Задачу ОГП можно запи- сать в виде min,max ,...,2,1,   ijij nji xc (12) ,1 1   ij n i x ,,...2,1 nj  (13) ,1 1   ij n j x ,,...,2,1 ni  (14) };1,0{ijx (15) здесь ),/( 01 jiijij wwdс  минимум ищется по переменным .ijx Если в задаче (12)–(15) коэффициенты целевой функции выбрать по формуле ,)/( 2 01 2 jiijij wwdс  то множество оптимальных решений не изменится. При этом новые коэффициенты ijс являются рациональными числами. В таком случае для задачи (12)–(15) существуют полиномиальные алгоритмы решения [13], т.е. задача принадлежит классу P. 3. NP-трудный частный случай задачи оптимизации групп преследования Для доказательства NP-трудности задачи ОГП рассмотрим ее частный слу- чай. Считаем, что число преследователей вдвое превышает число убегающих, т.е. ,2nm  при этом для каждого убегающего должны быть назначены ровно два преследователя, ,2 )2()1(  jj kk .,...2,1 nj  Пусть все n убегающих сосредоточе- ны в начале координат, n преследователей находятся в точке )0,1( , еще n пре- следователей сосредоточены в точке ).0,1( Считаем, что для любых двух преследователей: 1P и 2P таких, что 1P нахо- дится в точке ),0,1( а 2P — в точке ),0,1( и любого убегающего E справедливо следующее. Две окружности Аполлония: 1A и ,2A пересекаются или касаются; здесь окружность 1A относится к паре игроков E, ,1P а окружность 2A — к паре E, 2P (см. рисунок). Ниже выводится условие, необходимое и достаточное для это- го. Поскольку все игроки применяют оптимальные управления, одна из точек пе- ресечения этих окружностей представляет собой точку захвата цели. Если таких точек две: X и  1X (см. рисунок), то время захвата в обеих одинаково. Для рас- четов, производимых ниже, можно выбрать любую из этих точек, поскольку нас интересует только время захвата. Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 3 33 Задачу ОГП (10), (11) в рассматриваемом частном случае запишем в виде min,)(max)( ,...,2,1    Jj nj JtJF (16) ,2)( Jk j .,...,2,1 nj  (17) Назовем допустимое решение задачи (16), (17) правильным, если оно удовле- творяет следующему условию: в каждой группе преследования один из двух пре- следователей в начальный момент времени находится в точке ),0,1( а другой — в точке ).0,1( Справедлива следующая лемма. Лемма. Для каждого решения J задачи ОГП (16), (17) существует правильное решение J  такое, что ).()( JFJF  Существует полиномиальный алгоритм, преобразующий решение J в решение .J  Доказательство. Пусть вектор J не является правильным решением. Это значит, что найдутся две различные группы преследования: i и j, ,ji  такие, что в начальный момент времени в группе i оба преследователя находятся в точке )0,1( , а в группе j — в точке ).0,1( Такие группы назовем неправильными. Пусть максимальные скорости преследователей в группе i равны 1w и ,2w при- чем ,21 ww  а в группе j равны 3w и ,4w причем .43 ww  Переместим преследователя, имеющего скорость 2w , в группу j, а преследо- вателя, имеющего скорость 4w , — в группу i. Оптимальное время преследования в обеих группах не увеличится, поэтому значение целевой функции F также не увеличится. Количество неправильных групп уменьшится на две. Выполнив эту операцию некоторое число раз, получим правильный вектор J  такой, что справедливо неравенство ).()( JFJF  Очевидно, время работы описанного алгоритма ограничено полиномом от длины входных данных задачи. Лемма доказана. Задачу ОГП (16), (17) в описанном частном случае, для которой допустимы- ми являются только правильные решения, удовлетворяющие (17), назовем зада- чей оптимизации групп преследования на прямой (ОГПП). Придадим задаче ОГПП иную форму. Пусть точка захвата в j-й группе   jXX имеет координаты jj yx , (см. ри- сунок). В результате применения оптимальных стратегий все три игрока прибы- вают в точку  jX одновременно, поэтому справедлива система уравнений       ,/))1((/)( ,/))1((/)( 2 2 222 0 22 2 1 222 0 22 jjjjjj jjjjjj wyxwyx wyxwyx  где ,0 jw ,1 jw jw2 означают соответственно максимальные скорости убегающе- го игрока и двух догоняющих игроков в j-й группе. Перепишем эту систему урав- нений в виде         ./)2(/ ,/)2(/ 2 2 222 0 2 2 1 222 0 2 jjjjj jjjjj wrxXwX wrxXwX  Решая последнюю систему двух линейных уравнений с двумя неизвестными 2 jX и ,jx получаем ),2/(2 2 0 2 2 2 1 2 0 2 jjjjj wwwwX  поэтому   2 0 22 /))(( jjj wXJt ).2/(2 2 0 2 2 2 1 jjj www  Следовательно, задачу ОГПП можно записать в виде 34 ISSN 0572-2691 min, 2 2 max 2 0 2 2 2 1 ,...,2,1   J jjj nj www ,2)( Jk j ,,...,2,1 nj  или max,)2(min 2 0 2 2 2 1 ,...,2,1   Jjjj nj www (18) ,2)( Jk j .,...,2,1 nj  (19) Задача ОГПП в форме (18), (19) имеет вариант распознавания, в котором во- прос можно сформулировать следующим образом: существует ли допустимый вектор J такой, что выполняются неравенства ,2 2 0 2 2 2 1 Mwww jjj  ,,...,2,1 nj  (20) где M — целое положительное число? В разд. 4 будет доказана NP-полнота этой задачи. Изложенные рассуждения справедливы только в случае, если в каждой груп- пе преследования две окружности Аполлония имеют общие точки. Приведем не- обходимое и достаточное условие для этого. Пусть в j-й группе в начальный мо- мент времени преследователи 1P и 2P находятся в точках )0,1( и )0,1( соот- ветственно, а убегающий E — в точке )0,0( (см. рисунок). Пусть максимальные скорости игроков E, ,1P 2P равны соответственно ,0 jw ,1 jw .2 jw Окружности Аполлония 1A и 2A соответствуют парам игроков E, 1P и E, 2P . Пусть окруж- ность iA пересекает ось абсцисс в точках ia и ,ib причем ,ii ba  2,1i (см. рисунок). Очевидно, для того чтобы окружности Аполлония 1A и 2A имели общие точки, необходимо и достаточно выполнения системы неравенств      . , 21 21 bb aa (21) Из определения окружности Аполлония следует соотношение ,/)1(/ 1101 jj wawa  т.е. ,/1)/1/1/( 1101 jjj wwwa  откуда получаем )./( 1001 jjj wwwa  Анало- гично выводим ).(/ 0202 jjj wwwa  Поэтому первое неравенство в системе (21) равносильно соотношению .2 012 jjj www  Аналогично доказывается, что второе неравенство в системе (21) равносильно соотношению .2 012 jjj www  Из двух последних соотношений заключаем, что в j-й группе окружности Апол- лония имеют общие точки тогда и только тогда, когда выполняется неравенство .2 012 jjj www  (22) 4. Доказательство NP-трудности задачи оптимизации групп преследования В этом разделе доказаны теоремы о NP-полноте задачи ОГПП и о NP-труд- ности задачи ОГП. В работе [7] описана NP-полная в сильном смысле задача ПАРОСОЧЕТА- НИЕ С ОГРАНИЧЕНИЯМИ ПО ВЕСУ (ПОВ), которая формулируется следую- щим образом. Заданы непересекающиеся множества X и Y, каждое из которых со- Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 3 35 держит n элементов, размеры )(as (являющиеся целыми положительными числа- ми) всех элементов YXa  и вектор ограничений ),...,,( 21 nBBB с положи- тельными целыми координатами. Требуется определить, можно ли множество YX  так разбить на n непересекающихся подмножеств ,,...,, 21 nAAA каждое из которых содержит по одному элементу из X и Y, что    jAa jBas )( (23) для всех nj ,...,2,1 ? Описанная задача останется NP-полной в сильном смысле, если вместо усло- вия (23) использовать неравенство .)(   jAa jBas (24) Ниже используется задача ПОВ с условием (24). Обозначим ),(min0 ass YXa   ).(max1 ass YXa   (25) Очевидно, в задаче ПОВ величины )(as и jB имеет смысл выбирать только при условиях ,21 s ,22 10 sBs j  .,...,2,1 nj  (26) Легко доказать, что задача ПОВ остается NP-полной в сильном смысле при усло- виях (26), которые будем считать выполненными. Вариант распознавания задачи ОГПП можно сформулировать следующим образом. Заданы непересекающиеся множества X и Y, каждое из которых содер- жит n элементов, размеры )(aq (являющиеся целыми положительными числами) всех элементов ,YXa  вектор ),...,,( 00201 nwww с положительными целыми координатами и целое положительное число M. Под элементом a подразумевается преследователь, причем в момент времени 0t игрок находится в точке ),0,1( если ,Xa и находится в точке ),0,1( если .Ya Величина jw0 означает мак- симальную скорость убегающего игрока в j-й группе. Величина )(aq означает максимальную скорость преследователя a. Требуется определить, можно ли мно- жество YX  так разбить на n непересекающихся подмножеств ,,...,, 21 nAAA каждое из которых содержит по одному элементу из X и Y, что    jAa jwMaq 2 0 2 2)( (27) для всех nj ,...,2,1 ? Справедлива следующая теорема о NP-полноте задачи ОГПП. Теорема 1. Задача ОГПП является NP-полной в сильном смысле. Доказательство. Разумеется, речь идет о варианте распознавания задачи ОГПП. Нетрудно видеть, что ОГПП принадлежит классу NP. Сведем задачу ПОВ к задаче ОГПП. Выберем целые положительные числа k и d следующим образом: ,144 4 1sk  ,144 2 1sd  (28) 36 ISSN 0572-2691 где 1s удовлетворяет (25). Числа )(as и jB выберем по формулам ),)(()( 0sasdkas  ,YXa  (29) ),2(2 0sBdkB jj  ;,...,2,1 nj  (30) здесь ),(as ,jB n — входные данные индивидуальной задачи ПОВ. Входные данные индивидуальной задачи ОГПП (т.е. величины ,M ,0 jw ),(aq n) выберем в виде ,2 1dsM   ,2/ 10 dsBw jj    ,1)()(  asaq ,YXa  ;,...,2,1 nj  (31) здесь  x — целая часть числа x, величина 1s удовлетворяет (25). Соотношения (28)–(31) преобразуют индивидуальную задачу ПОВ в индиви- дуальную задачу ОГПП (это доказывается ниже) за время, ограниченное полино- мом от длины входа. Дальнейшее доказательство состоит из трех шагов. Шаг 1. Докажем, что построенная индивидуальная задача принадлежит мас- совой задаче ОГПП. Для этого достаточно доказать неравенства ,10 jw ,,...,2,1 nj  (32) ),(0 aqw j  ,,...,2,1 nj  ,YXa  (33) ,2)()( 0 jwaqaq  ,,...,2,1 nj  ,Xa  .Ya  (34) Неравенства (33) вытекают из (3), а соотношения (34) следуют из (22). Докажем неравенства (32), утверждающие, что максимальные скорости убегающих игроков должны быть положительными. Используя соотношения (26), (28) и (30) , получаем    112/2/ 1110 dskdsBdsBw jjj .1112 1 2 11  sss Последнее неравенство вытекает из условия 21 s (26). Неравенства (32) доказаны. Докажем неравенства (33), утверждающие, что максимальные скорости убегаю- щих игроков должны быть меньше максимальных скоростей догоняющих. Имеем           ).(1)()(2/)2(2/ 1010 aqasaskdssBdkdsBw jjj  Здесь использованы соотношения (26), (29)–(31). Докажем неравенства (34). Имеем      1)()()()()()( asasasasaqaq ;11211)()( 2/3 11  sdsasas (35) при выводе этой оценки использованы соотношения (25), (28), (29), (31). С помо- щью соотношений (28), (30) величину jw0 можно оценить следующим образом:    12/ 110 dskdsBw jj .112 2/3 1 s Из этой оценки и (35) вытекают неравенства (34). Шаг 2. Докажем эквивалентность неравенств (24) и (27) (т.е. NP-полноту за- дачи ОГПП). Пусть неравенства (24) справедливы для всех .,...,2,1 nj  Тогда, очевидно, выполняются неравенства ,)(   jAa jBas .,...,2,1 nj  Учитывая это, Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 3 37 а также используя (31), заключаем, что при каждом j справедливы неравенства    jAa aq )(2    jAa jBas )( .2 2 0 jwM  Таким образом, неравенства (27) выполня- ются при всех j. Предположим, для некоторого числа },...,2,1{ nj неравенство (24) не вы- полняется, т.е. справедливо неравенство .)(   jAa jBas (36) Докажем, что при этом j неравенство (27) также не выполняется, т.е. .2)( 2 0 2    jAa jwMaq (37) Поскольку    jAa j asB )( ,)(         jAa j asBd то с учетом целочисленности величин из (36) получаем .)(   jAa j asdB (38) Из (31) вытекает    jj AaAa asaq 22 )1)(()( .2))(2)((   jAa asas Используя (31) и (38), выводим  2 11 2 0 )12/(222 dsBdswM jj  222 jj BB .222)(    j Aa Basd j Из двух последних оценок заключаем, что для доказательства соотношения (37) до- статочно доказать неравенство    jAa as )( < .22/ jBd  (39) Поскольку из (29) и (30) следуют неравенства ,)( 1dskas  ),(2 1dskB j  то вместо (39) достаточно доказать неравенство .2/)(22 11 ddskdsk  Но последнее неравенство выполняется в силу (28). Поэтому неравенство (39) спра- ведливо, а вместе с ним справедливо также неравенство (37). Эквивалентность неравенств (24) и (27) доказана. Из этого следует, что инди- видуальная задача ОГПП имеет ответ «да» тогда и только тогда, когда имеет от- вет «да» соответствующая индивидуальная задача ПОВ. Таким образом, задача ПОВ сводится полиномиально к задаче ОГПП, поэтому ОГПП принадлежит клас- су NP-полных задач. Шаг 3 (доказательство NP-полноты в сильном смысле). Легко проверить, что описанное полиномиальное сведение задачи ПОВ к задаче ОГПП является также псевдополиномиальным в смысле, принятом в работе [7]. Задача ПОВ является NP-полной в сильном смысле. Поэтому из леммы 4.1 работы [7] следует, что за- дача ОГПП NP-полная в сильном смысле. Теорема доказана. Задача ОГП рассматривается в оптимизационной форме. Это значит, что требу- ется найти оптимальное решение .J Справедлива следующая теорема о NP-труд- ности задачи ОГП. 38 ISSN 0572-2691 Теорема 2. Задача ОГП является NP-трудной в сильном смысле. Доказательство. Входными данными индивидуальной задачи ОГПП явля- ются числа ,n ,ijw M. Те же величины, кроме числа M, являются входными дан- ными индивидуальной задачи ОГП (16), (17). Поэтому преобразование индивиду- альной задачи ОГПП в индивидуальную задачу ОГП (16), (17) тривиально. Предположим, существует алгоритм A, который вычисляет оптимальное ре- шение J задачи ОГП (16), (17) за полиномиальное время. В силу леммы, суще- ствуют правильное оптимальное решение J  задачи ОГПП и полиномиальный алгоритм ,1A преобразующий вектор J в вектор .J  Очевидно, существует по- линомиальный алгоритм ,2A который вычисляет соответствующее решению J  оптимальное значение целевой функции (18) задачи ОГПП. Последовательное применение алгоритмов A, 1A и 2A позволяет решить задачу ОГПП за полиноми- альное время. Таким образом, задача ОГПП сводится по Тьюрингу [7] к задаче ОГП. Поскольку по теореме 1 задача ОГПП NP-полная, то задача ОГП (16), (17) представляет собой NP-трудную задачу. Сильная NP-трудность задачи ОГП следует из сильной NP-полноты задачи ОГПП и тривиальности преобразования индивидуальной задачи ОГПП в индиви- дуальную задачу ОГП. Теорема доказана. Из теоремы 2 можно сделать выводы о том, какие методы следует применять для решения задачи ОГП. В отличие от некоторых частных случаев, один из кото- рых рассмотрен в разд. 2, в общем случае задача ОГП не может быть решена по- линомиальным или псевдополиномиальным алгоритмом (при условии P  NP). Для решения подобных задач применяются методы ветвей и границ, методы слу- чайного поиска с локальной оптимизацией, эвристические алгоритмы. Заключение В данной работе рассмотрены игры преследования на плоскости с простым движением, в которых принимают участие несколько преследователей и убегаю- щих. Считается, что количество преследователей больше числа убегающих и ско- рости преследователей больше скоростей убегающих. Для захвата целей множество преследователей разбивается на группы, при- чем для каждого убегающего создается одна группа. После захвата цели все пре- следователи группы и убегающий выбывают из игры. Считается, что в каждой группе игроки используют оптимальные стратегии. В качестве критерия исполь- зуется время захвата. Доказаны теоремы о NP-полноте и NP-трудности задач оптимизации групп преследования. Эти задачи являются NP-трудными в сильном смысле уже в слу- чае, когда для каждого убегающего необходимо назначить ровно двух преследо- вателей. На основе доказанных теорем сделаны выводы о том, какие методы сле- дует применять для решения задачи ОГП. С.В. Пашко СКЛАДНІСТЬ ЗАДАЧ ОПТИМІЗАЦІЇ ПЕРЕСЛІДУВАННЯ НА ПЛОЩИНІ Розглянуто диференційні ігри переслідування на площині, в яких для кожного втікача утворюється група переслідувачів. Доведено теореми про NP-повноту та NP-трудність задач оптимізації груп переслідування. Международный научно-технический журнал «Проблемы управления и информатики», 2013, № 3 39 S.V. Pashko COMPLEXITY OF PURSUIT OPTIMIZATION PROBLEMS ON A PLANE The differential pursuit-evasion games on a plane, in which a group of pursuers is created for every evader, are considered. The theorems about NP-completeness and NP-hardness of pursuit optimization problems are proved. 1. Айзекс Р. Дифференциальные игры. — М. : Мир, 1967. — 480 с. 2. Parsons T.D. Pursuit-evasion in a graph. Theory and applications of graphs. — Springer-Verlag, 1976. — P. 426–441 3. Чикрий А.А. Конфликтно управляемые процессы. — Киев : Наук. думка, 1992. — 384 с. 4. Благодатских А.И., Петров Н.Н. Конфликтное взаимодействие групп управляемых объек- тов. — Ижевск : Удмурт. ун-т, 2009. — 266 с. 5. Vieira M.A.M., Govindan R., Sukhatme G.S. Scalable and practical pursuit-evasion with net- worked robots // Journ. of Intel. Service Robotics. Special Issue on Networked Robots. — 2009. — 2. — P. 247–263. 6. Borie R., Tovey C., Koenig S. Algorithms and complexity results for pursuit-evasion problems // Proc. of the Intern. Joint Conf. on Artificial Intel. (IJCAI). — 2009. — P. 59–66. 7. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М. : Мир, 1982. — 416 с. 8. Иванов Р.П., Ледяев Ю.С. Оптимальность времени преследования в дифференциальной иг- ре многих объектов с простыми движениями // Тр. МИАН СССР. — 1981. — 158. — C. 87–97. 9. Рихсиев Б.Б. Дифференциальные игры с простыми движениями. — Ташкент : ФАН, 1989. — 232 с. 10. Ибрагимов Г.И., Рихсиев Б.Б. О некоторых достаточных условиях оптимальности времени преследования в дифференциальной игре со многими преследующими // Автоматика и те- лемеханика. — 2006. — № 4. — C. 16–24. 11. Петросян Л.А., Томский Г.В. Геометрия простого преследования. — Новосибирск : Наука, 1983. — 140 с. 12. Пашко С.В. Квазиоптимальные стратегии в дифференциальных играх преследования на плоскости // Международный научно-технический журнал «Проблемы управления и ин- форматики». — 2012. — № 6. — C. 30–43. 13. Гордон А.Я. Один алгоритм решения минимаксной задачи о назначениях // Исследования по дискретной оптимизации. — М. : Наука, 1976. — С. 327–333. Получено 06.12.2012 Статья представлена к публикации чл.-корр. НАН Украины А.М. Гупалом.

Сложность задач оптимизации преследования на плоскости

Репозитарії

Схожі ресурси