Авторефераты по всем темам >>
Авторефераты по техническим специальностям
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ ПРОГРАММНЫХ СИСТЕМ ИМ. А.К. АЙЛАМАЗЯНА РОССИЙСКОЙ АКАДЕМИИ НАУК На правах рукописи
Ардентов Андрей Андреевич
Алгоритмическое и программное обеспечение задач управления и обработки изображений
05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей 05.13.01 Системный анализ, управление и обработка информации (технические наук
и)
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата технических наук Переславль-Залесский 2012 г.
Работа выполнена в Исследовательском центре процессов управления Федерального государственного бюджетного учреждения науки Института программных систем им. А.К. Айламазяна РАН
Научный консультант:
доктор физико-математических наук Ю.Л. Сачков
Официальные оппоненты:
А.П. Кудрюков, доктор технических наук, профессор, заведующий лабораторией No ИПУ им. В.А. Трапезникова РАН;
.В. Локуциевский, кандидат физико-математических наук, учёный секретарь, ассистент кафедры общих проблем управления механико-математического факультета МГУ им. М.В. Ломоносова.
Ведущая организация:
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Владимирский государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых
Защита диссертации состоится 25 мая 2012 года в 15 час. на заседании Диссертационного совета ДМ 002.084.01 при ИПС им. А.К.Айламазяна РАН по адресу: 152021, Ярославская область, Переславский район, с. Веськово, ул. Петра I, д.4а.
С диссертацией можно ознакомиться в библиотеке ИПС им. А.К.Айламазяна РАН
Автореферат разослан 24 апреля 2012 г.
Ученый секретарь Диссертационного совета ДМ 002.084.кандидат технических наук С.М. Пономарева
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Данная диссертация посвящена разработке математического, алгоритмического и программного обеспечения задач механики, робототехники и обработки изображений, имеющих общую формулировку в терминах геометрической теории управления1. Актуальность выбора закона управления, который переводит систему из заданного начального состояния в заданное конечное состояние при условии минимума выбранной оценки интенсивности управляющих усилий, отмечается в монографии Н.Н. Красовского2.
В диссертации рассматриваются задачи для аффинных по управлению неголономных систем с нелинейными векторными полями, в которых размерность управления меньше размерности состояния. Ж.П. Ломонд3 указывает, что вычисление допустимой траектории между двумя состояниями неголономной системы является нетривиальной задачей, даже при отсутствии минимизируемого функционала и ограничений на управление. На данный момент не существует общего алгоритма, который бы конструировал для любой неголономной системы решение этой задачи точно или приближенно.
Дж. Лаферьер и Г. Суссман4 предложили метод управления для нильпотентных систем. Управляемая система является нильпотентной, если скобки Ли векторных полей при управлениях обращаются в ноль начиная с некоторого порядка. Такие системы дают нильпотентную аппроксимацию неголономных систем.
Понятие нильпотентной аппроксимации управляемой системы было введено в работе А.А. Аграчёва и А.В. Сарычева5, а также независимо в работе Х.Хермса6. Обычно в качестве локальной аппроксимации используется линеаризация управляемой системы, но для рассматриваемых неголономных систем линеаризация дает очень грубое приближение: ввиду того, что размерность управления меньше размерности состояния, линеаризация не может быть управляемой. Вместо нее в этом случае используют нильпотентную аппроксимацию, которая сохраняет Аграчев А.А., Сачков Ю.Л. Геометрическая теория управления, Физматлит, М., 2005.
Красовский Н.Н. Теория управления движением, М.: Наука, 1968.
Laumond J.P. Nonholonomic motion planning for mobile robots, Lecture notes in Control and Information Sciences, 229, Springer, Berlin, Heidelberg, 19Laferriere G., Sussmann H.J. A differential geometric approach to motion planning, Nonholonomic Motion Planing, Eds. Zexiang Li and J.F. Canny, Kluwer, 1992.
Аграчёв А.А., Сарычев А.В. Фильтрация алгебры Ли векторных полей и нильпотентная аппроксимация управляемых систем // ДАН СССР, 1987. Т. 295, c. 777Ц781.
Hermes H. Nilpotent and high-order approximations of vector fields systems // SIAM, 1991. Vol. 33, p. 238Ц264.
структуру управляемости исходных систем. Задача управления колёсным мобильным роботом с прицепом, изучаемая в диссертации, сводится к нильпотентной субримановой задаче на группе Энгеля. В работе А.М. Вершика и О.А. Граничиной7 задача на группе Энгеля интегрируется в эллиптических функциях с помощью уравнения ЭйлераЛагранжа, но вопрос оптимальности экстремальных тракторий не затрагивается.
Наряду с задачами управления мобильными колёсными роботами, в диссертации рассматривается классическая задача Эйлера об эластиках8.
Эта задача имеет богатую историю, связанную с именами Якоба Бернулли9 и Даниила Бернулли10: последний сформулировал её как задачу вариационного исчисления и предложил решить Леонарду Эйлеру. Эйлер, впервые рассмотревший эту задачу в 1744 г.11, получил дифференциальные уравнения для стационарных конфигураций стержня и описал их возможные качественные типы. Эти конфигурации называются эйлеровыми эластиками. Первая параметризация эластик эллиптическими функциями была получена Л. Заалшютцем12. Вопрос об оптимальности эластик был поднят в диссертации Макса Борна 1906 г.13: будущий нобелевский лауреат доказал отсутствие сопряженных точек на эластиках без точек перегиба, т. е. показал, что все неинфлексионные эластики являются локально оптимальными.
Кроме того, с помощью эластик Эйлера описываются экстремальные, а значит и оптимальные траектории (проекции траекторий на плоскость) для различных задач оптимального управления:
1. нильпотентной субримановой задачи на группе Энгеля, дающей нильпотентную аппроксимацию задаче управления мобильным роботом с прицепом;
Вершик А.М., Граничина О.А. Редукция неголономных вариационных задач к изопериметрическим и связности в главных расслоениях, Матем. заметки, 49:5 (1991), 37 Ляв А. Математическая теория упругости, ОНТИ, Москва-Ленинград, 19James 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 Ia 3, p 211Ц212.
Bernoulli D. 26th letter to L. Euler (October, 1742) // Fuss, Correspondance mathmatique et physique. St. Petersburg: 1843. Т. 2.
Эйлер Л. Приложение I: Об упругих стержнях // Метод нахождения кривых линий, обладающих свойствами максимума либо минимума, или решение изопериметрической задачи, взятой в самом широком смысле, Гостехтеориздат, Москва-Ленинград, 1934, 447Ц5Saalschutz L. Der Belastete Stab Unter Einwirkung Einer Seitlichen Kraft: Auf Grundlage Des Strengen Ausdrucks Fur Den Krummungsradius, Leipzig, 18Born M. Untersuchungen uber die Stabilitat der elastischen Linie in Ebene und Raum, unter verschiedenen Grenzbedingungen, Gottingen, Dieterich, 192. обобщенной задачи Дидоны, дающей нильпотентную аппроксимацию задаче об оптимальном качении шара по плоскости14 и задаче управления мобильным роботом с двумя прицепами.
Различные вопросы, связанные с оптимальностью эластик, рассматривались в ряде работ15 16 17. Однако полностью эта задача оптимального управления до недавнего времени оставалась нерешенной. Окончательное теоретическое решение задачи Эйлера об эластиках получено в 20г. Ю.Л. Сачковым18.
Эйлеровы эластики, а также их естественные обобщения находят важные применения в механике, инженерии19, теории управления20, теории аппроксимации21, молекулярной биологии22. Поэтому описанное в диссертации полное программное решение задачи Эйлера представляется весьма актуальным.
Эластики применяются в актуальных задачах компьютерной графики23, в частности для восстановления изображений24. Для решения задачи о восстановлении изображений существуют различные методы, использующие технику вариационного исчисления и дифференциальной геометрии25. В диссертации используются результаты работ одного из новых направлений нейрофизиологии - нейрогеометрии зрения26, а также современные результаты по субримановой геометрии27. Задача восJurdjevic V. The geometry of the plate-ball problem, Arch. Rat. Mech. Anal., v. 124 (1993), 305Ц3Maddocks, J.H. Stability of nonlinearly elastic rods, Arch. Rat. Mech. Anal., v. 85, 1984, 311Ц3Попов Е.П. Теория и расчет гибких упругих стержней, Наука, М., 19Jin M., Bao Z.B. Sufficient conditions for stability of Euler elasticas, Mechanics Research Communications, v. 35, 2007, 193Ц2Sachkov Yu.L. Conjugate points in EulerТs elastic problem, Journal of Dynamical and Control Systems, v. 14, No. 3, 2008, 409Ц4Fraser C.G. Mathematical technique and physical conception in EulerТs investigation of the elastica.
Centaurus, 34(3):211Ц246, 1991.
Harman P.M., Shapiro A.E., editors. The critical role of curvature in NewtonТs developing dynamics.
Cambridge University Press, 2002.
Jerome J.W. Smooth interpolating curves of prescribed length and minimum curvature // Proc.
Amer. Math. Soc. 1975. V. 51. P. 62-66.
Manning R.S., Maddocks J.H., Kahn J.D. A continuum rod model of sequence-dependent DNA structure // J. Chem. Phys. 1996. V. 105. P. 5626-5646.
Mumford D. Elastica and computer vision // Algebraic geometry and its applications. C.L.Bajaj, Ed., Springer-Verlag. New-York: 1994, P. 491-506.
Chan 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-5Duits 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-2Petitot J. Neurogeometrie de la vision. Modeles mathematiques et physiques des architectures fonctionelles, Editions de lТEcole Polytechnique, 2008.
Sachkov 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 для создания интерфейса.
Цель работы и задачи исследования.
Целью диссертационной работы является разработка конструктивных методов, алгоритмов и программ вычисления оптимальных решений в задачах управления, а также создание на этой основе программных средств обработки и анализа изображений.
Для достижения указанной цели необходимо было разработать эффективные алгоритмы и программные средства для решения следующих задач механики, робототехники и обработки изображений:
1) управление мобильным роботом с прицепом, 2) классическая задача Эйлера об эластиках, 3) антропоморфное (естественное для восприятия человека) восстановление изображений.
Общие методы исследования. Для решения поставленных задач использовались геометрическая теория управления, численные методы Ахиезер Н.И. Элементы теории эллиптических функций. М.: Наука, 1970.
анцош К. Практические методы прикладного анализа, М.: ГИФМЛ, 1961, 524 с.
решения алгебраических уравнений, методы компьютерной алгебры, параллельное программирование в системе gridMathematica и на языке С++ с использованием библиотеки TSim. Для аналитических преобразований и численных расчётов в диссертации использовался интерпретируемый язык программирования Mathematica, который поддерживает функциональный, процедурный и объектноЦориентируемый стили программирования. Кроме того в нем имеется возможность определять объекты подобно тому как это обычно делается в математике, задавая их свойства посредством правил.
Научная новизна. Предметом научной новизны являются:
а) параметризация экстремальных траекторий в задаче Эйлера об эластиках и в задаче управления аппроксимацией колесного робота с прицепом;
б) исследование оптимальности экстремальных траекторий для аппроксимации колёсного робота с прицепом;
в) алгоритмы и программы для решения задачи управления колёсным роботом с прицепом;
г) комплекс программ для моделирования эластик Эйлера и решения задачи Эйлера об эластиках;
д) параллельная программа для антропоморфного (естественного для восприятия человека, не содержащего точки возврата) восстановления изображений.
Теоретическая и практическая ценность. Представленные методы, алгоритмы и программы дают решение актуальных задач компьютерной графики, теории управления и упругости, механики и робототехники, и могут использоваться исследователями, а также преподавателями, аспирантами и студентами при работе в данных областях.
Достоверность результатов подтверждается корректным использованием математической теории управления. Основным понятиям, используемым в работе, даны точные определения. Все утверждения снабжены строгими математическими доказательствами.
Апробация работы. Результаты диссертации докладывались на следующих научных конференциях и совещаниях:
1) Международная конференция по математической теории управления и механике. Суздаль, 2009, 2011.
2) Молодежная конференция Теория управления: новые методы и приложения. Переславль, 2009.
3) Международная конференция по дифференциальным уравнениям и динамическим системам. Суздаль, 2010.
4) Workshop on Nonlinear Control and Singularities. Toulon, France, 2010.
5) Международная научная конференция студентов, аспирантов и молодых учёных Ломоносов-2011. Москва.
6) Третья традиционная всероссийская молодежная школа Управление, информация и оптимизация, пос. Ярополец, 2011.
7) Международная конференция Управление и оптимизация неголономных систем. Переславль, 2011.
Результаты диссертации докладывались и обсуждались на научноисследовательских семинарах:
1) Семинар по теории управления под рук. проф. Филиппа Жуана, Университет г. Руан, Франция, 2010 г.
2) Объединенный семинар по оптимизации и управлению Исследовательского центра системного анализа и Исследовательского центра процессов управления ИПС им. А.К. Айламазяна РАН под рук.
д.т.н. Цирлина А.М. и д.ф.-м.н. Сачкова Ю.Л., г. Переславль-Залесский, 2012 г.
3) Семинар кафедры общих проблем управления механико-математического факультета МГУ им. М.В. Ломоносова под рук. члена-корреспондента РАН Зеликина М.И., г. Москва, 2012 г.
4) Семинар лаборатории 7 Института проблем управления РАН под рук. д.т.н. Поляка Б.Т., г. Москва, 2012 г.
Научные исследования по теме диссертации были поддержаны следующими грантами РФФИ: 05-01-00703-а ( Исследование задач оптимального управления субримановой геометрии методами геометрической теории управления ), 09-01-00246-а ( Геометрические методы исследования задач оптимального управления с симметриями ), 09-01-90701-моб_ст ( Научная работа российского молодого ученого Ардентова Андрея Андреевича в Математическом Институте им. В.А.Стеклова РАН ), 10-0191103-НЦНИ_з ( Участие в Франко-Российском семинаре ГеометричеФ ская теория управления: методы и приложенияУ ), 11-01-16014-моб_з_рос ( Участие в третьей Традиционной всероссийской молодежной летней Школе Управление, информация и оптимизаФ цияУ ), 12-01-00913-а ( Новые методы исследования инвариантных задач оптимального управления на группах Ли, с приложениями в классической и квантовой механике и робототехнике ).
Параллельные алгоритмы и программы, разработанные в диссертации, были внедрены при реализации в Научно-технической программе Союзного государства Разработка и использование программно-аппаратных средств ГРИД-технологий и перспективных высокопроизводительных (суперкомпьютерных) вычислительных систем семейства СКИФУ, Ф 2008-2010.
Получено Свидетельство о государственной регистрации программы для ЭВМ OptimalInpainting №2010614762 от 21 июля 2010 г.
Результаты диссертации были внедрены в образовательный процесс Университета города Переславля им. А.К. Айламазяна (практикум на ЭВМ: приложение к курсу УМФ, работа в Wolfram Mathematica).
Публикации. Все результаты диссертации опубликованы в 7 работах автора, список которых приводится в конце автореферата. Работы [1]Ц[5] опубликованы в журналах, рекомендованных ВАК РФ.
ичный вклад. Все результаты диссертации получены автором самостоятельно.
Структура и объем диссертации. Диссертация состоит из пяти глав и заключения. Главы разбиты на 29 пунктов. Основной текст диссертации составляет 147 страниц, 39 иллюстраций и 4 таблицы. Библиография включает 97 наименований.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
В первой, вводной, главе рассматриваются три задачи механики, имеющие общую формулировку в терминах теории оптимального управления. Описывается, как с помощью символьных и численных вычислений получается решение оптимальной задачи, которое находит применение в задачах обработки изображений.
Вторая глава изучает аппроксимацию мобильного колёсного робота с прицепом. Рассматриваются две модели, предложенные Ж.-П. Ломондом30. Исследуется нильпотентная аппроксимация этих моделей. В Laumond J.P. Nonholonomic motion planning for mobile robots, Lecture notes in Control and Information Sciences, 229, Springer, Berlin, Heidelberg, 19некоторых естественных координатах она имеет следующий вид:
q = = u1X1 + u2X2, X1 =, X2 =, (1) x -y x2+yv q = (x, y, z, v) R4, u = (u1, u2) R2.
Для этой управляемой системы рассматривается соответствующая задача оптимального управления с граничными условиями:
q(0) = q0 = (x0, y0, z0, v0), q(t1) = q1 = (x1, y1, z1, v1), (2) и функционалом качества tJ = (u2 + u2) dt min, (3) 1 где точка q = (x, y, z, v) R4 = M задает состояние системы, терминальное время t1 фиксировано, а u = (u1, u2) R2 есть управление.
Сформулированная задача является левоинвариантной субримановой задачей на группе Энгеля для субримановой структуры на R4, заданной полями X1, X2 как ортонормированным базисом31. Задача (1)Ц(3) служит конкретной моделью для всего класса неголономных инвариантных субримановых задач с вектором роста (2, 3, 4); например, для систем, описывающих движение колёсного мобильного робота с прицепом (в диссертации описываются системы для двух моделей с различной связкой робота и прицепа).
Для решения задачи применяется принцип максимума Понтрягина32.
Подсистема сопряженных переменных гамильтоновой системы сводится к уравнению математического маятника33:
= - sin , = const. (4) cИнтеграл энергии маятника E = - cos [-||, +) определяет Аграчев А.А., Сачков Ю.Л. Геометрическая теория управления, Физматлит, М., 2005.
Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов, Наука, М., 1961.
Арнольд В.И. Обыкновенные Дифференциальные Уравнения. М.: Наука, изд. 2, 1975, 240 с.
разбиение фазового цилиндра маятника на подмножества:
C = 7 Ci, Ci Cj = , i = j, i=C = { = (, c, ) | S1, c, R}, C1 = { C | = 0, E (-||, ||)}, C2 = { C | = 0, E (||, +)}, C3 = { C | = 0, E = ||, c = 0}, C4 = { C | = 0, E = -||}, C5 = { C | = 0, E = ||, c = 0}, C6 = { C | = 0, c = 0}, C7 = { C | = c = 0}.
Для каждого подмножества Ci вычисляется параметризация экстремальных траекторий задачи. Для областей C1 (маятник колеблется) и C2 (маятник вращается) параметризация записывается в эллиптических функциях Якоби34. Если вектор сопряженной переменной C1, то формулы в случае = 1 (для изучения задачи достаточно ограничиться этим случаем) выражаются уравнениями:
xt = 2k(cn t - cn ), yt = 2 E(t) - E() - t, yt zt = 2k sn t dn t - sn dn - (cn t + cn ), yt vt = + 2k2 cn2 yt - 4k2 cn (sn t dn t - sn dn )+ 2 2 1 - k+ 2k2 cn t dn t sn t - cn dn sn + t+ 3 3 3k2k2 - + E(t) - E(), 3kгде sn, cn, dn, E эллиптические функции Якоби.
Следует отметить, что проекции экстремальных траекторий на плоскость (x, y) суть эйлеровы эластики (изучению этих траекторий посвящена вторая глава).
Экстремальные траектории удовлетворяют лишь необходимому условию максимума. Для исследования оптимальности найденных траекторий используются понятия геометрической теории управления:
Уиттекер Ю.Т., Ватсон Дж.Н. Курс современного анализа, - УРСС, М. 2002.
1. Точка разреза точка, в которой экстремальная траектория теряет глобальную оптимальность. Согласно усиленному условию Лежандра, малые дуги экстремальных траекторий оптимальны: время, когда траектория теряет свою оптимальность называется временем разреза.
2. Точка Максвелла точка, в которую приходят две различные экстремальные траектории в один момент времени, называемым временем Максвелла. Известно, что после времени разреза траектория перестает быть оптимальной.
3. Сопряженная точка точка, в которой матрица Якоби экспоненциального отображения вырождается. В первой сопряженной точке экстремальная траектория теряет свою локальную оптимальность.
4. Экспоненциальное отображение отображение, задающее параметризацию всех экстремальных траекторий с помощью вектора сопряженных переменных и конечного момента времени.
Для поиска точек Максвелла изучаются симметрии экспоненциального отображения. Рассматриваются отражения, сохраняющие поле направлений маятника. Действие отражений продолжается на множество траекторий маятника, а затем и на множество решений полной гамильтоновой системы принципа максимума Понтрягина. Вычисляются действия отражений на эластики Эйлера и на конечные точки геодезических qt. Построенные отражения являются симметриями экспоненциального отображения.
Определяются точки Максвелла, соответствующие построенным отражениям (симметриям). Вычисляется первое время Максвелла:
t1 : C (0, +], MAX C1 t1 = min(2p1, 4K)/, MAX z C2 t1 = 2Kk/, MAX 2 C6 t1 =, MAX |c| C3 C4 C5 C7 t1 = +, MAX где c, k являются координатами в пространстве сопряженных переменных; p1 > 0 первый корень функции fz(p) = dn p sn p+(p-2 E(p)) cn p;
z K = 1 - k2 sin2 t dt, = ||.
Известно, что время Максвелла t1 задает глобальную верхнюю MAX оценку времени разреза tcut, поэтому справедлива следующая теорема.
Теорема 1. Для любого C tcut() t1 (). (5) MAX Сопряженная точка является второй причиной потери оптимальности траектории. После первого сопряженного времени t1 экстремальная conj траектория перестает быть локально оптимальной. Для исследования сопряженного времени необходимо изучение знака якобиана экспоненциального отображения. Якобиан выражается через эллиптические функции Якоби. Вычислить вручную якобиан не представляется возможным, не говоря об исследовании его знака.
Упрощенные формулы якобиана вычисляются и анализируются с помощью системы компьютерной алгебры Wolfram Mathematica, которая позволяет оперировать большими объемами формул в символьной форме. Был разработан скрипт, основанный на свойствах эллиптических функций Якоби, который дал основу для доказательства следующей теоремы.
Теорема 2. Для любого C t1 () t1 (). (6) conj MAX С использованием полученной оценки времени разреза (теорема 1) и доказанной оценки сопряженного времени (теорема 2) описана глобальная структура экспоненциального отображения в субримановой задаче на группе Энгеля.
Неподвижные точки симметрий в образе экспоненциального отображения задают разбиение пространства состояний на подобласти:
M = Mi, i {1,..., 4}, (7) M1 = {q = (x, y, z, v)|x < 0, z > 0}, M2 = {q = (x, y, z, v)|x < 0, z < 0}, M3 = {q = (x, y, z, v)|x > 0, z < 0}, M4 = {q = (x, y, z, v)|x > 0, z > 0}.
Задается соответствие разбиения прообраза и образа экспоненциального отображения на основании оценки, полученной в теореме 1. С использованием однопараметрической группы растяжений, задача сводится к решению системы 3-x алгебраических уравнений. В векторном виде система записывается следующим образом:
Q() = Q1. (8) Для поиска решения системы (8) с некоторой фиксированной правой частью Q1, разработана программа в системе Mathematica. Программа прошла тестирование для различных случайных значений Q1 (ряд испытаний по 1000 тестов каждое). Наибольшую сложность представляют корни, расположенные близко к границам подмножеств прообраза экспоненциального отображения, которые соответствуют разбиению образа (7). Для проверки разрешимости систем в этом случае были заданы отдельные наборы тестов, соответствующие корням близ границы прообраза экспоненциального отображения. Прообраз экспоненциального отображения есть открытая область, поэтому было определено его компактное подмножество, для которого программа успешно выполняется. Программа не проходит тесты, соответствующие точкам, которые расположены на расстоянии < 10-5 от границ кубов, задающих прообраз экспоненциального отображения.
Третья глава посвящена изучению классической задачи Эйлера об эластиках, которая имеет следующую геометрическую формулировку.
Даны две точки ai = (xi, yi) R2, i {0, 1}, с закрепленными в них единичными векторами vi Ta R2, |vi| = 1, i {0, 1}. Требуется найти i гладкую кривую (t) фиксированной длины l, выходящую из точки a0 с вектором скорости v0 и попадающую в точку a1 с вектором скорости v(см. рис. 1). Кроме того, на кривую накладывается дополнительное условие: интеграл квадрата кривизны имеет наименьшее значение вдоль искомой кривой:
tk2(t) dt min.
(t) Rvaav1 l Рис. 1: Геометрическая постановка задачи задачи Эйлера об эластиках Описанная задача может быть также сформулирована как задача оптимального управления в пространстве M = R2 S следующим обраx,y зом:
cos q = = sin + u 0, u R, 0 0 x q(0) = 0, q(t1) = q1 = y1 , 0 tJ = u2 dt min.
Заметим, что кривизна кривой k = 2 + 2 = || = |u|.
Для этой задачи так же как для задачи на группе Энгеля применяется принцип максимума Понтрягина. Экстремальные траектории задачи параметризуются точками фазового цилиндра математического маятника.
Эластики разбиваются на следующие типы:
Х невырожденные:
(1) инфлексионные, (2) неинфлексионные, (3) критические, Х вырожденные:
(4) окружности, (5) прямые.
В программной среде Mathematica запрограммированы 5 модульных функций вычисления эластик по параметрам. На рис. 2 приведена одна из новых схем быстрого вычисления формул, задающих невырожденные эластики.
Функции вычисления эластик объединены в интерфейс для моделирования эластик на базе Wolfram Demonstration Project. В интерфейсе используются естественные параметры, задающие каждый тип эластик (см. скриншот интерфейса на рис. 3). Головной модуль выполняет функции интерфейса. Основными элементами управления в интерфейсе являются ползунки. Например, с помощью ползунка Angle задается начальный угол поворота эластики 0 [0, 2]. Если нажать справа от ползунка на кнопку +, то появится меню для управления ползунком.
x[t] y[t] form1 t - 2(form1 EEt0 + form2 CNt0 k)/r form2 t - 2(form2 EEt0 - form1 CNt0 k)/r EEt0 form1 form2 CNt EE[amt,k2]-EE[am0,k2] (2 k2 SN02-1) 2k Sqrt[1-k2 SN02] SN0 Cos[amt]-Cos[am0] SN SN0 SNk2 amt am0 SNk k am[ b0+r t,k2] am[b0,k2] Sin[am0] Рис. 2: Схема вычисления функций, задающих инфлексионную эластику Каждому типу эластик соответствуют определенные параметры (см.
рис. 3, блок parameters of elastica):
1. Angle, k, r, P hase, P eriods для инфлексионных эластик;
2. Angle, k, r, P hase, P eriods для неинфлексионных эластик;
3. Angle, r, b0, Length для критических эластик;
4. Angle, Radius, P eriods для окружностей;
5. Angle, Length для прямых.
После основных параметров находятся графические опции (блок graphic options на рис. 3), одинаковые для каждого типа эластики:
Х thickness параметр, задающий толщину линии;
Х dashing задает пунктирный стиль кривой;
Х color отвечает за цвет.
По заданным параметрам интерфейс вычисляет изображение соответствующей эластики и функции на языке Mathematica, определяющие выражение параметризации (блок Parametrization на рис. 3) текущей эластики длиной дуги t.
Рис. 3: Интерфейс на сайте В программной среде Mathematica разработана также программа, вычисляющая оптимальные решения в задаче Эйлера об эластиках. В работах Ю.Л. Сачкова35 36 задача оптимального управления об эластиках сведена к решению систем алгебраических уравнений:
Exp() = q1, N, q1 M, (9) где трехмерное пространство N прообраз экспоненциального отображения, а Exp() параметризация эластик при фиксированном t1 = 1, Sachkov Yu.L. Maxwell strata in EulerТs elastic problem Journal of Dynamical and Control Systems, v. 14, No. 2, 2008, 169Ц234.
Sachkov Yu.L. Conjugate points in EulerТs elastic problem, Journal of Dynamical and Control Systems, v. 14, No. 3, 2008, 409Ц439.
задаваемая экспоненциальным отображением. Образ экспоненциального отображения является полноторием:
M = {(x, y, ) | x2 + y2 < 1, S1}, (10) для которого согласно знаку функции P (x, y, ) = x sin -y cos задает2 ся разбиение на подмножества. Прообраз экспоненциального отображения разбивается на соответствующие подмножества, в которых система уравнений (9) однозначно разрешима.
В системе gridMathematica был разработан параллельный алгоритм вычисления глобально оптимальной эластики. Для поиска оптимальной эластики необходимо разрешить две идентичные системы с разными ограничениями, вычисление корней можно производить независимо.
Кроме того, поиск одного корня можно вести сразу на нескольких узлах:
узел, нашедший корень, отправляет результат вычисления на головной узел, который в свою очередь останавливает все остальные вычисления, связанные с поиском этого корня.
Обширное тестирование показало, что параллельное вычисление оптимально производить на двух узлах, при этом наблюдается ускорение вычисления больше чем в два раза. При увеличении числа узлов ускорение уменьшается. Это обусловлено тем, что в среднем время вычисления одной задачи не так велико, чтобы распределять вычисления между большим количеством узлов.
В таблице 1 приведены результаты решения 300 независимых задач, каждая из которых решается параллельно на нескольких узлах.
Таблица 1: Серия из 300 независимых тестов для задачи Эйлера об эластиках Число узлов: Время работы Ускорение:
n программы: t, c t1/t 1 20875 2 8624 2.3 7792 2.4 6596 3.5 6428 3.6 7167 2.Для тестирования алгоритма создавался набор случайных точек, для которых необходимо найти оптимальные эластики. Так как алгоритм не является эффективным для большого количества узлов, естественно реализовать алгоритм для параллельного поиска серии оптимальных эластик. Этот алгоритм используется для построения анимации, которая визуализирует деформацию оптимального решения задачи при непрерывном изменении граничных значений q1.
Известно, что в большинстве случаев, если близки координаты второго конца эластики, то близки и искомые корни системы уравнений. Таким образом, можно в качестве начального приближения задавать корень, вычисленный на предыдущем шаге. При этом время поиска сокращается в десятки раз. Но существуют точки, для которых не годится такого рода начальное приближение. Это точки, в которые приходят несколько оптимальных эластик (точки Максвелла). Подмножеством таких точек являются точки, задаваемые уравнением P = 0. Общая формула, с помощью которой можно было бы определить, является ли данная точка точкой Максвелла, не известна. В параллельной программе на кривой выбирается набор точек, удовлетворяющих условию P = 0. Затем эти точки помещаются в очередь, после чего запускается параллельный счет. Причем первые точки, помещенные в очередь, вычисляются без информации о предыдущем кадре, в отличие от остальных. Поэтому после j того как некоторый узел обработал точку q1 и выдал результат j, то j в очередь помещается задача, соответствующая следующей точке q1+с начальным приближением j. И так далее, пока все точки не будут обработаны.
Для описанных алгоритмов созданы программы, которые были протестирована на кластере СКИФ Первенец-М. Кривая, на которой выбираются точки, задавалась с помощью функции с большим количеством точек типа P = 0. При таком типе входных данных количество дуг, на которые разрезается кривая, достаточно велико. Следовательно, велико и число гранул параллелизма. Ниже приведена таблица 2, демонстрирующая эффективное распараллеливание алгоритма. В каждом испытании было измерено время работы программы t, c (см. рис. 4 слева); по этим данным были вычислены ускорение времени работы программы a = t1/ti (см. рис. 4 справа). Заметим, что в алгоритме используется метод случайного поиска, поэтому при повторных вычислениях возможны небольшие отклонения во времени выполнения алгоритма (см. ускорения для узлов на рис. 4 справа).
Для произвольной кривой, задающей деформацию правого конца эластики, количество точек вида P = 0 может быть не велико. Также данная кривая может содержать большое количество других точек разреза, для которых неизвестно аналитическое представление. Эти факторы могут a t 1412108642n n 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 Рис. 4: Пример времени и ускорения параллельной программы построения анимаций повлиять на результат распараллеливания.
Пример анимации глобально оптимальной эластики см. на рис. 5. Для исследования точек разреза были построены фильмы с цветной глобально оптимальной эластикой, меняющей цвет в зависимости от подобласти прообраза экспоненциального отображения, в которой расположен корень.
Таблица 2: Тестирование построения анимации из 1000 кадров Число узлов: Время работы Ускорение:
n программы: t, м t1/t 1 1374 2 693 1.3 467 2.4 355 3.5 297 4.6 214 6.7 188 7.8 173 7.Для того чтобы получить представление о поверхности разреза, рассматриваются сечения образа экспоненциального отображения, задаваемые формулой = const. С помощью программы такие сечения были раскрашены в цвета, соответствующие подобластям прообраза экспоненциального отображения. Границы перехода между цветами задают множество разреза.
Напомним, что множеством разреза называется множество точек, для которых обе эластики (кандидаты на оптимальную), у которых концы и касательные на концах совпадают, имеют одинаковое значение функциРис. 6: Поверхность разреза в полноРис. 5: Кадры фильма с глобально оптории тимальными эластиками онала упругой энергии.
Для соединения нескольких сечений в трехмерное изображение каждое сечение задается одинаковым количеством точек разреза. Затем точки из соседних сечений соединяются прямыми отрезками, строится каркас множества. Соседние отрезки формируют четырехугольники в трехмерном пространстве, которые закрашиваются цветом. Для полного построения множества разреза в полнотории находятся точки разреза в многих сечениях полнотория с некоторым шагом, и на их основе конструируется трехмерное изображение.
Построенное в рамках этой диссертации изображение множества разреза приведено на рис. 6. Для его построения было решено более полмиллиона задач Эйлера об эластиках с фиксированными граничными условиями, равномерно распределенными в полнотории, задающем множество достижимости задачи. Выполнить такой расчёт было не по силам для одного персонального компьютера. Использовался программный инструмент параллельного вычисления gridMathematica37 на кластере СКИФ Первенец-М.
Одно из применений эластик восстановление поврежденных или скрытых изображений, является одной из самых актуальных задач компьютерной графики. Четвертая глава диссертации использует результаты работ одного из новых направлений нейрофизиологии - нейрогео метрии зрения38, а также современные результаты по субримановой геометрии39. Согласно результатам нейрогеометрии зрения, человеческий мозг восстанавливает изофоты (x(t), y(t)) (линии уровня функции яркости изображения) на поврежденных изображениях на основе вариационного принципа 2 + 2 + 2 2 dt min, > 0, где = arctg(/).
Задача антропоморфного (естественного для восприятия человека) восстановления изображений сводится к левоинвариантной субримановой задаче на группе движений плоскости, которая также доставляет решение задачи оптимального управления колёсным роботом на плоскости, который может двигаться вперед и назад, и вращаться вокруг себя (машина Ридса-Шеппа).
Для решения задачи антропоморфного восстановления изображений разработан алгоритм устранения точек возврата, а также программа на языке C++ с использованием параллельной библиотеки TSim40. Так как поврежденные области на изображении можно восстанавливать независимо, то параллельная программа разбивает области повреждения на группы и принимает задачу восстановления областей из одной группы за гранулу параллелизма. Так как реализованный алгоритм восстановления одной области при практическом использовании решал задачу слишком быстро, пришлось рассматривать гранулы параллелизма, соответствующие различному количеству восстанавливаемых областей. Успешное распараллеливание задачи восстановления изображения возможно только для изображения большого размера с большим количеством областей повреждения.
Программа прошла испытание на кластере blade.botik.ru с использованием 4 узлов по 8 ядер каждый (всего 32 ядра). Пример корректного восстановления изображения приведен на рис. 7. Слева приведено исходное изображение, в центре поврежденное, справа расположено восстановленное изображение. Был написан скрипт, который производил тестирование алгоритма при различном количестве используемых Petitot J. Neurogeometrie de la vision. Modeles mathematiques et physiques des architectures fonctionelles, Editions de lТEcole Polytechnique, 20Сачков Ю.Л., Ардентов А.А., Маштаков А.П. Параллельный алгоритм и программа восстановления изофот для поврежденных изображений, Программные системы: теория и приложения, v. 1, No. 1, 2010, 3- Рис. 7: Пример восстановления изображения узлов (ядер). А именно, сначала запускается последовательное выполнение задачи, соответствующее вычислению на одном ядре. Затем последовательно запускается параллельная программа с использованием различного количества узлов (соответственно 8, 16, 24 и 32 ядра). Скрипт строит графики времени вычисления и ускорения для различного количества используемых ядер (см. рис. 8, слева расположен график времени, справа ускорения).
Рис. 8: Пример времени вычисления и ускорения программы восстановления изображения в зависимости от количества ядер Описанные в четвертой главе методы, алгоритмы и программы используются в параллельном программном комплексе для восстановления изображенийOptimalInpainting.
В пятой главе приводятся коды программ, разработанных в диссертации, а также описание нового гибридного метода решения систем алгебраических уравнений, обладающих свойством однозначной разрешимости и непрерывной завивисмости корня от правой части системы.
Такие системы возникают при решении всех трех рассматриваемых в диссертации задач.
В заключении кратко сформулированы основные результаты, полученные в диссертации.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ В рамках проекта Wolfram Demonstration Project был разработан интерфейс для моделирования эластик Эйлера, которые описывают экстремальные траектории в задаче Эйлера об эластиках и в задаче управления мобильным роботом с прицепом.
Для задачи управления аппроксимацией колёсного робота с прицепом получены следующие результаты:
1. параметризация экстремальных траекторий, 2. теоретическое сведение задачи оптимального управления к решению систем алгебраических уравнений, 3. программа для вычисления оптимальных траекторий.
Для задачи Эйлера об эластиках разработан программный комплекс, включающий в себя следующие параллельные программы:
1. вычисление глобально и локально оптимальных траекторий, 2. построение анимации из серии оптимальных траекторий, 3. построение множества разреза, описывающего скрытую симметрию задачи.
Для задачи управления мобильным роботом и задачи Эйлера об эластиках разработан общий гибридный метод и алгоритм решения систем алгебраических уравнений, обладающих свойством однозначной разрешимости и непрерывной зависисимости решений от правой части, к которым сводятся эти задачи. Алгоритм реализован в программной среде Mathematica.
Для задачи антропоморфного восстановления изображений был разработан алгоритм -регуляции для устранения точек возврата у восстанавливаемых кривых. Алгоритм был запрограммирован на языке C++ с использованием параллельной библиотеки TSim в рамках программного комплекса OptimalInpainting.
ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ [1] Ардентов А.А., Сачков Ю.Л. Решение задачи Эйлера об эластиках // Автоматика и телемеханика, No. 4, 2009, с. 78-88. (автора - 6 стр.) [2] Сачков Ю.Л., Ардентов А.А. Параллельные алгоритмы и программы для моделирования эйлеровых эластик // Программные продукты и системы, No. 4, 2009, с. 71-73. (автора - 1 стр.) [3] Сачков Ю.Л., Ардентов А.А., Касимов В.М., Маштаков А.П. Восстановление изображений на основе вариационного принципа // Программные продукты и системы, No. 4, 2009, c. 126-127. (автора - стр.) [4] Ардентов А.А. Экстремальные траектории в нильпотентной субримановой задаче на группе Энгеля (случай докритических колебаний маятника) // Современная математика. Фундаментальные направления, No. 42, 2011, с. 29-34.
[5] Ардентов А.А., Сачков Ю.Л. Экстремальные траектории в нильпотентной субримановой задаче на группе Энгеля // Математический сборник, Т. 202, No. 11, 2011, с. 31-54. (автора - 12 стр.) [6] Ардентов А.А., Сачков Ю.Л. Антропоморфное восстановление поврежденных изображений на основе методов субримановой геометрии // Программные системы: теория и приложения : электрон. научн. журн. 2011, No. 4(8), с. 3-15. (автора - 6 стр.) [7] Ардентов А.А. Интерфейс для моделирования эластик Эйлера в программной среде Mathematica // Программные системы: теория и приложения : электрон. научн. журн. 2012. T. 3, № 1(10), с. 31Ц50.
[8] Сачков Ю.Л., Ардентов А.А., Маштаков А.П. Свидетельство о государственной регистрации программы для ЭВМ OptimalInpainting No2010614762 от 21 июля 2010 г.
Авторефераты по всем темам >>
Авторефераты по техническим специальностям