Эллипсоидальные методы для задач управления при неэллипсоидальных ограничениях тема диссертации и автореферата по ВАК РФ 01.01.02, кандидат физико-математических наук Кирилин, Михаил Николаевич

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

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

Введение

1 Достижимость управляемых систем без неопределенности

1.1 Введение

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

1.3 Внешние и внутренние эллипсоидные аппроксимации для суммы эллипсоидов

1.4 Внутренняя эллипсоидальная аппроксимация.

1.5 Тугая внутренняя аппроксимация и рекуррентные уравнения.

1.6 Внешняя е-окрестность множества достижимости.

1.7 Внешняя эллипсоидальная е-аппроксимация.

1.8 Тугая внешняя е-аппроксимация и рекуррентные уравнения.

2 Достижимость управляемых систем при неопределенности с управлением без обратной связи при конечном числе точек коррекций

2.1 Введение

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

2.3 Эллипсоидальная внешняя е-аппроксимация множества достижимости тина max min.

2.4 Множество достижимости типа шах min.

2.5 Множество достижимости типа min max с А; точками коррекции

2.6 Множество достижимости типа max min с А; точками коррекции

2.7 Алгоритм построения внешней аппроксимация для множества достижимости с к точками коррекции

2.8 Примеры

2.9 Алгоритм построения е-касательных эллипсоидов для произвольного выпуклого множества.

3 Достижимость управляемых систем при неопределенности и управлении с обратной связью

3.1 Введение

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

3.3 Эволюционное уравнение.

3.4 О непрерывности сверху и снизу решения эволюционного уравнения

3.5 /i-окрестность множества достижимости.

3.6 Внешние и внутренние эллипсоидальный аппроксимации для симметричного невырожденного многогранника.

3.7 Внешние и внутренние аппроксимации исходной задачи.

3.8 Внешние эллипсоидальные аппроксимации, находящиеся в /^-окрестности исходной задачи.

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

3.10 Примеры .£

Введение диссертации (часть автореферата) на тему «Эллипсоидальные методы для задач управления при неэллипсоидальных ограничениях»

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

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

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

Альтернированный интеграл, введенный J1. С. Понтрягиным в работах [35, 36], рассмотренный в обратном времени, позволяет свести вычисление множества достижимости к интегрированию многозначных отображений [37]. Этот подход был продолжен в работах Е. Ф. Мищенко, М. С. Никольского, Е. С. Половинкина, Н. X. Розова.

Эффективным методом исследования управляемых систем послужил функциональный подход, разработанный Н.Н. Красовским и его сотрудниками [8], [11] - [19], [17, 57]. В монографии [12] предложена формализация дифференциальных игр и подробно исследована их структура. В частности, указано, каким образом можно построить синтезирующую стратегию управления, удерживающую траекторию внутри "стабильного моста", несмотря на действия второго игрока, и обеспечивающую выполнение фазовых ограничений и попадание на целевое множество в заданный момент времени.

Одним из самый общих подходов в теории управления является метод Динамического программирования, предложенный Р. Беллманом [2] и примененный к игровым задачам Р. Айзексом [1]. Данный метод заключается в погружении исходной задачи в параметризированный класс задач. Оптимальные значения функционала, вычисленные для каждого значения параметров, образуют функцию цены. При этом набор параметров, образующих позицию системы, должен быть достаточным для того, чтобы можно было сформулировать принцип оптимальности, выраженный в полугрупповом свойстве для функции цены. Тогда последняя является решением дифференциального уравнения в частных производных, называемого уравнением Гамильтона-Якоби-Белл-мана-Айзекса ( HJBA), а множество достижимости находится, как множество линий данной функции. Так как функция цены может быть не всюду гладкой, вводят различные понятия обобщенного решения уравнения Беллмана, например, вязкостные решения [52] или минимаксные решения [43, 44]. Если взять в качестве критерия оптимальности квадрат расстояния между начальным множеством и концом траектории в начальный момент времени и проминимизировать критерий оптимальности по управлению для всех траекторий, попадающих в точку х в момент времени t, мы определим соответствующую функцию цены V(t,x), и тогда искомое множество достижимости — есть множество уровня данной функции {х : V(t,x) <= 0}.

Одним из возможных методов построения внутренних и внешних аппроксимаций для множеств достижимости и разрешимости и нахождения и построения синтезирующей стратегии является метод эллипсоидальных аппроксимаций. Впервые эллипсоидальная техника рассматривалась в работах А.Б. Куржанского [20], §12, Ф. Швеппе

