Numerical Methods for Solving the Pursuit Optimization Problems

Problems in programming 2013; 4: 74-85

Збережено в:

Бібліографічні деталі
Дата:	2025
Автори:	Pashko, C.V., Yalovets, A.L.
Формат:	Стаття
Мова:	rus
Опубліковано:	Інститут програмних систем НАН України 2025
Теми:	УДК 518.9
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/743
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-743
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 Інститут програмних систем НАН України 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 rus https://pp.isofts.kiev.ua/index.php/ojs1/article/view/743/795 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-04-16T13:52:57Z
collection	OJS
language	rus
topic	УДК 518.9
spellingShingle	УДК 518.9 Pashko, C.V. Yalovets, A.L. Numerical Methods for Solving the Pursuit Optimization Problems
topic_facet	УДК 518.9 УДК 518.9
format	Article
author	Pashko, C.V. Yalovets, A.L.
author_facet	Pashko, C.V. Yalovets, A.L.
author_sort	Pashko, C.V.
title	Numerical Methods for Solving the Pursuit Optimization Problems
title_short	Numerical Methods for Solving the Pursuit Optimization Problems
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_sort	numerical methods for solving the pursuit optimization problems
title_alt	Численные методы решения задач оптимизации преследования
description	Problems in programming 2013; 4: 74-85
publisher	Інститут програмних систем НАН України
publishDate	2025
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â
first_indexed	2025-07-17T09:37:35Z
last_indexed	2025-07-17T09:37:35Z
_version_	1837886400106594304
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

Numerical Methods for Solving the Pursuit Optimization Problems

Репозитарії

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