Задачи об управлении протяженными объектами на плоскости тема автореферата и диссертации по математике, 01.01.02 ВАК РФ

Матвийчук, Александр Ростиславович АВТОР
кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ
Екатеринбург МЕСТО ЗАЩИТЫ
2005 ГОД ЗАЩИТЫ
   
01.01.02 КОД ВАК РФ
Диссертация по математике на тему «Задачи об управлении протяженными объектами на плоскости»
 
Автореферат диссертации на тему "Задачи об управлении протяженными объектами на плоскости"

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

На правах рукописи МАТВИЙЧУК Александр Ростиславович

ЗАДАЧИ ОБ УПРАВЛЕНИИ ПРОТЯЖЕННЫМИ ОБЪЕКТАМИ НА ПЛОСКОСТИ

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

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

Екатеринбург - 2005

Работа выполнена в отделе динамических систем Института математики и механики Уральского отделения РАН.

Научный руководитель: доктор физико-математических наук

В.Н. Ушаков

Официальные оппоненты: член-корреспондент РАН

A.Г. Чеицов,

доктор физико-математических наук

B.И. Ухоботов

Ведущая организация: Удмуртский государственный университет

Защита состоится " У "Л&АБРА 2005 года в -i i часов на заседании диссертационного совета Д 004.006.01 по защите диссертаций на соискание ученой степени доктора наук при Институте математики и механики Уральского отделения РАН (620219, г. Екатеринбург, ул. С. Ковалевской, 16).

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.

Автореферат разослан " 25" Ок ? 2005 года.

Ученый секретарь диссертационного совета кандидат физико-математических наук

А.А. Успенский

ММЧОЛ

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

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

A.Б. Куржанского, Ю.С. Осипова, А.И. Субботина, Е.Ф. Мищенко, Р.В. Гамкрелидзе, В.Г. Болтянского, а также зарубежных ученых Р. Капмана (R. Kaiman), Р. Беллмана (R. Bellman), Р. Айзекса (R. Isaacs), У. Флеминга (W. Fleming). Большой вклад в развитие теории оптимального управления внесли Р.Ф. Габасов, Ф.М. Кириллова, Б.Н. Пшеничный, Ф.Л Черноусько и их научные школы. Существенный прогресс в становлении и развитии теории оптимального управления связан также с именами Э.Г. Альбрехта, Б.И. Ананьева, A.B. Арутюнова, В.Д. Батухтина,

B.И. Благодатских, Н.Л. Григоренко, М.И. Гусева, А.Я. Дубовицкого, В.И. Жуковского, С.Г. Завалищина, М.И. Зеликина, А.Ф. Клейменова, A.B. Кряжимского, В.И. Максимова, A.A. Меликяна, A.A. Милютина, М.С. Никольского, B.C. Пацко, H.H. Петрова, Л.А. Петросяна,

A.Н. Сесекина, H.H. Субботиной, В.М. Тихомирова, Е.Л. Тонкова,

B.Е. Третьякова, В.И. Ухоботова, Т.Ф. Филипповой, А.Г. Ченцова, A.A. Чикрия, В.А. Якубовича, J.-P. Aubin, M. Bardi, Т. Basar, P. Bernhard, A.E. Bryson, R.J. Elliot, A. Friedman, Ho Yu-Chi, N.J. Kaiton, G.J. Olsder, E. Roxin, P. Varaiya, J. Warga и многих других ученых.

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

Теория динамических систем, стесненных фазовыми ограничениями, сформировалась под влиянием работ J .-P. Aubin1, А.Я. Дубовицкого2, Р.В. Гамкрелидзе3, А.Б. Куржанского4'5, A.A. Милютина6 и других авторов.

' Aubin J -Р Viability Theory Birkhauser, 1992

1 Дубовицкий А Я, Дубовицкий В.А Критерий существования содержательного принципа максимума в задаче с фазовыми ограничениями 11 Дифференц уравнения -1995 ~ТЭ1,№10 - С 1634-1640

3 Гамкрелидзе 1'В Оптимальные по быстродействию процессы при ограниченных фазовых координатах И Докл АН СССР - Т. 125, № 3. С 475-478

4 Курж апскии АН, Осипов ЮС К задаче управления! I щравичишвшн фаавцмчц-координатами // Прикл математика и механика - 1968 -Т 32, вып 2 (] iWifcHAlt ИОНЛ.ЧЬП " i

I БИБЛИОТЕКА

" '' « I«» .'Л

Существенный вклад а развитие этой теории внесли С.М. Асеев, A.B. Арутюнов, В.И. Благодатских7, М. Куинкампуа, П. Сент-Пьер8, Т.Ф. Филиппова9.

Теории динамических систем, стесненных фазовыми ограничениями, посвящены также исследования В.Н.Баранова10, E.JI. Тонкова", Е.К. Костоусовой12, В.Н. Ушакова и A.A. Незнахина13.

К традиционным задачам управления с фазовыми ограничениями близки задачи последовательного обхода множеств и более общие задачи последовательного обхода сечений многозначных отображений, которые подробно изучены в работах А.Г. Ченцова, A.A. Ченцова14 и Ю.И. Бердышева15.

В настоящее время в Институте математики и механики УрО РАН ведется разработка алгоритмов решения задач управления с фазовыми ограничениями, в том числе, разработка алгоритмов приближенного построения множеств достижимости при наличии фазовых ограничений. Так в отделе оптимального управления Е.К. Костоусовой12 разработаны методы построения двухсторонних оценок множеств достижимости линейных динамических систем (как с дискретным, так и с непрерывным временем) при наличии фазовых ограничений в дискретные моменты времени. Алгоритмы, разработанные для таких систем, могут быть применены для аппроксимации информационных областей, возникающих

5 Куржанскии А И, Филиппова ТФ Дифференциальные включения с фазовыми ограничениями Метод возмущений // Оптим упр и диффереиц уравнения Сб ст К 70-летию со дня рождения академика Е Ф Мищенко М. Наука Фи1 матлот.. 1995 С. 304-315 Тр МИР АН, т 211.

6 Левитин Е С, Милютин А А , Осмоловский H П. Теория условий высших порядков в гладких задачах на экстремум с ограничениями // Теоретические и прикладные вопросы оптимального управлеиия Иркутск. Наука, 1985. - С 4-40.

7 Арутюнов А В., Асеев С.М, Благодатских В И. Необходимые условия первого порядка в задаче оптимального управления дифференциальным включением с фазовыми ограничениями // Маг сб., 1993 Т. 184. №6, С. 3-32.

I Saint-Pierre Р, Qulncampo/x M An algorithm for viability Kemels in Holderian case- approximation by discrete dynamical systems II J Math SystemEstim Control 1995 V 5 № 1 P 115-118