G9], Ф. Черноусько [47]. В работах А.Б. Куржанского [59, 22, 23, 62, 61, 65, 63] построена конструктивная теория, объединяющая метод динамического программирования, альтернированный интеграл и функциональный подход, предложенный Н.Н. Красовским, направленная на решение задач до конца, то есть до конечного численного алгоритма. Для этого используется аппарат эллипсоидальных аппроксимаций [59, 62, 63, 64], позволяющий строить тугие внутренние и внешние эллипсоидальные аппроксимации для множеств достижимости и разрешимости. Объединение тугих внутренних и пересечение внешних эллипсоидных аппроксимаций позволяют построить множество достижимости и его границу. Каждая тугая внутренняя аппроксимация для множества разрешимости является слабоинвариантной системой множеств, поэтому она может быть использована в качестве синтезируещей стратегии управления. При этом синтез может быть представлен в явном виде, через параметры аппроксимации и задача синтеза сводится фактически к интегрированию системы обыкновенных дифференциальных уравнений для параметров эллипсоидальной аппроксимации.

Настоящая работа расширяет материал монографии [59]. В данной теории предполагается, что динамика системы описывается линейными дифференциальными уравнениями, а начальное состояние системы, управление и возмущения принадлежат геометрическим ( жестким или мгновенным ) ограничениям. Эти ограничения означают, что соответствующая величина в каждый момент времени должна находиться в заранее заданном непустом множестве. В качестве класса ограничивающих множеств взяты невырожденные эллипсоиды.

Однако на практике возникают ситуации, когда на управление и возмущение наложены вырожденные, негладкие, ограничения, например, в виде коробок или многогранников. Подобная постановка задачи была рассмотрена в работах Костоусовой Е.К. [54, 55] и для систем без неопределенности получении аппроксимации в виде параллелотопов.

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

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

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

Управляемая система задается дифференциальными уравнениями x(t) = A(t)x(t) + B(t)u, teT= [t0, ti]. (1)

Здесь x(t) £ P — положение системы, и € Rp — управление. Матрицы A(t), B(t) являются известными параметрами и обладают достаточной гладкостью.

Предполагается, что управление стеснено "жесткими" ограничениями, то есть принимает значение только из определенного множества: и € V{t). (2)

При этом используются два класса управлений: программные управления Uol (измеримые функции u(t)) и позиционные стратегии Ucl(многозначные отображения U(t, х) полунепрерывные сверху по фазовым переменным).

Предпологается, что множество V{t) является симметричным многогранником следующего вида т

