Содержание к диссертации
Введение
Глава I. Задача поиска кратчайшего по времени маршрута 17
1. Основные определения 17
2. Постановка задачи 25
3. Сведение задачи о движении многоугольника Т к задаче о движении ""центра" 26
4. Построение "запретных зон"
5. Построение кратчайшей по времени траектории для "центра" 0 36
6. Примеры 44
Глава II. Построение приближенных решений в задаче об оптимальном по быстродействию управлении 49
1. Основные определения 49
2. Множество достижимости ДВ (1.2) на [tQ,3] 51
3. Задача о приведении движения управляемой системы (1.1) на множество Xj за минимальное время 59
4. Второй способ построения разрешающего управления в задаче 3.2 78
Глава III. Алгоритмы вычисления оптимального по быстродействию управления подвижным объектом, динамика которого описывается уравнением вида х = и 83
1. Постановка задачи 83
2. Сведение задачи о движении многоугольника Т к задаче о движении "центра" 0 85
3. Построение приближений окрестностей "запретных зон" 87
4. Построение множеств достижимости 99
5. Построение допустимого управления поМД 103
6. Некоторые вопросы, связанные с окрестностями "запретных зон" .. 107
7. Примеры 110
Глава IV. Алгоритмы вычисления оптимального по быстродействию управления подвижным объектом с нелинейной динамикой вида 117
1. Постановка задачи 117
2. Предварительные построения (переход к задаче о движении "центра" О) 119
3. Построение множеств достижимости 123
4. Построение допустимого управления по МД 129
5. Способы уточнения управления и* (О 132
6. Сравнение способов построения управления 134
7. Множества ограниченного управления для нелинейной нестационарной системы 137
8. Примеры 140
Список литературы 150
Приложение 157
- Сведение задачи о движении многоугольника Т к задаче о движении ""центра"
- Задача о приведении движения управляемой системы (1.1) на множество Xj за минимальное время
- Некоторые вопросы, связанные с окрестностями "запретных зон"
- Множества ограниченного управления для нелинейной нестационарной системы
Введение к работе
Предыстория и актуальность темы. Диссертация посвящена
исследованию задач об управлении протяженными объектами на
плоскости, динамика которых стеснена фазовыми ограничениями.
Рассматриваемые в диссертации задачи относятся к теории оптимального
управления. Современный облик згой теории сформировался в
значительной степени под влиянием работ отечественных и зарубежных
математиков Н.Н. Красовского, Л.С. Понтрягина и их учеников
А.Б. Куржанского, Ю.С. Осипова, А.И. Субботина, Е.Ф. Мищенко,
Р.В. Гамкрелидзе, В.Г. Болтянского, а также зарубежных ученых
Р. Калмана (R. Kalman), Р. Беллмана (R. Bellman), Р. Айзекса (R. Isaacs),
У. Флеминга (W. Fleming). Большой вклад в развитие теории оптимального
управления внесли Р.Ф. Габасов, Ф.М. Кириллова, Б.Н. Пшеничный,
Ф.Л Черноусько и их научные школы. Существенный прогресс в
становлении и развитии теории оптимального управления связан также с
именами Э.Г. Альбрехта, Б.И. Ананьева, А.В. Арутюнова, В.Д. Батухтина,
В.И. Благодатских, Н.Л. Григоренко, М.И. Гусева, А.Я. Дубовицкого,
В.И. Жуковского, С.Г. Завалищина, М.И. Зеликина, А.Ф. Клейменова, А.В.
Кряжимского, В.И. Максимова, А.А. Меликяна, А.А. Милютина,
М.С. Никольского, B.C. Пацко, Н.Н. Петрова, Л.А. Петросяна,
А.Н. Сесекина, Н.Н. Субботиной, В.М. Тихомирова, Е.Л. Тонкова,
В.Е. Третьякова, В.И. У хоботова, Т.Ф. Филипповой, А.Г. Ченцова,
А.А. Чикрия, В.А. Якубовича, J.-P. Aubin, М. Bardi, Т. Basar, P. Bernhard,
А.Е. Bryson, R.J. Elliot, A. Friedman, Но Yu-Chi,
N.J. Kalton, G.J. Olsder, E. Roxin, P. Varaiya, J. Warga и многих других ученых.
Актуальность изучения управляемых систем, стесненных фазовыми ограничениями, обусловлена с одной стороны многочисленными задачами из различных областей механики, экономики, экологии и биологии, с другой стороны - внутренними потребностями, возникающими в математической теории управления динамическими системами.
Теория динамических систем, стесненных фазовыми ограничениями, сформировалась под влиянием работ J .-P. Aubin1, А.Я. Дубовицкого2, Р.В. Гамкрелидзе3, А.Б. Куржанского4'5, А.А. Милютина6 и других авторов.
' AubmJ-P Viability Theory Birkhauser, 1992
2 Дубиаинкий Л Я, Лубоаицкий В.А Критерий существования содержательного принципа максимума в
задаче с фазовыми ограничениями // Дифференц уравнения -1995 ~ТЭ1,№10 -С 1634-1640
3 Гамкрелидзе Г В Оптимальные по быстродействию процессы при ограниченных фазовых
координатах // Докл АН СССР - Т. 125, № 3. С 475-478
4 Куржапский АВ, Осипов ЮС К задаче управления! I шраилчишммн фадаимши^координатами //
Прикл математика и механика - 1968 -Т 32, вып 2-0 ІДОЗДНАЦИОНАЛЬІН ' і
I -
" і i«» .'Л
Существенный вклад а развитие этой теории внесли СМ. Асеев, А.В. Арутюнов, В.И. Благодатских7, М. Куинкампуа, П. Сент-Пьер8, Т.Ф. Филиппова9.
Теории динамических систем, стесненных фазовыми ограничениями, посвящены также исследования В.Н.Баранова10, Е.Л. Тонкова", Е.К. Костоусовой12, В.Н. Ушакова и А.А. Незнахина13.
К традиционным задачам управления с фазовыми ограничениями близки задачи последовательного обхода множеств и более общие задачи последовательного обхода сечений многозначных отображений, которые подробно изучены в работах А.Г. Ченцова, А.А. Ченцова14 и Ю.И. Бердышева15.
В настоящее время в Институте математики и механики УрО РАН ведется разработка алгоритмов решения задач управления с фазовыми ограничениями, в том числе, разработка алгоритмов приближенного построения множеств достижимости при наличии фазовых ограничений. Так в отделе оптимального управления Е.К. Костоусовой12 разработаны методы построения двухсторонних оценок множеств достижимости линейных динамических систем (как с дискретным, так и с непрерывным временем) при наличии фазовых ограничений в дискретные моменты времени. Алгоритмы, разработанные для таких систем, могут быть применены для аппроксимации информационных областей, возникающих
5 Куржаиский А И, Филиппова ТФ Дифференциальные включения с фазовыми ограничениями Метод
возмущении // Оптим упр и диффереиц уравнения Сб ст К 70-летию со дня рождения академика Є Ф
Мищенко М. Наука Физ матлит.. 1995 С. 304-315 Тр МИР АН, т 211.
6 Левитин Е С, Милютин А А , Осмоловский И П. Теория условий высших порядков в гладких задачах на
экстремум с ограничениями // Теоретические и прикладные вопросы оптимального управлепия -
Иркутск: Наука, 1985. -С 4-40.
7 Арутюнов А В., Асеев СМ, Благодатских В И. Необходимые условия первого порядка в задаче
оптимального управления дифференциальным включением с фазовыми ограничениями // Мат сб., 1993
Т. 184. №6, С. 3-32.
I Saint-Pierre Р, Qulncampo/x М An algorithm for viability Kernels in Holdenan case* approximation by
discrete dynamical systems IIJ Math SystemEstim Control 1995 V 5 J* 1 P 115-118
9 Филиппова T Ф Задачи о выживаемости для дифференциальных включений Дис д-ра физ -мат. наук
01 01.02. Екатеринбург, 1992 266 с / Ин-т математики и механики УрО РАН
10 Баранов В Н Задачи выживания для систем с последействием - Дис кандидата физ -мат наук
0101.02 Ижевск, 2003 109 с / Удмуртский государственный университет
" Тонкое Е.Л Динамические задачи выживания // Вести Перм гос тех ун-та Функционально-дифференциальные уравнения 1997 №4 С. 138-148
12 Костоусова Е К О внутренних полиэдральных оценках множеств достижимости линейных систем с фазовыми ограничениями // Алгоритмы и программные средства параллельных вычислений Екатеринбург: УрО РАН, 2001 Вып 5 С. 167-187.
" Незнахин А А, Ушаков В И Сеточный метод приближенного построения ядра выживаемости для дифференциального включения//Журн выч мат имат физ, 2001,41,6, С.895-908 м Чепцов А А, Чепцов А.Г Маршрутизация последовательного обхода системы подвижных множеств с использованием динамического программирования в условиях неточных вычислений функіцчи Беллмана//Проблемы управления и информатики 1999 №2 С 113-127
II Еердышев Ю И Об оптимальном по быстродействию последовательном обходе нелинейной
управляемой системой третьего порядка совокупности точек // Изв Академии наук Теория и системы
управления 2002 №3 С 41-48.
в задачах гарантированного оценивания в системах, где производятся неточные измерения в дискретные моменты времени.
В последнее десятилетие повышенный интерес к задачам управления с фазовыми ограничениями проявляется в отделе динамических систем Института математики и механики УрО РАН в связи с так называемой задачей обвода препятствий подвижным протяженным объектом. В этой задаче функционалом, подлежащим оптимизации, является время попадания подвижного объекта на терминальное множество16. Особенность этой задачи состоит в том, что управляемый объект, движущийся при наличии фазовых ограничений, является протяженным в фазовом пространстве. Эта протяженность заметно усложняет задачу оптимального по быстродействию управления. Другой важной задачей, стимулирующей повышенный интерес в отделе динамических систем к задаче управления с фазовыми ограничениями, явилась задача построения выживающих траекторий и ядер выживаемости15'8. Эти две задачи (задача обвода препятствий и задача выживаемости) тесно связаны с задачей построения и оценки множеств достижимости управляемых систем и дифференциальных включений1718. Имеющиеся в настоящее время процедуры построения множеств достижимости не предполагают, как правило, что в процессе их вычисления одновременно (или, более точно, -параллельно во времени) вычисляются и управления, приводящие в ту или иную заранее выбранную точку множества достижимости. В связи с этим возникает еще одна важная задача - задача о построении управления (после того, как множество достижимости построено), приводящего в заданную точку множества достижимости. Разумеется, что точно эту задачу решить невозможно. В диссертационной работе предлагается метод построения управления, решающего эту задачу приближенно. В основе
метода лежат конструкции поводыря .
Отметим, однако, что в диссертации идеология построения управления, прицеливающего на поводыря, используется не во всех главах, а только в той, в которой рассматриваются нелинейные управляемые системы. Так первая глава, в которой динамика подвижного протяженного объекта описывается простыми движениями, посвящена методу решения задачи об оптимальном быстродействии, который основан на применении известного алгоритма Дейкстры.
16 Вахрушев В А, Махова А В, Ушаков В И Один из алгоритмов решения задачи об обходе препятствий // Известия академии наук Теория и системы управления, 2000, № 1 С 101-109 1 Черноусько ФЯ Оценивание фазового состояния динамических систем Метод эллипсоидов М Наука, 1988 319 с
18 Kurzhamki А В, Valyi I Ellipsoidal techniques for dynamic systems control synthesis for uncertain systems
//Dynamic and Control 1992 №2. P 87-111
19 Красовскші И И, Субботин А И Позиционные дифференциальные игры М Наука, 1974.456с
20 Красовскии Н И Управление динамической системой // М Наука, 1985, 520с
Цель работы. Основная цель диссертации - исследование линейных и нелинейных задач об управлении протяженными объектами на плоскости при наличии фазовых ограничений, а также разработка алгоритмов и программ построения разрешающих управлений в этих задачах. При этом разработанные алгоритмы должны базироваться на использовании операций с многоугольниками, чтобы стать альтернативой достаточно развитым к настоящему моменту сеточным методам решения подобных задач.
Методы исследования. Исследования проводятся в рамках подхода, разрабатываемого в научной школе Н.Н. Красовского по оптимальному управлению. В частности, в диссертации при решении задач управления для систем с нелинейной динамикой активно используются конструкции
поводыря и экстремального прицеливания на движение поводыря ' Разработка алгоритмов и программ ведется только для задач управления на плоскости. Алгоритмы базируются на дискретном представлении времени, на представлении множеств из R2 в виде многоугольников на плоскости и применении различного рода операций к этим многоугольникам (например, операции объединения, пересечения многоугольников, обвод одного многоугольника другим и так далее).
Научная новизна. Данная работа является продолжением исследований тех задач управления с фазовыми ограничениями, которые проводились и проводятся в настоящий момент в Институте математики и механики УрО РАН и, в том числе, в отделе динамических систем Института. Эта диссертация продолжает исследования по построению выживающих траекторий и ядер выживаемости5-8,13, а также исследования задач обвода препятствий16.
Научная новизна диссертации состоит в том, что для решения упомянутых задач для нелинейных нестационарных управляемых систем используется трехэтапный метод построения решения: на 1-м этапе вычисляется последовательность множеств достижимости (в прямом времени) до момента встречи очередного множества достижимости с терминальным множеством, при этом выделяется точка из пересечения этих множеств; на 2-м этапе, отправляясь от выделенной точки, протягивается (в обратном времени) через множества достижимости движение поводыря, которое в результате приходит в некоторую точку начального множества; на 3-м этапе строится (в прямом времени) управление, и соответственно движение управляемой системы, приходящее в заданную окрестность терминального множества. Здесь можно отметить, что в диссертационной работе, в отличие от широко распространенных сеточных методов, все множества представлены в виде
многоугольников, что влечет применение более сложных процедур построения множеств достижимости, нежели в случае сеточных методов.
Элемент новизны присутствует также в том, что в задачах обвода препятствий подвижным объектом, динамика которого нестационарна, сами препятствия движутся по определенным известным нам программным законам. В свою очередь, в работах21,22 рассматриваются только стационарные системы, что позволяет в ряде случаев существенно упростить алгоритм, а, значит, и повысить скорость расчета траекторий, но при этом область применения подобных алгоритмов сужается.
Среди таких алгоритмов можно выделить так называемый быстро шагающий алгоритм (fast marching method - FMA)22, который применяется не только в задачах оптимального управления, но и в таких областях, как обработка изображений и распознавание образов. В частности, этот алгоритм используется для приближенного решения задачи поиска оптимальной по времени траектории для стационарной системы.
Особенностью FMA22 и алгоритмов, описанных в работе21, является то, что они применяются к объектам, способным менять свою ориентацию.
Теоретическая и практическая ценность работы. Представленная работа имеет теоретическую ценность: в ней для задач управления с фазовыми ограничениями представлен метод приближенного построения множеств достижимости и обоснована его сходимость. Предложен метод построения различных управлений в задаче сближения с терминальным множеством. Этот метод базируется на использовании конструкций поводыря. Также предложен вариант экстремального прицеливания на движение поводыря, обладающий определенными достоинствами.
Практическая ценность работы состоит в том, что для решения задачи управления при наличии фазовых ограничений предложен полезный алгоритм, основанный на операциях над многоугольниками. Использование этого алгоритма для поиска разрешающего управления во многих случаях дает выигрыш во времени счета на ЭВМ и в используемом объеме памяти по сравнению с сеточными методами.
Структура, объем и краткое содержание. Диссертационная работа состоит из настоящего введения, списка сокращений и обозначений, четырех глав, объединяющих 24 параграфа, приложения и списка литературы. Общий объем диссертации составляет 171 страницу, библиографический список включает 65 наименований, иллюстративный материал насчитывает 78 рисунков.
21 Laumond J -Г Robot motion planning and control - London Springer - Verlag London Limited, 1998 -
343 p.
22 Sethtan J A Level set methods and fast marching methods -Cambridge Cambridge university press, 1999 -
378 p.
Апробация работы. Основные результаты диссертации обсуждались и докладывались на семинарах на факультете вычислительной математики и кибернетики МГУ, на математических факультетах Удмуртского государственного университета и Челябинского государственного университета. Кроме того, научные результаты докладывались на 33, 34 и 35-й региональных молодежных конференциях "Проблемы теоретической и прикладной математики" (Екатеринбург, 2002, 2003, 2004 гг.), а также на XXIV Российской школе по проблемам науки и технологий, посвященной 80-летию со дня рождения академика В.П.Макеева (г. Миасс, 2004 г.). Кроме того, результаты были представлены в виде доклада на Международном семинаре "Теория управления и теория обобщенных решений уравнений Гамильтона-Якоби" посвященного 60-летию академика А.И. Субботина (Екатеринбург, 2005).
Все основные результаты диссертации являются новыми и принадлежат автору. Результаты, полученные совместно с руководителем, вошли в главу II. А именно, В.Н. Ушаковым была поставлена задача и намечена схема решения этой задачи. Все остальные результаты получены автором самостоятельно.
Публикации. Основные результаты диссертации достаточно полно отражены в работах диссертанта [1-8].
Сведение задачи о движении многоугольника Т к задаче о движении ""центра"
Диссертация посвящена исследованию задач об управлении протяженными объектами на плоскости, динамика которых стеснена фазовыми ограничениями. Рассматриваемые в диссертации задачи относятся к теории оптимального управления. Современный облик этой теории сформировался в значительной степени под влиянием работ отечественных и зарубежных математиков Н.Н. Красовского, Л.С. Понтрягина и их учеников А.Б. Куржанского, Ю.С. Осипова, А.И. Субботина, Е.Ф. Мищенко, Р.В. Гамкрелидзе, В.Г. Болтянского, а также зарубежных ученых Р. Калмана, Р. Беллмана, Р. Айзекса, У. Флеминга. Большой вклад в развитие теории оптимального управления внесли Р.Ф. Габасов, Ф.М. Кириллова, Б.Н. Пшеничный, Ф.Л Черноусько и их научные школы. Существенный прогресс в становлении и развитии теории оптимального управления связан также с именами Э.Г. Альбрехта, А.В. Арутюнова, В.Д. Батухтина, В.И. Благодатских, Н.Л. Григоренко, М.И. Гусева, А.Я. Дубовицкого, С.Г. Завалищина, М.И. Зеликина, А.Ф. Клейменова, А.В. Кряжимского, В.И. Максимова, А.А. Меликяна, А.А. Милютина, М.С. Никольского, B.C. Пацко, Н.Н. Петрова, Л.А. Петросяна, Н.Н. Субботиной, В.М. Тихомирова, Е.Л. Тонкова, В.Е. Третьякова, В.И. Ухоботова, Т.Ф. Филипповой, А.Г. Ченцова, А.А. Чикрия, В.А. Якубовича, J.-P. Aubin, М. Bardi, Т. Basar, P. Bernhard, А.Е. Bryson, R.J. Elliot, A. Friedman, Но Yu-Chi, N.J. Kalton, G.J. Olsder, E. Roxin, P. Varaiya, J. Warga и многих других ученых.
Актуальность изучения управляемых систем, стесненных фазовыми ограничениями, обусловлена с одной стороны многочисленными задачами из различных областей механики, экономики, экологии и биологии, с другой стороны - внутренними потребностями, возникающими в математической теории управления динамическими системами [1,19-21,38,39]. Теория динамических систем, стесненных фазовыми ограничениями, сформировалась под влиянием работ J.-P. Aubin, А.Б. Куржанского, А.Я. Дубовицкого, А.А. Милютина, Р.В. Гамкрелидзе [10,11,13-15,23-26,57,58] и других авторов. Существенный вклад а развитие этой теории внесли СМ. Асеев, А.В. Арутюнов, В.И. Благодатских, М. Куинкампуа, П. Сент-Пьер, Т.Ф. Филиппова, X. Франковска [3-5,63,47-48]. Теории динамических систем, стесненных фазовыми ограничениями, посвящены также работы В.Н. Баранова [65], Е.Л. Тонкова [43,44], В.Н. Ушакова и А.А. Незнахина [12,29-31,60].
К традиционным задачам управления с фазовыми ограничениями близки задачи последовательного обхода множеств и более общие задачи последовательного обхода сечений многозначных отображений, которые подробно изучены в работах А.Г. Ченцова, А.А. Ченцова и Ю.И. Бердышева [7,52,53].
В настоящее время ведется активная разработка алгоритмов решения задач с фазовыми ограничениями, в том числе разработка алгоритмов приближенного построения множеств достижимости при наличии фазовых ограничений. Так в Отделе оптимального управления Института математики и механики УрО РАН Е.К. Костоусовой (см. [16,17]) разработаны методы построения двухсторонних оценок множеств достижимости линейных динамических систем (как с дискретным, так и с непрерывным временем) при наличии фазовых ограничений в дискретные моменты времени. Алгоритмы, разработанные для таких систем, могут быть применены для аппроксимации информационных областей, возникающих в задачах гарантированного оценивания в системах, где производятся неточные измерения в дискретные моменты времени.
В последнее десятилетие повышенный интерес к задачам управления с фазовыми ограничениями проявляется в Отделе динамических систем Института математики и механики УрО РАН в связи с так называемой задачей обвода препятствий подвижным протяженным объектом. В этой задаче функционалом, подлежащим оптимизации, является время попадания подвижного объекта на терминальное множество [8,30-32]. Особенность этой задачи состоит в том, что управляемый объект, движущийся при наличии фазовых ограничений, является протяженным в фазовом пространстве. Эта протяженность существенно усложняет задачу оптимального по быстродействию управления. Другой важной задачей, стимулирующей повышенный интерес в Отделе динамических систем к задаче управления с фазовыми ограничениями, явилась задача построения выживающих траекторий и ядер выживаемости [25,47]. Эти две задачи (задача обвода препятствий и задача выживаемости) тесно связаны с задачей построения и оценки множеств достижимости управляемых систем и дифференциальных включений [54-56,60,61]. Имеющиеся в настоящее время процедуры построения множеств достижимости не предполагают, как правило, что в процессе их вычисления одновременно (или, более точно, - параллельно во времени) вычисляются и управления, приводящие в ту или иную заранее выбранную точку множества достижимости, В связи с этим возникает еще одна важная задача - задача о построении управления (после того, как множество достижимости построено), приводящего в заданную точку множества достижимости. Разумеется, что точно эту задачу решить невозможно. В диссертационной работе предлагается метод построения управления, решающего эту задачу приближенно. В основе метода лежат конструкции поводыря [20-21].
Отметим, однако, что в диссертации идеология построения управления, прицеливающего на поводыря, используется не во всех главах, а только в той, в которой рассматриваются нелинейные управляемые системы. Так первая глава, в которой динамика подвижного протяженного объекта описывается простыми движениями, посвящена методу решения задачи об оптимальном быстродействии, который основан на применении известного алгоритма Дейкстры.
Цель работы. Основная цель диссертации — исследование линейных и нелинейных задач об управлении протяженными объектами на плоскости при наличии фазовых ограничений, а также разработка алгоритмов и программ построения разрешающих управлений в этих задачах. При этом разработанные алгоритмы должны базироваться на использовании операций с многоугольниками, чтобы стать альтернативой достаточно развитым к настоящему моменту сеточным методам решения подобных задач.
Методы исследования. Исследования проводятся в рамках подхода, разрабатываемого в научной школе Н.Н. Красовского по оптимальному управлению. В частности, в диссертации при решении задач управления для систем с нелинейной динамикой активно используются конструкции поводыря и экстремального прицеливания на движение поводыря [20-21]. Разработка алгоритмов и программ ведется только для задач управления на плоскости. Алгоритмы базируются на дискретном представлении времени, на представлении множеств из R2 в виде многоугольников на плоскости и применении различного рода операций к этим многоугольникам (например, операции объединения, пересечения многоугольников, обвод одного многоугольника другим и так далее).
Задача о приведении движения управляемой системы (1.1) на множество Xj за минимальное время
Одним из ключевых понятий, используемых в данной диссертационной работе, является понятие многоугольника на плоскости.
Определение 1.1. Многоугольником на плоскости будем называть ограниченное связное множество на плоскости, граница которого состоит из конечного числа отрезков и является набором замкнутых ломаных линий (рис. 1.1). Тогда дополнение до многоугольника будет состоять из нескольких связных множеств, которые назовем компонентами дополнения.
Односвязные компоненты дополнения, являющиеся ограниченными множествами, назовем дырами многоугольника, а объединение ломаных линий, являющихся их границами, - внутренней границей многоугольника. При этом условимся, что нумерация вершин в таких ломаных будет осуществляться по часовой стрелке. Другими словами, при движении от вершины с меньшим номером к вершине с большим номером (кроме последней и первой вершин) дыра будет оставаться справа. Такую ориентацию будем считать отрицательной ориентацией. Среди компонентов дополнения есть неограниченное множество. Границу такого множества будем называть внешней границей многоугольника. Будем считать, что вершины внешней границы многоугольника пронумерованы против часовой стрелки (при обходе многоугольник остается слева). Такую ориентацию назовем положительной ориентацией.
Задав ориентацию границы, мы переходим от ребер границы (фактически отрезков) к направленным отрезкам, которые будем называть направленными ребрами.
В дальнейшем дырой будем называть не только ограниченные односвязные компоненты дополнения до некоторого многоугольника, но и односвязные области на плоскости, границы которых являются замкнутыми ломаными с отрицательной ориентацией.
Кроме того, будем различать многоугольники как открытые множества и многоугольники, как замкнутые множества. По смыслу задачи обвода препятствий, которая формулируется ниже, нам удобно (и мы будем) считать, что многоугольники - открытые множества (если из контекста не следует обратное), т.е. им не принадлежат их границы. Такие многоугольники будем называть открытыми многоугольниками или просто многоугольниками. Соответственно дыры открытых многоугольников, а также дыры, не являющиеся дополнением к какому-либо многоугольнику, будем считать замкнутыми множествами (если не оговорено отдельно или из контекста не следует обратное). Такие дыры будем называть замкнутыми дырами или просто дырами.
Если необходимо рассмотреть многоугольник как замкнутое множество, то такой многоугольник будем называть замкнутым многоугольником. Соответственно, дыры таких многоугольников будут открытыми множествами. Дыры, которым не принадлежит граница, будем называть открытыми дырами.
Замечание 1.1. Поскольку любой многоугольник определяется своими внешней и внутренней границами, представляющими собой набор замкнутых ломаных, то для задания многоугольника достаточно указать замкнутую ломаную (ЗЛ) с положительной ориентацией (в качестве внешней границы) и набор замкнутых ломаных с отрицательной ориентацией (в качестве внутренней границы), если в нем имеются дыры,
В связи с этим, ЗЛ с положительной ориентацией будем, при необходимости, рассматривать как многоугольник без дыр. Многоугольник без дыр будем называть простым многоугольником. В свою очередь, ЗЛ с отрицательной ориентацией будем, при необходимости, рассматривать как дыру.
Некоторые вопросы, связанные с окрестностями "запретных зон"
Идея построения "запретных зон" состоит в следующем. "Запретные зоны" Wn / = 1, 2, ...,iVr, получаются путем обвода подвижным многоугольником Y каждого из Yt с внешней стороны, а "запретная зона" (33) для арены путем обвода многоугольником Т арены G изнутри. Траектория, которую будет описывать при таком обводе "центр" О, окажется границей соответствующей "запретной зоны", причем эта граница будет являться замкнутой ломаной, из которой затем будут выделены многоугольники и дыры.
В итоге может оказаться, что для арены "запретной зоной" будет плоскость R2 с множеством замкнутых дыр Gt, і = 1, 2, ...,NC, где NG 1, а в "запретных зонах" Fn i = l, 2, ..., JVr, представляющих собой открытые многоугольники, могут получиться дыры. Дыры обладают следующими свойствами: 1) если в любую точку дыры "запретной зоны" Ч/і многоугольника препятствия Yi поместить "центр" О подвижного многоугольника Т , то многоугольник Т не будет пересекаться с препятствием Tf; 2) не существует пути, по которому можно перевести подвижный многоугольник своим "центром" в какую-либо точку дыры из любой точки, не принадлежащей дыре. Рассмотрим процедуру построения "запретной зоны" Fi для некоторого многоугольника-препятствия Тп 1 = 1, 2, ...,iVr. Будем считать, что границей Y{ является замкнутая ломаная {А[, Л , ..., А т }. В работе [8] "запретная зона" Ч/і строились путем обвода Yt с внешней стороны всеми ребрами AjAj+l, j = U 2, ...,Аґ , в результате чего получалось N многоугольников. Затем каждый из полученных многоугольников смещался в зависимости от того, где располагалось ребро АЛм относительно "центра" О. После этого все N многоугольников объединялись друг с другом методом, описанным в [9] и в результате получался многоугольник У(.. При таком подходе к построению "запретных зон" основное время тратится на процедуру объединения N многоугольников. Это хороший метод, но в случае, когда число вершин подвижного многоугольника мало, т.е. N є (3,4,5}, а количество вершин многоугольников-препятствий и арены достаточно большое, то имеет смысл воспользоваться алгоритмом, изложенным ниже. Отметим, что при малом N алгоритм, приведенный ниже, позволяет тратить меньше времени на построение для каждого Уі его "запретной зоны" Fn поскольку для последующего объединения получится уже не более N -2 многоугольников, что как минимум на 2 многоугольника меньше, чем в [8]. В предлагаемом в данной диссертации методе предварительно проводится триангуляция многоугольника У таким образом, чтобы количество треугольников было минимально. После триангуляции д получится множество треугольников Tj , У = 1, 2, ...,Л/д, где У = \\Yf, и ІУЛ ЛГ - 2. Затем препятствие Tf обводится всеми полученными треугольниками Yf, j = 1, ...,ЛГД. В результате обвода каждого многоугольника Yi треугольниками У , / = 1, ...,ЛГЛ, получатся замкнутые ломаные, возможно с самопересечениями. Из этих ломаных для каждого препятствия У; выделяются многоугольники ї /, 7 = 1» —)А д) в которых могут быть дыры. Объединение на последнем этапе многоугольников /, 7 = 1, ...,ІУд, друге другом дает "запретную зону" Wt для Уг
Рассмотрим подробно обвод препятствия 7 , треугольником Уу, чья граница задана в виде простого массива вершин (С/, С{, С/}. Для этого в треугольнике yf выбирается его "центр" Oj - произвольная точка, принадлежащая треугольнику Yj и жестко связанная с ним.
При обводе треугольником Yj препятствия Yt "центр" Oj будет двигаться по траектории, являющейся замкнутой ломаной (пусть это //, состоящая из вершин {Efj,El2„...,Ef }). Поскольку границей Г, является некоторая ЗЛ {A{t А[, ..., А т}, то каждой вершине границы Yt соответствует от одной до трех вершин замкнутой ломаной // (рис. 4.1). Именно из-за возможности случая, когда на к-ои шаге алгоритма {к = \\т1) обвода треугольником препятствия Yt из одной вершины A k+l образуются три вершины ломаной // (рис. 4.1.в), следует рассматривать два соседних ребра А кА к+1 и А к+1А к+2, т.к. эта пара ребер однозначно определяет угол при вершине А ш.
Множества ограниченного управления для нелинейной нестационарной системы
Имеющиеся в настоящее время процедуры (приближенного) построения множеств достижимости управляемых систем не предполагают, что в ходе их реализации определяются вместе с точками множеств достижимости и управления, приводящие движение системы в эти точки. Нереально - строить одновременно с множествами достижимости управления, приводящие движение во все точки этих множеств. Процесс имеет смысл разделить: сначала нужно построить множество достижимости, а затем, - управление, приводящее в наперед заданную точку множества достижимости.
В связи с этим сформулируем задачу оптимального быстродействия, которая базируется на понятии множества достижимости. Пусть в фазовом пространстве Rm заданы ограниченные замкнутые множества Х0 и Xf такие, что Х0сФ(/0), a ([t0,3]xXf)r\X &0. При этом будем полагать, что существует такой момент є[ґ0,.9], что & — минимальный из моментов времени, удовлетворяющих Xj с\ X(t) 0. Задача 3.1. Требуется построить допустимое управление « (?) /є[ґ0,і9], приводящее фазовый вектор x[t] системы (1.1) из Х0 на Xf за минимальное время. Замечание 3.1, В связи с тем, что точно решить задачу для общего случая не представляется возможным, мы вынуждены отказаться от точной постановки задачи и формулировать задачу менее жестко, как задачу о приведении движения системы в некоторую заранее выбранную окрестность точки. При этом будем формировать управление так, чтобы движение системы находилось в течение всего промежутка времени в некоторой заранее заданной окрестности фазового ограничения. Уточним задачу об управлении. и в этом смысле ДВ (3.1) имеет более широкие возможности, чем система (1.1) и ДВ (1.2). В процессе решения задачи 3.2 мы сначала построим, пользуясь более широкими возможностями ДВ (3.1), ломаную Эйлера ДВ (3.1), проходящую через множества Х(п)(1 в моменты tt єГ{ и оканчивающуюся в момент tN в точке y\tN ]. Эта ломаная Эйлера призвана играть роль поводыря при построении в системе (1.1) управления u{t), te[t0 tN ], решающего задачу 3.2. Ломаную Эйлера y[t], t =[tQ,tN ], будем строить, отправляясь от точки y[tN ] и пятясь во времени к начальному моменту t0. Но при этом каждое звено ломаной y[t], отвечающее промежутку [/(,//+]], будет определено "в прямом времени", исходя из некоторой точки y[tf] множества Рл,(/(), tj rl. В общем случае такую ломаную мы можем построить только для ДВ (3.1), обладающего большими возможностями по сравнению с системой (1.1) и ДВ (1.2). Действительно, система {Xм (0: і,єГ } была определена "в прямом времени" при помощи ДВ (1.2). Для ДВ (1.2) мы не можем в принципе построить такую ломаную y[t], поскольку точка y[tN ]єї(" ( ) определена равенством где xltNf_l\ X{"\tNf_x)i /0(i,)eF((vl,%rl]) - некоторая неизвестная нам пара, которую, вообще говоря, мы не можем восстановить. момент tN при условии, что диаметр А(п) разбиения Гп достаточно мал. Укажем процедуру построения этой ломаной на промежутке [t0,tN ]. Глобально — это попятная процедура, локально на каждом промежутке ІЛ» /+і ] разбиения Г І - это процедура построения y[t] "в прямом времени". Начнем осуществлять эту процедуру, отправляясь от конечной точки MXv ] ломаной и соответственно последнего отрезка \tN _lttN ] разбиения г{. Напомним, что точка y\tN ] представима в виде (3.2), где которую, вообще говоря, мы не можем восстановить (т.е. точно вычислить) (см. рис. 3.1). Попытаемся найти в X{n)(tN _,) некоторую точку y\tN„,], из которой можно попасть в y[tN ] с помощью звена некоторой ломаной Эйлера ДВ (3.1).