9 Филиппова T Ф Задачи о выживаемости дня дифференциальных включений Дис д-ра физ -магг. наук 01 01.02. Екатеринбург, 1992 266 с / Ин-т математики и механики УрО РАН

10 Баранов В H Задачи выживания для систем с последействием - Дис кандидата физ -мат наук 0101.02 Ижевск, 2003 109 с / Удмуртский государственный университет

" Тонкое E.J1 Динамические задачи выживания // Вести Перм гос тех ун-та Функционально-дифференциальные уравнения 1997 №4 С. 138-148

12 Костоусова Е К О внутренних полиэдральных оценках множеств достижимости линейных систем с фазовыми ограничениями II Алгоритмы и программные средства параллельных вычислений Екатеринбург: УрО РАН, 2001 Вып 5 С. 167-187.

" Незнахин А А, Ушаков В И Сеточный метод приближенного построения ядра выживаемости для дифференциального включения И Журн выч мат имат физ, 2001,41,6, С.895-908 м Чепцов А А, Чепцов А.Г Маршрутизация последовательного обхода системы подвижных множеств с использованием динамического программирования в условиях неточных вычислений функции Беллмана // Проблемы управления и информатики 1999 №2 С 113-127

II Еердышев Ю И Об оптимальном по быстродействию последовательном обходе нелинейной

управляемой системой третьего порядка совокупности точек // Изв Академии наук Теория и системы

управления 2002 №3 С 41-48.

в задачах гарантированного оценивания в системах, где производятся неточные измерения в дискретные моменты времени.

В последнее десятилетие повышенный интерес к задачам управления с фазовыми ограничениями проявляется в отделе динамических систем Института математики и механики УрО РАН в связи с так называемой задачей обвода препятствий подвижным протяженным объектом. В этой задаче функционалом, подлежащим оптимизации, является время попадания подвижного объекта на терминальное множество16. Особенность этой задачи состоит в том, что управляемый объект, движущийся при наличии фазовых ограничений, является протяженным в фазовом пространстве. Эта протяженность заметно усложняет задачу оптимального по быстродействию управления. Другой важной задачей, стимулирующей повышенный интерес в отделе динамических систем к задаче управления с фазовыми ограничениями, явилась задача построения выживающих траекторий и ядер выживаемости1'5'8. Эти две задачи (задача обвода препятствий и задача выживаемости) тесно связаны с задачей построения и оценки множеств достижимости управляемых систем и дифференциальных включений17'18. Имеющиеся в настоящее время процедуры построения множеств достижимости не предполагают, как правило, что в процессе их вычисления одновременно (или, более точно, -параллельно во времени) вычисляются и управления, приводящие в ту или иную заранее выбранную точку множества достижимости. В связи с этим возникает еще одна важная задача - задача о построении управления (после того, как множество достижимости построено), приводящего в заданную точку множества достижимости. Разумеется, что точно эту задачу решить невозможно. В диссертационной работе предлагается метод построения управления, решающего эту задачу приближенно. В основе

19 20

метода лежат конструкции поводыря ■ .

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

16 Вахрушев В А, Махоеа А В, Ушаков В И Один из алгоритмов решении задачи об обходе

препятствий // Известии академии наук Теория и системы управления, 2000, № 1 С 101-109 1 Черноусько ФЯ Оценивание фазового состояния динамических систем Метод эллипсоидов М Наука, 1988 319 с

18 Kurzhamki А В, Valyi 1 Ellipsoidal techniques for dynamic systems control synthesis for uncertain systems //Dynamic and Control 1992 №2. P 87-111

19 Красовскии И И, Субботин А И Позиционные дифференциальные игры М Наука, 1974.456с

20 Красовскии Н И Управление динамической системой // М Наука, 1985, 520с

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

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

19 20

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

Научная новизна. Данная работа является продолжением исследований тех задач управления с фазовыми ограничениями, которые проводились и проводятся в настоящий момент в Институте математики и механики УрО РАН и, в том числе, в отделе динамических систем Института. Эта диссертация продолжает исследования по построению выживающих траекторий и ядер выживаемости5-8,13, а также исследования задач обвода препятствий16.

Научная новизна диссертации состоит в том, что для решения упомянутых задач для нелинейных нестационарных управляемых систем используется трехэтапный метод построения решения: на 1-м этапе вычисляется последовательность множеств достижимости (в прямом времени) до момента встречи очередного множества достижимости с терминальным множеством, при этом выделяется точка из пересечения этих множеств; на 2-м этапе, отправляясь от выделенной точки, протягивается (в обратном времени) через множества достижимости движение поводыря, которое в результате приходит в некоторую точку начального множества; на 3-м этапе строится (в прямом времени) управление, и соответственно движение управляемой системы, приходящее в заданную окрестность терминального множества. Здесь можно отметить, что в диссертационной работе, в отличие от широко распространенных сеточных методов, все множества представлены в виде

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

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

Среди таких алгоритмов можно выделить так называемый быстро шагающий алгоритм (fast marching method - FMA)22, который применяется не только в задачах оптимального управления, но и в таких областях, как обработка изображений и распознавание образов. В частности, этот алгоритм используется для приближенного решения задачи поиска оптимальной по времени траектории для стационарной системы.

Особенностью FMA22 и алгоритмов, описанных в работе21, является то, что они применяются к объектам, способным менять свою ориентацию.

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

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

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

21 Laumond J -P Robot motion planning and control - London Springer - Verlag London Limited, 1998 -343 p.

22 Sethtan J A Level set methods and fest marching methods -Cambridge Cambridge university press, 1999 -378 p.

Апробация работы. Основные результаты диссертации обсуждались и докладывались на семинарах на факультете вычислительной математики и кибернетики МГУ, на математических факультетах Удмуртского государственного университета и Челябинского государственного университета. Кроме того, научные результаты докладывались на 33, 34 и 35-й региональных молодежных конференциях "Проблемы теоретической и прикладной математики" (Екатеринбург, 2002, 2003, 2004 гг.), а также на XXIV Российской школе по проблемам науки и технологий, посвященной 80-летию со дня рождения академика В.П.Макеева (г. Миасс, 2004 г.). Кроме того, результаты были представлены в виде доклада на Международном семинаре "Теория управления и теория обобщенных решений уравнений Гамильтона-Якоби" посвященного 60-летию академика А.И. Субботина (Екатеринбург, 2005).

Все основные результаты диссертации являются новыми и принадлежат автору. Результаты, полученные совместно с руководителем, вошли в главу II. А именно, В.Н. Ушаковым была поставлена задача и намечена схема решения этой задачи. Все остальные результаты получены автором самостоятельно.

