Эффективные стратегии преследования, основанные на использовании функции Ляпунова

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2016
Автор:	Пашко, С.В.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Видавничий дім "Академперіодика" НАН України 2016
Назва видання:	Доповіді НАН України
Теми:	Інформатика та кібернетика
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/98135
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Эффективные стратегии преследования, основанные на использовании функции Ляпунова / С.В. Пашко // Доповiдi Нацiональної академiї наук України. — 2016. — № 1. — С. 26-33. — Бібліогр.: 5 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-98135
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-981352025-02-09T09:55:31Z Эффективные стратегии преследования, основанные на использовании функции Ляпунова Ефективнi стратегiї переслiдування, заснованi на використаннi функцiї Ляпунова Effective pursuit strategies based on the use of the Lyapunov function Пашко, С.В. Інформатика та кібернетика Данная работа посвящена дифференциальным играм преследования, в которых несколько игроков догоняют одного. В качестве критерия используется время захвата цели. Предполагается, что убегающий игрок окружен преследователями. Для известной стратегии параллельного сближения описана функция, задающая точное гарантированное время захвата цели. Эта функция используется в качестве функции Ляпунова для построения новой стратегии преследования, превосходящей стратегию параллельного сближения. Дана робота присвячена диференцiйним iграм переслiдування, в яких кiлька гравцiв доганяють одного. Критерiєм виступає час захоплення цiлi. Вважається, що втiкач оточений переслiдувачами. Для вiдомої стратегiї паралельного зближення описана функцiя, що задає точний гарантований час захоплення цiлi. Ця функцiя використовується як функцiя Ляпунова для побудови нової стратегiї переслiдування, що перевершує стратегiю паралельного зближення. This paper is concerned with differential pursuit-evasion games, in which several players chase one. The time of capture of a target is used as the criterion. It is assumed that the target is surrounded by pursuers. The function that sets the exact guaranteed time of a capture of the target for the well-known strategy of parallel approach is described. This function is used as a Lyapunov function for constructing the new chase strategy, which outperforms the strategy of parallel approach. 2016 Article Эффективные стратегии преследования, основанные на использовании функции Ляпунова / С.В. Пашко // Доповiдi Нацiональної академiї наук України. — 2016. — № 1. — С. 26-33. — Бібліогр.: 5 назв. — рос. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/98135 518.9 ru Доповіді НАН України application/pdf Видавничий дім "Академперіодика" НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Інформатика та кібернетика Інформатика та кібернетика
spellingShingle	Інформатика та кібернетика Інформатика та кібернетика Пашко, С.В. Эффективные стратегии преследования, основанные на использовании функции Ляпунова Доповіді НАН України
description	Данная работа посвящена дифференциальным играм преследования, в которых несколько игроков догоняют одного. В качестве критерия используется время захвата цели. Предполагается, что убегающий игрок окружен преследователями. Для известной стратегии параллельного сближения описана функция, задающая точное гарантированное время захвата цели. Эта функция используется в качестве функции Ляпунова для построения новой стратегии преследования, превосходящей стратегию параллельного сближения.
format	Article
author	Пашко, С.В.
author_facet	Пашко, С.В.
author_sort	Пашко, С.В.
title	Эффективные стратегии преследования, основанные на использовании функции Ляпунова
title_short	Эффективные стратегии преследования, основанные на использовании функции Ляпунова
title_full	Эффективные стратегии преследования, основанные на использовании функции Ляпунова
title_fullStr	Эффективные стратегии преследования, основанные на использовании функции Ляпунова
title_full_unstemmed	Эффективные стратегии преследования, основанные на использовании функции Ляпунова
title_sort	эффективные стратегии преследования, основанные на использовании функции ляпунова
publisher	Видавничий дім "Академперіодика" НАН України
publishDate	2016
topic_facet	Інформатика та кібернетика
url	https://nasplib.isofts.kiev.ua/handle/123456789/98135
citation_txt	Эффективные стратегии преследования, основанные на использовании функции Ляпунова / С.В. Пашко // Доповiдi Нацiональної академiї наук України. — 2016. — № 1. — С. 26-33. — Бібліогр.: 5 назв. — рос.
series	Доповіді НАН України
work_keys_str_mv	AT paškosv éffektivnyestrategiipresledovaniâosnovannyenaispolʹzovaniifunkciilâpunova AT paškosv efektivnistrategiíperesliduvannâzasnovaninavikoristannifunkciílâpunova AT paškosv effectivepursuitstrategiesbasedontheuseofthelyapunovfunction
first_indexed	2025-11-25T15:28:14Z
last_indexed	2025-11-25T15:28:14Z
_version_	1849776669484646400
fulltext	оповiдi НАЦIОНАЛЬНОЇ АКАДЕМIЇ НАУК УКРАЇНИ 1 • 2016 IНФОРМАТИКА ТА КIБЕРНЕТИКА УДК 518.9 http://dx.doi.org/10.15407/dopovidi2016.01.026 С.В. Пашко Институт программных систем НАН Украины, Киев E-mail: pashko55@yahoo.com Эффективные стратегии преследования, основанные на использовании функции Ляпунова (Представлено академиком НАН Украины Ф.И. Андоном) Данная работа посвящена дифференциальным играм преследования, в которых несколько игроков догоняют одного. В качестве критерия используется время захвата цели. Пред- полагается, что убегающий игрок окружен преследователями. Для известной стра- тегии параллельного сближения описана функция, задающая точное гарантированное время захвата цели. Эта функция используется в качестве функции Ляпунова для построения новой стратегии преследования, превосходящей стратегию параллельного сближения. Ключевые слова: дифференциальная игра, стратегия преследования, время преследо- вания, функция Ляпунова. Задачи преследования — уклонения занимают одно из центральных мест в теории дина- мических игр. В данной работе рассматривается задача преследования одного убегающего несколькими преследователями. В качестве критерия выступает время захвата цели, ко- торое преследователи стремятся минимизировать, а убегающий игрок стремится максими- зировать. В последнее время проявляется интерес к созданию многоагентных роботизированных систем защиты, систем беспилотных летательных аппаратов и т. д., поэтому рассматрива- емая задача является актуальной. В работах [1, 2] задача преследования — уклонения решена при условии, что убегающий игрок не принадлежит внутренности выпуклой оболочки, образованной преследователями. Найдены оптимальные стратегии игроков и цена игры. Доказано, что все игроки с постоян- ными максимальными скоростями движутся к определенной точке, где и происходит захват © С.В. Пашко, 2016 26 ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2016, №1 цели. В данной работе рассматриваются только игры, в которых убегающий игрок прина- длежит внутренности выпуклой оболочки, образованной преследователями. Оптимальные стратегии известны не для всех таких игр. Построенная в работе новая стратегия преследования существенно использует класси- ческую стратегию параллельного сближения, которая состоит в следующем. Каждый пре- следователь, зная скорость преследуемого в данный момент времени, считает эту скорость постоянной и вычисляет на линии движения убегающего игрока точку захвата, в которой он может догнать его, двигаясь с постоянной максимальной скоростью. В текущий момент времени вектор скорости преследователя направлен на точку захвата, а величина скорости максимальна. Если максимальные скорости преследователя и убегающего равны, а точка захвата отсутствует, преследователь двигается параллельно убегающему игроку. В работах [3–5] предполагается, что все преследователи применяют стратегию парал- лельного сближения. При этом условии найдена оптимальная стратегия уклонения и точное гарантированное время преследования T . В данной работе время T , зависящее от координат игроков, используется как функция Ляпунова для построения стратегии преследования, которая обеспечивает время захвата цели меньшее, чем стратегия параллельного сближения. Стратегии агентов и гарантированное время преследования. Пусть в точке X0 = X0(t) n-мерного действительного евклидового пространства En в момент времени t расположен преследуемый игрок E, а в точках Xi = Xi(t) находятся преследователи Pi, i = 1, 2, . . . ,m. Векторы Vi = Vi(t) размерности n, i = 0, 1, . . . ,m, обозначают скорости игроков (нулевое значение индекса i относится к игроку E). Пространство En состоит из n-мерных векторов X = (x1, x2, . . . , xn) c вещественными компонентами, 2 6 n < ∞. Норма вектора X задается формулой ∥X∥ = ⟨X,X⟩1/2, где ⟨X,Y ⟩= n∑ i=1 xiyi — скалярное произведение векторовX=(x1, x2, . . . , xn) и Y =(y1, y2, . . . , yn). Игра начинается в момент времени t = 0. Уравнения движения игроков имеют вид Ẋi = Vi, i = 0, 1, . . . ,m. Считаем, что выполняются ограничения 0 6 ∥Vi(t)∥ 6 wi, t > 0, i = 0, 1, . . . ,m, где 0 < wi < ∞ — максимальная величина скорости. Пусть выполняются неравенства w0 6 wi, i = 1, 2, . . . ,m. Движение игроков предполагается простым. В каждый момент времени игрок может выбрать произвольный вектор скорости движения, норма которого не превосходит заданной величины. Скорость V0(t) считается кусочно-непрерывной функцией от времени. Обозначим Z(t) = (X0(t), X1(t), . . . , Xm(t)) фазовый вектор, содержащий координаты игроков, зависящие от времени. Игрок E управляет своими координатами, выбирая в ка- ждый момент времени вектор скорости V0, являющийся функцией от времени и от точки Z(t). Функцию V0(t, Z(t)), t > 0, назовем стратегией убегающего игрока и обозначим SE . Преследователь Pi в каждый момент времени выбирает вектор скорости Vi, который зависит от времени, точки Z(t) и от вектора V0(t). Функцию Vi(t) = Vi(t, Z(t), V0(t)), t > 0, назовем стратегией преследователя и обозначим SPi , i = 1, 2, . . . ,m. Стратегией преследо- вания назовем вектор SP = (SP1 , SP2 , . . . , SPm). Временем завершения игры назовем величину T (Z(0), SE , SP ) = inf{t : min i=1,...,m (∥Xi(t)−X0(t)∥ − li) < 0}, где li > 0 — заданные числа. Игрок E стремится максимизировать величину T (Z(0), SE , SP ), а преследователи стремятся ее минимизировать. Считаем, что ∥Xi(0)−X0(0)∥ > li, i = ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2016, №1 27 = 1, 2, . . . ,m. Гарантированным временем преследования для стратегии SP назовем величи- ну T (Z(0), SP ) = sup SE T (Z(0), SE , SP ). Из двух стратегий преследования более эффективной будем считать ту, для которой гарантированное время преследования меньше. Гарантированное время преследования для стратегии параллельного сбли- жения. Пусть все преследователи используют стратегию параллельного сближения. Для этого случая в работах [3–5] исследована оптимальная стратегия убегающего игрока и най- дено гарантированное время преследования. Обозначим conv{X1, X2, . . . , Xm} выпуклую оболочку точек X1, X2, . . ., Xm. Пусть int X — внутренность множества X. Рассмотрим случай, когда точка расположения убегаю- щего X0 принадлежит внутренности выпуклой оболочки точек X1, X2, . . . , Xm, т. е. выпол- няется условие X0 ∈ int conv{X1, X2, . . . , Xm}. (1) Стратегия параллельного сближения обладает следующим свойством. Углы между ве- кторами → X0Xi и → X0Xj на протяжении игры остаются постоянными, потому что прямые X0(t)Xq(t) и X0(0)Xq(0) параллельны при каждом t > 0; q = 1, 2, . . . ,m [2]. Поэтому из то- го, что условие (1) выполняется в начальный момент следует, что это условие выполняется на протяжении всей игры. Из теоремы 1 [3] следует существование оптимальной стратегии уклонения S∗ E = = (t∗1, t ∗ 2, . . . , t ∗ m, Z ∗ 1 , Z ∗ 2 , . . . , Z ∗ m), где величины t∗i , Z ∗ i означают следующее. Представим вре- менной промежуток [0, T ∗), где T ∗ = T (S∗ E) = m∑ i=1 t∗i — момент окончания игры, в виде объединения m непересекающихся промежутков, [0, T ∗) = m∪ i=1 [τ (1) i , τ (2) i ). Длина промежутка [τ (1) i , τ (2) i ) равна t∗i , а вектор скорости стратегии уклонения S∗ E на промежутке [τ (1) i , τ (2) i ) ра- вен w0Z ∗ i , причем ∥Z∗ i ∥ = 1, i = 1, 2, . . . ,m, n-мерные векторы Z∗ i не изменяются с течением времени. Теорема 2 [3] утверждает, что в каждый момент времени t ∈ (0, T ∗) такой, что опти- мальная стратегия V ∗ 0 (t) непрерывна, выполняется равенство ∥V ∗ 0 (t)∥ = w0. Из работы [3] следует, что с любой наперед заданной точностью можно получить опти- мальную стратегию уклонения, решив задачу линейного программирования следующего вида ∑ R∈{R} tR → max, (2) ∑ R∈{R} uiRtR 6 di − li, i = 1, 2, . . . ,m, (3) tR > 0, R ∈ {R}. (4) Здесь R — (n−1)-мерный вектор; {R} — конечное множество таких векторов, определенное в [3]; tR — переменные, величины uiR определяются в [3], di = ∥Xi(0) −X0(0)∥. Обозначим Ni = (Xi(0) − X0(0))/∥Xi(0) − X0(0)∥, i = 1, 2, . . . ,m. При условии равен- ства скоростей всех игроков в работе [4] доказана теорема, позволяющая точно определить 28 ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2016, №1 оптимальную стратегию уклонения, используя оптимальное решение следующей задачи линейного программирования ∑ I∈{I} 2∑ k=1 tIk → max, (5) ∑ I∈{I} 2∑ k=1 uiIktIk 6 di − li, i = 1, 2, . . . ,m, (6) tIk > 0, I ∈ {I}, k = 1, 2. (7) Здесь I = {i1, i2, . . . , in−1} — подмножество множества {1, 2, . . . ,m} такое, что система век- торов H = {Ni1 , Ni2 , . . . , Nin−1} линейно независима; {I} — множество всех таких подмно- жеств; NI1, NI2 — векторы единичной длины, ортогональные каждому вектору из систе- мы H, причем NI1 = −NI2; величины uiIk расчитываются по формулам uiIk = { 0, ⟨Ni, NIk⟩ < 0, 2w0⟨Ni, NIk⟩, ⟨Ni, NIk⟩ > 0, i = 1, 2, . . . ,m, I ∈ {I}, k = 1, 2. Пусть три игрока преследуют одного на плоскости, т. е. m = 3, n = 2. Символами α, β, γ обозначим углы X2,X0, X3, X3,X0,X1, X1,X0,X2 соответственно. Имеем α+β+γ = 2π. Считаем, что γ 6 β 6 α. Из условия (1) вытекают неравенства γ > 0, α < π. Оптимальное значение целевой функции задачи (5)–(7) обозначим T ∗. В [4] выведена формула T ∗ = 1 2w0 ( d1 − l1 sinβ + d2 − l2 + d3 − l3 sinα ) . (8) Стратегия преследования, использующая функцию Ляпунова. В каждый мо- мент времени t > 0 в пространстве En выберем декартову систему координат таким обра- зом, чтобы игрок E находился в ее центре, X0(t) = (0, 0, . . . , 0), t > 0. Считаем, что на- правления осей координат не изменяются со временем. Уравнения движения преследова- телей имеют вид Ẋi = Vi − V0, i = 1, 2, . . . ,m. Фазовым вектором будем считать Z(t) = = (X1(t), . . . , Xm(t)), фазовое пространство состоит из всех фазовых векторов. Стратегия, построенная ниже, основана на использовании функции Ляпунова W (Z). Считаем, что функция W (Z), определенная на фазовом пространстве и принимающая ко- нечные вещественные значения, удовлетворяет следующим условиям: 1) функция W (Z) непрерывна и ограничена снизу; 2) существует такая стратегия преследования, что при любой стратегии уклонения по- чти в каждый момент времени t > 0, предшествующий моменту окончания игры, выпол- няется неравенство Ẇ (t) 6 c, где c < 0 — константа. Условия 1 и 2 гарантируют существование стратегии преследования, которая обеспе- чивает завершение игры за конечное время. В каждый момент времени преследователи выбирают свою скорость таким образом, чтобы функция W (t) =W (X1(t), X2(t), . . . , Xm(t)) убывала наиболее быстро. Выберем функцию W в виде W = T ∗, где T ∗ — оптимальное значение целевой функции задачи (2)–(4) или (5)–(7). Очевидно, величина W является функцией от фазовой точки Z, W = W (Z) = W (Z(t)). ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2016, №1 29 Если преследователи применяют стратегию параллельного сближения, а убегающий применяет описанную выше оптимальную стратегию S∗ E , то справедливо равенство Ẇ (t) = = −1. Но если преследователи выбирают скорости из условия минимума величины Ẇ (t) и почти всегда выполняется неравенство Ẇ (t) < −1, то цель будет захвачена быстрее. Не- равенство Ẇ (t) > −1 невозможно, так как преследователи могут использовать стратегию параллельного сближения. На множестве точек Z, удовлетворяющих условию (1) и неравенствам ∥Xi∥ > li, i = 1, 2, . . . ,m, функция W (Z) является кусочно-гладкой. Если фазовая точка принадлежит об- ласти гладкости, то скорости преследования, при которых величина Ẇ (t) принимает ми- нимальное значение, легко рассчитать, используя градиент функции W (Z). В противном случае для определения скоростей преследования достаточно решить несколько простых экстремальных задач, по одной для каждой прилегающей области гладкости. Рассмотрим подробно стратегию преследования для простой игры при условиях m = 3, n = 2, w0 = w1 = w2 = w3 = w. (9) Из условий (8), (9) вытекает, что функция W вычисляется по формуле W = 1 2w ( d1 − l1 sinβ + d2 − l2 + d3 − l3 sinα ) , (10) где 0 < γ 6 β 6 α < π. Если точка X0 = (0, 0), в которой расположен убегающий, принадлежит границе мно- жества conv{X1, X2, X3}, и выполняются неравенства ∥Xi∥ > li, i = 1, 2, 3, то величи- на W (X1, X2, X3) принимает значение +∞. При условии (1) справедливо соотношение W (X1, X2, X3) < ∞. Если стратегия преследования такова, что Ẇ (t) 6 −1, то из спра- ведливости условия (1) в начальный момент следует его справедливость на протяжении всей игры. Из этого следует, что выполняются неравенства 0 < α, β, γ < π. Пусть Xi = (xi, yi), i = 1, 2, 3. Если выполняются соотношения α ̸= β, α ̸= γ, β ̸= γ, то функция W = W (Z) = W (x1, y1, x2, y2, x3, y3) имеет непрерывные частные производные по переменным x1, y1, x2, y2, x3, y3, иначе гладкость функции W нарушается. Используя (10), найдем градиент G = (Wx1 ,Wy1 ,Wx2 ,Wy2 ,Wx3 ,Wy3) функции W (x1, y1, x2, y2, x3, y3) при условиях 0 < γ < β < α < π. Здесь Wxi , Wyi означают производные функции W по переменным xi, yi соответственно. Имеем sinα = √ 1− cos2 α = √ 1− ⟨X2, X3⟩2 ∥X2∥2∥X3∥2 = √ (x22 + y22)(x 2 3 + y23)− (x2x3 + y2y3)2 (∥X2∥∥X3∥) = = √ x22y 2 3 + x23y 2 2 − 2x2y2x3y3 ∥X2∥∥X3∥ = \|D23\| (d2d3) . (11) Здесь D23 = x2y3 − x3y2, di = ∥Xi∥, i = 1, 2, 3. Аналогично выводим sinβ = \|D13\| d1d3 , (12) где D13 = x1y3 − x3y1. Из (10)–(12) имеем W = d3 2w ( d1 d1 − l1 \|D13\| + d2 d2 − l2 + d3 − l3 \|D23\| ) . (13) 30 ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2016, №1 Из неравенств 0 < α, β, γ < π следует, что величины D13 и D23 не равны нулю. Пусть s13 = { −1, D13 < 0, 1, D13 > 0. Из определения D13 получаем формулы ∂\|D13\|/∂x1 = s13y3, ∂\|D13\|/∂y1 = −s13x3, с помощью которых из (14) выводим Wx1 = d3 2wD2 13 ( D13x1 ( 2x1 − l1x1 d1 ) − s13y3d1(d1 − l1) ) , Wy1 = d3 2 wD2 13 (( 2y1 − l1y1 d1 ) D13 + s13x3d1(d1 − l1) ) . Остальные компоненты градиента вычисляются аналогично. В области гладкости функции W найдем скорости игроков, для которых достигается минимакс Ẇ (t). Пусть ψ(t) — угол, образующий с осью абсцисс вектор скорости V0(t); φi(t) — угол, который образует с осью абсцисс вектор скорости Vi(t), i = 1, 2, 3. Имеем V0(t) = w(cosψ(t), sinψ(t)), Vi(t) = w(cosφi(t), sinφi(t)). Система уравнений Ẋi = Vi − V0, i = 1, 2, 3, принимает вид ẋi(t) = w(cosφi(t)− cosψ(t)), ẏi(t) = w(sinφi(t)− sinψ(t)), i = 1, 2, 3. Обозначим φ = (φ1, φ2, φ3). Имеем min φ max ψ Ẇ (t) = min φ max ψ ( 3∑ i=1 (Wxi ẋi(t) +Wyi ẏi(t)) ) = = wmin φ max ψ ( 3∑ i=1 (Wxi(cosφi − cosψ) +Wyi(sinφi − sinψ)) ) = = wmin φ max ψ ( 3∑ i=1 (Wxi cosφi +Wyi sinφi)− ( cosψ 3∑ i=1 Wxi + sinψ 3∑ i=1 Wyi )) = = w (∑3 i=1 (Wxi cosφi +Wyi sinφi)− ( cosψ 3∑ i=1 Wxi + sinψ ∑3 i=1 Wyi )) . (14) Здесь φi, ψ — значения переменных, для которых достигается минимакс. Обозначим ρ0 = √( 3∑ i=1 Wxi )2 + ( 3∑ i=1 Wyi )2 , ρi = √ (Wxi) 2 + (Wyi) 2, i = 1, 2, 3. Из (14) вытекают соотношения cosψ = − 3∑ i=1 Wxi ρ0 , sinψ = − 3∑ i=1 Wyi ρ0 , cosφi = −Wxi ρi , sinφi = −Wyi ρi , i = 1, 2, 3. ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2016, №1 31 Таким образом, для достижения минимакса функции Ẇ (t) в момент времени t игроки должны выбирать скорости по формулам V0 = −w ρ0  3∑ i=1 Wxi 3∑ i=1 Wyi  , Vi = −w ρi ( Wxi Wyi ) , i = 1, 2, 3. Величина Ẇ (t) при этом вычисляется следующим образом Ẇ (t) = w ( ρ0 − 3∑ i=1 ρi ) . (15) Во всех рассмотренных примерах величина Ẇ (t), рассчитанная по формуле (15), оказалось меньше, чем −1, что обеспечивает меньшее время захвата цели по сравнению со стратегией параллельного сближения. Найдем скорости преследователей в случае отсутствия непрерывных частных производ- ных, т. е. в случае выполнения условий γ = β < α, или γ < β = α, или γ = β = α. Пусть в некоторой точке Z фазового пространства выполняются соотношения γ = β < < α. Тогда W = max{W1,W2}, где W1 = 1 2w ( d1 − l1 sinβ + d2 − l2 + d3 − l3 sinα ) , W2 = 1 2w ( d1 − l1 sin γ + d2 − l2 + d3 − l3 sinα ) . Обозначим M — множество точек Z фазового пространства, удовлетворяющих уравне- нию W1(Z) = W2(Z). Очевидно, Z ∈ M . В некоторой окрестности точки Z множество M представляет собой гладкую пятимерную поверхность. Пусть G1 и G2 — градиенты фун- кций W1 и W2 соответственно; H — вектор единичной длины, ортогональный к поверхно- сти M в точке Z. Нетрудно видеть, что H = z(G1 − G2), где z — действительное число. Пусть H = (G1 − G2)/∥G1 − G2∥. Обозначим V = (V1, V2, V3), V 0 = (V0, V0, V0). Считая вектор V 0 постоянным, решим две экстремальные задачи (16) и (17), и из двух полученных оптимальных решений выберем то, значение целевой функции для которого меньше: ⟨V − V 0, G1⟩→ V min, ⟨V − V 0,H⟩ > 0, ∥Vi∥ 6 w, i = 1, 2, 3, (16) ⟨V − V 0, G2⟩→ V min, ⟨V − V 0,H⟩ 6 0, ∥Vi∥ 6 w, i = 1, 2, 3. (17) Случаи γ < β = α и γ = β = α рассматриваются аналогично. Таким образом, построена стратегия преследования на основе выбранной функции Ля- пунова. Из построения следует, что для каждой игры эта стратегия обеспечивает время захвата цели, которое не больше, чем время, необходимое для стратегии параллельного сближения. Вместе с тем, для всех рассмотренных примеров время завершения игры ока- залось строго меньшим, чем у стратегии параллельного сближения. 32 ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2016, №1 Цитированная литература 1. Айзекс Р. Дифференциальные игры. – Москва: Мир, 1967. – 480 с. 2. Рихсиев Б.Б. Дифференциальные игры с простыми движениями. – Ташкент: ФАН, 1989. – 232 с. 3. Пашко С.В., Яловец А.Л. Максимальное время преследования для стратегии параллельного сбли- жения // Пробл. программирования. – 2014. – № 4. – С. 78–93. 4. Пашко С.В. Гарантированное время преследования для стратегии параллельного сближения в случае равенства скоростей игроков // Компьют. математика. – 2014. – № 1. – С. 140–149. 5. Пашко С.В. Гарантированное время преследования для стратегии параллельного сближения // Доп. НАН України. – 2014. – № 4. – С. 43–48. References 1. Isaacs R. Differential games, New York: Dover Publications, 1999. 2. Rikhsiev B.B. Simple motion differential games, Tashkent: Fan, 1989 (in Russian). 3. Pashko S.V., Yalovets A. L. Problems in Programming, 2014, No 4: 78–93 (in Russian). 4. Pashko S.V. Maximal time of pursuit for the strategy of parallel approach in case of equal speeds, in Computer Mathematics, Kiev: Institute of Cybernetics of the NAS of Ukraine, 2014, No 1: 140-149 (in Russian). 5. Pashko S.V. Dopov. NAN Ukraine, 2014, No 4: 43–48 (in Russian). Поступило в редакцию 27.08.2015 С.В. Пашко Iнститут програмних систем НАН України, Київ E-mail: pashko55@yahoo.com Ефективнi стратегiї переслiдування, заснованi на використаннi функцiї Ляпунова Дана робота присвячена диференцiйним iграм переслiдування, в яких кiлька гравцiв доганя- ють одного. Критерiєм виступає час захоплення цiлi. Вважається, що втiкач оточений переслiдувачами. Для вiдомої стратегiї паралельного зближення описана функцiя, що задає точний гарантований час захоплення цiлi. Ця функцiя використовується як функцiя Ляпу- нова для побудови нової стратегiї переслiдування, що перевершує стратегiю паралельного зближення. Ключовi слова: диференцiйна гра, стратегiя переслiдування, час переслiдування, функцiя Ляпунова. S.V. Pashko Institute of Software Systems of the NAS of Ukraine, Kiev E-mail: pashko55@yahoo.com Effective pursuit strategies based on the use of the Lyapunov function This paper is concerned with differential pursuit-evasion games, in which several players chase one. The time of capture of a target is used as the criterion. It is assumed that the target is surrounded by pursuers. The function that sets the exact guaranteed time of a capture of the target for the well-known strategy of parallel approach is described. This function is used as a Lyapunov function for constructing the new chase strategy, which outperforms the strategy of parallel approach. Keywords: differential game, chase strategy, time of capture, Lyapunov function. ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2016, №1 33

Эффективные стратегии преследования, основанные на использовании функции Ляпунова

Репозитарії

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