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

сЬ О*

мо^^овский ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ \ ^ им. М.В. ЛОМОНОСОВА

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

На правах рукописи УДК 517.9

ЧХАРТИШВИЛИ Александр Гедеванович

МЕТОД СЛЕДЯЩИХ ОБЛАСТЕЙ В ЗАДАЧАХ ДИНАМИЧЕСКОГО ПОИСКА

01.01.02 * дифференциальные уравнения

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата фюихо-математическн* наук

Мосхва 1994 г.

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

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

Официальные оппоненты доктор физико-математических наук,

профессор Н .Л .ГРИ ГОРЕН КО кандидат физико-математических наук, старший научный сотрудник А.К.КЕРИМОВ

Ведущая организация • Математический институт им. В.А.Стеклова РАН

в 14 часов 30 мннуг на заседании Специализированного совета К.053.05.87 в Московском государственном университете имени М.ВЛомоносова по адресу: 119899, Москва, Воробьевы горы, МГУ, 2-Й учебный корпус, факультет вычислительной математики и кибернетики, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ.

Зашита диссертации состоится

Автореферат разослан

Ученый секретарь Специализированною совета.

В М.ГОВОРОВ

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

Актуальность темы. Конфликтные задачи об управлении объектами, которые описывакчси обыкновенными дифференциальными уравнениями, принят объединять термином дифференциальные игры, Типичным примером дифференциальной шры является )лдачн преследования одного подвижного управляемою обьекш другим. К таким задачам относится и рассматриваемая в предлагаемой работе динамическая задача поиска подвижного объекта.

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

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

Ликршура но поиску довольно обширна. Интересные результаты получены Д.П.Кимом, Л.А.Петросяном, А.Ю.Гарнаевым, Н.А.Зенкевичем, Ф.Л.Черноусько н др. В большинстве работ рассматриваются вероятностные постановки задач, причем решение игры нередко ищется а смешанных стратегиях.

Дифференциальная игра поиска с участием двух

точечных объектов А (ищущий) и 6> (уклоняющийся)

в достаточно общей постановке может быть описана системой уравнений следующего вида

* = , У ,

х (о) = х0 , ^(о)--^,

где

хьХсГ, уьХсГ ,и1\)сПр, V£ Ус ^

(гдесь 17 и V". - управляющие компакты, а Л и

линейно связные множества, по которым объекты

перемешаются). Кроме того, в поисковой игре задастся 1срм>шальное множество

