Следящие области в задачах поиска тема автореферата и диссертации по математике, 01.01.02 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.а ЛОМОНОСОВА ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ

На правах рукописи

ГУБАЙДУЛЛИН Салават Муышетаневнч

УДК 517.9

СЛВДЯЩИЕ ОБЛАСТИ В ЗАДАЧАХ ПОИСКА 01.01.0Z - дифференциальные уравнения

АВТОРЕФЕРАТ

днссерта1рда на соискание ученой'степмм кандидата физико-одтемалпеских наук

Москва 1993

Работа выполнена на кафедр« общей иа тема гики факультета вычислительной математика и кибернетики Московского Государственного Университета им. М.В. Ломоносова

Научный руководитель доктор физгко-математкческих наук, профессор ШИКИН Е.В.'

Официальные о.ппоненты доктор физию-мятематических наук, профессор БЛАГОДАТСКИХ В.И. кандидат физико-математических наук, старший научный сотрудник КЕРИМОВ А.К.

Ведущая организация - Сгшт-Пегербургский государственный университет

Защита диссертации состоится *_" __________ 1993 г. ■

14.30 часов на заседании Спеииалширо ванного совета К 053.05.87 при Московском Государственном Университете им. М.В. Ломоносова по . адресу: 119899, Москва, Воробьевы горы, МГУ, факультет вычислительной математики а кибернетики, аудитория 685.' »

С диссертацией коасно озаакоккться в библиотеке факультета.

Авторефери разослан "_"_1993 г.

Ученый секретарь Спсцкалкзированяого совета, доцент

В.М.ГОВбРОВ

ОБИЯ ХАРАКТЕРИСТИКИ РАБОТЫ

Актуальность тени. Предмет настоячего исследования относится к конфликтна задача» об управлении объектами, которые описываптся обыкновенными дифференциальными уравнениями. Такие задачи принято объединять термином дифференциальные игры.

Дифференциальные игры имеет cdqmm неисчерпаема источником практические задачи. Больнинство этих задач укладываются в следувчув обчуи схему. Имеется динамическая система, описываемая дифференциальными уравнениями, которые связывапт ее фазовые координата с дправляшчиыи н другими силами. Часть сия нацелена на выполнение некоторой задачи, другие силы могут меаать достиленип этой цели. Поэтому процесс трактуется как игра иеяду противоборствушдеии сторонами. Игровой характер таких конфликтных задач управления проявляется особенно в той предположении, что тону или иному объекту в кааднй момент времени будуций образ действии противника неизвестен или известен неточно и, всяедствии этого, при определении своих действий этот объект колет опираться линь на знание своих возможностей и возмояностей противника.

Фундаментальный вклад в развитие теории дифференциальных игр внесли Р.Айзеке. Л.С.Понтрягин, Н.Н.Красовский, Е.Ф.Ниме-нко, Р.В.Гамкрелидзе и др.

Типичными примерами дифференциальных игр является задачи преследования одного движущегося управляемого объекта другим. При зтом.преследуидий (нцуций) стремится осуцествить встречу как MOIHO ранЫе, а преследуемый ( убегащий ) стремится оттянуть ее на более поздним срок. К таким задача» относится и рассматриваемая в настоящей работе динамическая задача поиска подвитого объекта.

Основополагащими работами матеиатической теории поиска принята считать работа Купмана11 , выход которых стимулировал появление значительного числа публикаций по теории поиска.

Ш. Коормап D.O. The theory of seach. Part I. II, III // Oper. Res. 1956. U. 4, NN 3,5, 1957. Ü. 5,Ä 5.

Стало общепринятым разделять задачи поиска в зависимости от поведения объекта поиска на два класса: поиск неподвшного объекта и поиск подвивного объекта. Задача с неподвимным прячущийся была рассмотрена Ййзексом ^ . Впервые задача поиска с подбивных прячущимся в случае, когда мномество Q , на которой проводится поиск, .является круго*, была решена в работе Зеликина^. Интересные результаты по ре-вспив задач поиска получены Д.П. Никои Л.ft. Пвтросяныи, Б.Б. Рихсиевмм, А.В. Гарнаевнм, Н.Й. Зенкевичем^с) и др.

