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

• Матвийчук, Александр Ростиславович
• кандидат физико-математических наук
• 2005

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

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

Введение.

Глава 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 рисунков. Нумерация параграфов осуществляется в пределах каждой главы. Нумерация формул двойная: в первой позиции указывается номер параграфа, в котором приведена формула, во второй - порядковый номер формулы в этом параграфе. Такая же нумерация принята для определений, теорем, замечаний, примеров и рисунков. Текст замечаний выделен курсивом. Основные сокращения и обозначения объяснены в списке сокращений и обозначений.

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

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