Публикации. Основные результаты диссертации достаточно полно отражены в работах диссертанта [1-8].

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

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

Глава I представленной диссертационной работы содержит в себе вводную часть диссертации. Ее главное назначение - дать определения ключевым понятиям, используемым в диссертации. Также в этой главе описывается задача поиска кратчайшего по времени маршрута для простой системы, знакомство с которой положило начало исследованиям автора по тематике диссертации. Эта задача является вводной в общую тематику исследований, которые ведутся и по настоящее время.

Данная глава состоит из шести параграфов. В параграфе 1 приводятся определения понятий, используемых во всей диссертационной работе. Среди ключевых определений можно выделить определение многоугольника, дыры и массива. В параграфе 2 формулируется задача об оптимальном по быстродействию управлении подвижным протяженным объектом Г', заданным в виде многоугольника на плоскости. В сформулированной задаче предполагается, что препятствия на плоскости -неподвижные многоугольники, а объект Т* не меняет ориентацию с

течением времени. Кроме того, динамика подвижного объекта Г' описывается простыми движениями. Таким образом, это - простейшая задача обвода препятствий из задач, рассмотренных в диссертации. В параграфе 3 предлагается способ решения поставленной задачи, в котором рассмотрение подвижного многоугольника У* подменяется рассмотрением некоторого его "центра" - точки О. При такой подмене , вместо многоугольников-препятствий рассматриваются так называемые

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

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

В главе II рассматривается нелинейная нестационарная управляемая система, динамика которой описывается векторным дифференциальным уравнением

х = /0,х,и), иеР, 1е[(0,&], (0<9«х>. (1)

Здесь х - т-мерный фазовый вектор системы, стесненный фазовым ограничением (/,*)еФ, < 6 [/0,5]; и - управление, стесненное ограничением иеР, где Р - компакт в евклидовом пространстве Яг.

На управляемую систему (1) накладываются традиционные условия, обеспечивающие существование, единственность и продолжимость решений системы на весь промежуток 5]. Под допустимым

управлением и(1), I е [10,£>] понимается любая измеримая по Лебегу функция, удовлетворяющая и(/)еР,

Для этой управляемой системы рассматривается задача об оптимальном по быстродействию переводе фазового вектора х из начального множества Х0 на некоторое терминальное множество X} за

кратчайшее время с сохранением фазовых ограничений. При этом предполагается, что Х0 и Хг - ограниченные замкнутые множества в

пространстве И".

Предлагается метод приближенного построения решений задачи об оптимальном быстродействии. Этот метод составляет базу алгоритмов

построения разрешающего управления в задачах управления с фазовыми ограничениями, рассмотренных в главах III и IV.

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

