Введение к работе
Актуальность темы. Данная диссертация посвящена разработке математического, алгоритмического и программного обеспечения задач механики, робототехники и обработки изображений, имеющих общую формулировку в терминах геометрической теории управления1. Актуальность выбора закона управления, который переводит систему из заданного начального состояния в заданное конечное состояние при условии минимума выбранной оценки интенсивности управляющих усилий, отмечается в монографии Н.Н. Красовского2.
В диссертации рассматриваются задачи для аффинных по управлению неголономных систем с нелинейными векторными полями, в которых размерность управления меньше размерности состояния. Ж.П. Ло-монд3 указывает, что вычисление допустимой траектории между двумя состояниями неголономной системы является нетривиальной задачей, даже при отсутствии минимизируемого функционала и ограничений на управление. На данный момент не существует общего алгоритма, который бы конструировал для любой неголономной системы решение этой задачи точно или приближенно.
Дж. Лаферьер и Г. Суссман4 предложили метод управления для ниль-потентных систем. Управляемая система является нильпотентной, если скобки Ли векторных полей при управлениях обращаются в ноль начиная с некоторого порядка. Такие системы дают нильпотентную аппроксимацию неголономных систем.
Понятие нильпотентной аппроксимации управляемой системы было введено в работе А.А. Аграчёва и А.В. Сарычева5, а также независимо в работе Х.Хермса6. Обычно в качестве локальной аппроксимации используется линеаризация управляемой системы, но для рассматриваемых неголономных систем линеаризация дает очень грубое приближение: ввиду того, что размерность управления меньше размерности состояния, линеаризация не может быть управляемой. Вместо нее в этом случае используют нильпотентную аппроксимацию, которая сохраняет
^грачев А.А., Сачков Ю.Л. Геометрическая теория управления, Физматлит, М., 2005.
2Красовский Н.Н. Теория управления движением, М.: Наука, 1968.
3Laumond J.P. Nonholonomic motion planning for mobile robots, Lecture notes in Control and Information Sciences, 229, Springer, Berlin, Heidelberg, 1998
4Laferriere G., Sussmann H.J. A differential geometric approach to motion planning, Nonholonomic Motion Planing, Eds. Zexiang Li and J.F. Canny, Kluwer, 1992.
5Аграчёв А.А., Сарычев A.B. Фильтрация алгебры Ли векторных полей и нильпотентная аппроксимация управляемых систем // ДАН СССР, 1987. Т. 295, с. 777-781.
6Hermes Н. Nilpotent and high-order approximations of vector fields systems // SIAM, 1991. Vol. 33, p. 238-264.
структуру управляемости исходных систем. Задача управления колёсным мобильным роботом с прицепом, изучаемая в диссертации, сводится к нильпотентной субримановой задаче на группе Энгеля. В работе A.M. Вершика и О.А. Граничиной7 задача на группе Энгеля интегрируется в эллиптических функциях с помощью уравнения Эйлера-Лагранжа, но вопрос оптимальности экстремальных тракторий не затрагивается.
Наряду с задачами управления мобильными колёсными роботами, в диссертации рассматривается классическая задача Эйлера об эластиках8.
Эта задача имеет богатую историю, связанную с именами Якоба Бернулли9 и Даниила Бернулли10: последний сформулировал её как задачу вариационного исчисления и предложил решить Леонарду Эйлеру. Эйлер, впервые рассмотревший эту задачу в 1744 г.11, получил дифференциальные уравнения для стационарных конфигураций стержня и описал их возможные качественные типы. Эти конфигурации называются эйлеровыми эластиками. Первая параметризация эластик эллиптическими функциями была получена Л. Заалшютцем12. Вопрос об оптимальности эластик был поднят в диссертации Макса Борна 1906 г.13: будущий нобелевский лауреат доказал отсутствие сопряженных точек на эластиках без точек перегиба, т. е. показал, что все неинфлексионные эластики являются локально оптимальными.
Кроме того, с помощью эластик Эйлера описываются экстремальные, а значит и оптимальные траектории (проекции траекторий на плоскость) для различных задач оптимального управления:
1. нильпотентной субримановой задачи на группе Энгеля, дающей ниль-потентную аппроксимацию задаче управления мобильным роботом с прицепом;
Вершик A.M., Граничина О.А. Редукция неголономных вариационных задач к изопериметри-ческим и связности в главных расслоениях, Матем. заметки, 49:5 (1991), 37—44 8Ляв А. Математическая теория упругости, ОНТИ, Москва-Ленинград, 1935
9 James Bernoulli. Quadratura curvae, e cujus evolutione describitur inflexae laminae curvatura. In Die Werke von Jakob Bernoulli, pages 223-227. Birkhauser, 1692. Med. CLXX; Ref. UB: L la 3, p 211-212.
wBernoulli D. 26th letter to L. Euler (October, 1742) // Fuss, Correspondance mathematique et physique. St. Petersburg: 1843. T. 2.
11 Эйлер Л. Приложение I: Об упругих стержнях // Метод нахождения кривых линий, обладающих свойствами максимума либо минимума, или решение изопериметрической задачи, взятой в самом широком смысле, Гостехтеориздат, Москва-Ленинград, 1934, 447-572
12Saalschutz L. Der Belastete Stab Unter Einwirkung Einer Seitlichen Kraft: Auf Grundlage Des Strengen Ausdrucks Fur Den Krummungsradius, Leipzig, 1880
13Born M. Untersuchungen uber die Stabilitat der elastischen Linie in Ebene und Raum, unter verschiedenen Grenzbedingungen, Gottingen, Dieterich, 1906
2. обобщенной задачи Дидоны, дающей нильпотентную аппроксимацию задаче об оптимальном качении шара по плоскости14 и задаче управления мобильным роботом с двумя прицепами.
Различные вопросы, связанные с оптимальностью эластик, рассматривались в ряде работ15 16 17. Однако полностью эта задача оптимального управления до недавнего времени оставалась нерешенной. Окончательное теоретическое решение задачи Эйлера об эластиках получено в 2008 г. Ю.Л. Сачковым18.
Эйлеровы эластики, а также их естественные обобщения находят важ-
ные применения в механике, инженерии , теории управления , теории аппроксимации21, молекулярной биологии22. Поэтому описанное в диссертации полное программное решение задачи Эйлера представляется весьма актуальным.
Эластики применяются в актуальных задачах компьютерной графики23, в частности для восстановления изображений24. Для решения задачи о восстановлении изображений существуют различные методы, использующие технику вариационного исчисления и дифференциальной геометрии25. В диссертации используются результаты работ одного из новых направлении нейрофизиологии — неирогеометрии зрения , а также современные результаты по субримановой геометрии27. Задача вос-
uJurdjevic V. The geometry of the plate-ball problem, Arch. Rat. Mech. Anal., v. 124 (1993), 305-328
15Maddocks, J.H. Stability of nonlinearly elastic rods, Arch. Rat. Mech. Anal., v. 85, 1984, 311-354
16Попов Е.П. Теория и расчет гибких упругих стержней, Наука, М., 1986
17Jin М., Bao Z.B. Sufficient conditions for stability of Euler elasticas, Mechanics Research Communications, v. 35, 2007, 193-200
18Sachkov Yu.L. Conjugate points in Euler's elastic problem, Journal of Dynamical and Control Systems, v. 14, No. 3, 2008, 409-439
19Fraser C.G. Mathematical technique and physical conception in Euler's investigation of the elastica. Centaurus, 34(3):211-246, 1991.
20Harman P.M., Shapiro A.E., editors. The critical role of curvature in Newton's developing dynamics. Cambridge University Press, 2002.
21 Jerome J.W. Smooth interpolating curves of prescribed length and minimum curvature // Proc. Amer. Math. Soc. 1975. V. 51. P. 62-66.
22Manning R.S., Maddocks J.H., Kahn J.D. A continuum rod model of sequence-dependent DNA structure If J. Chem. Phys. 1996. V. 105. P. 5626-5646.
23Mumford D. Elastica and computer vision // Algebraic geometry and its applications. C.L.Bajaj, Ed., Springer-Verlag. New-York: 1994, P. 491-506.
24Chan T.F., Kang S.H., Shen J. Euler's elastica and curvature based inpainting, SIAM Journal of Applied Math., v. 63, No. 2, 2002, 564-592
25Duits R., Franken E.M. Left-invariant parabolic Evolutions on SE(2) and Contour Enhancement via Invertible Orientation Scores. Part I: Linear Left-invariant Diffusion Equations on SE(2), Quarterly of Applied Mathematics, v. 68, No. 2, June 2008, 255-292
26Petitot J. Neurogeometrie de la vision. Modeles mathematiques et physiques des architectures fonctionelles, Editions de l'Ecole Polytechnique, 2008.
27Sachkov Yu.L. Cut locus and optimal synthesis in the sub-Riemannian problem on the group of motions of a plane, ESAIM: Control, Optimisation and Calculus of Variations, No. 17, 2011, 293-321.
становления изображений формулируется как левоинвариантная субри-манова задача на группе движений плоскости, которая также доставляет решение задачи оптимального управления колёсным робот на плоскости, который может двигаться вперед и назад, и вращаться вокруг себя (машина Ридса-Шеппа).
Все рассматриваемые в диссертации задачи оптимального управления сводятся к решению систем алгебраических уравнений в эллиптических функциях Якоби28. Решаемые уравнения обладают свойством однозначной разрешимости и непрерывной зависимости решения от правой части.
Книга по прикладному анализу К. Ланцоша29 знакомит широкий круг инженеров с современными методами численного решения систем уравнений, возникающих в практической деятельности. Построение схем, эффективно уменьшающих ошибку и дающих возможность оценить ее с достаточной точностью, представляет не только практическую ценность, но и самостоятельный научный интерес.
Представленные в диссертации результаты основаны на программной реализации в среде компьютерной алгебры Wolfram Mathematica с использованием программных инструментов параллельного вычисления gridMathematica и TSim, а также интернет приложения Wolfram Demonstration Project для создания интерфейса.
Цель работы и задачи исследования.
Целью диссертационной работы является разработка конструктивных методов, алгоритмов и программ вычисления оптимальных решений в задачах управления, а также создание на этой основе программных средств обработки и анализа изображений.
Для достижения указанной цели необходимо было разработать эффективные алгоритмы и программные средства для решения следующих задач механики, робототехники и обработки изображений:
управление мобильным роботом с прицепом,
классическая задача Эйлера об эластиках,
антропоморфное (естественное для восприятия человека) восстановление изображений.
Общие методы исследования. Для решения поставленных задач использовались геометрическая теория управления, численные методы
28Ахиезер Н.И. Элементы теории эллиптических функций. М.: Наука, 1970. 29Ланцош К. Практические методы прикладного анализа, М.: ГИФМЛ, 1961, 524 с.
решения алгебраических уравнений, методы компьютерной алгебры, параллельное программирование в системе gridMathematica и на языке C++ с использованием библиотеки TSim. Для аналитических преобразований и численных расчётов в диссертации использовался интерпретируемый язык программирования Mathematica, который поддерживает функциональный, процедурный и объектно-ориентируемый стили программирования. Кроме того в нем имеется возможность определять объекты подобно тому как это обычно делается в математике, задавая их свойства посредством правил.
Научная новизна. Предметом научной новизны являются:
а) параметризация экстремальных траекторий в задаче Эйлера об эла
стиках и в задаче управления аппроксимацией колесного робота с
прицепом;
б) исследование оптимальности экстремальных траекторий для аппрок
симации колёсного робота с прицепом;
в) алгоритмы и программы для решения задачи управления колёсным
роботом с прицепом;
г) комплекс программ для моделирования эластик Эйлера и решения
задачи Эйлера об эластиках;
д) параллельная программа для антропоморфного (естественного для
восприятия человека, не содержащего точки возврата) восстановле
ния изображений.
Теоретическая и практическая ценность. Представленные методы, алгоритмы и программы дают решение актуальных задач компьютерной графики, теории управления и упругости, механики и робототехники, и могут использоваться исследователями, а также преподавателями, аспирантами и студентами при работе в данных областях.
Достоверность результатов подтверждается корректным использованием математической теории управления. Основным понятиям, используемым в работе, даны точные определения. Все утверждения снабжены строгими математическими доказательствами.
Апробация работы. Результаты диссертации докладывались на следующих научных конференциях и совещаниях:
1) Международная конференция по математической теории управления и механике. Суздаль, 2009, 2011.
Молодежная конференция «Теория управления: новые методы и приложения». Переславль, 2009.
Международная конференция по дифференциальным уравнениям и динамическим системам. Суздаль, 2010.
Workshop on Nonlinear Control and Singularities. Toulon, France, 2010.
Международная научная конференция студентов, аспирантов и молодых учёных «Ломоносов-2011». Москва.
Третья традиционная всероссийская молодежная школа «Управление, информация и оптимизация», пос. Ярополец, 2011.
Международная конференция «Управление и оптимизация неголо-номных систем». Переславль, 2011.
Результаты диссертации докладывались и обсуждались на научно-исследовательских семинарах:
Семинар по теории управления под рук. проф. Филиппа Жуана, Университет г. Руан, Франция, 2010 г.
Объединенный семинар по оптимизации и управлению Исследовательского центра системного анализа и Исследовательского центра процессов управления ИПС им. А.К. Айламазяна РАН под рук. д.т.н. Цирлина A.M. и д.ф.-м.н. Сачкова Ю.Л., г. Переславль-За-лесский, 2012 г.
Семинар кафедры общих проблем управления механико-математического факультета МГУ им. М.В. Ломоносова под рук. члена-корреспондента РАН Зеликина М.И., г. Москва, 2012 г.
Семинар лаборатории 7 Института проблем управления РАН под рук. д.т.н. Поляка Б.Т., г. Москва, 2012 г.
Научные исследования по теме диссертации были поддержаны следующими грантами РФФИ: 05-01-00703-а («Исследование задач оптимального управления субрнмановой геометрии методами геометрической теории управления»), 09-01-00246-а («Геометрические методы исследования задач оптимального управления с симметриями»), 09-01-90701-моб_ст («Научная работа российского молодого ученого Ардентова Андрея Андреевича в Математическом Институте им. В.А.Стеклова РАН»), 10-01-91103-НЦНИ_з («Участие в Франко-Российском семинаре „Геометрическая теория управления: методы и приложения"»),
11-01-16014-моб_з_рос («Участие в третьей Традиционной всероссийской молодежной летней Школе „Управление, информация и оптимизация"»), 12-01-00913-а («Новые методы исследования инвариантных задач оптимального управления на группах Ли, с приложениями в классической и квантовой механике и робототехнике»).
Параллельные алгоритмы и программы, разработанные в диссертации, были внедрены при реализации в Научно-технической программе Союзного государства «Разработка и использование программно-аппаратных средств ГРИД-технологий и перспективных высокопроизводительных (суперкомпьютерных) вычислительных систем семейства „СКИФ"», 2008-2010.
Получено Свидетельство о государственной регистрации программы для ЭВМ Optimallnpainting №2010614762 от 21 июля 2010 г.
Результаты диссертации были внедрены в образовательный процесс Университета города Переславля им. А.К. Айламазяна (практикум на ЭВМ: приложение к курсу УМФ, работа в Wolfram Mathematica).
Публикации. Все результаты диссертации опубликованы в 7 работах автора, список которых приводится в конце автореферата. Работы [1]-[5] опубликованы в журналах, рекомендованных ВАК РФ.
Личный вклад. Все результаты диссертации получены автором самостоятельно.
Структура и объем диссертации. Диссертация состоит из пяти глав и заключения. Главы разбиты на 29 пунктов. Основной текст диссертации составляет 147 страниц, 39 иллюстраций и 4 таблицы. Библиография включает 97 наименований.
Похожие диссертации на Алгоритмическое и программное обеспечение задач управления и обработки изображений