7>(0 = М{р, Р) = {х:х = р + а е [-1,1]}. (3) i=l

Начальное состояние системы ограниченно включением x(to) € А4(х°,Х°).

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

В разделе 1.3 рассмотрены основные конструкции и положения из теории эллипсоидального исчисления (59].

Заключение диссертации по теме «Дифференциальные уравнения», Кирилин, Михаил Николаевич

Заключение

В заключение кратко сформулируем основные результаты работы:

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

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

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

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

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

2. Беллман Р. Динамическое программирование. М.: ИЛ, 1960.

3. Варайя П., Курмсанский А. Б. Достижимость при постояннодействующих возмущениях. ДАН, т.372, N1-6, 2000.

4. Гантмахер Ф.Р., Теория матриц, Москва, "Наука", 1988.

5. Кирилин М. Н. Эллипсоидальные аппроксимации в задачах достижимости с неэл-линсоидальными ограничениями. Внешние эллипсоиды. // Вестн. Моск. ун-та. Сер. 15. ВМК. 2004. N 4

6. Кирилин М. Н. Эллипсоидальные аппроксимации в задачах достижимости с неэллипсоидальными ограничениями. Внутренние эллипсоиды. // Известия РАН. Теория и системы управления. 2004. N 6.

7. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. Наука, Москва, 1981.

8. Красовский Н. Н. Об одной задаче преследования // ПММ. 1963. Т. 27. N 2. с. 244-254.

9. Красовский Н. Н. К задаче об успокоении линейной системы при минимальной интенсивности управления // ПММ. 1965. Т. 29. N 2. с. 218-225.

10. Красовский Н. Н. К задаче преследования в случае линейных однотипных объектов // ПММ. 1966. Т. 30. N 2. с. 209-225.

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

12. Красовский Н.Н., Игровая задача о встрече движения. Наука, Москва, 1970.

13. Красовский Н. Н. Минимаксное поглощение в игре сближения // ПММ. 1971. Т. 35. N 6. с. 945-951.

14. Красовский Н. Н. Дифференциальная игра сближения-уклонения I // Известия АН СССР. Техническая кибернетика. 1973. N 2. с. 3-18.

15. Красовский Н. Н. Дифференциальная игра сближения-уклонения II // Известия АН СССР. Техническая кибернетика. 1973. N 3. с. 22-41.

16. Красовский Н. Н. Дифференциальные игры. Аппроксимационные и формальные модели // Математический сборник. 1978. Т. 107 (149). N 4 (12). с. 541-571.

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

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

19. Красовский Н. Н., Субботин А. И., Ушаков В. Н. Минимаксная дифференциальная игра // Доклады АН СССР. 1972. Т. 206. N 2. с. 277-280.

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

21. Куржанский А. Б. Дифференциальные игры сближения при ограниченных фазовых координатах // Доклады АН СССР. 1970. Т. 192. N 3. с. 491-494.

22. Куржанский А. Б. Альтернированный интеграл Понтрягина в теории синтеза управлений // Труды МИАН. 1999. Т. 224. с. 234-248.

23. Куржанский А. Б., Мельников Н. Б. О задаче синтеза управлений: альтернированный интеграл Понтрягина и уравнение Гамильтона-Якоби // Математический сборник. 2000. Т. 191. N 6. с. 69-100.

24. Куржанский А. Б., Никонов О. И. К задаче синтеза стратегий управления. Эволюционные уравнения и многозначное интегрирование // Доклады АН СССР. 1990. Т. 311. N 4. с. 788-793.

25. Куржанский А. Б., Никонов О. И. Эволюционные уравнения для пучков траекторий синтезированных систем управления // Доклады РАН. 1993. Т. 333. N 4. с. 578-581.

26. Куржанский А. Б., Филиппова Т. Ф. Об описании множества выживающих траекторий дифференциального включения // Доклады АН СССР. 1986. Т. 289. N 1. с. 38-41.

27. Никольский М. С. Об альтернированном интеграле JI. С. Понтрягина // Математический сборник. 1981. Т. 126 (158). N 1 (9). с. 136-144.

28. Никольский М. С. О нижнем альтернированном интеграле Понтрягина в линейных дифференциальных играх преследования // Математический сборник. 1985. Т. 128 (170). N 1 (9). с. 35-49.

29. Половинкин Е. С. Неавтономные дифференциальные игры // Дифференциальные уравнения. 1979. Т. 15. N 6. с. 1007-1017.

30. Половинкин Е. С., Иванов Г. Е., Балашов М. В., Константинов Р. В., Хорее А. В. Об одном алгоритме численного решения линейных дифференциальных игр // Математический сборник. 2001. Т. 192. N 10. с. 95-122.

31. Пономарев А. П. Оценка погрешности численного метода построения альтернированного интеграла Понтрягина // Вестник МГУ. Сер. вычисл. матем. и киберн. 1978. Т. 4. с. 37-43.

32. Пономарев А. П., Розов Н. X. Устойчивость и сходимость альтернированных сумм Понтрягина // Вестник МГУ. Сер. вычисл. матем. и киберн. 1978. Т. 1. с. 82-90.

33. Пономарев А. П., Розов Н. X. О дифференцируемое™ опорной функции альтернированного интеграла // Математические заметки. 1981. Т. 30. N 6. с. 865-870.

34. Понтрягин JI. С. Обыкновенные дифференциальные уравнения. М.: Наука, 5-е изд., 1982.

35. Понтрягин Л. С. О линейных дифференциальных играх I // Доклады АН СССР. 1967. Т. 174. N 6. с. 1278-1280.

36. Понтрягин Л. С. О линейных дифференциальных играх II // Доклады АН СССР. 1967. Т. 175. N 4. с. 910-912.

37. Понтрягин Л. С. Линейные дифференциальные игры преследования // Математический сборник. 1980. Т. 112 (154). N 3 (7). с. 307-330.

38. Понтрягин JI.C., Принцип максимума в оптимальном управлении, Москва, "Наука", 1989.

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

40. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973.

41. Субботин А. И. К задаче об игровой встрече движений // ПММ. 1967. Т. 31. N 5. с. 834-840.

42. Субботин А. И. Экстремальные стратегии в дифференциальных играх с полной памятью // Доклады АН СССР. 1972. Т. 206. N 3. с. 552-555.

43. Субботин А. И. Минимаксные неравенства и уравнения Гамильтона-Якоби. М.: Наука, 1991.

44. Субботин А. И. Обобщенные решения уравнений в частных производных первого порядка. Перспективы динамической оптимизации. М., И.: Институт компьютерных исследований, 2003.

45. Тихонов А. Н., Васильева А. В., Свешников А. Г. Дифференциальные уравнения. М.: Наука, 1980.

46. Филиппов А. Ф. Дифференциальные уравнения с разрывной правой частью. М.: Наука, 1985.

47. Черноусько Ф. Л., Оптимальные гарантированные оценки неопределенности с помощью эллипсоидов, /., II., III., Изв. Акад. Наук СССР, Тех. Кибернетика 3,4,5 1980.

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

49. Aubin J.-P., Frankowska H. Set-valued Analysis. Boston: Birkhauser, 1990.

50. Boyd S., El Ghaoui L., Feron E., Balakrishnan V., Linear Matrix Inequalities in System and Control Theory, SIAM, Studies in Applied Mathematics, 1994.

51. Chernousko F.L., State Estimation for Dynamic Systems, CRC Press, 1994.

52. Crandall M. G., Lions P.-L. Viscosity solutions of Hamilton-Jacobi equations // Transactions of American Mathematical Society. 1983. V. 277. p. 1-41.

53. Kirilin M. N., Kurzhanski А. В., Ellipsoidal techniques for reachability problems under nonellipsoidal constraints,// Proc. NOLCOS-Ol. V. 2. IFAC, Elsevier Science, St. Petersburg, 2001.

54. Kostousova E.K., State estimation for dinamic system via parallelotopes: optimization and parallel computations. Optimization Methods & Software, V.9, p.2G9-306.

55. Kostousova E.K. Control synthesis via parallelotopes: optimization and parallel computations. Optimization Methods & Software, V. 14, p.267-310.

56. Krasovski N. N., Subbotin A. I. Positional Differential Games. Springer Verlag, 1988.

57. Kurzhanski А. В., FilippovaT. F., On the Theory of Trajectory Tubes: a Mathematical Formalism for Uncertain Dynamics, Viability and Control, in: Advances in Nonlinear Dynamics and Control, ser. PSCT 17, pp.122 188, Birkhauser, Boston, 1993.

58. Kurzhanski А. В., Vdlyi I. Ellipsoidal Calculus for Estimation and Control. SCFA. Boston: Birkhauser, 1997.

59. Kurzhanski А. В., Varaiya P. Ellipsoidal techniques for reachability analysis // Lecture Notes in Computer Sciences. 1999. V. 1790. p. 202-214.

60. Kurzhanski А. В., Varaiya P. Dynamic optimization for reachability problems // Journal of Optimization Theory and Applications. 2001. V. 108. N. 2. p. 227-251.

61. Kurzhanski А. В., Varaiya P. Ellipsoidal techniques for reachability analysis. Internal approximation // Systems and Control Letters. 2000. V. 41. p. 201-211.

62. Kurzhanski А. В., Varaiya P. Ellipsoidal techniques for reachability analysis. Part I: External approximations. Part II: Internal approximations. Box-valued constraints // Optimization methods and software. 2002. V. 17. p. 177-237.

63. Kurzhanski А. В., Varaiya P. Reachability analysis for uncertain systems the Ellipsoidal Technique. // Journal of nonlinear, impulse and discontinuous systems, N. 1., 2001

64. Kurzhanski А. В., Varaiya P. On reachability under uncertainty // SIAM Journal on Control. V. 41. N. 1. p. 181-216. 2002

65. Ky F. Minimax theorems // Proc. Nat. Acad, of Sci. USA. 1953. V. 39. N. 1. p. 42-47.

66. Lions P.-L., Souganidis P. E. Differential games, optimal control and directional derivatives of viscosity solutions of Bellman's and Isaac's equations // SIAM Journal on Control an Optimization. 1995. V. 23. p. 566-583.

67. Puri A., Borkar V. and Varaiya P., e Approximations of Differential Inclusions, in: R.Alur, T.A.Henzinger, and E.D.Sonntag eds., Hybrid Systems,pp. 109 - 123, LNCS 1201, Springer, 1996.

68. Schweppe F. C., Uncertain Dynamic Systems, Prentice Hall, Englewood ClifTs, NJ, 1973.

69. Valyi I., Ellipsoidal Methods in Time-Optimal Control, in: Modeling Techniques for Uncertain Systems, A.B.Kurzhanski, V.M.Veliov eds., ser. PCST 18, Birkhauser, Boston, 1994.

70. Varaiya P., Lin J. Existence of saddle points in differential games // SIAM Journal on Control an Optimization. 1969. V. 7. N. 1. p. 142-157.