Numerical Methods for Solving the Pursuit Optimization Problems

Problems in programming 2013; 4: 74-85

Gespeichert in:

Bibliographische Detailangaben
Datum:	2025
Hauptverfasser:	Pashko, C.V., Yalovets, A.L.
Format:	Artikel
Sprache:	Russisch
Veröffentlicht:	PROBLEMS IN PROGRAMMING 2025
Schlagworte:	УДК 518.9
Online Zugang:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/743
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Problems in programming
Завантажити файл:

Institution

Problems in programming

_version_	1859499576526897152
author	Pashko, C.V. Yalovets, A.L.
author_facet	Pashko, C.V. Yalovets, A.L.
author_sort	Pashko, C.V.
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
collection	OJS
datestamp_date	2025-04-16T13:52:57Z
description	Problems in programming 2013; 4: 74-85
first_indexed	2025-07-17T09:37:35Z
format	Article
fulltext	Прикладні засоби програмування та програмне забезпечення © С.В. Пашко, А.Л. Яловец, 2013 74 ISSN 1727-4907. Проблеми програмування. 2013. № 4 УДК 518.9 С.В. Пашко, А.Л. Яловец ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ ПРЕСЛЕДОВАНИЯ Рассмотрены дифференциальные игры преследования на плоскости, в которых для каждого убегающе- го создается группа преследователей. Сформулированы задачи оптимизации групп преследования. По- строены численные методы решения таких задач, выполнены вычислительные эксперименты и сдела- ны выводы об эффективности методов. Введение В данной работе рассматриваются методы решения задач оптимизации пре- следования на плоскости, применяемые в разрабатываемом программном обеспече- нии. Одно из центральных мест в теории динамических игр занимают задачи пре- следования и убегания. Динамические иг- ры, согласно [1], разделяются на игры ка- чества и игры степени. В играх качества представляют интерес два исхода игры. Например, требуется определить, могут ли преследователи захватить цель до опреде- ленного момента времени или нет. В играх степени требуется построить оптимальные стратегии игроков, для которых достигает- ся минимакс функции платы. В настоящей работе задача преследования в пределах одной группы рассматривается как игра степени. Следует отметить достигнутые успехи в построении роботизированных систем преследователей на практике, в ко- торых несколько роботов преследуют не- которое количество целей [2]. В работе [3] изучается сложность задач преследования, в которых число преследователей и число преследуемых больше одного. В этих задачах критерием качества является время окончания игры, т. е. время захвата всех целей. Движения игроков считаются простыми, при этом предполагается, что максимальная ско- рость каждого преследователя превосхо- дит максимальную скорость любого убе- гающего. Каждому преследователю раз- решается захватить не более одного убе- гающего. Множество преследователей разбивается на группы, причем для каждой цели создается одна группа [4]. В любой момент времени группы могут быть пере- формированы. После захвата цели вся группа вместе с целью выбывают из игры. Все цели должны быть захвачены. Требу- ется найти оптимальный состав групп, т. е. такой, для которого момент захвата по- следней цели минимален. В каждой группе преследователи и убегающий игрок при- меняют оптимальные или близкие к ним стратегии движения; такого рода стратегии изучались в [1, 5–9]. В работе [3] показано, что задача оптимизации состава групп преследования является NP-трудной в сильном смысле. Из этого сделаны выводы о том, какие численные методы следует применять для ее решения. В настоящей работе описаны метод случайного поиска с локальной оптимиза- цией и метод ветвей и границ для оптими- зации групп преследования. Выполнены численные эксперименты, из которых сле- дуют выводы об эффективности этих ме- тодов. 1. Преследование одного убегающего Рассмотрим задачу оптимального преследования одного убегающего груп- пой преследователей. Пусть на плоскости в точке 0X находится преследуемый игрок E, а в точках iX находятся преследующие его игроки iP , ki ,...,2,1 . Обозначим iV скорости игроков, ki ,...,2,1,0 (нулевое Прикладні засоби програмування та програмне забезпечення 75 значение индекса i относится к игроку E); здесь iV – двумерные векторы. Уравнения движения игроков имеют вид ii VX  , ki ,...,2,1,0 . (1) Будем считать, что выполняются ограни- чения  ii wV , ki ...,,2,1,0 , (2) где iw – максимальная величина скорости, 22 yxX  – длина вектора ),( yxX  . Кроме того, скорость iV считается кусоч- но-непрерывной функцией от времени. Это означает, что в каждом ограниченном временном интервале существует не больше конечного числа точек разрыва первого рода. Игрок i управляет своими коорди- натами, выбирая в каждый момент време- ни скорость iV . Функция )(tVi – управ- ление i-го игрока. Движение, осуществля- емое таким образом, называется простым. Игра начинается в момент времени 0t и считается законченной, когда координаты одного из преследователей в некоторый момент Tt  совпадают с координатами E, случай T не исключается. Преследо- ватели стремятся уменьшить время T, пре- следуемый стремится его увеличить. Счи- таем, что iww 0 , ki ,...,2,1 . (3) Стратегию игрока i можно опреде- лить как функцию ))(,( tItSi , где )(tI – информация, доступная игроку в момент t. Значением этой функции является управ- ление )(tVi ; игрок i вычисляет свое управ- ление по формуле ))(,( tItSV ii  . Пусть ))(),...,(),(()( 10 tXtXtXtX k u  – фазовый вектор, содержащий координаты игроков, зависящие от времени. Далее считается, что стратегия убегающего зависит только от времени и фазового вектора, а стратегии преследователей зависят еще и от скорости убегающего игрока. Управления )(tVi вы- числяются по формулам: ))(,()( 00 tXtStV u , (4) ))(),(,()( 0 tVtXtStV u ii  , ki ,...,2,1 . (5) Используя уравнения (1), (4), (5), приходим к системе дифференциальных уравнений )),(,()( 00 tXtStX u (6) ))),(,(),(,()( 0 tXtStXtStX uu ii  ki ,...,2,1 , (7) Tt 0 , 0)0( uu XX  . (8) Здесь 0uX – заданное начальное значение вектора uX . Решением системы (6)–(8) считается абсолютно непрерывная функ- ция ))(),...,(),(()( 10 tXtXtXtX k u  , произ- водная которой всюду удовлетворяет соотношениям (6), (7) за исключением, быть может, конечного числа моментов времени в каждом ограниченном временном отрезке. Пусть ),...,,( 21 kSSSS  – страте- гия преследования. Пара стратегий убега- ния и преследования ),( 0 SS называется совместной, если существует единствен- ное решение )(tX u системы уравнений (6)–(8), причем управления )(tVi , вычис- ляемые по формулам (4), (5), являются ку- сочно-непрерывными функциями от t и удовлетворяют соотношениям (2). Приве- денное определение совместной пары стратегий аналогично определению, дан- ному в [6]. Пусть величина ),),0(( 0 SSXT u равна времени захвата цели, если страте- гии 0S и S совместны, и равна  в про- тивном случае. Оптимальным временем преследования назовем число ),),0((supinf 0 0 SSXTt u SS  . (9) Ясно, что из соотношений (3) сле- дует t . Назовем стратегию S опти- Прикладні засоби програмування та програмне забезпечення 76 мальной стратегией преследования, если для каждой стратегии 0S выполняется не- равенство   tSSXT u ),),0(( 0 . Назовем стратегию  0S оптимальной стратегией убегания, если для каждой стратегии S справедливо неравенство:   tSSXT u ),),0(( 0 . Обозначим ),...,,( 21 kVVVV  управ- ление преследования, соответствующее стратегии S. Предположим, преследуемый объект и преследователи применяют оп- тимальные стратегии  0S и S . Получаю- щиеся при этом управления назовем парой оптимальных управлений ),( 0  VV . В случае 2k оптимальные управ- ления  0V и V указаны в [1] (раздел 6.8). Для произвольных значений k задачи оптимального преследования изучаются в [5, 6]. Если имеется только один пресле- дователь, т. е. 1k , то оптимальное время преследования вычисляется по формуле: )/( 01 wwdt  , где d – расстояние между игроками. Рассмотрим подробнее игру с двумя преследователями, т. е. при условии 2k . Обозначим iA окружность Аполло- ния, относящуюся к паре игроков E, iP , 2,1i . Она представляет собой геометри- ческое место точек, в которых могут встретиться игроки E и iP , если они дви- гаются равномерно и прямолинейно с мак- симальными скоростями. Пусть iQ – за- мкнутый круг Аполлония, соответствую- щий окружности iA . Тогда 21 QQQ  – множество таких точек плоскости, до ко- торых игрок E успевает дойти не позже каждого преследователя. Внутренность множества Q представляет собой множе- ство точек, до которых игрок E успевает дойти раньше любого преследователя. Пусть QX  – наиболее удаленная точка от точки 0X из множества Q, т. е. для каж- дого QX  справедливо неравенство  0XX 0XX  . Обозначим  0S стратегию убегаю- щего игрока, которая состоит в том, что он двигается равномерно и прямолинейно с максимальной скоростью по направлению к точке X . До момента времени, равного 00 / wXX  , захват произойти не может, поэтому 00 / wXXt   . В данной игре каждый из преследовате- лей может применить стратегию парал- лельного сближения [8]. В работе [9] до- казано, что применение каждым пресле- дователем этой стратегии приводит к захвату цели за время, которое не пре- восходит величины 00 / wXX  , откуда следует неравенство: 00 / wXXt   . Из двух последних неравенств вытекает соотношение 00 / wXXt   . Управление убегающего игрока, при котором он движется равномерно и прямолинейно с максимальной скоростью по направлению к точке X , обозначим  0V . Управление преследователей, при ко- тором они движутся равномерно и прямо- линейно с максимальной скоростью по направлению к той же точке X , обозна- чим V . Пара ),( 0  VV – это пара оптима- льных управлений. 2. Задача оптимизации групп преследования Рассмотрим задачу формирования оптимальных групп преследования. Пусть на плоскости имеются m преследователей Прикладні засоби програмування та програмне забезпечення 77 и n убегающих, причем 1 nm . Все игроки обладают простым движением, максимальная скорость каждого пресле- дователя больше максимальной скорости любого убегающего. Для каждого убега- ющего образуется группа преследовате- лей, которая после его захвата выбывает вместе с ним из игры. Цель считается за- хваченной, если ее координаты совпадают с координатами одного из преследовате- лей, входящих в группу. Для каждой це- ли заданы минимальное и максимальное количества игроков, которые могут при- надлежать группе. Все цели должны быть захвачены. Требуется составить группы преследования таким образом, чтобы об- щее время завершения игры принимало минимальное значение. Как и в [3], считаем, что в каждой группе игроки применяют оптимальные (или почти оптимальные) стратегии, а время захвата t вычисляется по формуле (9). Пусть целочисленный вектор ),...,,( 21 mjjjJ  задает распределение преследователей по группам. Число ij означает номер цели, которую преследует i-й преследователь, },...,2,1{ mi , },...,2,1,0{ nji  ; если 0ij , то i-й пре- следователь не принимает участия в по- гоне. Обозначим )(Jt j  оптимальное вре- мя преследования в j-й группе (относя- щейся к j-й цели). Пусть натуральное чис- ло )(Jk j равно количеству преследовате- лей в j-й группе. Задачу оптимизации групп преследования можно записать сле- дующим образом: min,)(max ,...,2,1 J j nj Jt   (10) )2()1( )( jjj kJkk  , nj ,...,2,1 . (11) Здесь )2()1( , jj kk задают соответственно ми- нимально возможное и максимально воз- можное число преследователей в j-й группе. Входными данными этой задачи являются координаты на плоскости всех игроков в начале игры, их максимальные скорости, числа )1( jk , )2( jk , m, n. Считаем, что входные данные представляют собой целые числа; максимальные скорости и числа )1( jk , )2( jk , m, n считаются положи- тельными. Предполагаем, что система ограничений (11) совместна, т. е. выпол- няются соотношения )2()1( jj kk  , nj ,...,2,1 ;    n j jkm 1 )1( . Задачу (10), (11) назовем ОПТИ- МИЗАЦИЯ ГРУПП ПРЕСЛЕДОВАНИЯ (сокращенно ОГП). В задаче требуется найти оптимальное значение вектора J, состоящего из целых чисел. Поскольку входные данные также являются целыми числами, то имеет смысл вопрос о том, какова алгоритмическая сложность задачи ОГП. В работе [3] доказана следующая теорема. Теорема. Задача ОГП – NP-трудная в сильном смысле. Заметим, что в [3] эта теорема до- казана при условии, что },...,2,1{ nji  (все преследователи назначаются на цели). Однако такая задача тривиальным обра- зом сводится по Тьюрингу к рассматри- ваемой здесь задаче ОГП. Поэтому теоре- ма остается справедливой при условии },...,2,1,0{ nji  . Задача ОГП – NP-трудная в силь- ном смысле уже в случае, когда для каж- дого убегающего необходимо назначить ровно двух преследователей. Из приведенной теоремы можно сделать выводы о том, какие методы сле- дует применять для решения задачи ОГП. В общем случае задача ОГП не может быть решена полиномиальным или псев- дополиномиальным алгоритмом (при условии P  NP). Для решения подобных задач применяются эвристические алго- ритмы, методы полного перебора, ветвей и границ, случайного поиска с локальной оптимизацией. Прикладні засоби програмування та програмне забезпечення 78 3. Методы оптимизации групп преследования Опишем методы поиска оптималь- ного решения J задачи ОГП: метод ветвей и границ и методы случайного поиска с локальной оптимизацией. Изло- жение общих схем этих методов имеется в [10]. Метод ветвей и границ в процес- се работы разбивает все множество до- пустимых решений задачи ОГП на под- множества. Каждое подмножество реше- ний определяется вектором J, отождеств- ляющимся с некоторой вершиной дерева ветвления. Корневой вершине дерева со- ответствует множество всех допустимых решений; все компоненты соответст- вующего вектора J равны нулю. Листу дерева соответствует одно допустимое решение задачи ОГП. В процессе ветвления вершина дерева, не являющаяся листом, порождает несколько вершин. Считаем, что в исходной вершине (не являющейся корнем дерева) полностью сформированы группы преследования для целей с номерами 1,2,…, 0n , где )(00 Jnn  , nn  01 . Порожденная вершина отличается тем, что в ней полностью сформирована группа преследования для )1( 0 n -й цели. Рассмотрим пример. Пусть для задачи ОГП выполняются условия 4m , 2n , 1 )1( 2 )1( 1  kk , 2 )2( 2 )2( 1  kk . Корневая вершина )0,0,0,0(J порождает десять вершин )0,0,0,1( , )0,0,1,0( , )0,1,0,0( , )1,0,0,0( , )0,0,1,1( , )0,1,0,1( , )1,0,0,1( , )0,1,1,0( , )1,0,1,0( , )1,1,0,0( . Первая из этих вершин означает, что для поимки первой цели сформирована группа, состоящая из одного преследователя (первого). Послед- няя вершина означает, что группу для первой цели составляют третий и четвер- тый преследователи. Первая вершина )0,0,0,1( порождает шесть вершин )0,0,2,1( , )0,2,0,1( , )2,0,0,1( , )0,2,2,1( , )2,0,2,1( , )2,2,0,1( , являющихся листьями. Последний лист )2,2,0,1( означает, что на первую цель назначен первый преследо- ватель, а вторую цель преследует группа, состоящая из третьего и четвертого преследователей. Заметим, что число 0n равно значению максимальной компо- ненты вектора J. В процессе работы метода ветвей и границ для вершин, не являющихся листьями, вычисляются оценки )(00 Jtt  , )(11 Jtt  , )(22 Jtt  . Оценка 0t для вершины J строится следующим образом. Пусть },...,2,1{ 0n – множество целей, для которых вектором J сформированы группы преследования, },...,,{ 21 siii – множество всех задейство- ванных преследователей. Из этих мно- жеств образуем новую задачу ОГП в форме (10), (11), заменяя число m числом s, а число n числом 0n . Найдем допустимое, близкое к оптимальному решение J  этой задачи, применяя алгоритм локальной оптимизации 0A , который описан далее. Значение целевой функции в точке J  выбирается в качестве оценки 0t . Ясно, что при условии )(max 0,...,2,1 0 Jtt j nj    множество допустимых решений, определяемое вектором J, не содержит оптимального решения и вер- шину J можно исключить из рассмот- рения. Величина 1t – оценка снизу значе- ния целевой функции (10) на множестве допустимых решений, заданных вектором J. Она вычисляется следующим образом. Для каждой цели j из множества },...,2,1{ 00 nnn  выбираем группу пре- следователей из числа незадействованных такую, что выполняются условия (11) и время захвата  jt принимает минимальное значение. Полагаем },...,,),(max{ 211 00     nnn tttJtt . Величина 2t – оценка сверху зна- чения целевой функции (10) на множестве допустимых решений, заданных вектором J. Она получается следующим образом. Используя множество незадействованных преследователей, вектор J преобразуем в Прикладні засоби програмування та програмне забезпечення 79 допустимый вектор задачи ОГП с по- мощью эвристического алгоритма 1A , формирующего оставшиеся несформиро- ванными группы преследователей с номерами nnn ,...,2,1 00  . Этот алгоритм описан далее. Затем выполняем алгоритм 0A локальной оптимизации, в результате работы которого получаем точку ло- кального минимума J  , представляющую собой допустимое решение задачи ОГП. Значение целевой функции (10) в точке J  принимаем в качестве оценки 2t . Текущее множество векторов J, рассматриваемых методом, обозначим Q. Пусть J – оптимальное решение задачи ОГП, t – оптимальное значение целевой функции. Обозначим 1)()( 011  JnJnn . Метод ветвей и границ состоит из следующих шагов. 1. Полагаем )0,...,0(J , )(2 Jtt  , JJ  , где J  – точка локального мини- мума, соответствующая значению )(2 Jt . 2. Если множество Q пусто, то вычисления прекращаем; величина t равна минимуму общего времени преследования, а соответствующий ей вектор J определяет оптимальное распределение преследователей по группам. 3. Из множества Q выбираем вектор J с минимальным значением )(1 Jt . Вектор J удаляем из множества Q. Если вы- полняется соотношение  tJt )(1 , пере- ходим к шагу 2. 4. Выполняем шаг ветвления. Век- тор J преобразуем во множество векторов },...,,{ 21 rJJJR  следующим образом. Из всех незадействованных преследователей составляем всевозможные группы преследования для цели с номером 1n , удовлетворяющие условиям (11). Пусть количество таких групп равно r. Каждая группа представляет собой множество номеров преследователей },...,,{ 21 kiii . Используя вектор J и s-ю по порядку группу преследования },...,,{ 21 kiii , об- разуем вектор sJ из множества R. Ком- поненты вектора sJ равны компонентам вектора J, за исключением того, что компоненты с номерами kiii ,...,, 21 вектора sJ равны числу 1n . 5. Предположим, nn 1 (все группы сформированы). Для каждого вектора sJ из множества R вычисляем значение )(max)( ,...,2,1 sj nj s JtJt    целевой функции (10) и, если это значение меньше t , вы- полняем присвоения )( sJtt  , sJJ  . Переходим к шагу 2. 6. Предположим, nn 1 . Для каж- дого вектора sJ из множества R выпол- няем следующие действия. 6.1. Если согласно вектору sJ число незадействованных преследователей меньше нужного количества, требуемого ограничениями (11), удаляем вектор sJ из множества R. 6.2. Если )(max)( 1,...,2,1 0 sj nj s JtJt    , удаляем вектор sJ из множества R. 6.3. Если )(max)( 1,...,2,1 2 sj nj s JtJt    , удаляем вектор sJ из множества R. Если  tJt s )(2 , полагаем )(2 sJtt  , sJJ  , где sJ  – точка локального минимума, соответствующая значению )(2 sJt . 6.4. Если  tJt s )(1 , удаляем вектор sJ из множества R. Все оставшиеся во множестве R векторы добавляем к множеству Q. Пере- ходим к шагу 2. □ Алгоритм локальной оптимиза- ции 0A , использующий начальное допус- тимое решение J задачи ОГП, состоит из следующих шагов. 1. Находим номер 0j группы, время преследования в которой максимально среди всех групп. Прикладні засоби програмування та програмне забезпечення 80 2. Поочередно для групп ,...,2,1j njj ,...,1,1 00  выполняем следующее. Пусть },...,,{ 0002010 kiiiI  – множество преследователей, составляющих группу 0j , а },...,,{ 1112111 kiiiI  – множество преследователей, составляющих группу j. Перераспределяя преследователей множества 10 II  между группами 0j и j всеми возможными способами, удовлетво- ряющими ограничениям (11), образуем множество пар групп. В каждой паре пер- вая группа преследует цель 0j , а вторая – цель j. Пусть время преследования в пер- вой группе равно 0t , а во второй – 1t . Вы- берем пару, в которой общее для обеих групп время преследования ),max( 10 ttt  минимально. Пусть первая группа образо- вана множеством преследователей 2I },...,,{ 222221 kiii , а вторая – множеством },...,,{ 3332313 kiiiI  ; при этом 10 II  32 II  . Если время t меньше времени преследования в исходной группе 0j , то группу 0I заменим группой 2I , а группу 1I заменим группой 3I . Произведем соот- ветствующие изменения в векторе J и перейдем к шагу 1. Если не найдена группа j, позволяющая уменьшить максимальное время преследования в группах 0j и j, вычисления прекращаем. □ Рассмотрим эвристический алго- ритм 1A построения близкого к оптималь- ному допустимого решения задачи ОГП. Предполагается, что имеется начальный вектор J, в котором первые 0n групп преследования уже сформированы. Алго- ритм 1A формирует только группы пресле- дования nnn ),...,2(),1( 00  . В частности, возможно 00 n , т. е. алгоритм форми- рует все группы. Алгоритм 1A состоит из следующих шагов. 1. Просматриваем все группы от )1( 0 n -й до n-й. Если в j-й группе число преследователей меньше величины )1( jk , входящей в (11), то в эту группу добавляется незадействованный преследо- ватель, обеспечивающий наибольшее уменьшение времени преследования в группе. В модифицированной таким образом группе время преследования определяется согласно формуле (9). Шаг 1 выполняется до тех пор, пока имеется хотя бы одна цель j, число преследователей которой меньше, чем )1( jk . 2. Просматриваем все группы от )1( 0 n -й до n-й. Если в j-й группе число преследователей меньше величины )2( jk , входящей в (11), то в эту группу добавляется незадействованный преследо- ватель, обеспечивающий наибольшее уменьшение времени преследования в группе. Шаг 2 выполняется до тех пор, пока имеется хотя бы одна цель j, число преследователей которой меньше, чем )2( jk , и есть незадействованные пресле- дователи. □ Метод случайного поиска с локальной оптимизацией состоит из следующих шагов. 1. Случайным образом формируем допустимое решение J задачи ОГП. Используя решение J в качестве началь- ного, с помощью алгоритма локальной оптимизации 0A вычисляем локальный оптимум J  . 2. Из всех полученных локальных оптимумов J  запоминаем наилучший. Если выполняется критерий останова, прекращаем вычисления, иначе переходим к шагу 1. □ На шаге 1 решение J выбирается согласно равномерному (или близкому к нему) распределению вероятностей на множестве допустимых решений. В качестве критерия останова можно выбрать достижение заранее за- данного числа повторения шага 1 или достижение заранее заданного числа ша- гов, на протяжении которых наилучшее достигнутое значение целевой функции не изменяется. Прикладні засоби програмування та програмне забезпечення 81 4. Результаты численных экспериментов Рассмотрим результаты численных экспериментов с методами полного пере- бора, ветвей и границ, случайного поиска с локальной оптимизацией. Ограничимся случаем, когда в каждой группе преследо- вания допускается участие не более двух преследователей, т. е. справедливы соот- ношения 21 )2()1(  jj kk , nj ,...,2,1 . (12) Для этого имеются две причины. Во- первых, в задачах преследования на плос- кости такой численный состав групп представляется актуальным. Во-вторых, в случае, если число преследователей в группе больше двух, алгоритм расчета оптимального времени согласно соотно- шению (9) известен не для всех способов взаимного расположения преследователей и цели. Оценим количество допустимых решений задачи ОГП при условиях (12). Пусть число 1N равно количеству допу- стимых решений при условиях 1 )1( jk , 1 )2( jk , nj ,...,2,1 ; число 2N равно ко- личеству допустимых решений при усло- виях 2 )1( jk , 2 )2( jk , nj ,...,2,1 ; число 3N равно количеству таковых при услови- ях 1 )1( jk , 2 )2( jk , nj ,...,2,1 . Нетрудно вывести формулы )!( ! 1 nm m N   , nnm m N 2)!2( ! 2   ,     n j jnjnm m N 03 2)!2( ! . Значения величин 1N , 2N , 3N при некоторых значениях m и n приведены в табл. 1. Вычислительные эксперименты проводились на персональном компьютере с процессором Pentium® Dual-Core 2,5 GHz. Задачи ОГП формировались случай- ным образом. При этом все координаты (т. е. x или y) целей и преследователей счита- лись независимыми случайными величи- нами, равномерно распределенными на отрезке [–1;1]. Величины скоростей целей и преследователей считались независимы- ми случайными величинами, равномерно распределенными на отрезках [1; 1,9] и [2; 2,9] соответственно. Задачу ОГП при условиях 10m , 5n , 1 )1( jk , 2 )2( jk , nj ,...,2,1 , метод полного перебора решил за 2,5 сек. про- цессорного времени. При условиях 12m , 6n , 1 )1( jk , 2 )2( jk , nj ,...,2,1 , этим методом для решения использовано боль- ше, чем 5 минут. Эти данные и табл. 1 поз- воляют приблизительно оценить количе- ство времени, необходимое для работы ме- тода полного перебора. Метод пригоден только для задач малой размерности и зна- чительно уступает методу ветвей и границ по скорости. В табл. 2 приведены характери- стики работы метода ветвей и границ в зависимости от количества участников. Для каждой пары значений m и n реше- но сто задач ОГП, после чего вычислены данные, приведенные в табл. Символами E, M,  обозначены соответственно среднее время решения задачи, макси- мальное время решения задачи и стан- дартное отклонение времени решения в секундах. Символом S обозначено среднее число решений, помещенных методом ветвей и границ во множество Q в про- цессе решения задачи. Вычислительные эксперименты го- ворят о том, что среднее время решения задачи ОГП методом ветвей и границ быстро растет с ростом чисел m и n, что подтверждается данными табл. 2. Величи- ны M и  , приведенные в данной таблице, свидетельствуют о нестабильном характе- ре работы метода. При фиксированных значениях величин m и n время решения задачи сильно зависит от входных данных и колеблется в широких пределах. Прикладні засоби програмування та програмне забезпечення 82 В табл. 3 приведены результаты ис- пытаний метода случайного поиска с ло- кальной оптимизацией, описанного в раз- деле 3. Для каждой пары значений m и n решено сто задач ОГП. Для каждой задачи методом ветвей и границ вычислялось точное оптимальное значение целевой функции t . Затем эта же задача решалась методом случайного поиска с локальной оптимизацией. Пусть 0C – количество шагов, вы- полненных методом случайного поиска с локальной оптимизацией в процессе реше- ния задачи ОГП, т. е. количество выпол- ненных шагов 1 данного метода. Пусть 1C – суммарное количество выполненных алгоритмом локальной оптимизации 0A шагов 1 этого метода в процессе решения- задачи ОГП. Далее символами 0E , 0M , 0 обозначены соответственно среднее, максимальное значение и стандартное от- клонение величины 0C , а символами 1E , 1M , 1 обозначены аналогичные характе- ристики величины 1C . Данные табл. 3 показывают, что для получения оптимального решения методу случайного поиска с локальной оптимизацией достаточно небольшого количества итераций. Количество ис- пользованного процессорного времени по сравнению со временем метода ветвей и границ незначительно. Стабильность работы этого метода по сравнению с ме- тодом ветвей и границ выше, так как ве- личины ii E/ меньше величин E/ из табл. 2. Опишем еще один вычислитель- ный эксперимент. Случайным образом генерировались задачи ОГП при условии nm 2 . После этого для каждой задачи координаты n преследователей полага- лись равными координатам целей, так что оптимальное значение целевой функции каждой задачи ОГП оказывалось равным нулю. Задачи решались методом случай- ного поиска с локальной оптимизацией. Для каждой пары значений m и n решено сто задач ОГП. Отличие от предыдущего эксперимента заключается в больших значениях чисел m и n, при которых ре- шить задачу методом ветвей и границ не удается. Результаты приведены в табл. 4. Данные табл. 4 говорят о стабильной ра- боте метода при указанных размерностях задач. Во всех случаях найдено опти- мальное решение. Среднее время решения одной задачи при условиях 400m , 200n равно 1,0 сек. Из результатов экспериментов можно сделать вывод о высокой точности и скорости метода случайного поиска с локальной оптимизацией даже при значи- тельных размерностях решаемых задач ОГП. Таблица 1. Зависимость количества допустимых решений задачи ОГП от чисел m и n № m n 1N 2N 3N 1 10 5 30240 113400 824040 2 12 6 665280 7484400 5.5×10 7 3 14 7 1.7×10 7 6.8×10 8 5.0×10 9 4 16 8 5.1×10 8 8.1×10 10 6.0×10 11 5 18 9 1.7×10 10 1.2×10 13 9.2×10 13 6 20 10 6.7×10 11 2.3×10 15 1.7×10 16 7 100 50 3.0×10 93 8.2×10 142 6.1×10 143 Прикладні засоби програмування та програмне забезпечення 83 Таблица 2. Зависимость времени решения задачи ОГП методом ветвей и границ от чисел m и n № m n E M  S 1 12 6 0.2 8.3 0.9 1069 2 13 6 0.4 13.6 1.5 1225 3 13 7 1.0 27.7 3.6 4072 4 14 7 4.5 108.3 15.7 13262 Таблица 3. Зависимость количества итераций метода случайного поиска с локальной оптимизацией от чисел m и n № m n 0E 0M 0 1E 1M 1 1 12 6 1.3 6 0.8 10.4 50 7.9 2 13 6 2.2 17 2.5 18.1 150 22.9 3 13 7 1.9 15 2.2 18.3 196 26.6 4 14 7 1.5 17 1.8 15.8 217 22.2 Таблица 4. Зависимость трудоемкости метода случайного поиска с локальной оптимизацией от чисел m и n № m n 0E 0M 0 1E 1M 1 1 100 50 2.2 12 2.2 501.0 2493 452.1 2 200 100 5.0 32 5.4 2650.2 15573 2748.7 3 400 200 38.1 275 51.0 46769.2 327643 61905.4 5. Применение оптимизации групп преследования в программной системе ”Навигация” Программная система ”Навигация” предназначена для моделирования пове- дения множества реактивных агентов в сложной динамической среде. В частно- сти, система позволяет решать задачи оп- тимизации преследования на плоскости, в том числе оптимизировать состав групп преследования. Приведем пример вычис- ления оптимальных траекторий и групп преследования. Предположим, имеется четыре преследователя и два убегающих. Скорости преследователей превышают скорости убегающих. Считаем, что в каж- дой группе количество преследователей должно быть не меньше одного и не больше двух. Следует решить задачу ОГП в форме (10), (11) при условиях 4m , 2n , 1 )1( jk , 2 )2( jk , 2,1j . На рисунке два убегающих распо- ложены выше четырех преследователей. Оптимальные траектории игроков при- надлежат прямым линиям. В каждой группе объекты двигаются с максималь- ными скоростями по направлению к точ- ке X , которая является наиболее уда- ленной от убегающего игрока точкой в пересечении кругов Аполлония (см. раздел 1). Прикладні засоби програмування та програмне забезпечення 84 Рисунок. Оптимальные траектории преследования и убегания Заключение В данной работе рассмотрены игры преследования на плоскости с простым движением, в которых принимают участие несколько преследователей и убегающих. Считается, что количество преследовате- лей больше числа убегающих, и скорости преследователей больше скоростей убега- ющих. Для захвата целей множество пре- следователей разбивается на группы, при- чем для каждого убегающего создается одна группа. После захвата цели все пре- следователи группы и убегающий выбы- вают из игры. Считается, что в каждой группе игроки используют оптимальные стратегии. В качестве критерия использу- ется время захвата. Приведена теорема о NP-трудности задач оптимизации групп преследования. Эти задачи являются NP-трудными в сильном смысле уже в случае, когда для каждого убегающего необходимо назна- чить ровно двух преследователей. На ос- нове этой теоремы сделаны выводы о том, какие методы следует применять для ре- шения задачи оптимизации групп пресле- дования. Описаны методы ветвей и границ и случайного поиска с локальной оптимиза- цией. Выполнены численные эксперимен- ты, на основании которых сделаны выво- ды о высокой скорости и точности метода случайного поиска с локальной оптимиза- цией для рассматриваемых задач. 1. Айзекс Р. Дифференциальные игры. – М.: Мир, 1967. – 480 с. 2. Marcos A. M. Vieira and Ramesh Govindan and Gaurav S. Sukhatme. "Scalable and Practical Pursuit-Evasion with Networked Robots" // Journal of Intelligent Service Robotics. Special Issue on Networked Robots. – 2009. – N 2. – P. 247–263. 3. Пашко С.В. Сложность задач оптимизации преследования на плоскости // Проблемы управления и информатики. – 2013. – № 3. – С. 27–39. 4. Чикрий А.А. Конфликтно управляемые процессы. – Киев: Наук. думка, 1992. – 384 с. 5. Иванов Р.П., Ледяев Ю.С. Оптимальность времени преследования в дифферен- Прикладні засоби програмування та програмне забезпечення 85 циальной игре многих объектов с простыми движениями // Труды МИАН СССР. – 1981. – 158. – C. 87–97. 6. Рихсиев Б.Б. Дифференциальные игры с простыми движениями. – Ташкент: ФАН, 1989. – 232 с. 7. Ибрагимов Г.И., Рихсиев Б.Б. О некоторых достаточных условиях оптимальности времени преследования в дифферен- циальной игре со многими пресле- дующими // Автоматика и телемеханика. – 2006. – № 4. – С. 16–24. 8. Петросян Л.А., Томский Г.В. Геометрия простого преследования. – Новосибирск: Наука, 1983. – 140 с. 9. Пашко С.В. Квазиоптимальные стратегии в дифференциальных играх преследования на плоскости // Проблемы управления и информатики. – 2012. – № 6. – С. 30– 43. 10. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация // Алгоритмы и сложность. – М.: Мир, 1985. – 510 с. Получено 04.02.2013 Об авторах: Пашко Сергей Владимирович, кандидат физико-математических наук, старший научный сотрудник, Яловец Андрей Леонидович, доктор технических наук, заместитель директора института. Место работы авторов: Институт программных систем НАН Украины, 03187, Киев-187, проспект Академика Глушкова, 40. Тел.: (044) 526 6025, E-mail: pashko55@yahoo.com Тел.: (044) 526 1538, E-mail: yal@isofts.kiev.ua mailto:pashko55@yahoo.com mailto:yal@isofts.kiev.ua
id	pp_isofts_kiev_ua-article-743
institution	Problems in programming
keywords_txt_mv	keywords
language	Russian
last_indexed	2025-07-17T09:37:35Z
publishDate	2025
publisher	PROBLEMS IN PROGRAMMING
record_format	ojs
resource_txt_mv	ppisoftskievua/ba/98e973fb1b394fe8045df4f4d865aaba.pdf
spelling	pp_isofts_kiev_ua-article-7432025-04-16T13:52:57Z Numerical Methods for Solving the Pursuit Optimization Problems Численные методы решения задач оптимизации преследования Pashko, C.V. Yalovets, A.L. УДК 518.9 УДК 518.9 Problems in programming 2013; 4: 74-85 Рассмотрены дифференциальные игры преследования на плоскости, в которых для каждого убегающего создается группа преследователей. Сформулированы задачи оптимизации групп преследования. Построены численные методы решения таких задач, выполнены вычислительные эксперименты и сделаны выводы об эффективности методов.Problems in programming 2013; 4: 74-85 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-04-16 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/743 PROBLEMS IN PROGRAMMING; No 4 (2013); 74-85 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2013); 74-85 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2013); 74-85 1727-4907 ru https://pp.isofts.kiev.ua/index.php/ojs1/article/view/743/795 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
spellingShingle	УДК 518.9 Pashko, C.V. Yalovets, A.L. Numerical Methods for Solving the Pursuit Optimization Problems
title	Numerical Methods for Solving the Pursuit Optimization Problems
title_alt	Численные методы решения задач оптимизации преследования
title_full	Numerical Methods for Solving the Pursuit Optimization Problems
title_fullStr	Numerical Methods for Solving the Pursuit Optimization Problems
title_full_unstemmed	Numerical Methods for Solving the Pursuit Optimization Problems
title_short	Numerical Methods for Solving the Pursuit Optimization Problems
title_sort	numerical methods for solving the pursuit optimization problems
topic	УДК 518.9
topic_facet	УДК 518.9 УДК 518.9
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/743
work_keys_str_mv	AT pashkocv numericalmethodsforsolvingthepursuitoptimizationproblems AT yalovetsal numericalmethodsforsolvingthepursuitoptimizationproblems AT pashkocv čislennyemetodyrešeniâzadačoptimizaciipresledovaniâ AT yalovetsal čislennyemetodyrešeniâzadačoptimizaciipresledovaniâ

Numerical Methods for Solving the Pursuit Optimization Problems

Institution

Ähnliche Einträge