Квазиоптимальные стратегии в дифференциальных играх преследования на плоскости

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

Full description

Saved in:

Bibliographic Details
Published in:	Проблемы управления и информатики
Date:	2012
Main Author:	Пашко, С.В.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2012
Subjects:	Оптимальное управление и методы оптимизации
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/207539
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Квазиоптимальные стратегии в дифференциальных играх преследования на плоскости / С.В. Пашко // Проблемы управления и информатики. — 2012. — № 6. — С. 30–43. — Бібліогр.: 9 назв. - рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-207539
record_format	dspace
spelling	Пашко, С.В. 2025-10-09T11:36:21Z 2012 Квазиоптимальные стратегии в дифференциальных играх преследования на плоскости / С.В. Пашко // Проблемы управления и информатики. — 2012. — № 6. — С. 30–43. — Бібліогр.: 9 назв. - рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207539 518.9 10.1615/JAutomatInfScien.v44.i11.30 Робота присвячена диференціальним іграм переслідування на площині, в яких кілька гравців доганяють одного. Визначено та досліджено квазіоптимальні стратегії гравців. Виведено нерівності, що задають множини таких стратегій. Для відомих стратегій знайдено умови, за яких вони квазіоптимальні. Розглянуто задачі вибору найкращої стратегії з множини квазіоптимальних. This paper is concerned with differential pursuit games on a plane, in which several players chase one. Quasi-optimal strategies of players are defined and investigated. The inequalities which specify the sets of such strategies are derived. For the known strategies the conditions under which they are quasi-optimal are found. The problems of choice of the best strategy from a set of the quasi-optimal are considered. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Оптимальное управление и методы оптимизации Квазиоптимальные стратегии в дифференциальных играх преследования на плоскости Квазіоптимальні стратегії в диференціальних іграх переслідування на площині Quasi-Optimal Strategies in the Differential Pursuit Games on a Plane Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Квазиоптимальные стратегии в дифференциальных играх преследования на плоскости
spellingShingle	Квазиоптимальные стратегии в дифференциальных играх преследования на плоскости Пашко, С.В. Оптимальное управление и методы оптимизации
title_short	Квазиоптимальные стратегии в дифференциальных играх преследования на плоскости
title_full	Квазиоптимальные стратегии в дифференциальных играх преследования на плоскости
title_fullStr	Квазиоптимальные стратегии в дифференциальных играх преследования на плоскости
title_full_unstemmed	Квазиоптимальные стратегии в дифференциальных играх преследования на плоскости
title_sort	квазиоптимальные стратегии в дифференциальных играх преследования на плоскости
author	Пашко, С.В.
author_facet	Пашко, С.В.
topic	Оптимальное управление и методы оптимизации
topic_facet	Оптимальное управление и методы оптимизации
publishDate	2012
language	Russian
container_title	Проблемы управления и информатики
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
format	Article
title_alt	Квазіоптимальні стратегії в диференціальних іграх переслідування на площині Quasi-Optimal Strategies in the Differential Pursuit Games on a Plane
description	Робота присвячена диференціальним іграм переслідування на площині, в яких кілька гравців доганяють одного. Визначено та досліджено квазіоптимальні стратегії гравців. Виведено нерівності, що задають множини таких стратегій. Для відомих стратегій знайдено умови, за яких вони квазіоптимальні. Розглянуто задачі вибору найкращої стратегії з множини квазіоптимальних. This paper is concerned with differential pursuit games on a plane, in which several players chase one. Quasi-optimal strategies of players are defined and investigated. The inequalities which specify the sets of such strategies are derived. For the known strategies the conditions under which they are quasi-optimal are found. The problems of choice of the best strategy from a set of the quasi-optimal are considered.
issn	0572-2691
url	https://nasplib.isofts.kiev.ua/handle/123456789/207539
citation_txt	Квазиоптимальные стратегии в дифференциальных играх преследования на плоскости / С.В. Пашко // Проблемы управления и информатики. — 2012. — № 6. — С. 30–43. — Бібліогр.: 9 назв. - рос.
work_keys_str_mv	AT paškosv kvazioptimalʹnyestrategiivdifferencialʹnyhigrahpresledovaniânaploskosti AT paškosv kvazíoptimalʹnístrategíívdiferencíalʹnihígrahpereslíduvannânaploŝiní AT paškosv quasioptimalstrategiesinthedifferentialpursuitgamesonaplane
first_indexed	2025-11-25T20:34:05Z
last_indexed	2025-11-25T20:34:05Z
_version_	1850524875406442496
fulltext	© С.В. ПАШКО, 2012 30 ISSN 0572-2691 ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ И МЕТОДЫ ОПТИМИЗАЦИИ УДК 518.9 С.В. Пашко КВАЗИОПТИМАЛЬНЫЕ СТРАТЕГИИ В ДИФФЕРЕНЦИАЛЬНЫХ ИГРАХ ПРЕСЛЕДОВАНИЯ НА ПЛОСКОСТИ Введение Теория дифференциальных игр является развитой математической дисципли- ной [1–6], одно из центральных мест в которой занимают задачи преследования и убегания. Согласно [1] дифференциальные игры можно разделить на две группы: игры качества и игры степени. В играх качества интерес представляют два исхо- да игры. Например, требуется определить, может ли преследователь захватить цель до определенного момента времени или нет. В играх степени требуется построить оп- тимальные стратегии игроков, для которых достигается минимакс функции платы. Примерами методов решения задач качества являются первый прямой метод Л.С. Понтрягина [4] и метод разрешающих функций [6]. Для построения опти- мальных стратегий в играх степени применяются методы, связанные с основным уравнением теории дифференциальных игр [1], попятные процедуры Л.С. Понт- рягина и Б.Н. Пшеничного [4, 5]. Данная работа посвящена дифференциальным играм преследования на плос- кости, в которых несколько игроков догоняют одного. Рассматриваются игры степени, в которых функцией платы является время захвата цели, зависящее от стратегий игроков. Оптимальные стратегии в рассматриваемых играх образуют седловую точку функции платы. Если стратегия одной из противоборствующих сторон по некото- рым причинам отклоняется от оптимальной, то у другой стороны появляются до- полнительные возможности в виде множества стратегий, названных квазиопти- мальными. Применение преследователями квазиоптимальной стратегии пресле- дования обеспечивает захват цели за время, которое не больше цены игры. Применение преследуемым игроком квазиоптимальной стратегии убегания при- водит к захвату цели за время, которое не меньше цены игры. В настоящей работе выведены неравенства, задающие множества таких стра- тегий. Для известных стратегий найдены условия, при которых они являются ква- зиоптимальными. Оказалось, что стратегия параллельного сближения квазиопти- мальна при условии, что количество преследователей не больше двух. Если же число преследователей не меньше трех, то стратегия параллельного сближения может не быть квазиоптимальной. Рассмотрены задачи выбора наилучшей стратегии из множества квазиопти- мальных. 1. Задача преследования, стратегии игроков и цена игры На неограниченной плоскости имеется преследуемый игрок E с координата- ми ),( 00 yx и преследующие его игроки iP с координатами ),,( ii yx .,...,2,1 ni  Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 6 31 Обозначим ),( iyixi vvV  скорости игроков, ni ,...,2,1,0 (нулевое значение ин- декса i относится к игроку E ). Уравнения движения игроков имеют вид ;sin ,cos iiiiy iiiix vyv vxv     ,,...,2,1,0 ni  (1) здесь iv — величина скорости, , 2ii Vv  i — угол направления скорости, 22 2 yxX  — длина вектора ).,( yxX  Будем считать, что выполняются ограничения ,0 ii wv  ,,...,2,1,0 ni  где  iw0 — максимальная величина скорости. Кроме того, скорость iV считается кусочно-непрерывной функцией от времени. Это означает, что в каждом ограниченном временном интервале суще- ствует не больше конечного числа точек разрыва. Обсуждение преимуществ ис- пользования кусочно-непрерывных функций управления движением имеется в [7]. Игра начинается в момент времени 0t и считается законченной, когда коор- динаты одного из преследователей в некоторый момент Tt  совпадают с коорди- натами E. Преследователи стремятся уменьшить время T, преследуемый стремится его увеличить. Предположим, все iP управляются из единого центра, и не имеет значения, который из игроков догонит цель. Считаем, что ,0 iww  .,...,2,1 ni  (2) Фазовыми координатами этой игры являются координаты вектора ).,,...,,,,( 1100 nn yxyxyxX  Игрок i управляет своими координатами, в каждый момент времени выбирая скорость ),( iyix vv согласно уравнениям (1), где ,0 ii wv  ),(tvv ii  ),(tii  .,...,2,1,0 ni  Пара функций ),( iiv  называется стратеги- ей i-го игрока. Стратегию игрока E обозначим ,ES стратегию игрока iP обозначим . iPS Та- ким образом, ),,( 00  vSE ),,( iiP vS i  .,...,2,1 ni  Пусть ,...,( 21 PPP SSS  )..., nPS — стратегия преследования. Платой игры называется время ),,( PE SSXTT  захвата цели. Ценой игры )(XU называется минимакс платы .maxmin)( TXU EP SS  (3) Для рассмотренных ниже игр выполняется равенство ,minmaxmaxmin TT PEEP SSSS  все минимумы и максимумы в котором существуют. Если минимумы и максимумы достигаются, то последнее соотношение эквивалентно существованию стратегий  ES и ,PS образующих седловую точку функции платы: ).,,(),,(),,( PEPEPE SSXTSSXTSSXT   (4) Стратегии  ES и  PS назовем оптимальными стратегиями убегания и преследова- ния соответственно. Обозначим )(tUU   производную от цены игры по времени. Если обе сторо- ны действуют оптимально, то 1U при условии Tt 0 (в течение каждого от- резка времени длительностью t цена игры уменьшается на величину ).t Пред- положим, что по некоторым причинам игрок E применяет стратегию ,ES которая для него не является оптимальной. Пусть преследователи стремятся действовать та- ким образом, чтобы время захвата не превосходило цену игры (3). В этом случае применяемая стратегия преследования PS также не обязана быть оптимальной. 32 ISSN 0572-2691 Предположим, U как функция от времени на протяжении игры имеет не бо- лее чем конечное число точек разрыва и .T Если в каждой точке непрерывно- сти функции U по времени выполняется условие ,1U (5) то момент окончания игры T не превосходит величины ),(XU вычисленной по формуле (3). Действительно, используя условие ,0)(  TtU получаем .)1()]0()([)0()( 00 TdtdtUtUTtUtUXU TT    В рассмотренных ниже играх непрерывность в точке t скоростей ),(tVV ii  ,,...,2,1,0 ni  влечет существование и непрерывность функции U в точке t. Cтратегию ,PS удовлетворяющую неравенству (5) для всех ),,0( Tt  в ко- торых скорости ),(tVV ii  ,,...,2,1,0 ni  непрерывны, назовем квазиоптимальной стратегией преследования. Cтратегию ,ES удовлетворяющую неравенству 1U для всех ),,0( Tt  в которых скорости ,iV ,,...,2,1,0 ni  непрерывны, назовем квазиоптимальной стратегией убегания. Заметим, что принадлежность стратегии к числу квазиоптимальных может зависеть от действий противной стороны. Часто используются следующие две стратегии преследования. В первой из них векторы скоростей всех преследователей направлены на убегающего игрока. Такую стратегию преследования назовем простой стратегией. Вторая стратегия заключается в следующем. Каждый преследователь, зная скорость преследуемого в текущий момент времени, считает эту скорость постоянной и вычисляет на ли- нии движения игрока E точку, в которой он может догнать его, двигаясь с посто- янной максимальной скоростью. В текущий момент времени он двигается по направлению к этой точке. Такую стратегию принято называть стратегией парал- лельного сближения. Будем считать, что в каждой из этих двух стратегий пресле- дователи действуют на максимальных скоростях. Заметим, что подобные страте- гии исследовались с помощью геометрических методов в работе [3]. 2. Игра с одним преследователем В случае одного преследователя )1( n игра решается просто: игроки P и E двигаются с максимальными скоростями вдоль направления, задаваемого векто- ром ,PE оптимальные траектории игроков лежат на прямой PE. Точка захвата X также лежит на прямой PE на расстоянии Uw0 от точки E, цена игры U вычисля- ется по формуле ).(/ 012 wwEPU  Предположим, в некоторый момент времени 0t скорости ,0V 1V непре- рывны по t (рис. 1). Пусть )(tdd  — расстояние между игроками. Цена игры )(tU в момент t вычисляется по формуле ),/()()( 01 wwtdtU  (6) а скорость d изменения расстояния между игроками вычисляется по формуле ,,01 nVVd  здесь  , — скалярное произведение, n — единичный век- тор, лежащий на прямой PE и направленный от P к E. Из последнего соотношения и (6) следует )./(,)(/ 010101 wwnVVwwdU   (7) Из (7) вытекает, что условие (5) равносильно неравенству 0101 , wwnVV  . (8) Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 6 33 Выбирая величину скорости 1V из условия (8), игрок P использует квазиопти- мальную стратегию преследования. Время преследования в этом случае не пре- восходит цены игры U. Если игрок P имеет скорость ,1V то игрок E может выбрать квазиоптималь- ную стратегию, используя неравенство ., 0101 wwnVV  В этом случае вре- мя захвата не меньше величины U. E A V0 n P B V1 Q Рис. 2 Предположим, преследователь применяет стратегию параллельного сближе- ния (рис. 2). На рисунке прямые AB и EP , а также AE и BQ параллельны, вектор PQ равен разнице скоростей .01 VV  Имеем  201 ,, PQnPQnVV ;01 ww  последнее неравенство вытекает из неравенства треугольника. Соот- ношение (8) (а вместе с ним и неравенство (5)) выполняется. Таким образом, стра- тегия параллельного сближения квазиоптимальна при каждой стратегии игрока E. Предположим, преследователь применяет простую стратегию (рис. 3). Имеем ;,,, 012210101 wwEQVnVnVnVV  неравенство (8) выпол- няется. Поэтому простая стратегия преследования (совпадающая в рассматривае- мом случае с оптимальной) также принадлежит множеству квазиоптимальных стратегий при каждой стратегии игрока E. P V1 n V0 Q E Рис. 3 3. Игра с двумя преследователями Пусть в погоне за игроком E принимают участие два преследователя: 1P и 2P (рис. 4). Игроки E, ,1P 2P находятся в точках E, ,1P ,2P имея скорости ,0V ,1V 2V соответственно. Обозначим 1A окружность Аполлония, относя- щуюся к паре игроков E, .1P Она представляет собой геометрическое место точек, в которых могут встретиться игроки E и ,1P если они двигаются равномерно и пря- молинейно с максимальными ско- ростями. Пусть 2A — окружность Аполлония, относящаяся к паре иг- роков E, .2P Если окружности 1A и 2A совпадают или не пересекаются, или касаются, то игра сводится к V1 V0 n P E Рис. 1 P1 P2 E V1 V2 V0 T1 T2 X * A1 A2 C Рис. 4 34 ISSN 0572-2691 игре с одним преследователем, которая рассматривалась в предыдущем разделе. Предположим, окружности 1A и 2A имеют ровно две точки пересечения: 1K и .2K Пусть С — пересечение замкнутых кругов 1A и ,2A X — точка из множе- ства С, наиболее удаленная от E. Если X не совпадает с одной из двух точек 1K и 2K (принадлежит дуге одной из окружностей), то игра сводится к игре с одним преследователем. Если 1KX  или ,2KX  причем отрезок EX лежит на диаметре одной из окружностей Аполлония, то игра также сводится к игре с од- ним преследователем. Подобные игры ниже не рассматриваются. Далее будем считать, что X совпадает с одной из точек 1K или ,2K причем отрезок EX не лежит на диаметре 1A или .2A Такую игру, не сводящуюся к игре с одним пре- следователем, обозначим .2G Описанная игра рассматривалась в [1]. В этой работе указаны оптимальные стратегии: игроки должны двигаться равномерно и прямолинейно с максимальной скоростью по направлению к точке ,X в которой происходит захват. Цена игры U вычисляется по формуле ./ 02 wXE=U  Кривые 1T и 2T (рис. 4) изображают траектории преследователей 1P и 2P в случае, когда они используют простую стратегию, а преследуемый игрок с мак- симальной скоростью двигается в направлении точки .X Ясно, что при этом время захвата больше цены игры. В этом случае простая стратегия преследования не является квазиоптимальной (в отличие от игры с одним преследователем, в ко- торой такая стратегия квазиоптимальна при каждой стратегии игрока E). Найдем выражение для производной U цены игры 2G по времени в момент, когда скорости игроков ,0V ,1V 2V непрерывны. Считаем ),,( yxX  ),,( 111 yxP  ).,( 222 yxP  Заметим, что точка X единственна, за исключением случая, когда все три игрока лежат на одной прямой и преследуемый расположен между преследовате- лями (точки ,1K 2K находятся на одинаковом расстоянии от точки E). В этом случае в качестве X выберем одну из точек ,1K ;2K сделанные выводы будут справедливы также относительно второй точки. В процессе вывода формул для производной U без ограничения общности будем считать, что преследуемый игрок постоянно находится в начале координат, а скорости преследователей 1P и 2P равны соответственно 01 VV  и .02 VV  При этом координаты точки X зависят от времени. Кроме того, выберем направление координатных осей так, чтобы точка X лежала на оси ординат, т.е. ),,0( yX  причем 0y (рис. 5). Имеем ,// 002 wywXU   ./ 0wyU   (9) Легко показать, что одна из точек ,1P 2P (будем считать, что это 1P ) лежит во втором или третьем квадранте, а вторая точка 2P лежит в первом или четвертом квадранте, и ни одна из них не принадлежит оси ординат (рис. 5). Поскольку все три игрока, двигаясь с максимальными скоростями равномерно 2 X * y P1 P2 E 1 φ2 φ1 x Рис. 5 Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 6 35 и прямолинейно, прибывают в точку X одновременно, то справедлива система уравнений       .0)()/()()( ,0)()/()()( 222 02 2 2 2 2 222 01 2 1 2 1 yxwwyyxx yxwwyyxx (10) Хотя считается ,0x производные по x могут быть ненулевыми, поэтому пере- менная x включена в уравнения (10). Система (10) определяет неявные функции ),,,( 2211 yxyxx и ).,,,( 2211 yxyxy Обозначим ,)/( 2 0wwr ii  .2,1i Якобиан J этой системы по переменным yx, вычисляется следующим образом: ));()((4 )(2),(2 )(2),(2 112221 2222 1111 yryyxyryyx yryyxrxx yryyxrxx J     здесь учтено равенство .0x Очевидно, справедливы неравенства  ii wyy /)( ,/ 0wy поэтому ,0 yryy ii 2,1i (здесь учтены условия (2)). Из этих со- отношений следует .0J Все условия теоремы о неявных функциях ([8]) выпол- нены, поэтому в некоторой окрестности точки ),0( y функции ),,,( 2211 yxyxx и ),,,( 2211 yxyxy существуют и имеют непрерывные частные производные по всем аргументам. Обозначим ).()(4/ 112221 yryyxyryyxJ  Поскольку ,0J то справедливо неравенство .0 (11) Найдем частные производные ,/ 1xy  ,/ 1yy  ,/ 2xy  ./ 2yy  Дифферен- цируя равенства (10) по ,1x получаем линейную относительно неизвестных 1/ xx  и 1/ xy  систему уравнений                     .0)()( ,0)()()( 1 22 1 22 1 11 1 111 x y yryy x x xrxx x y yryy x x xrxxxx Учитывая соотношение ,0x получаем                     .0)( ,)( 1 22 1 2 1 1 11 1 1 x y yryy x x x x x y yryy x x x Из последней системы находим .// 211  xxxy Аналогичным образом полу- чаем ,/)(/ 121  yyxyy ,// 212  xxxy ./)(/ 212  yyxyy Поскольку выполняется равенство (9) и существуют непрерывные частные производные ,/ 1xy  ,/ 1yy  ,/ 2xy  ,/ 2yy  производную U можно вычис- лить следующим образом: . 1 / 2 2 2 2 1 1 1 10 0                     y y y x x y y y y x x y w wyU  Подставляя вычисленные значения ,/ 1xy  ,/ 1yy  ,/ 2xy  2/ yy  и учитывая соотношения ,01 1 1 VV y x         ,02 2 2 VV y x         получаем .),,( 1 02210112 0 VVPXxVVPXx w U     (12) Соотношение (12) вместе с неравенством 1U ( 1U ) определяет множество квазиоптимальных стратегий преследования (убегания). 36 ISSN 0572-2691 Придадим соотношению (12) иной вид. Обозначим   0112 , VVPXx ., 0221 VVPXx   Имеем . 0   w U (13) Пусть ,1 2 — углы, образуемые векторами XP1 и XP2 с осью абсцисс соот- ветственно (см. рис. 5). Используя соотношения ,0Uwy  ,cos iii Uwx  iii Uwyy  sin , ,2,1i запишем  ))/(sin(cos))/(sin(cos 0 2 0111220 2 022211 UwwwUwUwUwwwUwUw )),sin(coscos()/( 1201221 2 021  wwwUwww (14)  ))(()())(()( 0221022101120121 yyxxyyxx vvyyxvvxxvvyyxvvxx  ))(())(()( 022101121221 yyyyxx vvyyxvvyyxvvxx ).sincos)(cossin)(coscos)(( 210221012112 2 21  yyyyxx vvvvvvUww (15) Пусть ,0n ,1n 2n — единичные векторы, коллинеарные векторам ,EX ,1 XP XP2 соответственно. Из (15) выводим  2111112222 2 21 cos)sincos(cos)sincos(( yxyx vvvvUww )).sin(,cos,cos,())sin( 1200211122 2 21120  nVnVnVUwwv y (16) Подставляя выражения  (14) и  (16) в формулу (13), получаем . coscos)sin( cos,cos,)sin(, 1221120 1222111200    www nVnVnV U (17) Отметим, что величину 02 / wXE=U  мы называли ценой игры, но выше в качестве таковой она не использовалась. Пусть  ES — стратегия преследуемого игрока, состоящая в том, что он двигается равномерно и прямолинейно с мак- симальной скоростью по направлению к точке ,X  PS — стратегия преследова- телей, заключающаяся в их равномерном и прямолинейном движении с максима- льной скоростью в направлении точки .X С помощью формулы (17) можно до- казать справедливость соотношений (4). Это значит, что стратегии  ES и  PS оптимальны. Сделаем выводы из соотношения (17). Справедливы неравенства  2/ ,2/1  ,2/32/ 2  .012  Нетрудно видеть, что точки E и X лежат по одну сторону прямой 21, PP (см. рис. 5). Из этого факта легко вывести неравенство .12  Поэтому ,0)sin( 12  ,0cos 1  .0cos 2  Очевид- но, ,, iiii wnVw  .2,1,0i Согласно (11) и (14) знаменатель правой части (17) меньше нуля. Из этого вытекает, что если преследуемый игрок применяет стратегию  ES (при этом справедливо соотношение ),, 000 wnV  то выполняется неравенство .1U Если преследователи применяют стратегию  PS (для которой справедли- вы соотношения ,, iii wnV  ),2,1i то выполняется неравенство .1U Как и следовало ожидать, стратегии  ES и  PS квазиоптимальны при любых стратеги- ях противной стороны. Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 6 37 Производная U как функция от скоростей 21,VV принимает минимальное значение (цена игры уменьшается с максимальной скоростью) при условии, что ,, iii wnV  ,2,1i т.е. преследователи применяют стратегию .PS Производ- ная U как функция от скорости 0V принимает максимальное значение (цена игры уменьшается с минимальной скоростью) при условии, что ,, 000 wnV  т.е. пре- следуемый игрок применяет стратегию .ES Если преследуемый игрок применяет стратегию ,ES а преследователи при- меняют простую стратегию, то справедливо неравенство .1U Таким образом, в игре 2G простая стратегия преследования не всегда является квазиоптималь- ной. Выше этот вывод был сделан на основе геометрических соображений. Запишем еще одну формулу для производной ,U которая используется ниже. Обозначим ),,( 11 0 1 iyixii vvVVV  .2,1i Из соотношения (15) выводим  )sincoscossincoscos)(( 21 1 221 1 121 1 1 1 2 2 21 yyxx vvvvUww  )cos)sincos(cos)sincos(( 21 1 11 1 112 1 22 1 2 2 21 yxyx vvvvUww .)cos,cos,( 21 1 112 1 2 2 21  nVnVUww (18) Подставляя в (13) выражение  (14) и выражение  (18), получаем . coscos)sin( cos,cos, 1221120 12 1 221 1 1    www nVnV U (19) Оказывается, в игре с двумя преследователями стратегия параллельного сближения является квазиоптимальной при каждой стратегии игрока E. Это дока- зывается в следующем разделе. 4. Квазиоптимальность стратегии параллельного сближения в случае двух преследователей Рассмотрим игру ,2G описанную в разд. 3. Предположим, каждый из пре- следователей применяет стратегию параллельного сближения. Докажем квази- оптимальность этой стратегии преследования при каждой стратегии игрока E. Без ограничения общности можно считать игру 2G такой, что выполняются соотношения ,10 w ,1y т.е. )1,0(),0(  yX (см. рис. 5); тогда для цены игры выполняется соотношение .1/ 0  wyU Очевидно, этого можно добиться, выбирая соответствующий масштаб по осям абсцисс и ординат и соответствую- щую единицу измерения времени. При этом преследуемый игрок находится в начале координат, т.е. ),0,0(E точка 1P лежит во втором или третьем квадран- те, точка 2P — в первом или четвертом квадранте, ни одна из точек ,1P 2P не принадлежит оси ординат. Поскольку преследователь iP проходит отрезок XPi за единицу времени, то справедливы формулы ,)1( 22 iii yxw  ,2,1i (20) где ),( ii yx — координаты преследователя .iP Из условий (2) следуют неравен- ства ,1iw .2,1i Справедлива следующая теорема. Теорема. Стратегия параллельного сближения в игре 2G квазиоптимальна при каждой стратегии преследуемого игрока. Доказательство. Следует доказать неравенство 1U для всех моментов времени, в которых скорости игроков ,0V ,1V 2V непрерывны. Так как ,10 w 38 ISSN 0572-2691 знаменатель правой части (19) отрицателен (в силу (11) и (14)), то из (19) следует, что неравенство 1U эквивалентно соотношению .0cos)sin,(cos)sin,( 1222 1 22111 1 1  wnVwnV (21) Из соотношений (20) и (21), используя равенства ),sin,(cos iiin  icos ,/ ii wx ,/)1(sin iii wy выводим неравенство, эквивалентное соотноше- нию (21): .0 1 /)1( / , 1 /)1( / , 2 2 2 22 221 2 1 1 1 1 1 11 111 1 2 2                                   w y w wy wx V w x w y w wy wx V w x Умножая обе части последнего неравенства на число 21ww и используя (20), по- лучаем                 1 2 1 2 1 1 11 12 1)1( 1 , yyx y x Vx .01)1( 1 , 2 2 2 2 2 2 21 21                  yyx y x Vx (22) Пусть id — расстояние от i-го преследователя до начала координат, id ,22 ii yx  .2,1i Поскольку преследователи применяют стратегию параллель- ного сближения (рис. 6), то существуют та- кие положительные вещественные числа ,, 21 aa что справедливы соотношения ,1        i i i i i y x d a V .2,1i (23) На рис. 6 вектор EA изображает скорость 0V преследуемого, вектор BP1 — ско- рость 1V преследователя ,1P вектор CP1 равен разности скоростей ;01 VV  прямые AE и BC параллельны, прямые AB и EC параллельны. Из (22) и (23) выводим ;0)()( 2 2 22 2 2 2 2 11 2 11 2 1 1 1 2                  ydyd d a xydyd d a x из этого неравенства получаем .0)()( 22 2 2 2111 1 1 12                  da d y dxda d y dx (24) Обозначим i угол, который образует вектор iEP с осью абсцисс, 2,1i (рис. 5). Поскольку точка 1P находится слева от оси ординат, а точка 2P — справа, то .021 xx Используя это неравенство и формулы ,cos iii dx  ,sin iii dy  ,2,1i получаем неравенство, эквивалентное соотношению (24) .0)( cos sin )( cos sin 22 22 22 11 11 11        da d d da d d (25) Выведем формулы для величин ., 21 aa Пусть 20Vv  — величина скоро- сти преследуемого игрока. Предположим, .10 0wv  Пусть  — угол, образу- y x P1 E 1     A A1 B B1 C Рис. 6 Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 6 39 емый прямыми EA и EP1 (см. рис. 6),  — угол, образуемый прямыми BP1 и .1EP Обозначим c расстояние от точки A до прямой EP1 (см. рис. 6), . 2121 BBAAс  Имеем .sinsin 1121121 w v w v EA c vw vc w c BP c  (26) Очевидно, ,2/2/  поэтому .0cos  Учитывая последнее неравенство и соотношение (26), получаем .cossincoscos 222 111  vvwvwa Пусть  1 — угол, образуемый прямой EA с осью абсцисс. Из преды- дущего соотношения следует ).cos()(sin 11 222 11  vvwa Для 2a имеет место аналогичная формула, т.е. справедливы соотношения ),cos()(sin222 iiii vvwa  .2,1i (27) Равенства (27) выведены в предположении .10  v Если ,0v то стратегия па- раллельного сближения означает движение преследователей в направлении непо- движного объекта E, находящегося в начале координат. Согласно соотноше- нию (23), в этом случае ,ii wa  поэтому формулы (27) справедливы при условии .10  v Обозначим , cos sin 11 11 1    d d Q . cos sin 22 22 2    d d Q Неравенство (25), которое требуется доказать, принимает вид ;0)cos()(sin222 2 1         iiiii i dvvwQ (28) здесь учтены равенства (27). Заметим, что ,sin2 iid  .2,1i (29) Действительно, из неравенств 1iw и (20) следует ,1)1( 22  ii yx откуда .sin2/2 2222 iiiiiii yxyyxd  Поэтому ,0iQ .2,1i (30) Обозначим ),( vf левую часть неравенства (28), .)cos()(sin),( 222 2 1          iiiii i dvvwQvf Следует доказать неравенство 0),( vf (31) при каждом v, принадлежащем отрезку ]1,0[ , и при каждом . Дальнейшее доказательство состоит из трех шагов. На первом шаге до- казывается справедливость (31) при условии ,1v на втором — при условии ,0v на третьем из двух доказанных утверждений выводится неравенство при условии .10  v 1. Докажем неравенство .0),1( f (32) Используя формулы (20), получаем .)cos()(cossin2),1( 22 2 1          iiiiiii i dddQf (33) 40 ISSN 0572-2691 Обозначим .sin22 iiii ddс  В силу (29) выполняется неравенство .0iс Рассмотрим функции ,)(cos)(cossin2 222 iiiiiii cddg  .2,1i Обозначим ,cos1 z ,sin2 z ,cos1 iin  ,sin2 iin  ),,( 21 zzz  ).,( 21 iii nnn  Из соотношения iii  sinsincoscos)cos( следует .,)cos( ii nz Таким образом, .,)( 2 iiii nzczgg  Нетрудно про- верить, что при условии 0c функция 2)( xcxg  выпукла по x. Используя этот факт, легко доказать выпуклость функций )(zgi по z. Заменяя в (33) )cos( i выражением ,, inz получаем .,,sin2)(),1( 22 2 1          iiiiiii i dnznzddQzff Из соотношений (30) и выпуклости функций )(zgi следует выпуклость функции )(zf по z. Для того чтобы доказать неравенство (32), достаточно доказать неравенство 0)( zf при условии .12 2 2 1  zz Покажем, что минимальное значение целевой функции задачи выпуклого программирования min,)( zf (34) 012 2 2 1  zz (35) равно нулю. Рассмотрим точку ).1,0(z Имеем .0sinsinsin2)( 2 1 22          i iiiiiii dddQzf (36) Частная производная функции )(zf по переменной 1z в точке z равна нулю:                   1 1 2 11 2 1 1 11 11 cos1 sinsin2 sin cos sin )( 1 ddd d zf z .0cos1 sinsin2 sin cos sin 2 2 2 22 2 2 2 22 22                  ddd d (37) Частная производная функции )(zf по переменной 2z в точке z вычисля- ется следующим образом:                             2 22 2 22 22 1 11 1 11 11 sin1 sin sin cos sin sin1 sin sin cos sin )( 2 dd d dd d zf z 2 2 1 1 cos sin cos sin       . (38) Поскольку точки E и X лежат по одну сторону прямой 21, PP (см. рис. 5), справедливо неравенство .21  Кроме того, ,221  поэтому ,0)sin( 21  откуда вытекает неравенство .0sincoscossin 2121  Разделив обе части последнего неравенства на величину 21coscos  и учиты- вая при этом, что ,0cos 1  ,0cos 2  получаем неравенство 0 cos sin cos sin 2 2 1 1        . (39) Из неравенств (38) и (39) следует .0)( 2  zf z (40) Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 6 41 Обозначим ))(),(()( 21 zfzfzf zz  градиент функции ).(zf Пусть )(zh 12 2 2 1  zz — функция, стоящая в левой части ограничения (35),        2 12)( z z zh — градиент этой функции. Из соотношений (37), (40) следует, что для некоторой не- отрицательной константы k справедливо соотношение ).()(   zhkzf Это ра- венство и равенство 0)( zh образуют достаточное условие оптимальности точ- ки z в задаче (34), (35) [9]. Используя равенство (36), заключаем, что при усло- виях 12 2 2 1  zz справедливо неравенство .0)( zf Соотношение (32) доказано. 2. Докажем неравенство 0)( cos sin )( cos sin ),0( 22 22 22 11 11 11        dw d d dw d d f . (41) Используя (20), выводим           111 2 1 11 11 1sin2 cos sin ),0( ddd d d f .1sin2 cos sin 222 2 2 22 22           ddd d d Нетрудно показать, что при условии (29) выполняются неравенства   i ii d d sin ,sin1sin22 iiiii ddd        2,1i (для доказательства следует рас- смотреть, как изменяется левая часть неравенства, если id изменяется от )sin2;0max( i до , а угол i фиксирован). Поэтому 2 2 1 1 cos sin cos sin ),0(      f . Согласно соотношению (39) правая часть последнего неравенства неотрицатель- на, откуда следует, что .0),0( f Неравенство (41) доказано. 3. Функция ),( vf является вогнутой функцией от v на отрезке ]1,0[ , поэтому при условии ]1,0[v справедливо неравенство ).,1(),0()1(),(  vffvvf Из этого неравенства и соотношений (32), (41) следует неравенство (31), из которого, в свою очередь, следует (21). Теорема доказана. 5. Игра, в которой принимают участие больше двух преследователей В случае, когда число преследователей больше двух, ограничимся выяснением вопроса о том, является ли квазиоптимальной стратегия параллельного сближения. Рассмотрим пример с тремя преследователями: ,1P ,2P 3P (рис. 7), которые расположены в вершинах равностороннего треугольника. Пусть  X — точка, равно- удаленная от точек ,1P ,2P 3P , т.е. .3/)( 321 PPPX   Преследуемый игрок E находится в точке .  X Максимальные скорости всех преследователей равны w, максимальная ско- рость игрока E равна 2/w . Легко доказать опти- мальность стратегий игроков, которые заключаются в том, что преследователи двигаются к точке  X с максимальной скоростью, а игрок E остается на ме- сте. Захват происходит в точке ,  X цена игры вы- числяется по формуле ./ 21 wXP=U  (42) P3 P2 P1 L X * K M N Рис. 7 42 ISSN 0572-2691 Оказывается, в описанной игре стратегия параллельного сближения может не быть квазиоптимальной. Действительно, пусть на некотором отрезке времени в начальном периоде игры преследуемый E двигается равномерно с максимальной скоростью по периметру равностороннего треугольника KMN с центром в точке ,  X проходя вершины в указанном порядке (см. рис. 7). Сторона этого треуголь- ника считается достаточно малой. Преследователь ,1P применяя стратегию парал- лельного сближения, двигается вдоль ломаной L. Нетрудно видеть, что длина лома- ной превосходит расстояние между точками 1P и .  X Точно так же преследователи 2P и 3P двигаются вдоль ломаных, длины которых превосходят величину . 21  XP Таким образом, применение стратегии параллельного сближения приводит к тому, что цель будет достигнута за время, которое больше цены игры (42), откуда вытекает, что эта стратегия не квазиоптимальна. 6. Использование дополнительных критериев преследователями Допустим, преследователи, кроме основной цели захвата, имеют дополни- тельные критерии, которые они используют в случае, когда преследуемый игрок действует неоптимально. Допустим также, что преследователи с помощью одного из таких критериев (обозначим его F) выбирают наилучшую стратегию PS из множества квазиоптимальных стратегий. Иначе говоря, преследователи в каче- стве стратегии выбирают оптимальное решение задачи .1 min,)(   U SF PS P  (43) Приведем примеры критериев F для игры .2G Пример 1. Допустим, необходимо минимизировать скорость преследователя 1P из-за ограниченности его ресурсов. Следует выбрать .),( 2121 VVVF  Пример 2. Допустим, в некоторый момент времени преследователи стремят- ся максимизировать скорость сближения с целью. Следует выбрать ),( 21 VVF ),(),( 222111 MVaMVa  ; здесь 0ia — весовые коэффициенты, iM — еди- ничный вектор, направленный на цель, т.е. ,/)( 2iii PEPEM  .2,1i Вместо (43) рассмотрим более простую задачу. Из соотношений (11) и (14) следует, что знаменатель правой части формулы (17) меньше нуля. Поэтому из (17) вытекает, что неравенство 1U равносильно соотношению )sin(,cos,cos, 12001122211  nVnVnV , где 12211201 coscos)sin(  www . Используя последнее неравенство, задачу (43) заменим следующей: min,),( 21, 21 VV VVF  ),sin(,cos,cos, 12001122211  nVnVnV (44) ,121 wV  .222 wV  Пусть ),(1 tV )(2 tV — оптимальные решения задачи (44), вычисленные для каж- дого момента времени. Чтобы эти функции определяли стратегию преследования, они должны быть кусочно-непрерывными, т.е. в каждом ограниченном временном интервале должно быть не больше конечного числа точек разрыва. Количество та- ких точек зависит от траектории преследуемого игрока. Для широкого множества траекторий игрока E функции ),(1 tV )(2 tV оказываются непрерывными или кусоч- Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 6 43 но-непрерывными. Если это не так или число точек разрыва оказывается слишком большим, целесообразно использовать приближенное решение задачи (43). Заключение В данной работе для дифференциальных игр преследования на плоскости с одним убегающим и несколькими преследователями определены и исследованы множества квазиоптимальных стратегий. В игре с одним преследователем условия квазиоптимальности стратегии пре- следования задаются соотношениями (5), (7). В игре с двумя преследователями, не сводящейся к игре с двумя игроками, условия квазиоптимальности стратегии преследования задаются соотношениями (5), (17) или (5), (19). Условия квази- оптимальности стратегии убегания в этих играх задаются теми же соотношения- ми, но в (5) знак неравенства следует заменить противоположным. Простая стратегия преследования в игре с одним преследователем совпадает с оптимальной, а в игре с двумя преследователями может не быть квазиоптимальной. Стратегия параллельного сближения в игре с одним или двумя преследовате- лями квазиоптимальна, хотя не всегда совпадает с оптимальной стратегией пре- следования. В игре с тремя преследователями эта стратегия не всегда является квазиоптимальной. С.В. Пашко КВАЗІОПТИМАЛЬНІ СТРАТЕГІЇ В ДИФЕРЕНЦІАЛЬНИХ ІГРАХ ПЕРЕСЛІДУВАННЯ НА ПЛОЩИНІ Робота присвячена диференціальним іграм переслідування на площині, в яких кілька гравців доганяють одного. Визначено та досліджено квазіоптимальні стратегії гравців. Виведено нерівності, що задають множини таких стратегій. Для відомих стратегій знайдено умови, за яких вони квазіоптимальні. Розгля- нуто задачі вибору найкращої стратегії з множини квазіоптимальних. S.V. Pashko QUASI-OPTIMAL STRATEGIES IN THE DIFFERENTIAL PURSUIT GAMES ON A PLANE This paper is concerned with differential pursuit games on a plane, in which several players chase one. Quasi-optimal strategies of players are defined and investigated. The inequalities which specify the sets of such strategies are derived. For the known strategies the conditions under which they are quasi-optimal are found. The problems of choice of the best strategy from a set of the quasi-optimal are considered. 1. Айзекс Р. Дифференциальные игры. — М. : Мир, 1967. — 480 с. 2. Кунцевич В.М., Лычак М.М. Синтез оптимальных и адаптивных систем управления. Игро- вой подход. — Киев : Наук. думка, 1985. — 245 с. 3. Петросян Л.А., Томский Г.В. Геометрия простого преследования. — Новосибирск : Наука, 1983. — 140 с. 4. Понтрягин Л.С. Избранные научные труды : В 3 т. — М.: Наука, 1988. — Т. 2. — 576 с. 5. Пшеничный Б.Н., Остапенко В.В. Дифференциальные игры. — Киев : Наук. думка, 1992. — 264 c. 6. Чикрий А.А. Конфликтно управляемые процессы. — Киев : Наук. думка, 1992. — 384 с. 7. Болтянский В.Г. Математические методы оптимального управления. — М. : Наука, 1969. — 408 с. 8. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. — М. : Наука, 1969. — Т. 1. — 607 с. 9. Карманов В.Г. Математическое программирование. — М. : ФИЗМАТЛИТ, 2004. — 264 с. Получено 29.05.2012 Статья представлена к публикации членом редколлегии член.-корр. НАН Украины А.А. Чикрием.

Квазиоптимальные стратегии в дифференциальных играх преследования на плоскости

Institution

Similar Items