Опимем иатематическуп модель реальной конфликтной ситуации поиска с разделенными объектами.

Пусть конфликтно управляемая система -В складывается из двух объектов, идущего и прячущегося, текущие состояния которых описываются их фазовыми векторами h-h(t) н $*S(t) подчиненными уравнениям двивення

h-tth.u),

где hs.RntStr, UtUcR9, ifzVcfr9 ' ( U и V - непустые компакты ; f(h,U) . f,(S,V) - заданные «гцнкцин, отравасвие дииаияческие свойства системы <£ в в зависимости от рассматриваемой задачи обладавшие теми или иными свойствами, ¿/ и V суть вектора управляемых воздействий С управления), подчиненные противоборствуем« сторонан - ичу-«ему и убегавчеку объектам соответственно; допустимые значения величин h , S ,U или V могут быть стеснена какинн-нибудь дополнительншш ограничениям, отрасасдиаи киненаткку н динамику управляемых объектов).

[21. ййзекс Р. Дифференциальное игры, - И.: Пир, 136?, 13]. Зеликин И.И. Об одной дифференциальной игре с неполной информации // Доклады П11 СССР. 1972. Т.202. 8 5. (41. Ким Д.П. Истоды поиска и преследования подвнаннх объек-тоа. - К.: Наука, 1339.

[5]. Пегросян Л.А., Гарнаев 0.0. Игры поиска. С,- П.: Нэд-во СПбГУ, 1992.

(61. Петросян Л.А., Зенкевич Н.Й. Оптимальный поиск в условиях конфликта. - Я.: Нзд-во Лен, нн-та, 193?»

. -5В пространстве /С =/f фиксируется некоторое непустое, терминальное множество М . При первом попадании точки Z(t)-(h(t), S(t)) на множество М поисковый процесс считается законченным. Цельв ищущего звляется гарантированное выведение Z(t) из ' 'положения 1(0) = (h(o), S(O)) на терминальное множество М за сколь возможна более короткое время, Цельв убегавшего является уклонение 2(t) от попадания на множество М сколь возиомно долго. Подобные задачи часто изучается в следувщей постановке. Предполагается, что обоим конфликтующим объектам известны уравнения.компакты U и V и териинальное множество М , Збегавщий кроме этого знает.начальные состояния h(O) и S(О) и при каждом t>0 управление U(t)(-U, Считается, что управление U(t)t U при t>D строится программным образом, то есть фиксируется как функция t>0 до начала движения и никак не зависит от управления V(t),

В реальных поисковых задачах управления обычно выбирае-■тся на основании некоторой информации о динамических возможностей объектов и текущих изменениях их состояний. При этом уровня информированности объектов могут быть различными. Характерной чертой поисковых задач является отсутствие информации о будущем выборе управления убегавшим ( по отноменив к настоящему, текущему моменту t ). Этим обстоятельством можно объяснить недостаточна«! разработанность аффективных методов мх режениз.

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

/? -a, S*v,

r*e ܀ Uc R*, VtVcR\ hzXcR3; StVctf*

{U и V - некоторые компакты, X к У- регулярнее воверхности яля ограничиваемые ими множества), м указцдааягся условия, обеспечивавшие успежный (результативный) аощск. Более точно, формулируется и обосновывается достаточные условия на мно-

сества и . V . X и У , при выполнении которых существует непрерывная вектор-функция U (t) ( управление ищущего ) и отвечающее ей решение h(t) первого уравнения ( траектория ивущего ), такие, что дли любой непрерывной вектор-функции V(í) С управление убегающего ) и либого отвечающего ей ревения $(t) второго уравнения ( траектории убегающего ), косно указать иоиент вреиени Т , в который расстояние иежду траекторияии hit) и S(t) не будет превосходить заданного числа ¿ : d ( h (Т), S (t)) <