В этой же главе дается определение множеств достижимости системы (1). Под множеством достижимости системы (1) Y{t*-,t.,xt), ta <t, <t* <Э, X, бФ(1,), с начальным условием *[/,] = *., отвечающим моменту /*, понимается множество всех точек х' е Rm, для каждой из которых найдется допустимое управление, порождающее решение хЩ уравнения (1), удовлетворяющее условиям *[f,] = .x,; л[<*] = х*; хЩ е Ф(1), / е [/»;/*].

Кроме того, управляемой системе х = f{t,x,u) ставится в соответствие дифференциальное включение (ДВ)

xeF(t,x),te[t0,&], (2)

где F(t,х) = со{/(/,х,и): иеР}.

Символом X(t'-,t.,x,), t0<t,<t'< .9, х, еФ(!.) обозначается множество всех х е Rm, для которых существуют решения *[/] ДВ (2), удовлетворяющие х[/,] = х[/*] = **; x[t] е Ф(1), le[t,;í']. Таким образом, X(t';t,,x.) - множество достижимости ДВ (2), отвечающее моменту t*, с начальным условием jc[í.] = х,. Также вводится Z(t';t.,x,) - множество достижимости ДВ (2) в момент /* в пространстве Rm в случае, когда на фазовый вектор х не наложены какие-либо ограничения.

В параграфе 2 приводится определение множества достижимости на [г0,>9] ДВ (2). В этом параграфе используется схема рассуждений и доказательств, аналогичная схеме из работы A.A. Незнахина и В.Н. Ушакова'3.

Определение 1. Множеством достижимости X ДВ (1.2) на [/„, i9] назовем множество всех (/„х,)еФ таких, что х. е X(t.-,tu,X'„).

Учитывая условия наложенные на систему (1), считается, что все рассматриваемые конструкции (множества достижимости, всевозможные траектории и точки) содержатся в некоторой достаточно большой окрестности D множества Ф, представляющей собой ограниченное и замкнутое множество в [í0,i9]x R".

Вводятся следующие обозначения: L = L(D)<оо, К = max{|| f(t,x,u)\\: (*,*,и)е[/0,Я]х£>х/>}<оо, й>(Д) = Лй>* ((1 + /ОД) и а( Д) =

= svp{ d(F(t,,x,),F(t ,x )): (U,x,),{t ,x ) из D,\t.-t \ + \\x,-x ||< A}, A>0.

В этом же параграфе осуществляется дискретизация промежутка [/,„<9] путем задания разбиений Г„ = {/„, ..., tN(n)=3}, п = 1,2,...,

промежутка [f0,i9], таких, что диаметры А(и) = шах{А,: 0 < i < N(n) - 1}, А, = /м -1, разбиений Гп монотонно стремятся к нулю с ростом номера п.

Разбиение Гп фиксируется на время и ему ставится в соответствие последовательность {ej чисел с,, заданных рекуррентно: = 0, ем =й>(Д,) + (1+ LA,)e,, < = 0, 1, ..., N(n)-l. Кроме того, разбиению Г„ ставится в соответствие последовательность {Х<я)(/,)} множеств которая задается также рекуррентно: XM(t0) = X0, ХМ(<,+,) = Ф«,ЛмГ\Щ^Х^Ц,)), / = 0, 1, ..., N{n)~ 1. Здесь Ф(!)с -е -окрестность множества 0(t) в пространстве Rm, е>0; Z(t";t.,xt) = x. + (t'-t.)F(l„x,), l0St,<t'<S, x.eRm;

Z(t';t.,X,) = (J Z(t ,U,x,).

Определение 2. Пусть X° - множество всех точек (i,,ji,)e[(0,i9]x Rm, представимых в виде (1„х.)=\\т(хп,хп), где {(г„,х„): т„ =/„(/,),

П~ГХ>

хп е Х(п)(тп)} , tn{и) = max ti, - некоторая последовательность из

If € Г„ ¡/¡^Х*

Таким образом, А'0 есть некоторый предел последовательности {X{n)(l.)}, когда « —► оо, а А(п> - диаметр разбиения Гп стремится к нулю. В этом же параграфе формулируется и доказывается теорема 1. Теорема 1. Справедливо равенство Х° = X.

В параграфе 3 формулируется задача об управлении. Для этого в XM(tN/)r\ Х{ выбирается точка ]\lNf ] и задается некоторое е' >0. Здесь

tN е Г„ - наименьший из моментов разбиения Гп, для которого выполняется XM(tN)n Xf (предполагается, что такой момент существует). Пусть Г/ = {<0, ..., tNf}.

Задача 2. Требуется построить допустимое управление u{t), t&[t0,tN ], приводящее фазовый вектор лг£/] системы (1.1) из Х0 в е' -окрестность точки y[tNf] в момент tN/: x[tN^eOe.(y[tNf]) -

-{хей*: ||х-^н ]\\<е*}\ при этом должно выполняться включение

Для решения задачи 2 кроме всего прочего рассматривается ДВ с малым параметром е > О

+ (3)

где е = {и»еЛ": |М|£1}.

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

ДВ (3), ломаная Эйлера ДВ (3) проходящая через множества

ХМ(1К/), 1<л))' •••> в моменты I, е Г/. Эта ломаная Эйлера

играет роль поводыря'9 при построении в системе (1) с начальным условием л[/0] = Я'о1 управления и'(1), 1е[10,1к ], решающего задачу 2. При этом показывается, что при условии достаточной малости диаметра А<л) разбиения Гп такая ломаная Эйлера ДВ (3) существует.

После того, как построен поводырь, в прямом времени способом экстремального прицеливания19'20 по шагам [Г(,/1Ч1), / = О, 1, ..., Nг -1

разбиения Г/ вычисляется управление к*(0, / е ['о Оно строится

последовательно как кусочно-постоянное управление г/(/) = «*(/,), /е[/„/ж), » = 0, 1, ..., Л^-1.

В параграфе 3 формулируется и доказывается теорема, в которой утверждается, что при определенных условиях на динамику системы, фазовое ограничение Ф и диаметр А(л) разбиения Гп найдется такое разбиение Г/={/0, г,, ..., <ЛГ/}, что движение х[/] не покидает в'-

окрестности фазового ограничения.

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

Глава III посвящена исследованию задач обвода препятствий на плоскости Л2 подвижным протяженным объектом Т* с "центром" в точке О, положение которого на плоскости Я2 представимо точкой х = (х1,х2)т е Я2. Динамика подвижного объекта описывается уравнением х = и, где *еЛ2, /е[*0,<9], ие Р, Р - компакт в плоскости Л2. В главе III рассматривается алгоритм приближенного построения оптимальных

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

В параграфе 1 приводится постановка задачи, в которой требуется построить допустимое управление и'(0> ^ е [г0, .9], приводящее фазовый вектор *[?] системы х = и из X. на множество за минимальное

^ время, где е - заданное положительное число.

Рассматриваемая задача является нестационарной в том смысле, что многоугольники-препятствия Т:(Г), / = 1, 2, , ? е [/0,5], 1 передвигаются в течение времени по известным (нам) программным

законам. При этом предполагается, что это передвижение многоугольников-препятствий происходит с сохранением их ориентации на плоскости Я2.

В параграфе 2 рассматриваются вопросы, связанные с переходом к задаче о движении "центра" О подвижного многоугольника Т'. Необходимость замены "запретных зон" их окрестностями обсуждается в параграфе 3.

Замена "запретных зон" их окрестностями вызвана тем, что на практике не всегда реально выбрать по заранее заданной величине е' > О шаг Д(п); требуемый шаг Д(л> может оказаться настолько малым, что реализация представленных алгоритмов на ЭВМ потребует очень большого времени вычислений. В этом же параграфе приводится числениый алгоритм построения приближений окрестностей "запретных зон".

Процедура численного построения множеств достижимости с использованием операций над многоугольниками описывается в параграфе 4. Эта процедура в соответствии с предложенной в главе схемой базируется на переходе к дискретной модели времени, то есть на ( подмене промежутка [(а, ,9] разбиением Гп ={/„, ..., = >9}.

Построение множеств достижимости начинается с множества

* где X*, ] = I, ...,и0, - замкнутые многоугольники, и

м

заканчивается в тот момент, когда впервые выполняется -У(я'(/,)п X) ф 0

(предполагается, что такой момент существует).

В параграфе 5 для управляемой системы х~и, иеР, описан численный алгоритм приближенного построения оптимального управления по уже построенной системе множеств Л><">(0 > / = 0, 1, ..., N/.

Здесь Р - выпуклый многоугольник, tN/ - момент времени, когда впервые

выполняется: X{n\t, )nXf*0.

Особенность численного алгоритма в этом случае заключается в том, что поводырь уЩ совпадает с движением хЩ управляемой системы. Кроме того, движение системы x[t] приходит не просто в некоторую окрестность множества Xf, а в одну из точек пересечения Xм (t,^ )r\Xf.

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

В параграфе 7 приведены смоделированные на ЭВМ примеры, иллюстрирующие работу описанного в главе III алгоритма.

Глава IV посвящена описанию численного алгоритма вычисления разрешающего управления в задаче обвода препятствий подвижным многоугольником Г* с фиксированной ориентацией и нелинейной динамикой вида х = f(t,x)+B(t,x) u, иеР - выпуклый компакт в R2. Основу алгоритма составляет описанный в главе II метод приближенного вычисления оптимального по быстродействию управления.

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

Здесь, как и в задаче, рассмотренной в главе III, имеется неподвижная арена (7, внутри которой располагаются подвижные многоугольники-препятствия Г,(0, ' = !> 2, ...,Nr, tе|/0,.9], совершающие плоскопараллельные движения по известным нам программным законам. Препятствия задают фазовое ограничение, имеющее непустые сечения

Динамика подвижного многоугольника Т" описывается системой вида

где / е [/0,5], и = (и,,и2)т е Л2, Р - выпуклый многоугольник в Я2.

На управляемую систему (4) накладываются традиционные условия, обеспечивающие существование, единственность и продолжимость решений системы на весь промежуток (б[/0,.9].

х = f(t,x)+B(t,x) u,

(4)

Задача 3. Требуется построить допустимое управление и'(<), (е[10,3], приводящее фазовый вектор х[1] системы (4) из стартового множества X, на множество (х . за минимальное время. Здесь е -

заданное положительное число.

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

В параграфе 3 описан численный алгоритм построения множеств

^ А

достижимости X,, г' = 1, ..., N/, где X, = для системы (4). Здесь Х\,

У = 1, ..., я,, - замкнутые многоугольники. В этом алгоритме, как и в случае линейной системы из предыдущей главы, все множества представлены в виде многоугольников и дыр. В основу алгоритма лег метод вычисления множеств достижимости в дискретном времени, описанный в главе II.

Численный метод построения (приближенного) оптимального по быстродействию управления описан в параграфе 4. Это управление конструируется в соответствии со схемой, предложенной в параграфах 3 и 4 главы II. Схема предполагает предварительное построение поводыря по которому затем вычисляется разрешающее управление «*(/) и отвечающая ему траектория хЩ управляемой системы. Для расчета дг[/] предлагаются два метода экстремального прицеливания на у['].

После того как вычислены «*(?) и *[*], их можно попытаться скорректировать, используя процедуры, описанные в параграфе 5.

В параграфе 6 главы IV сравниваются два способа экстремального прицеливания, описанные в параграфах 3 и 4 главы II, и выявляются те особенности, которые присущи каждому из этих способов.

В параграфе 7 рассматриваются множества ограниченного управления как альтернатива окрестностям "запретных" зон.

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

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

Работа выполнена при поддержке грантов РФФИ в рамках проектов № 05-01-00601, гранта Президента РФ в рамках программы

государственной поддержки ведущих научных школ НШ-791.2003.1, а также конкурса научных проектов молодых ученых и аспирантов УрО РАН 2004 года.

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Матвийчук А.Р., Ушаков В.Н. Построение оптимального пути движения многоугольника на плоскости с препятствиями И Проблемы теоретической и прикладной математики: Труды 33-й Региональной молодежной конференции. Еактеринбург: УрО РАН, 2002. С.254-255.

2. Матвийчук А.Р., Ушаков В.Н. Задача об оптимальном по быстродействию управлении подвижным объектом на плоскости при наличии препятствий. // Ин-т математики и механики УрО РАН. Екатеринбург, 2003. Деп. в ВИНИТИ 21.01.03 № 125-В2003.

3. Матвийчук А.Р. Оптимальное по быстродействию управление подвижным объектом на плоскости при наличии препятствий // Наука и технологии. Труды XXIII Российской школы по проблемам науки и технологий. - Миасс: МСНТ, 2003. С.294-305.

4. Матвийчук А.Р. Один алгоритм построения множества управляемости при наличии фазовых ограничений. // Вестник Челябинского университета. Серия 3. Математика, механика, информатика. -Челябинск: Изд-во центра ЧелГУ. №2, Т.8,2003. С.153-166.

5. Матвийчук А.Р. Задача об оптимальном по быстродействию управлении подвижным объектом на плоскости при наличии фазовых ограничений// Изв. РАН. Теория и системы управления. 2004. №1. С.89-95.

6. Матвийчук А.Р., Устинов A.C., Ушаков В.Н. Один из алгоритмов решения задачи об оптимальном по быстродействию управлении подвижным объектом на плоскости при наличии препятствий // Труды XXIV Российской школы по проблемам науки и технологий, посвященной 80-летию со дня рождения академика В.П.Макеева. -Миасс: МСНТ, 2004. С.258-269.

7. Ушаков В.Н., Матвийчук А.Р., Шагалова Л.Г. К решению задач управления с фазовыми ограничениями // Некоторые задачи динамики и управления: Сб. науч. тр. / под. ред. В.Д. Батухтина; Челяб. гос. ун-т, ИММ УрО РАН. Челябинск: Челяб. гос. ун-т, 2005, С. 134-158.

8. Матвийчук А.Р., Успенский A.A., Ушаков В.Н., Пахотинских В.Ю. О построении разрешающих управлений в задачах управления с фазовыми ограничениями // Теория управления и теория обобщенных решений уравнений Гамильтона-Якоби: Тез. докл. Междунар. семинара, поев. 60-летию акад. А.И. Субботина. - Екатеринбург: Изд-во Урал, унта, 2005. С. 106-107.

МАТВИЙЧУК Александр Ростиславович

ЗАДАЧИ ОБ УПРАВЛЕНИИ ПРОТЯЖЕННЫМИ ОБЪЕКТАМИ НА ПЛОСКОСТИ

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

Подписано в печать 18.10.05 Формат 60x84 1/16. Объем 1 п.л. Тираж 100 экз. Заказ № 51 Размножено с готового оригинал-макета в типографии "Уральский центр академического обслуживания" 620219, г. Екатеринбург, ул. С. Ковалевской, 18

V

I \

)

I

I

М21

РНБ Русский фонд

2006-4 19463

 
Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Матвийчук, Александр Ростиславович

Список сокращений и обозначений.

Введение.

Глава I. Задача поиска кратчайшего по времени маршрута.

§ 1. Основные определения.

§2. Постановка задачи.

§3. Сведение задачи о движении многоугольника Т* к задаче о движении-"центра" 0.

§4. Построение "запретных зон".

§5. Построение кратчайшей по времени траектории для "центра" 0.

§6. Примеры.

Глава II. Построение приближенных решений в задаче об оптимальном по быстродействию управлении.

§ 1. Основные определения.

§2. Множество достижимости ДВ (1.2) на [/0,«9].

§3. Задача о приведении движения управляемой системы (1.1) на множество Xу за минимальное время.

§4. Второй способ построения разрешающего управления в задаче 3.2.

Глава III. Алгоритмы вычисления оптимального по быстродействию управления подвижным объектом, динамика которого описывается уравнением вида х = и.

§ 1. Постановка задачи.

А §2. Сведение задачи о движении многоугольника У* к задаче о движении "центра" 0.

§3. Построение приближений окрестностей "запретных зон".

§4. Построение множеств достижимости.

§5. Построение допустимого управления по МД.

§6. Некоторые вопросы, связанные с окрестностями "запретных зон".

§7. Примеры.

Глава IV. Алгоритмы вычисления оптимального по быстродействию управления подвижным объектом с нелинейной динамикой вида х = f{t,x) + B(t,x)'U.

§ 1. Постановка задачи.

§2. Предварительные построения (переход к задаче о движении центра" О).

§3. Построение множеств достижимости.

§4. Построение допустимого управления по МД.

§5. Способы уточнения управления u*(t).

§6. Сравнение способов построения управления.

§7. Множества ограниченного управления для нелинейной нестационарной системы.

§8. Примеры.

 
Введение диссертация по математике, на тему "Задачи об управлении протяженными объектами на плоскости"

Предыстория и актуальность темы. Диссертация посвящена исследованию задач об управлении протяженными объектами на плоскости, динамика которых стеснена фазовыми ограничениями. Рассматриваемые в диссертации задачи относятся к теории оптимального управления. Современный облик этой теории сформировался в значительной степени под влиянием работ отечественных и зарубежных математиков H.H. Красовского, JI.C. Понтрягина и их учеников

A.Б. Куржанского, Ю.С. Осипова, А.И. Субботина, Е.Ф. Мищенко, Р.В. Гамкрелидзе, В.Г. Болтянского, а также зарубежных ученых Р. Калмана, Р. Беллмана, Р. Айзекса, У. Флеминга. Большой вклад в развитие теории оптимального управления внесли Р.Ф. Габасов, Ф.М. Кириллова, Б.Н. Пшеничный, Ф.Л Черноусько и их научные школы. Существенный прогресс в становлении и развитии теории оптимального управления связан также с именами Э.Г. Альбрехта, A.B. Арутюнова,

B.Д. Батухтина, В.И. Благодатских, H.JI. Григоренко, М.И. Гусева, А.Я. Дубовицкого, С.Г. Завалищина, М.И. Зеликина, А.Ф. Клейменова,

A.B. Кряжимского, В.И. Максимова, A.A. Меликяна, A.A. Милютина, М.С. Никольского, B.C. Пацко, H.H. Петрова, JI.A. Петросяна, H.H. Субботиной, В.М. Тихомирова, E.JI. Тонкова, В.Е. Третьякова,

B.И. Ухоботова, Т.Ф. Филипповой, А.Г. Ченцова, A.A. Чикрия, В.А. Якубовича, J.-P. Aubin, M. Bardi, Т. Basar, P. Bernhard, A.E. Bryson, R.J. Elliot, A. Friedman, Ho Yu-Chi, N.J. Kaiton, G.J. Olsder, E. Roxin, P. Varaiya, J. Warga и многих других ученых.

Актуальность изучения управляемых систем, стесненных фазовыми ограничениями, обусловлена с одной стороны многочисленными задачами из различных областей механики, экономики, экологии и биологии, с другой стороны - внутренними потребностями, возникающими в математической теории управления динамическими системами [1,1921,38,39].

Теория динамических систем, стесненных фазовыми ограничениями, сформировалась под влиянием работ J.-P. Aubin, А.Б. Куржанского,

A.Я. Дубовицкого, А.А.Милютина, Р.В. Гамкрелидзе [10,11,13-15,2326,57,58] и других авторов. Существенный вклад а развитие этой теории внесли С.М. Асеев, A.B. Арутюнов, В.И. Благодатских, М. Куинкампуа, П. Сент-Пьер, Т.Ф. Филиппова, X. Франковска [3-5,63,47-48].

Теории динамических систем, стесненных фазовыми ограничениями, посвящены также работы В.Н. Баранова [65], E.JI. Тонкова [43,44],

B.Н. Ушакова и A.A. Незнахина [12,29-31,60].

К традиционным задачам управления с фазовыми ограничениями близки задачи последовательного обхода множеств и более общие задачи последовательного обхода сечений многозначных отображений, которые подробно изучены в работах А.Г. Ченцова, A.A. Ченцова и Ю.И. Бердышева [7,52,53].

В настоящее время ведется активная разработка алгоритмов решения задач с фазовыми ограничениями, в том числе разработка алгоритмов приближенного построения множеств достижимости при наличии фазовых ограничений. Так в Отделе оптимального управления Института математики и механики УрО РАН Е.К. Костоусовой (см. [16,17]) разработаны методы построения двухсторонних оценок множеств достижимости линейных динамических систем (как с дискретным, так и с непрерывным временем) при наличии фазовых ограничений в дискретные моменты времени. Алгоритмы, разработанные для таких систем, могут быть применены для аппроксимации информационных областей, возникающих в задачах гарантированного оценивания в системах, где производятся неточные измерения в дискретные моменты времени.

В последнее десятилетие повышенный интерес к задачам управления с фазовыми ограничениями проявляется в Отделе динамических систем Института математики и механики УрО РАН в связи с так называемой задачей обвода препятствий подвижным протяженным объектом. В этой задаче функционалом, подлежащим оптимизации, является время попадания подвижного объекта на терминальное множество [8,30-32].

Особенность этой задачи состоит в том, что управляемый объект, движущийся при наличии фазовых ограничений, является протяженным в фазовом пространстве. Эта протяженность существенно усложняет задачу оптимального по быстродействию управления. Другой важной задачей, стимулирующей повышенный интерес в Отделе динамических систем к задаче управления с фазовыми ограничениями, явилась задача построения выживающих траекторий и ядер выживаемости [25,47]. Эти две задачи (задача обвода препятствий и задача выживаемости) тесно связаны с задачей построения и оценки множеств достижимости управляемых систем и дифференциальных включений [54-56,60,61]. Имеющиеся в настоящее время процедуры построения множеств достижимости не предполагают, как правило, что в процессе их вычисления одновременно (или, более точно, - параллельно во времени) вычисляются и управления, приводящие в ту или иную заранее выбранную точку множества достижимости. В связи с этим возникает еще одна важная задача - задача о построении управления (после того, как множество достижимости построено), приводящего в заданную точку множества достижимости. Разумеется, что точно эту задачу решить невозможно. В диссертационной работе предлагается метод построения управления, решающего эту задачу приближенно. В основе метода лежат конструкции поводыря [20-21].

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

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

Методы исследования. Исследования проводятся в рамках подхода, разрабатываемого в научной школе H.H. Красовского по оптимальному управлению. В частности, в диссертации при решении задач управления для систем с нелинейной динамикой активно используются конструкции поводыря и экстремального прицеливания на движение поводыря [20-21]. Разработка алгоритмов и программ ведется только для задач управления на плоскости. Алгоритмы базируются на дискретном представлении времени, на представлении множеств из R2 в виде многоугольников на плоскости и применении различного рода операций к этим многоугольникам (например, операции объединения, пересечения многоугольников, обвод одного многоугольника другим и так далее).

Научная новизна. Данная работа является продолжением исследований тех задач управления с фазовыми ограничениями, которые проводились и проводятся в настоящий момент в Институте математики и механики УрО РАН и, в том числе, в Отделе динамических систем Института. Эта диссертация продолжает исследования по построению выживающих траекторий и ядер выживаемости [20-32], а также исследования задач обвода препятствий [8].

Научная новизна диссертации состоит в том, что для решения упомянутых задач для нелинейных нестационарных управляемых систем используется трехэтапный метод построения решения: на 1-м этапе вычисляется последовательность множеств достижимости (в прямом времени) до момента встречи очередного множества достижимости с терминальным множеством, при этом выделяется точка из пересечения этих множеств; на 2-м этапе, отправляясь от выделенной точки протягивается (в обратном времени) через множества достижимости движение поводыря, которое в результате приходит в некоторую точку начального множества; на 3-м этапе строится (в прямом времени) движение управляемой системы и управление, приводящее в окрестность терминального множества. Отметим, что в представленной работе, в отличие от широко распространенных сеточных методов, все множества представлены в виде многоугольников, что требует более сложных процедур построения множеств достижимости, нежели в случае сеточных методов.

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

Среди таких алгоритмов можно выделить так называемый быстро шагающий алгоритм (fast marching method - FMA) [64], который применяется не только в задачах оптимального управления, но и в таких областях, как обработка изображений и распознавание образов. В частности, этот алгоритм используется для приближенного решения задачи поиска оптимальной по времени траектории для стационарной системы. Этот алгоритм во многом схож с известным алгоритмом Дейкстры, и, как и алгоритм Дейкстры (в случае, когда он применяется к сетке для нахождения кратчайшего пути), является сеточным методом, в котором однажды рассмотренный пиксел навсегда исключается из рассмотрения. В связи с этим, в общем случае FMA не применим к нестационарным системам.

Особенностью FMA [64] и алгоритмов, описанных в работе [62], является то, что они применяются к объектам, способным менять свою ориентацию. Так, например, в работе [62] приводятся различные подходы к решению задачи нахождения кратчайшей возможной траектории для неголономной системы, в которой, например, могут накладываться ограничения на величину радиуса разворота протяженного объекта за счет введения дополнительных фазовых переменных в дифференциальную систему. При этом, как и в работе [64], в [62] рассматриваются только стационарные системы. В этой же работе для решения некоторых задач используется подход, основанный на применении принципа максимума Понтрягина.

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

Кроме того, вводятся жесткие условия на то, какими (открытыми или замкнутыми) должны быть множества при выполнении над ними описанных в диссертации операций. Это необходимо для того, чтобы применяемые к многоугольникам алгоритмы давали корректный результат. Например, операция объединения двух многоугольников будет корректна, если оба этих многоугольника или замкнуты или открыты. Важно отметить, что такой подход не сужает область применения представленных методов.

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

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

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

Структура, объем и краткое содержание. Диссертационная работа состоит из настоящего введения, списка сокращений и обозначений, четырех глав, объединяющих 24 параграфа, приложения и списка литературы. Общий объем диссертации составляет 171 страницу, библиографический список включает 65 наименований, иллюстративный материал насчитывает 78 рисунков. Нумерация параграфов осуществляется в пределах каждой главы. Нумерация формул двойная: в первой позиции указывается номер параграфа, в котором приведена формула, во второй - порядковый номер формулы в этом параграфе. Такая же нумерация принята для определений, теорем, замечаний, примеров и рисунков. Текст замечаний выделен курсивом. Основные сокращения и обозначения объяснены в списке сокращений и обозначений.

 
Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Матвийчук, Александр Ростиславович, Екатеринбург

1. Айзеке Р. Дифференциальные игры. "Мир", 1967 г.

2. Андерсон, Джеймс А. Дискретная математика и комбинаторика: Пер. с англ. - М.: Издательский дом «Вильяме», 2003. 960 с.

3. Арутюнов А.В. Условия экстремума. Анормальные и вырожденные задачи. - М.: Изд-во «Факториал», 1997. - 256 с.

4. Арутюнов А.В., Асеев СМ., Благодатских В.И. Необходимые условия первого порядка в задаче оптимального управлениядифференциальным включением с фазовыми ограничениями //Мат. сб., 1993. Т. 184. № 6, 3-32.

5. Арутюнов А.В., Благодатских В.И. Принцип максимума для дифференциальных включений с фазовыми ограничениями // Тр.МИАН СССР, 1991. Т. 200. 4-26.

6. Беллман Р. Динамическое программирование. М.: Изд-во иностр. лит., 1960.

7. Бердышев Ю.И. Об оптимальном по быстродействию последовательном обходе нелинейной управляемой системойтретьего порядка совокупности точек // Изв. Академии наук.Теория и системы управления. 2002. №3. 41-48.

8. Вахрушев В.А., Махова А.В., Ушаков В.Н. Один из алгоритмов решения задачи об обходе препятствий // Известия академии наук.Теория и системы управления, 2000, № 1.

9. Вахрушев В.А., Тарасьев А.М., Ушаков В.Н. Алгоритмы пересечения и объединения множеств на плоскости. // Управлениес гарантированным результатом. Свердловск: УНЦ АН СССР,1987. 101-109.150

10. Гамкрелидзе Р.В. Оптимальные по быстродействию процессы при ограниченных фазовых координатах // Докл. АН СССР. - Т. 125, №3.-С. 475-478.

11. Гамкрелидзе Р.В. Основы оптимального управления. - Тбилиси: Изд-во Тбил. ун-та, 1977.^ 12. Гусейнов Х.Г., Моисеев А.Н., Ушаков В.Н. Об аппроксимацииобластей достижимости управляемых систем // ПММ. 1998. Т. 65.№ 2 . 179-187.

12. Дубовицкий А.Я., Дубовицкий В.А. Критерий существования содержательного принципа максимума в задаче с фазовымиограничениями // Дифференц. уравнения. - 1995. - Т.31, № 10. - 1634-1640.

13. Дубовицкий А.Я., Дубовицкий В.А. Принцип максимума в регулярных задачах оптимального управления, у которых концыфазовой траектории лежат на границе фазового ограничения. //Автомат, и телемех. 1987. №12. 25 - 33 (РЖМат 1988, 4Б919).

14. Дубовицкий А.Я., Милютин А.А. Теория принципа максимума // Методы теории экстремальных задач в экономике. - М: Наука,1981.-С. 138-177.

15. Котелъникова А.Н. Одна задача о стабильном отслеживании и лидировании объекта с последействием. Препринт. Екатеринбург:УрО РАН, 2004. 43 с.151

16. Красовский Н.Н. Теория управления движением. М.: Наука, 1968. 476 с.

17. Красовский Н.Н. Управление динамической системой // М.: Наука, 1985, 520с.

18. Красовский Н.Н, Субботин А.И. Аппроксимация в дифференциальных играх // Прикл. математика и механика. 1973.Т. 37, вып. 2. 197-204.

19. Красовский Н.Н, Субботин А.И. Позиционные дифференциальные игры. М : Наука, 1974. 456с.

20. Куржанский А. Б. Управление и наблюдение в условиях неопределенности. М.: Наука, 1977, 392 стр.

21. Куржанский А.Б., Осипов Ю.С. К задаче управления с ограниченными фазовыми координатами // Прикл. математика имеханика. - 1968. - Т. 32, вып. 2. - 194-202.

22. Левитин КС, Милютин А.А., Осмоловский Н.П. Теория условий высших порядков в гладких задачах на экстремум с ограничениями// Теоретические и прикладные вопросы оптимального управления.- Иркутск: Наука, 1985. - 4-40.

23. Матвийчук А.Р. Задача об оптимальном по быстродействию управлении подвижным объектом на плоскости при наличиифазовых ограничений // Изв. РАН. ТиСУ. 2004. №1. 89-95

24. Матвийчук А.Р. Один алгоритм построения множества управляемости при наличии фазовых ограничений. // Вестникчелябинского университета. Серия 3. Математика, механика,152информатика. - Челябинск: Изд-во центра ЧелГУ. №2, Т.8, 2003. -С.153-166.

25. Митчел Дж., Маунт Д., Пападимитриу К. Дискретная геодезическая задача. // Кибернетический сборник. 1990. Вып. 27.

26. Незнахин А. А. О построении ядра выживаемости для обобщенной динамической системы. // Деп. в ВИНИТИ 06.12.00 № 3082-В00.22 с.

27. Незнахин А.А., Ушаков В.Н. Построение ядра выживаемости с ограниченным блужданием для дифференциального включения. //Деп. в ВИНИТИ 16.12.00 № 3083-В00 24 с.

28. Незнахин А.А., Ушаков В.Н. Сеточный метод приближенного построения ядра выживаемости для дифференциальноговключения // Журн. выч. мат. и мат. физ., 2001, 41,6, 895-908.

29. Никольский М.С. Об аппроксимации множества достижимости для дифференциального включения. // Вестн. Моск. ун-та, сер. 15 выч.мат. и киб., 1987, 4, 31-34.

30. Никольский М.С. Об одном методе аппроксимации множества достижимости для дифференциального включения. // Журн.вычисл. матем. и физики. 1998. Т. 28. № 8. 1252-1254.

31. Осипов Ю.С. Позиционное управление в параболических системах. //Прикл. матем. и мех., 1977, 41, 2, 195 - 2 0 1 .

32. Пацко В.С., Турова В.Л. Численное решение дифференциальных игр на плоскости. Препринт. Екатеринбург: УрО РАН, 1995. 77 с.

33. Половинкин Е.С. Стабильность терминального множества и оптимальность времени преследования в дифференциальных играх1984, т. 20, №3, с. 433 - 446.

34. Понтрягин Л.С. О линейных дифференциальных играх. I. Докл. АН СССР, 1967.Т.174,№6.

35. Понтрягин Л.С. Структура дифференциальных игр. Докл. АН СССР, 1969. Т. 184, №2.153

36. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. М.: Наука, 1969.

37. Субботин А.И., Ченцов А.Г. Оптимизация гарантии в задачах управления. М.: Наука, 1981. 287с.

38. Тимофеев А.В. Адаптивные робототехнические комплексы. Л.: Машиностроение, 1988.

39. Тонкое Е.Л. Динамические задачи выживания // Вести. Перм. гос. тех. ун-та. Функционально-дифференциальные уравнения. 1997.№4. 138-148.

40. Тонкое Е.Л. Равномерная достижимость и ляпуновская приводимость билинейной управляемой системы // ТрудыИнститута математики и механики. Т. 6, № 1. Екатеринбург: УрОРАН, 2000. 209-238.

41. Ухоботое В.И. Синтез гарантированного управления на основе аппроксимационной схемы // Труды Института математики имеханики. Т. 6, № 1. Екатеринбург: УрО РАН, 2000. 239-246.

42. Ушаков В.Н. К задаче построения стабильных мостов в дифференциальной игре сближения-уклонения // Изв. АН СССР.Техн. кибернетика 4, 1980. 32-45.

43. Филиппова Т.Ф. Задачи о выживаемости для дифференциальных включений.: Дис. д-ра физ.-мат. наук: 01.01.02. Екатеринбург, 1992.266 с. / Ин-т математики и механики УрО РАН.

44. Филиппова Т.Ф. Об одном достаточном условии оптимальности в задаче управления ансамблем траекторий. // Оценивание динамикиуправляемых движений. Свердловск, 1988, 111-118.

45. Филиппова Т.Ф. Управление в условиях неопределенности системой с негладкой правой частью. // Дифференц. уравнения,1983, 19, 10,1963 - 1699.

46. Хедли Дж. Нелинейное и динамическое программирование. М.: Мир, 1967.154

47. Хрипунов А.П., Ушаков В.Н. Построение интегральных воронок дифференциальных включений. // ЖВМ и МФ, 1994, Т. 34, № 7.

48. Ченцов А.А., Ченцов А.Г. Маршрутизация последовательного обхода системы подвижных множеств с использованиемдинамического программирования в условиях неточныхвычислений функции Беллмана // Проблемы управления иинформатики. - 1999 - №2. - 113-127.

49. Ченцов А.Г., Ченцов П.А. К вопросу о построении процедуры разбиения конечного множества на основе метода динамическогопрограммирования // А и Т. 2000. №4. 129-142.

50. Черноусъко Ф.Л. Оценивание фазового состояния динамических систем. Метод эллипсоидов. М.: Наука, 1988. 319 с.

51. Черноусько Ф.Л. Эллипсоидальная аппроксимация множеств достижимости линейной системы с неопределенной матрицей //Прикл. математика и механика. 1996. Т.60., Вып. 6. 940-950.

52. Черноусъко Ф.Л., Меликян А.А. Игровые задачи управления и поиска. М.: Наука, 1976.

53. АиЫп З.-Р. У1аЫШу ТЬеогу. Вп-кпаизег, 1992.

54. АиЫп Х-Р., СЬгке К МопоЮпе туапап!: зокиюпз 1о тс1изюпз III. Ьопскт Май. 8ос, 1977, 16. Р. 357-366.

55. КгуагЫтзкИ А.К, Озгроу Уи. 8. РозШопа1 Моёе1т§ ог" СОПИТ>1 т Бупаппса! 8у51ет8 // З^оспазйс Орйпихайоп. ВегНп е!с:8рпп§ег-Уег1а§, 1986. Р. 696-704. (Ьес1.1Чо1е5 т Соп1го1 апё 1пй)гт.5с1.: УО1. 81)

56. КиггкатЫ А.В., Уа1уг I. ЕШр5оЫа1 {есЬшдиез &г с!упат1с зуз^етз: соп1;го1 8уп1Ье515 &г ипсег1ат зуз^етз // Оупат1С апо! Соп1го1. 1992.№ 2 . Р. 87-111.

57. КиггкатЫ А.В., Усйуг I. ЕШрзоШа1 ^есЬтциез Гог ёупапис зуз^етз: Ше ргоЫетз ог*соп1;го1 зуп1;Ьез1з // Вупат1с апё Соп1го1. 1991. № 1. Р.357-378.155

58. Баранов В.Н. Задачи выживания для систем с последействием.: Дис. кандидата физ.-мат. наук: 01.01.02. Ижевск, 2003. 109 с. /Удмуртский государственный университет.156