при лервом попадании на которое пары (~Х, игра считается оконченной.

Булем считать, что поведение ищущего объекта описывается соотношениями

■Ь'УМ ,*{0)*то, ^ 1тсГ\

в поведение уклоняющегося объекта О

г

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

я II , а также

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

В задачах поиска координаты уклоняющегося объекта обычно неизвестны ищущему вплоть до окончания игры (информационная дискриминация ищущего), Поэтому последний выбирает свое управление Ц ("I) программно, то есть фиксирует как функцию времени еще до начала игры. Довольно ясно, что точечное совладение объектов не может служить условием окончания игры, поскольку в таком жестком предположении даже задача поиска неподвижного объекта может быть содержательной лишь в одномерном случае (поиск на графе). Поэтому естественно считать, что игра оканчивается при попадании объекта Ь в некоторую окрестность объекта А (например в круг или тар с центром в А ), Возможна и такая постановка задачи

поиска: шрокп перемешаются по области с вырезами, и условием обнаружения является попадание в прямую видимость.

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

:£ - К , Ц V ,

где

л<ХсС\ уеУсК4, геУс/Я*,

а »ерминлльное множество имеет следующий вид

I с/е6/

Задачу динамического поиска будем изучать в

следующей постановит. сформулировать и обосновать

достаточные условия на множества

и \ , при выполнении которых существует кусочно-

непрерывная функция (управление ищущего) и

отвечающее ей решение \ (О ' перво! о уравнения

(траектория ищущего), такие, что для любой кусочно-

непрерывн«;! функции Г(I) (украшения лклоняюшетося)

и любого отвечающего ей решения (траектории

уклоняющегося) можно указать момент времен» X , в который точка (^ ("О ^ Ц (Т)) впервые попадает на заданное терминальное множество N .

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

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

1. Указан способ построения стандартной следящей области на плоскости, на сфере, на многообразии постоянной кривизны, в трехмерном евклидовом пространстве.

2. Найдены некоторые геометрические свойства стандартной следящей области.

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

4. Исследованы задачи поиска на плоскости, на поверхности цилиндра, на сфере, * на односвязиой поверхности вращения; на звездной поверхности. При помощи следящих областей найдены достаточные условия на параметры задачи, выполнение которых гарантирует успешный поиск. Указаны траектории ищущего игрока и верхняя оценка минимума времени поиска.

в

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

Общая методика исследован»

я.

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

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

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

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

Апробация. Результаты работы докладывались на научных конференциях "Лобачевский и современная геометрия" (Казань, 1992 г.) и "Понтрягинские чтения-1\"' (Воронеж, 1993 г.), на семинаре под руководством

профессора Э.Г. Позняка (механико-математичсскин факультет МГУ), в МИРАНе на семинарах под руководством член-корреспондента РАН Р.В. Рлмкрспнд« и профессора В.Ю. Благодатскнх.

П у б л и к I» н н и. Результаты диссертации опублнко-ваиы в работах [1)-(8].

Структура и объем работы. Диссертация состоит из введения и двух глин, Объем работы - 97 машинописных страниц, библиография - 45 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

глав.

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

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

В параграфе 1.1 в общей форме обсуждается идея остаточной области, упреждающей области и их объединения • следящей области.

Рассмотрим игровую задачу поиска с двумя точечными объектами А (ищущим) и Е> (уклоняющимся), которые перемещаются по некоторой кусочно-гладкой поверхности 5 с постоянными линейными скоростями и р>

соответственно, причем > ¡Ъ . Таким образом,

управлениями, находящимися в распоряжении игроков,

являются направления векторов скорости в каждый момент времени.

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

Ищущий объект стремится обнаружить уклоняющегося, то есть добиться того, чтобы расстояние между ними сократилось до заданного числа С , или, что то же самое, чтобы объект Ь попал в круг радиуса С (('-круг обнаружения) с центром в точке А .

Идея следящей области заключается в том, что при движении объекта А запретным для объекта Ь является не только круг обнаружения, но и более обширное множество.

Уклоняющийся объект, избегая ищущего, волен выбирать дня своего передвижения, вообще говоря, любую траекторию. Однако в силу ограниченности скорости он не способен мгновенно оказываться там, откуда только что. ушел ищущий. Множество, где нахождение объекта невозможно по указанном причине, назовем остаточной областью. В нее уклоняющийся не успевает попасть. Другое запретное для уклоняющегося множество возникает из иных . соображений: если уклоняющийся находится в нем в

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

В параграфе 1.2 изучается построение' следящих . областей в случае простого движения объектов на некоторых конкретных множествах.

В пункте 1.2. А. строится следящая область на плоскости.

Рассмотрим на плоскости два точечных объекта А и Р). Предположим, что объект Д перемещается с постоянной скалярной скоростью , а объект & - со скалярной скоростью, не превышающей постоянной р> ■, где £><о(. При этом объект А стремится обнаружить объект & , то есть добиться того, чтобы расстояние между ними сократилось до заданного положительного числа I .

Введем на плоскости прямоугольную декартову систему координат т . Пусть А движется по некоторой регулярной кривой ^ . заданной уравнениями ЭС^Н:) (параметризацию кривой ^ ' ограничения общности можно считать такой, что ее скорость совпадав* со скоростью . (X ).Пусть далее ( ^ , ^(О)) координаты ■ точки, в которой объект А находится в заданый момент 10=0 . На этот момент времени граница

упреждающей области (без дуги круга контроля) может быть описана следующими формулами:

. ч = уb) + U^-t) йп Ш ±

.где величины Q(í) и Л определяются соотношениями

<fftH'«a6>(¿), tp(t)=oUn0ft), ЬйГССО^ .

Уравнения границы остаточной области имеют схожую структуру. .

В пунктах 1.2.Б. и 1.2.В. приведены уравнения границы следящей области для задач поиска в трехмерном евклидовом пространстве и на многообразии.

В первом случае следящая область рассматривается как объединение шаров, а во втором как объединение геодезических кругов; центры этих шаров (Соответственно, геодезических кругов) лежат на траектории ищущего игрока, а радиусы по определенному закону сначала увеличиваются от нуля до t , а затем вновь уменьшаются до нуля.

В параграфе 1.3 приведены некоторые .свойства стандартной следящей области.

На любой момент времени форма следящей области зависит от параметров задачи , |Ь , Ь и выбранной траектории ^ , Однако длина' отрезка, высекаемого

т траектории ^ следящей областью, постоянна и равна Имеет место также следующий факт. При некоторых условиях на параметры задачи и на степень искривленности траектории, площадь следящей области (в трехмерном случае - объем) является инвариантом задачи. '

Например, при движении объектов Д и 6 по евклидовой плоскости справедливо следующее утверждение.

ТЕОРЕМА. Для любой траектории на плоскости, кривизна ^ которой удовлетворяет условию

площадь следящей области постоянна и равна

В параграфе доказаны соответствующие теоремы для поверхностей постоянной кривизны и для трехмерного

евклидова пространства. Все рассмотрения этого параграфа проводятся в фиксированный момейт времени

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

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

При движении ищущего объекта по сильно искривленной траектории возникает тонкая следящая область. В пункте 1.4.Б. она строится для случая движения ищущего объекта по окружности.

Следящие области рассмотренных выше типов можно было построить, зная некоторый небольшой участок траектории объекта А . Однако если известна вся траектория ищущего, то есть траектория перемещения объекта А от начального момента до времени окончания ^рассмотрений, то можно говорить о полной следящей области. Полная следящая область - это множество, в каждой точке которого объект Ъ либо не может находиться (полная остаточная область), либо будет непременно обнаружен через некоторое время (полная упреждаюшаяобласть). В пункте 1.4.В. приведен пример полной следящей области.

В пункте 1.5. вводится еще один класс следящих областей • самокасающиеся следящие области. Доказана

лемма о том, что траектория перемещения ищущего объекта, для которой в каждый момент времени соответствующая следящая область является самокасающейся (предоптимальная траектория), однозначно определяется любой своей дугой длины Ь0 ■ ■ '

В параграфе 1.6, рассматриваюся следящие области в' случае непростого движения и в случае переменного множества обнаружения.

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

Пол решением задачи обнаружения понимается следующее:

1) нахождение достаточных условий на параметры задачи, при выполнении которых существует такая траектория объекта А , что при любом начальном положении объекта Р) и при любом избранном им -управлении £ -встреча объектов состоится за конечное время:

2) конструктивное построение траектории объекта А , обеспечивающей успешное решение задачи поиска (обнаружение) при найденых условиях на параметры.

В параграфе 2,1. строится предоптимальная траектория на плоскости, при движении по которой полная остаточная область совпадает с открытым кругом радиуса

В параграфе 2.2. строится поисковая траектория на поверхности круглого цилиндра. Находится время гарантированною поиска.

В параграфах 2.3. и 2.4 соответственно строятся траектории" обнаружения на сфере и на одиосмзной поверхности вращения. Как и в случае конечного цилиндра, получено уравнение траектории объекта А и требуемое время. В пункте 2.3.Б. предлагается решение задачи обнаружения с препятствием в виде шара. ^

В параграфе 2.4 рассматривается задача обнаружения на поверхности с осевой звездностыо. Задача решается посредством отображения поверхности в квадрат с римановой метрикой с дальнейшим построением траектории в квадрате и переносе ее на заданную поверхность.

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

1. Чхартишвилн А.Г. Об одном геометрическом свойстве следящей области в двумерной задаче поиска. • М.: Деп. ВИНИТИ, 1990. N60-891.

2. Чхартишвнли А.Г. Об одном геометрическом свойстве ' следящей области 8 задачах поиска //. Вестнйк Моек ун-та, Сер.1, Математика. Механика. 1992, N3.

3. Губайдуллин С.М., Чхартишвнли А.Г., Шикйн Е.В.* Геометрические свойства следящей области в задаче 'поиска. • Международная конференция "Лобачевский и современная геометрия" - Казань, 18-22 августа 1992г. Тезисы докладов. 4.1, с.27-28, 1992.

4. Чхартишвилн А.Г., Шикин Е.В. Задачи поиска и обнаружения на некоторых поверхностях // Понтрягинские чтенця-1У. Весенняя воронежская математическая школа. Тезисы докладов (3-8 мая 1993г.). - Воронеж, 1993. ' -

5. Чхартишвнли А.Г., Шикни Е.В. Метод следящих областей в задачах поиска//Математический сборник, 1993, Т.184, N10.

6. Чхартишвилн А.Г.. Шикни Е.В. Динамические задачи поиска и обнаружения на некоторых замкнутых поверхностях // Дифференциальные уравнения. 1993, Т.29, N11.

7. Чхартишвнли А.Г.. Шикин Е.В. Следящая область .в пространстве Лобачевского II Вестник Моек ун-та, Сер.1, Математика. Механика. 1994, N2.

8. Чхартишвнли А.Г. О феномене тонкой следящей области в. задаче динамического поиска. - М.: Деп. ВИНИТИ, 1994, N 1445-В94.