Для обоснования этих условий разработан геометрнчесий кетод следящих областей.

Научная новизна. В диссертации содержатся следующие новые результаты:

1. Введено новое понятие следящей области, указан способ ее построения и некоторые свойства.

Для динамической задачи поиска с разделенными переменными (случай простого двивения) построены уравнения, описываи-вдие слвдяцие области на плоскости, на регулярной поверхности постоянной кривизны, в трехмерной евлидовок пространстве.

2. Выведено достаточное условие успешного поиска на некоторых поверхностях и в ограничиваемых ими множествах» указаны соответствуйте стратегии.

Исследована задача поиска на поверхности бесконечного круглого цилиндра; при покори следящих областей найдены условия на параметры задачи, выполнение которых гарантирует успе-«ный поиск Собнарувение) я указана траектория . двивения кщуцего игрока, оптимальная в классе винтовых линий.

Рассиотрена дкяакическая задача поиска на.торе: получены достаточные условия успевного поиска (обнаругення) однин и двумя ищущими игрокаин.

Рассмотрены трехмерные задачи поиска внутри бесконечного круглого цилиндра и в по/ноторкк. В кавдой из этих задач найдены достаточные условия и соответствувцие траектории, гаран-тирувщие успевное заверсенке поиска,

3. Проведен геометрически» анализ известной стратегии поиска на плоскости и показано, как, используя следящуп область, можно ев улцчккть.

• -?-

Цель работы. Разработка нового иетода исследования двух- и трехмерных задач динамического поиска. Полу-чениа новых достаточных условии успеаного поиска (обнарцхе-ния) подвижного объекта и построение соответствунчих стратегий.

Обцаа методика исследования.

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

Теоретическая и практическая ценность. Полученные результаты иогут быть использована для теоретических исследований дннаиических задач поиска как одшш, так и несколькими ицуциии.

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

Использование следящей области в задачах поиска позволяет ответить на ряд ванных вопросов, возникавших в ходе их реяения, наприаер, таких, как поиск оптииальной траектории двиаения ицуцего игрока, отыскание максимальной контрояируе-иой области в задаче блокировки, сравнение различных стратегий поиска и др.

Апробация. Результаты работы докладывались на Неадународной научной конференции "Лобачевский и соврененная геоаетриа" , проходив»ей в Казани в 1992 году, на сеаинарс но оптииальвоау управлении под руководство» профессоров Никольского М.С. и Григоренко Н.Л. ( НГЗ ) и на семинаре по геометрии под руководство* профессора Позияка З.Г. ( ИГУ ).

Публикации. Результаты диссертации опубликованы в работах П3-151.

С т р у к т у р а и обьеи работа. Диссертация состоит из Введения и двух глав. Обьеи работы 33 иаяинонисных страниц, библиографиия 32 наименования.

СОДЕРШНЕ РЙБОГН.

Диссертационная работа состоит из введения и двух глав.

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

Первая глава посвящена вопроса* построения следящих областей и исследовании некоторых их свойств.

В § 1 вводится понятие следящей области для поискового процесса, который проходит $ выделенном множестве в я о которой, участвуют два объекта - ищущий Н и убегавший 5 .

Предположим, что в стационарном половених ищущий игрок Н контролирует некоторую область К и способен двигаться по области 0 с постоянной скалярной скоростьв оС , имея возможность в каждый ионент вреиенн произвольны« образец изменять-направление своего движения. Убегапщий игрок <5 цосет двигаться по области О со скалярной скоростьв, не бояьвей , и такие иивет возможность в лвбой номент вреиени как угодно изксиять направление своего движения. Убегавший 5 считается пойманный кгрокоа Н , есля он попадает в область контроля К игрока И ..

Пусть кривая X лепит п области О и является траекторией движения ищущего игрока Н . При поступательно« движении ицущего ио этой траектория X возникает

изменяющееся во вревеш множество , запретное дяа

убегавшего 6 . О кавдка комвнт времени- зто, следящее, множество слагается из двух областей — упреждавшей к

остаточной. Если игрок «5 находится в упревдагцей области, то через некоторое время он будет непременно обкарусен кгрокои Н в остаточнуи же область кгро» «$ к расскатривассоку воквнтд просто не успевает попасть.

& этом же параграфе полаченн уравнения граница следящей области для плоского случая, когда область контроля К является кругом радиуса 6 .

При условии, что кривая X , заданная уравнения** ¿С = V(t), % = Y(t) • параиетрнэована так. что ее

скалярная скорость совпадает со скоростьв игрока Н , граница упрекдавщей части следяцей области описывается следущиви формулаки:

X^(t)^({-ßt)cos(6(t)±A)J • . .

y=V(t)i(£-ßt)sin(Q(t)tl),

iß ' ' где Л =äzccas .а

угол наклона траектория X к оси X . '••

Сравнения границы остаточной области инеят сховуп структура вследствии того, что фориа следящей области в ка1дый воиеит врехенн не зависит от направления двиаения игрока И по траектории X .

В § § 2 и 3 приведена уравнения граница следящей области дяа задач поиска на регулярной поверхности постоянной отрицательной кривизна н в тремернои евклидовой пространство. .

В первой случае следяt^aa область рассыатрйваетса как объединение геодезических кругов, а во второй karr -объединение паров; центры этих геодезических кругов (соответственно паров) яеаат иа траекторпя идущего игрока, а радвуск по определенной^ закону сначала увеличивавтся от нуля До С , а зато» пнивь уйеньвазтся до щяя.

3 заклпченис главы I обсуядавтся вопроса введения подходящих пзраяетрязацяй траектории движения нцуцего игрока п возаоапость прибякаетюго построения следящей области для траектории с произвольной иаранетризацней.

Вторая глава посваяеиа рссёнтш задач гоясва иа некотория регулярных поверхностях п в ограничивавши кт трехнчрннх областях.

Для этих задач при покоем следящей области находятся со-дераательнне достаточнее условия,'ггря внполиепяя которая воз-коаен успеиный поиск (обиаруяеотш), я . раздается соответс-

вцвцие траектории переиенення ичуцего И .

В § 1 рассмотрен случай, ногда поисковое мновество является бесконечный круглы» цилиндров С радиуса I .

Показано, что винтовая линия, выбранная в качестве траектории X перемещения игрока Н и пересекавшая образующие цилиндра под постоянный углом \) , таким, что

I 4 /, л /7 7* ' -

при выполнении условий

■ Ях£<е<Жг /1/

и

обеспечивает обнаружение игрока 6' , если известно, в какой часта цилиндра он находится т.е. в какув сторону по винтовой линии наддевнт двигается игроку Н . В классе винтовых линий эта траектория является оптиыалыюй.

Другой двумерной задачей, рассматриваемой о работе, является задача поиска на торе. Эта задача оказыватся более славной. Однако идея следацай области позволяет и о этой случае найти достаточные условия уеденного поиска ( обнаруме-аий ) и вы&рать соответствувцув траектории движения ичучего игрока.

В § 2 показано, что если для юра Т , заданного векторной функцией

(о/^гсач'Оз/лг, 2-ьиг/};

где d - const, г - const, d>z>0,

в качестве траектории X движения идучего игрока Н выбрана спираль, которая пересекает параллели тора под постоянным углом 6 , определяемым равенсвтом

кй

то, при выполнении условия f1/ в каждой следяяей области можно выделить поперечнув муфту, целиком состоячуп из точек следяжей области и, следовательно, запретнув для игрока J .

Вследствии того, что тор ограничен, при перемещении по спирали<Z в противополоянах направлениях двух обьектов У/и Hi с постоянными скалярными скоростями сС объект S непременно окаяется в геодезической круге обнаруаения либо объекта Н'/ либо объекта Нг (■§ 3). Один иеджии игрок Н обеспечизает поимку убегаижего $ на торе, двигаясь по этой спирали, при выполнении условия (§ 4)

В поисковых задачах, рассмотренных в §§ 1-4, компакт U является сферой радиуса Ы , компакт V - варом радиуса ,/> а X совпадает с У и является либо цилиндром С либо тором 7.

Б §§ 5 и В рассмотрена трехмерные задачи поиска п бесконечном круглой цилиндре и в полнотории. Б каждой из этих задач найдена достаточные условия, гарантирупшге успешное заверяенне поиска, и указана соответствуй*«!? траектории.

При поиске в бесконечной круглой цилиндре С поремедз-ние игрока S допускается ив только по поверхности цилиндра, но к внутри него со скорость«, ив пр?ям»а«япй , я to время, как игрок И повет перемещаться тилько по повер-

хности цилиндра С со скалярной скоростьв о( (<) , контролируя «ар заданного радиуса ¿.

Пусть параметра задачи связаны неравенством

- аит 4г)'< ^ (£ ~ >/г(зг-е)')

и & - произвольное число, заклвченное между

г(Л-ахссоэт) и д/{-/цп^ё]).■

Тогда, если взять в качестве траектории перемещения объекта Н винтовую линии X. , которая пересекает образующие цилиндра под постоянным углом \) , определяемым условием

]/ = агся/п 27 >

где / вычисляется по формуле

то в ка«д ык монет времен я в цилиндре возникает разделяп-щее его мноаество, целиком состоящее из точек следящей области. Двигаясь по этой кривой, при выполнения условия

". ¿¡^Ч? :

игрок // непременно накроет игрока $ маром контроля, если игрок 6 'находится в той «е части цилиндра, куда движется игрок Н .

При поиске в полнотории, ограниченном тором/, предполагается. что игрок И контролирует «ар заданного радиуса / и перемещается по тору Т со скалярной скоростьв оС , а убегающий игрок <5 перемещается внутри тора и по его границе со скалярной скорость», не превыааящвй $ ).

При перемещении игрока // по спирали, пересекающей пара-лели тора под постоянным углом д > определяемым равенством

аЧ(Рл-е)М+г) Уо(г-г

¿У

в полнотории в камдвй аоиент возникает пробка, целипоа состоящая из точек следацой области. При виполнения условия

ч / / ,:/ / г ) <? , / _)2 '•

Ф ( ¿-/(Н^ЯЪТгГ У

игрок Н накроет игрока 4 иарон контроля за конечное

вреия. г г '

В трехиернах задачах поиска (§§ 5-6) коипакт V является

сферой радиуса . коипакт V- аарон радиуса / . иноввство ^

является либо цилиндре» С либо тором Т . а аноаествоГсоот-

ввгсвешю либо пипуклни иновоствок. огранпчешши цялкндроа 6

либо ПОЛНОТОРИЕИ.

в 5 7 показано, как, вспользуя геонетрическпе свойства следящей области, новно улачвить изпсстнуп стратегия в плос-эадачв поиска.

По теме диссертации опубликовали следующие работы: .

1. Губайдуллин С.Н. Построение переменной контролируемой ■ области в задаче поиска на плоскости при заданной ; траектории двивення, - П.: Дел.ВИНИТИ, 1990, Н 37'Л -В90.

2. Губайдуллин С.Ц, Анализ одной стратегии в плоской задаче обнаружения. -И.: Деп.ВИННТН, 1990, Н 3?50 - МО.

3. Губайдуллин С.И/ Следящая область в задачах поиска. -К.: Деп.ВИНИТИ, 1992, Н 2020 - В92.

4. Губайдуллин С.У., Чхартнавилн А.Г., Иикин Е.В. Геометрические свойства следящей области а задаче поиска.

Иевдународная конференция "Лобачевский и совреиешма геометрия" - Казань, 18-22 августа 1992г. Тезисы докладов. ч.1., С. 27-20,'1992.'

5. Губайдуллин С.И,. 8шшн Е.В. Следящая область на цилиндре н на торе // Вести. Иоск. ун-та. Сер.15, Вычислительная математика и кибернетика. 1992, 112.