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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ ПРОГРАММНЫХ СИСТЕМ ИМ. А.К. АЙЛАМАЗЯНА РОССИЙСКОЙ АКАДЕМИИ НАУК

На правах рукописи

Ардентов Андрей Андреевич

Алгоритмическое и программное обеспечение задач управления и обработки изображений

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

05.13.01 — Системный анализ, управление и обработка информации (технические науки)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 С [.іт, £012

Переславль-Залесский — 2012 г.

005017703

Работа выполнена в Исследовательском центре процессов управления Федерального государственного бюджетного учреждения науки Института программных систем им. А.К. Айламазяна РАН

Научный руководитель:

доктор физико-математических наук Ю.Л. Сачков

Официальные оппоненты: А.П. Кудрюков,

доктор технических наук, профессор, заведующий лабораторией N0 1 ИПУ им. В.А. Трапезникова РАН;

Л.В. Локуциевский,

кандидат физико-математических наук, учёный секретарь, ассистент кафедры общих проблем управления механико-математического факультета МГУ им. М.В. Ломоносова.

Ведущая организация:

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Владимирский государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых»

Защита диссертации состоится « 25 » мая

2012 года в 15 час. на заседании Диссертационного совета

ДМ 002.084.01 при ИПС им. А.К.Айламазяна РАН по адресу: 152021,

Ярославская область, Переславский район, с. Веськово, ул. Петра I, д.4а.

С диссертацией можно ознакомиться в библиотеке ИПС им. А.К.Айламазяна РАН

Автореферат разослан « 24 » апреля 2012 г.

Ученый секретарь Диссертационного совета ДМ 002.0

кандидат технических наук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Данная диссертация посвящена разработке математического, алгоритмического и программного обеспечения задач механики, робототехники и обработки изображений, имеющих общую формулировку в терминах геометрической теории управления1. Актуальность выбора закона управления, который переводит систему из заданного начального состояния в заданное конечное состояние при условии минимума выбранной оценки интенсивности управляющих усилий, отмечается в монографии H.H. Красовского2.

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

Дж. Лаферьер и Г. Суссман4 предложили метод управления для ниль-потентных систем. Управляемая система является нильпотентной, если скобки Ли векторных полей при управлениях обращаются в ноль начиная с некоторого порядка. Такие системы дают нильпотентную аппроксимацию неголономных систем.

Понятие нильпотентной аппроксимации управляемой системы было введено в работе A.A. Аграчёва и A.B. Сарычева5, а также независимо в работе Х.Хсрмса0. Обычно в качестве локальной аппроксимации используется линеаризация управляемой системы, но для рассматриваемых неголономных систем линеаризация дает очень грубое приближение: ввиду того, что размерность управления меньше размерности состояния, линеаризация не может быть управляемой. Вместо нее в этом случае используют нильпотентную аппроксимацию, которая сохраняет

1Аграчев A.A., Сачков Ю.Л. Геометрическая теория управления, Физматлит, M., 2005.

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

3Laumond J.P. Nonholonomic motion planning for mobile robots, Lecture notes in Control and Information Sciences, 229, Springer, Berlin, Heidelberg, 1998

4Lafcrriere G., Sussmann H.J. A differential geometric approach to motion planning. Nonholonomic Motion Planing, Eds. Zcxiang Li and J.F. Canny, Kluwer, 1992.

°Аграчсв A.A., Сарычев A.D. Фильтрация алгебры Ли векторных полей и нильпотентная аппроксимация управляемых систем // ДАН СССР, 1987. Т. 295, с. 777-781.

6 Hermes Н. Nilpotent and high-order approximations of vector fields systems 11 SIAM, 1991. Vol. 33, p. 238-2G4.

структуру управляемости исходных систем. Задача управления колёсным мобильным роботом с прицепом, изучаемая в диссертации, сводится к нильпотентной субримановой задаче на группе Энгеля. В работе A.M. Вершика и O.A. Граничиной7 задача на группе Энгеля интегрируется в эллиптических функциях с помощью уравнения Эйлера-Лагранжа, но вопрос оптимальности экстремальных тракторий не затрагивается.

Наряду с задачами управления мобильными колёсными роботами, в диссертации рассматривается классическая задача Эйлера об эластиках8.

Эта задача имеет богатую историю, связанную с именами Якоба Бер-нулли9 и Даниила Бернулли10: последний сформулировал её как задачу вариационного исчисления и предложил решить Леонарду Эйлеру. Эйлер, впервые рассмотревший эту задачу в 1744 г.11, получил дифференциальные уравнения для стационарных конфигураций стержня и описал их возможные качественные типы. Эти конфигурации называются эйлеровыми эластиками. Первая параметризация эластик эллиптическими функциями была получена Л. Заалшютцем12. Вопрос об оптимальности эластик был поднят в диссертации Макса Борна 1906 г.13: будущий нобелевский лауреат доказал отсутствие сопряженных точек на эластиках без точек перегиба, т. е. показал, что все неинфлексионные эластики являются локально оптимальными.

Кроме того, с помощью эластик Эйлера описываются экстремальные, а значит и оптимальные траектории (проекции траекторий на плоскость) для различных задач оптимального управления:

1. нильпотентной субримановой задачи на группе Энгеля, дающей ниль-потентную аппроксимацию задаче управления мобильным роботом с прицепом;

7Вершик A.M., Граничина O.A. Редукция неголономных вариационных задач к изонериметри-ческим и связности н главных расслоениях, Матем. заметки, 49:5 (1991), 37—44

8Ляв А. Математическая теория упругости, ОНТИ, Москва-Ленинград, 1935

9 James Bernoulli. Quadrat ига curvae, е cujus evolutionedescribitur ¡nflexae laminae curvatura. In Die Werke von Jakob Bernoulli, pages 223-227. Birkhauser, 1C92. Med. CLXX; Ref. UB: L la 3, p 211-212.

10Bernoulli D. 26th letter to L. Euler (October, 1742) // Fuss, Correspondance mathématique et physique. St. Petersburg: 1843. T. 2.

"Эйлер Л. Приложение I: Об упругих стержнях // Метод нахождения кривых линий, обладающих свойствами максимума либо минимума, или решение изопериметрической задачи, взятой в самом широком смысле, Гостехтеориздат, Москва-Ленинград, 1934, 447-572

12Saalschutz L. Der Belastete Stab Unter Einwirkung Einer Seitlichen Kraft: Auf Grundlage Des Strengen Ausdrucks Fur Den Krümmungsradius, Leipzig, 1880

l3Born M. Untersuchungen über die Stabiiitat der elastischen Linie in Ebene und Raum, unter verschiedenen Grenzbedingimgen, Gottingen, Dietericli, 1906

2. обобщенной задачи Дидоны, дающей нильпотентную аппроксимацию задаче об оптимальном качении шара по плоскости14 и задаче управления мобильным роботом с двумя прицепами.

Различные вопросы, связанные с оптимальностью эластик, рассматривались в ряде работ15 16 17. Однако полностью эта задача оптимального управления до недавнего времени оставалась нерешенной. Окончательное теоретическое решение задачи Эйлера об эластиках получено в 2008 г. Ю.Л. Сачковым18.

Эйлеровы эластики, а также их естественные обобщения находят важные применения в механике, инженерии19, теории управления20, теории аппроксимации21, молекулярной биологии22. Поэтому описанное в диссертации полное программное решение задачи Эйлера представляется весьма актуальным.

Эластики применяются в актуальных задачах компьютерной графики23, в частности для восстановления изображений24. Для решения задачи о восстановлении изображений существуют различные методы, использующие технику вариационного исчисления и дифференциальной геометрии25. В диссертации используются результаты работ одного из новых направлений нейрофизиологии — нейрогеометрии зрения26, а также современные результаты по субримановой геометрии27. Задача вос-

14Jui-(ijevic V. The geometry of the plate-ball problem, Arch. Rat. Mecli. Anal., v. 124 (1993), 305-328

nMat!docks, J.H. Stability of nonlinearly elastic tods, Arch. Rat. Mecli. Anal., v. 85, 1984, 311-354

16Попов Е.П. Теория и расчет гибких упругих стержней, Наука, M., 1980

"Jin M., Bao Z.D. Sufficient conditions for stability of Etiler elasticas, Mechanics Research Communications, v. 35, 2007, 193-200

18Sachkov Yu.L. Conjugate ¡joints in Eulors 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. G2-GG.

22Manning R.S., Matldocks J.H., Kahn J.D. A continuum rod model of sequence-dependent DNA structure // J. Chem. Phys. 199G. V. 105. P. 5G2G-5G4G.

23Mumford 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., S hen J. Euler's elastica and curvature based inpainting, SIAM Journal of Applied Math., v. G3, No. 2, 2002, 5G4-592

2°Duits R., Frankcn 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. 08, No. 2, June 2008, 255-292

26PctitoC J. Neurogeometrie de la vision. Modeles mathématiques et physiques des architectures fonctionelles, Editions de TEcole 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 для создания интерфейса.

Цель работы и задачи исследования.

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

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

1) управление мобильным роботом с прицепом,

2) классическая задача Эйлера об эластиках,

3) антропоморфное (естественное для восприятия человека) восстановление изображений.

Общие методы исследования. Для решения поставленных задач использовались геометрическая теория управления, численные методы

28Ахиезср Н.И. Элементы теории эллиптических функций. М.: Наука, 1970.

29Ланцош К. Практические методы прикладного анализа, М.: ГИФМЛ, 1961, 524 с.

решения алгебраических уравнений, методы компьютерной алгебры, параллельное программирование в системе gridMathematica и на языке С++ с использованием библиотеки ТБт. Для аналитических преобразований и численных расчётов в диссертации использовался интерпретируемый язык программирования МаЛетаЫса, который поддерживает функциональный, процедурный и объектно-ориентируемый стили программирования. Кроме того в нем имеется возможность определять объекты подобно тому как это обычно делается в математике, задавая их свойства посредством правил.

Научная новизна. Предметом научной новизны являются:

а) параметризация экстремальных траекторий в задаче Эйлера об эластиках и в задаче управления аппроксимацией колесного робота с прицепом;

б) исследование оптимальности экстремальных траекторий для аппроксимации колёсного робота с прицепом;

в) алгоритмы и программы для решения задачи управления колёсным роботом с прицепом;

г) комплекс программ для моделирования эластик Эйлера и решения задачи Эйлера об эластиках;

д) параллельная программа для антропоморфного (естественного для восприятия человека, не содержащего точки возврата) восстановления изображений.

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

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

Апробация работы. Результаты диссертации докладывались на следующих научных конференциях и совещаниях:

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) Объединенный семинар по оптимизации и управлению Исследовательского центра системного анализа и Исследовательского центра процессов управления ИПС им. А.К. Айламазяна РАН под рук. д.т.н. Цирлина A.M. и д.ф.-м.н. Сачкова Ю.Л., г. Переславль-За-лесский, 2012 г.

3) Семинар кафедры общих проблем управления механико-математического факультета МГУ им. М.В. Ломоносова под рук. члена-корреспондента РАН Зеликина М.И., г. Москва, 2012 г.

4) Семинар лаборатории 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 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Вторая глава изучает аппроксимацию мобильного колёсного робота с прицепом. Рассматриваются две модели, предложенные Ж.-П. Ло-мондом30. Исследуется нильпотентная аппроксимация этих моделей. В

30Laumond J.P. Nonholonomic motion planning for mobile robots, Lecture notes in Control and Information Sciences, 229, Springer, Berlin, Heidelberg, 1998

некоторых естественных координатах она имеет следующий вид:

Q =

/х\

У

Z

\ V )

= щХі + и2Х2, Х\ =

( 1 \ О

2

V о /

/

0

1

X 22 2

\

q = (x,y,z,v) Є :

и = (Ui,U2) Є

Для этой управляемой системы рассматривается соответствующая задача оптимального управления с граничными условиями:

9(0) = <?о = (яо, 2/о, ¿о, «о), = щ = (хь уи ги щ),

и функционалом качества

rt 1

= / С«?

Jo

+ u2) dt —» min,

(2)

(3)

где точка д = (х, у, 2,») Є I4 = М задает состояние системы, терминальное время £1 фиксировано, аи = и2) Є Е2 есть управление.

Сформулированная задача является левоинвариантной субримановой задачей на группе Энгеля для субримановой структуры на Е4, заданной полями Хі, Х2 как ортонормированным базисом31. Задача (1)-(3) служит конкретной моделью для всего класса неголономных инвариантных субримановых задач с вектором роста (2,3,4); например, для систем, описывающих движение колёсного мобильного робота с прицепом (в диссертации описываются системы для двух моделей с различной связкой робота и прицепа).

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

'ІЧ

к уравнению математического маятника :

—asmd,

а

const.

(4)

Интеграл энергии маятника Е = — — асовв Є [—|а|, +оо) определяет

31Аграчев А.А., Сачков Ю.Л. Геометрическая теория управления, Физматлит, М, 2005.

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

33Арнольд В.И. Обыкновенные Дифференциальные Уравнения. М.: Наука, изд. 2, 1975, 240 с.

разбиение фазового цилиндра маятника на подмножества:

С = и7і=1Сі, СпС, = 0, ¿^і, С = {\={9,с,а) | 0 є 51, с, а Є К},

Сі = {Л є С С2 = {Л є С С3 = {А є С С4 = {Л є С С5 = {А Є С С6 = {Л є С С7 = {ХеС

а=£0,Е е(-\а\,\а\)},

а^0,Е = |а|, с ф 0},

а = |а|, с = 0},

а=0, с^О}, а = с = 0}.

Для каждого подмножества С* вычисляется параметризация экстремальных траекторий задачи. Для областей С\ (маятник колеблется) и С'г (маятник вращается) параметризация записывается в эллиптических функциях Якоби34. Если вектор сопряженной переменной Л Є Сі, то формулы в случае а = 1 (для изучения задачи достаточно ограничиться этим случаем) выражаются уравнениями:

х( = 2/с(сп<^ — спір),

= 2к (эп <рь ёп щ — эп <р сіп ір — ^(сп щ + сп ¥>)) >

Щ

V

= — + 2к2 сп2 <руі — 4к2 сп (¿>(бп ^ dn <рг — эп ір dn ір)+ 6

/2 2 1-А:2

+ 2А;2 ( - сп щ гіп щ эп щ - - сп ір гіп (р эп <р + ^2 ¿+

+

2/г — 1 Зк2

(еы-ЕЫ)),

где эп, сп, dn, Е - эллиптические функции Якоби.

Следует отметить, что проекции экстремальных траекторий на плоскость (х, у) суть эйлеровы эластики (изучению этих траекторий посвящена вторая глава).

Экстремальные траектории удовлетворяют лишь необходимому условию максимума. Для исследования оптимальности найденных траекторий используются понятия геометрической теории управления:

34 Уиттекер Ю.Т., Ватсон Дж.Н. Курс современного анализа, — УРСС, М. 2002.

1. Точка разреза — точка, в которой экстремальная траектория теряет глобальную оптимальность. Согласно усиленному условию Лежанд-ра, малые дуги экстремальных траекторий оптимальны: время, когда траектория теряет свою оптимальность называется временем разреза.

2. Точка Максвелла — точка, в которую приходят две различные экстремальные траектории в один момент времени, называемым временем Максвелла. Известно, что после времени разреза траектория перестает быть оптимальной.

3. Сопряженная точка — точка, в которой матрица Якоби экспоненциального отображения вырождается. В первой сопряженной точке экстремальная траектория теряет свою локальную оптимальность.

4. Экспоненциальное отображение — отображение, задающее параметризацию всех экстремальных траекторий с помощью вектора сопряженных переменных и конечного момента времени.

Для поиска точек Максвелла изучаются симметрии экспоненциального отображения. Рассматриваются отражения, сохраняющие поле направлений маятника. Действие отражений продолжается на множество траекторий маятника, а затем и на множество решений полной гамиль-тоновой системы принципа максимума Понтрягина. Вычисляются действия отражений на эластики Эйлера и на конечные точки геодезических qt. Построенные отражения являются симметриями экспоненциального отображения.

Определяются точки Максвелла, соответствующие построенным отражениям (симметриям). Вычисляется первое время Максвелла:

¿МАХ : с — (О.+оо],

Л € Ci 4iax = min(2pi,

А € С2 ¿мах = 2Кк/а,

Л Є С6 => ¿мах

2тг

W

А Є С3 U С4 U С5 U С7 => ¿[1АХ = +оо,

где с, к являются координатами в пространстве сопряженных переменных; рі > 0 — первый корень функции /2(р) = с!прзпр+ (р — 2 Е(р)) спр; К = /05 л/Т^2зїпЧсИ, а = л/Н-

Известно, что время Максвелла ¿мдх задает глобальную верхнюю оценку времени разреза ісМ, поэтому справедлива следующая теорема.

Теорема 1. Для любого А е С

¿ciit(A) ^ ¿мах(А)- (5)

Сопряженная точка является второй причиной потери оптимальности траектории. После первого сопряженного времени i'otlj экстремальная траектория перестает быть локально оптимальной. Для исследования сопряженного времени необходимо изучение знака якобиана экспоненциального отображения. Якобиан выражается через эллиптические функции Якоби. Вычислить вручную якобиан не представляется возможным, не говоря об исследовании его знака.

Упрощенные формулы якобиана вычисляются и анализируются с помощью системы компьютерной алгебры Wolfram Mathematica, которая позволяет оперировать большими объемами формул в символьной форме. Был разработан скрипт, основанный на свойствах эллиптических функций Якоби, который дал основу для доказательства следующей теоремы.

Теорема 2. Для любого А е С

Сj(A) ^ 4ах(А). (6)

С использованием полученной оценки времени разреза (теорема 1) и доказанной оценки сопряженного времени (теорема 2) описана глобальная структура экспоненциального отображения в субримановой задаче на группе Энгеля.

Неподвижные точки симмстрий в образе экспоненциального отображения задают разбиение пространства состояний на подобласти:

M = UMi, ге{1,...,4}, (7)

Mi = {q = (z, у, z, v)\x < 0, г > 0}, М2 = {q = (х, у, z, v)\x < 0, z < 0}, Ms = {q = (x,y,z,v)\x > 0,2 < 0}, M4 = {q = {x,y,Zlv)\x > 0, z > 0}.

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

0(A) = Qv (8)

Для поиска решения А системы (8) с некоторой фиксированной правой частью Q1, разработана программа в системе Mathematica. Программа

прошла тестирование для различных случайных значений (З1 (ряд испытаний по 1000 тестов каждое). Наибольшую сложность представляют корни, расположенные близко к границам подмножеств прообраза экспоненциального отображения, которые соответствуют разбиению образа (7). Для проверки разрешимости систем в этом случае были заданы отдельные наборы тестов, соответствующие корням близ границы прообраза экспоненциального отображения. Прообраз экспоненциального отображения есть открытая область, поэтому было определено его компактное подмножество, для которого программа успешно выполняется. Программа не проходит тесты, соответствующие точкам, которые расположены на расстоянии < Ю-5 от границ кубов, задающих прообраз экспоненциального отображения.

Третья глава посвящена изучению классической задачи Эйлера об эластиках, которая имеет следующую геометрическую формулировку. Даны две точки а, = (хьЫ е К2,г е {0,1}, с закрепленными в них единичными векторами (Е Т^ = 1,г е {0,1}. Требуется найти

гладкую кривую фиксированной длины I, выходящую из точки ао с вектором скорости «о и попадающую в точку аг с вектором скорости у\ (см. рис. 1). Кроме того, на кривую накладывается дополнительное условие: интеграл квадрата кривизны имеет наименьшее значение вдоль искомой кривой:

■¿1

У(*)

Рис. 1: Геометрическая постановка задачи задачи Эйлера об эластиках

Описанная задача может быть также сформулирована как задача оптимального управления в пространстве М = М^ х следующим образом:

rt 1

J = / it2 dt —» min.

Jo

Заметим, что кривизна кривой к = ^/х2 + у2 — \0\ = М-

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

• невырожденные:

(1) инфлексионные,

(2) неинфлексионные,

(3) критические,

• вырожденные:

(4) окружности,

(5) прямые.

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

Функции вычисления эластик объединены в интерфейс для моделирования эластик на базе Wolfram Demonstration Project. В интерфейсе используются естественные параметры, задающие каждый тип эластик (см. скриншот интерфейса на рис. 3). Головной модуль выполняет функции интерфейса. Основными элементами управления в интерфейсе являются ползунки. Например, с помощью ползунка Angle задается начальный угол поворота эластики в() G [0,2п]. Если нажать справа от ползунка на кнопку +, то появится меню для управления ползунком.

SNOSNO

am[bO,k2]

SinfamO]

forml t - 2(form1 EEtO+form2 CNtOk)/r form21 - 2(form2 EEtO- forml CNtOk)/r

EEtO form 1

EE[amt,k2]-EE[amO,k2] (2k2SN02-1)

form 2 CNtO

2k Sqrtfl-k2SN02] SNO Cos[amt]-Cos(amO]

Рис. 2: Схема вычисления функций, задающих инфлексионную эластику

Каждому типу эластик соответствуют определенные параметры (см. рис. 3, блок parameters of elastica):

1. Angle, к, r, Phase, Periods для инфлексионных эластик;

2. Angle, к, г, Phase, Periods для неинфлексионных эластик;

3. Angle, г, bo, Length для критических эластик;

4. Angle, Radius, Periods для окружностей;

5. Angle, Length для прямых.

После основных параметров находятся графические опции (блок graphic options на рис. 3), одинаковые для каждого типа эластики:

• thickness параметр, задающий толщину линии;

• dashing задает пунктирный стиль кривой;

• color отвечает за цвет.

По заданным параметрам интерфейс вычисляет изображение соответствующей эластики и функции на языке Mathematica, определяющие выражение параметризации (блок Parametrization на рис. 3) текущей эластики длиной дуги t.

Euler's elasticae

»parameters of elastica

jnq/e 1.16239

;0®a@0 0

к .........................1..... O.S56

»■graphic options

thickness ■............... ;.........

dashing

4 0.6

/ t t ». t V I O.i \ » s

s \ i \ % / ч i \ t A t \ 0.2 \ 4 4 . \ 1 i t t t ! !

-0.i y>/ \i » i -0.2 \ i -oh

ft I \ / t

___V -.„-"'.о.,

¥ Parameterization

x[c._l :. 0.39714789063478056*(0.4130687614720634*t - 0.56981

Y[t_] 0.9177546256839811.(0. 4130687614720834.t - 0.569801

type of elastica: ©Inflectional ONon-inflectional ©Critical (' Circle CLine

Рис. 3: Интерфейс на сайте http://demonstrations.wolfram.com

В программной среде Mathematica разработана также программа, вычисляющая оптимальные решения в задаче Эйлера об эластиках. В работах Ю.Л. Сачкова35 36 задача оптимального управления об эластиках сведена к решению систем алгебраических уравнений:

Exp(ï/) =9i, V е N, qi е М, (9)

где трехмерное пространство N прообраз экспоненциального отображения, a Exp(f) параметризация эластик при фиксированном t\ = 1,

35Sachkov Yu.L. Maxwell strata in Euler's elastic problem Journal of Dynamical arid Control Systems, v. 14, No. 2, 2008, 169-234.

36Sachkov Yu.L. Conjugate points in Euler's elastic problem, Journal of Dynamical and Control Systems, v. 14, No. 3, 2008, 409-439.

задаваемая экспоненциальным отображением. Образ экспоненциального отображения является полноторием:

М = {(х,у,9)\х2 + у2 <1, deS1}, (10)

9 9

для которого согласно знаку функции Р(х, у, в) = х sin - —у cos — задается разбиение на подмножества. Прообраз экспоненциального отображения разбивается на соответствующие подмножества, в которых система уравнений (9) однозначно разрешима.

В системе gridMathematica был разработан параллельный алгоритм вычисления глобально оптимальной эластики. Для поиска оптимальной эластики необходимо разрешить две идентичные системы с разными ограничениями, вычисление корней можно производить независимо. Кроме того, поиск одного корня можно вести сразу на нескольких узлах: узел, нашедший корень, отправляет результат вычисления на головной узел, который в свою очередь останавливает все остальные вычисления, связанные с поиском этого корня.

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

В таблице 1 приведены результаты решения 300 независимых задач, каждая из которых решается параллельно на нескольких узлах.

Таблица 1: Серия из 300 независимых тестов для задачи Эйлера об эластиках

Число узлов: Время работы Ускорение:

п программы: t, с ti/t

1 20875 1

2 8624 2.4

3 7792 2.6

4 G596 3.1

5 G428 3.2

6 7167 2.9

Для тестирования алгоритма создавался набор случайных точек, для которых необходимо найти оптимальные эластики. Так как алгоритм не является эффективным для большого количества узлов, естественно ре-

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

Известно, что в большинстве случаев, если близки координаты второго конца эластики, то близки и искомые корни системы уравнений. Таким образом, можно в качестве начального приближения задавать корень, вычисленный на предыдущем шаге. При этом время поиска сокращается в десятки раз. Но существуют точки, для которых не годится такого рода начальное приближение. Это - точки, в которые приходят несколько оптимальных эластик (точки Максвелла). Подмножеством таких точек являются точки, задаваемые уравнением Р = 0. Общая формула, с помощью которой можно было бы определить, является ли данная точка точкой Максвелла, не известна. В параллельной программе на кривой выбирается набор точек, удовлетворяющих условию Р = 0. Затем эти точки помещаются в очередь, после чего запускается параллельный счет. Причем первые точки, помещенные в очередь, вычисляются без информации о предыдущем кадре, в отличие от остальных. Поэтому после того как некоторый узел обработал точку д( и выдал результат и3, то в очередь помещается задача, соответствующая следующей точке д{ с начальным приближением гА И так далее, пока все точки не будут обработаны.

Для описанных алгоритмов созданы программы, которые были протестирована на кластере «СКИФ Первенец-М». Кривая, на которой выбираются точки, задавалась с помощью функции с большим количеством точек типа Р = 0. При таком типе входных данных количество дуг, на которые разрезается кривая, достаточно велико. Следовательно, велико и число гранул параллелизма. Ниже приведена таблица 2, демонстрирующая эффективное распараллеливание алгоритма. В каждом испытании было измерено время работы программы Ь, с (см. рис. 4 слева); по этим данным были вычислены ускорение времени работы программы а = ¿х/^ (см. рис. 4 справа). Заметим, что в алгоритме используется метод случайного поиска, поэтому при повторных вычислениях возможны небольшие отклонения во времени выполнения алгоритма (см. ускорения для узлов на рис. 4 справа).

Для произвольной кривой, задающей деформацию правого конца эластики, количество точек вида Р = 0 может быть не велико. Также данная кривая может содержать большое количество других точек разреза, для которых неизвестно аналитическое представление. Эти факторы могут

Рис. 4: Пример времени и ускорения параллельной программы построения анимаций

повлиять на результат распараллеливания.

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

Таблица 2: Тестирование построения анимации из 1000 кадров

Число узлов: Время работы Ускорение:

п программы: t, м ti/t

1 1374 1

2 G93 1.98

3 4G7 2.94

4 355 3.87

5 297 4.G3

б 214 G.42

7 188 7.31

8 173 7.94

Для того чтобы получить представление о поверхности разреза, рассматриваются сечения образа экспоненциального отображения, задаваемые формулой д = const. С помощью программы такие сечения были раскрашены в цвета, соответствующие подобластям прообраза экспоненциального отображения. Границы перехода между цветами задают множество разреза.

Напомним, что множеством разреза называется множество точек, для которых обе эластики (кандидаты на оптимальную), у которых концы и касательные на концах совпадают, имеют одинаковое значение функци-

Рис. 5: Кадры фильма с глобально оптимальными эластиками

Рис. 6: Поверхность разреза в полно-тории

онала упругой энергии.

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

Построенное в рамках этой диссертации изображение множества разреза приведено на рис. 6. Для его построения было решено более полмиллиона задач Эйлера об эластиках с фиксированными граничными условиями, равномерно распределенными в полнотории, задающем множество достижимости задачи. Выполнить такой расчёт было не по силам для одного персонального компьютера. Использовался программный инструмент параллельного вычисления gridMathematica37 на кластере «СКИФ Первенец-М».

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

37 http://wolfram.com/products/gridmathematica

метрии зрения38, а также современные результаты по субримановой геометрии39. Согласно результатам нейрогеометрии зрения, человеческий мозг восстанавливает изофоты (x(f), y(t)) (линии уровня функции яркости изображения) на поврежденных изображениях на основе вариационного принципа

X2 + у2 + о? в2 dt —> min, а > О,

где в = arctg{у/х).

Задача антропоморфного (естественного для восприятия человека) восстановления изображений сводится к левоинвариантной субримановой задаче на группе движений плоскости, которая также доставляет решение задачи оптимального управления колёсным роботом на плоскости, который может двигаться вперед и назад, и вращаться вокруг себя (машина Ридса-Шеппа).

Для решения задачи антропоморфного восстановления изображений разработан алгоритм устранения точек возврата, а также программа на языке С++ с использованием параллельной библиотеки TSim40. Так как поврежденные области на изображении можно восстанавливать независимо, то параллельная программа разбивает области повреждения на группы и принимает задачу восстановления областей из одной группы за гранулу параллелизма. Так как реализованный алгоритм восстановления одной области при практическом использовании решал задачу слишком быстро, пришлось рассматривать гранулы параллелизма, соответствующие различному количеству восстанавливаемых областей. Успешное распараллеливание задачи восстановления изображения возможно только для изображения большого размера с большим количеством областей повреждения.

Программа прошла испытание на кластере blade.botik.ru с использованием 4 узлов по 8 ядер каждый (всего 32 ядра). Пример корректного восстановления изображения приведен на рис. 7. Слева приведено исходное изображение, в центре — поврежденное, справа расположено восстановленное изображение. Был написан скрипт, который производил тестирование алгоритма при различном количестве используемых

3sPctitot J. Neurogeometrie de la vision. Modeles mathématiques et. physiques des architectures fonctionellcs, Editions de Г Ecole Polytechnique, 2008

39Сачков Ю.Л., Ардентов A.A., Маштаков A.П. Параллельный алгоритм и программа восстановления изофот для поврежденных изображений, Программные системы: теория и приложения, v. X, No. 1, 2010, 3-20

40http://wiki.bot ik.ru/TSim/

Рис. 7: Пример восстановления изображения

узлов (ядер). А именно, сначала запускается последовательное выполнение задачи, соответствующее вычислению на одном ядре. Затем последовательно запускается параллельная программа с использованием различного количества узлов (соответственно 8, 16, 24 и 32 ядра). Скрипт строит графики времени вычисления и ускорения для различного количества используемых ядер (см. рис. 8, слева расположен график времени, справа — ускорения).

во

МО »

гоо

150 100 м

Рис. 8: Пример времени вычисления и ускорения программы восстановления изображения в зависимости от количества ядер

Описанные в четвертой главе методы, алгоритмы и программы используются в параллельном программном комплексе для восстановления изображений Opt imal Inpaint ing.

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

з 4 s t 7 • s и и 12 » и is« i? 11 и го и я гз м и «?7» я ю 3t зг t г j < 5 в г в » ie и 12 13 м и te 17 ia и го гг гг гз г« и гв 27 гв и зв и п

шимости и непрерывной завивисмоети корня от правой части системы. Такие системы возникают при решении всех трех рассматриваемых в диссертации задач.

В заключении кратко сформулированы основные результаты, полученные в диссертации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

В рамках проекта Wolfram Demonstration Project был разработан интерфейс для моделирования эластик Эйлера, которые описывают экстремальные траектории в задаче Эйлера об эластиках и в задаче управления мобильным роботом с прицепом.

Для задачи управления аппроксимацией колёсного робота с прицепом получены следующие результаты:

1. параметризация экстремальных траекторий,

2. теоретическое сведение задачи оптимального управления к решению систем алгебраических уравнений,

3. программа для вычисления оптимальных траекторий.

Для задачи Эйлера об эластиках разработан программный комплекс, включающий в себя следующие параллельные программы:

1. вычисление глобально и локально оптимальных траекторий,

2. построение анимации из серии оптимальных траекторий,

3. построение множества разреза, описывающего скрытую симметрию задачи.

Для задачи управления мобильным роботом и задачи Эйлера об эластиках разработан общий гибридный метод и алгоритм решения систем алгебраических уравнений, обладающих свойством однозначной разрешимости и непрерывной зависисимости решений от правой части, к которым сводятся эти задачи. Алгоритм реализован в программной среде Mathematica.

Для задачи антропоморфного восстановления изображений был разработан алгоритм а-регуляцин для устранения точек возврата у восстанавливаемых кривых. Алгоритм был запрограммирован на языке С++ с использованием параллельной библиотеки TSim в рамках программного комплекса Optimallnpainting.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

[1] Ардентов A.A., Сачков Ю.Л. Решение задачи Эйлера об эластиках // Автоматика и телемеханика, No. 4, 2009, с. 78-88. (автора - 6 стр.)

[2] Сачков Ю.Л., Ардентов A.A. Параллельные алгоритмы и программы для моделирования эйлеровых эластик // Программные продукты и системы, No. 4, 2009, с. 71-73. (автора - 1 стр.)

[3] Сачков Ю.Л., Ардентов A.A., Касимов В.М., Маштаков А.П. Восстановление изображений на основе вариационного принципа // Программные продукты и системы, No. 4, 2009, с. 126-127. (автора - 1 стр.)

[4] Ардентов A.A. Экстремальные траектории в нильпотентной субри-мановой задаче на группе Энгеля (случай докритических колебаний маятника) // Современная математика. Фундаментальные направления, No. 42, 2011, с. 29-34.

[5] Apdei imoe A.A., Сачков Ю.Л. Экстремальные траектории в нильпотентной субримановой задаче на группе Энгеля // Математический сборник, Т. 202, No. 11, 2011, с. 31-54. (автора - 12 стр.)

[6] Ардентов A.A., Сачков Ю.Л. Антропоморфное восстановление поврежденных изображений на основе методов субримановой геометрии // Программные системы: теория и приложения : электрон, научи. журн. 2011, No. 4(8), с. 3-15. (автора - б стр.)

[7] Ардентов A.A. Интерфейс для моделирования эластик Эйлера в программной среде Mathematica // Программные системы: теория и приложения : электрон, научн. журн. 2012. Т. 3, № 1(10), с. 31-50.

[8] Сачков Ю.Л., Ардентов A.A., Маштаков А.П. Свидетельство о государственной регистрации программы для ЭВМ Optimallnpainting No2010614762 от 21 июля 2010 г.

1 Введение

1.1 Задачи механики, робототехники и управления.

1.2 Задачи оптимального управления.

1.3 Символьные и численные компьютерные вычисления

1.4 Задачи обработки изображений.

2 Аппроксимация мобильного робота с прицепом

2.1 Модели мобильного робота с прицепом.

2.2 Нильпотентная аппроксимация мобильного робота с прицепом.

2.3 Гамильтонова система принципа максимума Понтрягина и математический маятник.

2.4 Дискретные симметрии экспоненциального отображения.

2.5 Точки Максвелла

2.6 Сопряженное время и симметрии экспоненциального отображения

2.7 Оценка сопряженного времени для случая докритических колебаний математического маятника

2.8 Оценка сопряженного времени для случая посткритических колебаний математического маятника.

2.9 Оценка сопряженного времени для критического и вырожденного случаев

2.10 Сведение задачи к решению системы алгебраических уравнений.

3 Задача Эйлера об эластиках

3.1 Постановка задачи об эластиках.

3.2 Экстремальные траектории в задаче оптимального управления.

3.3 Интерфейс для моделирования эластик в среде Ма1;Ьета1лса.

3.4 Поиск оптимальных решений

3.5 Анимации семейств эластик.

3.6 Множество разреза.

4 Методы, алгоритмы и программы машинной графики: приложение к восстановлению изображений

4.1 Постановка задачи восстановления изображений и метод ее решения

4.2 Субриманова задача на группе движений плоскости.

4.3 Сведение задачи оптимального управления к решению системы уравнений

4.4 Параллельный алгоритм восстановления изображений.

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

1.1 Задачи механики, робототехники и управления

В диссертации рассматриваются следующие задачи механики и робототехники:

1. управление колёсным мобильным роботом с прицепом (см. главу 2),

2. задача о стационарных профилях упругого стержня (классическая задача Эйлера об эластиках, см. главу 3),

3. оптимальное управление машиной Ридса-Шеппа (задача антропоморфного восстановления изображений, см. главу 4).

Существуют разнообразные модели колёсных мобильных роботов с прицепами, которые описываются нелинейными неголономными управляемыми системами с линейным управлением [2-5]. В главе 2 рассматривается аппроксимация колёсного робота с одним прицепом для двух таких моделей (см. раздел 2.1), описанных в работе Ж.П. Ло-монда [6]. Актуальность выбора закона управления, который переводит систему из заданного начального состояния в заданное терминальное состояние при условии минимума выбранной оценки интенсивности управляющих усилий, отмечается в монографии H.H. Красовского [7].

Ж.П. Ломонд указывает, что вычисление допустимой траектории между двумя состояниями неголономной системы является нетривиальной задачей, даже при отсутствии ограничений на управление и минимизируемого функционал. На данный момент не существует общего алгоритма, который бы конструировал для любой неголономной системы решение этой задачи точно или приближенно. Конструктивное решение имеется лишь для систем специального вида. Например, в работе М. Флисса, Дж. Левина, Ф. Мартина и П. Рушона [8] описывается метод управления дифференциально плоскими системами, т. е. системами, допускающими линеаризацию по выходу. Однако эти методы неприменимы напрямую для многих моделей мобильного робота с прицепом и используют специфику конкретной рассматриваемой модели.

Дж. Лаферьер и Г. Суссман [9] предложили метод управления для нильпотентных систем. Управляемая система является нильпотентной, если скобки Ли векторных полей при управлениях обращаются в ноль начиная с некоторого порядка. Такие системы дают нильпотентную аппроксимацию неголономных систем.

Понятие нильпотентной аппроксимации управляемой системы было введено в работе A.A. Аграчёва и A.B. Сарычева [10], а также независимо в работе Х.Хермса [11]. Обычно в качестве локальной аппроксимации используется линеаризация управляемой системы, но для рассматриваемых неголономных систем линеаризация дает очень грубое приближение: ввиду того, что размерность управления меньше размерности состояния, линеаризация не может быть управляемой. Нильпотентная аппроксимация сохраняет структуру управляемости исходных систем. В работе А.Беллаиша [12] описан алгоритм построения нильпотентной аппроксимации. Таким образом, задача управления колёсным мобильным роботом с прицепом сводится к нильпотентной задаче оптимального управления (см. раздел 2.2).

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

Эта задача имеет богатую историю, связанную с именами Якоба Бернулли [13] и Даниила Бернулли [14]: последний сформулировал её как задачу вариационного исчисления и предложил решить Леонарду Эйлеру. Эйлер, впервые рассмотревший эту задачу в 1744 г. [15], получил дифференциальные уравнения для стационарных конфигураций стержня и описал их возможные качественные типы. Эти конфигурации называются эйлеровыми эластиками. Первая параметризация эластик эллиптическими функциями была получена Л. Заалшютцем [16]. Вопрос об оптимальности эластик был поднят в диссертации Макса Борна 1906 г. [17]: будущий нобелевский лауреат доказал отсутствие сопряженных точек на эластиках без точек перегиба, т. е. показал, что все неинфлексионные эластики являются локально оптимальными. Подробное описание истории исследования эластик можно найти в литературе [18-20].

Кроме того, с помощью эластик Эйлера описываются экстремальные, а значит и оптимальные траектории (проекции траекторий на плоскость) для различных задач оптимального управления:

1. нильпотентной субримановой задачи на группе Энгеля, дающей нильпотентную аппроксимацию задачи управления мобильным роботом с прицепом;

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

Различные вопросы, связанные с оптимальностью эластик, рассматривались в работах [20-24]. Однако полностью эта задача оптимального управления до недавнего времени оставалась нерешенной. Окончательное, в определенном смысле, решение задачи Эйлера об эластиках получено Ю.Л. Сачковым [25,26] в 2008 г.

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

Заключение

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

1. параметризация экстремальных траекторий,

2. теоретическое сведение задачи оптимального управления к решению систем алгебраических уравнений,

3. программа для вычисления оптимальных траекторий.

Для задачи Эйлера об эластиках разработан программный комплекс, включающий в себя следующие параллельные программы:

1. вычисление глобально и локально оптимальных траекторий,

2. построение анимации из серии оптимальных траекторий,

3. построение множества разреза, описывающего скрытую симметрию задачи.

Для задачи антропоморфного восстановления изображений был разработан алгоритм а-регуляции для устранения точек возврата у восстанавливаемых кривых. Алгоритм был запрограммирован на языке С++ с использованием параллельной библиотеки TSim в рамках программы Optimallnpainting.

Кроме того, для задачи управления мобильным роботом и задачи Эйлера об эластиках разработан общий гибридный метод и алгоритм решения систем алгебраических уравнений, обладающих свойством однозначной разрешимости и непрерывной зависисимости решений от правой части, к которым сводятся эти задачи. Алгоритм реализован в программной среде Mathematica. И наконец, в рамках проекта Wolfram

Demonstration Project был разработан интерфейс для моделирования эластик Эйлера, которые описывают экстремальные траектории в задаче Эйлера об эластиках и в задаче управления мобильным роботом с прицепом.

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

1. Аграчев А.А., Сачков Ю.Л. Геометрическая теория управления, Физматлит, М., 2005.

2. Sordalen O.J. Feedback Control of Nonholonomic Mobile Robots, doctoral thesis, Department of Engineering Cybernetics, The Norwegian Institute of Technology, 1993.

3. Rouchon P., Fliess M., Levine J., Martin P. Flatness and motion planning: the car with n trailers, Eur. Contr. Conf. (1993) pp. 1518-1522.

4. Barraquand J., Latombe J. Nonholonomic multibody mobile robots: Controllability and motion planning in the presence of obstacles, Algorithmica, Vol. 10, No. 2. (1 October 1993), pp. 121-155.

5. De Luca A., Oriolo G., Samson C. Control of a Nonholonomic Car-Like Robot, in J.-P. Laumond (Ed.) Robot Motion Planning and Control, Lecture Notes in Control and Information Sciences, vol. 229, pp. 171-253, Springer Verlag, London, 1998.

6. Laumond J.P. Nonholonomic motion planning for mobile robots, Lecture notes in Control and Information Sciences, 229, Springer, Berlin, Heidelberg, 1998.

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

8. Fliess M., Levine J., Martin P., Rouchon P. On differential flat nonlinear systems // IFAC NOLCOS Symposium, Bordeaux, France, pp. 408-412, 1992.

9. Laferriere G., Sussmann H.J. A differential geometric approach to motion planning, Nonholonomic Motion Planing, Eds. Zexiang Li and J.F. Canny, Kluwer, 1992.

10. Аграчёв А.А., Сарычев А.В. Фильтрация алгебры Ли векторных полей и ниль-потентная аппроксимация управляемых систем // ДАН СССР, 1987. Т. 295, с. 777-781.

11. Hermes H. Nilpotent and high-order approximations of vector fields systems // SIAM, 1991. Vol. 33, p. 238-264.

12. Bellaiche A. „The tangent space in sub-Riemannian geometry", Sub-Riemannian geometry, A. Bellaiche and J.-J. Risler, Eds., Birkhäuser, Basel, Swizerland, 1996, pp. 1-78.

13. Bernoulli J. Véritable hypothèse de la résistance des solides, avec la demonstration de la corbure des corps qui font ressort // Collected works. Geneva: 1744.

14. Bernoulli D. 26th letter to L. Euler (October, 1742) // Fuss, Correspondance mathématique et physique. St. Petersburg: 1843.

15. Эйлер Л. Приложение I: Об упругих стержнях // Метод нахождения кривых линий, обладающих свойствами максимума либо минимума, или решение изопери-метрической задачи, взятой в самом широком смысле, Гостехтеориздат, Москва-Ленинград, 1934, 447-572.

16. Saalschutz L. Der Belastete Stab Unter Einwirkung Einer Seitlichen Kraft: Auf Grundlage Des Strengen Ausdrucks Fur Den Krümmungsradius, Leipzig, 1880.

17. Born M. Untersuchungen über die Stabiiitat der elastischen Linie in Ebene und Raum, unter verschiedenen Grenzbedingungen, Gottingen, Dieterich, 1906.

18. Truesdell C. The Influence of Elasticity on Analysis: The Classic Heritage // Bulletin American Math. Society. 1983. V. 9. No. 3. pp. 293-310.

19. Timoshenko S. History of Strength of Materials. New-York: McGraw-Hill, 1953.

20. Ляв А. Математическая теория упругости, Л.: ОНТИ, M., 1935.

21. Levyakov S.V., Kuznetsov V.V. Stability analysis of planar equilibrium configurations of elastic rods subjected to end loads, Acta Mechanica, v. 211, 2010, 73-87.

22. Maddocks J.H. Stability of nonlinearly elastic rods, Arch. Rat. Mech. Anal., v. 85, 1984, 311-354.

23. Попов Е.П. Теория и расчет гибких упругих стержней, Наука, М., 1986.

24. Jin M., Bao Z.B. Sufficient conditions for stability of Euler elasticas, Mechanics Research Communications, v. 35, 2007, 193-200

25. Sachkov Yu.L. Maxwell strata in Euler's elastic problem, Journal of Dynamical and Control Systems, v. 14, No. 2, 2008, 169-234.

26. Sachkov Yu.L. Conjugate points in Euler's elastic problem, Journal of Dynamical and Control Systems, v. 14, No. 3, 2008, 409-439.

27. Сачков Ю.Л. Управляемость и симметрии инвариантных систем на группах Ли и однородных пространствах, Физматлит, М., 2007.

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

29. Арнольд В.И. Обыкновенные Дифференциальные Уравнения. М.: Наука, изд. 2, 1975, 240 с.

30. Ахиезер Н.И. Элементы теории эллиптических функций. М.: Наука, 1970.

31. Вершик A.M., Граничина О.А. Редукция неголономных вариационных задач к изопериметрическим и связности в главных расслоениях, Матем. заметки, 49:5 (1991), 37-44.

32. Moiseev J., Sachkov Yu.L. Maxwell strata in sub-Riemannian problem on the group of motions of a plane, ESAIM: COCV, v. 16, 2010, 380-399.

33. Sachkov Yu.L. Conjugate and cut time in sub-Riemannian problem on the group of motions of a plane, ESAIM: COCV, 16 (2010), 1018-1039.

34. 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.

35. Сачков Ю.Л. Оптимальность эйлеровых эластик // Доклады Академии Наук, ноябрь 2007, Т. 417, No 1, 23-25.

36. Wolfram S. Mathematica: A system for doing mathematics by computer, Reading (MA): Addison-Wesley, 1991.

37. Сайт программной системы компьютерной алгебры Wolfram Mathematica: http://www.wolfram.com/mathematica/

38. Ланцош К. Практические методы прикладного анализа, М.: ГИФМЛ, 1961.

39. Демидович Б.П., Марон И.А., Шувалова Э.З. Численные методы анализа — М.: Наука, 1967.

40. Kelley С.Т. Iterative Methods for Linear and Nonlinear Equations, SIAM, Philadelphia, 1995.

41. Гавурин M.K. Лекции по методам вычислений, M.: Наука, 1971.

42. Сайт суперкомпьюетрной программы «СКИФ» союзного государства: http:// skif.pereslavl.ru/skif/

43. Collins G.W. Fundamental Numerical Methods and Data Analysis, II, NASA ADS, 2003, 254 pages.

44. Mumford D. Elastica and computer vision // Algebraic geometry and its applications. C.L.Bajaj, Ed., Springer-Verlag. New-York: 1994, pp. 491-506.

45. Ссылка на сайт Wolfram gridMathematica:http://wolfram.com/products/gridmathematica/

46. Birkhoff G., de Boor C.R. Piecewise polynomial interpolation and approximation // Approximation of Functions. Proc. Sympos. General Motors Res. Lab., 1964. Elsevier. Amsterdam: 1965. pp. 164-190.

47. Golumb M., Jerome J. Equilibria of the curvature functional and manifolds of nonlinear interpolating spline curves // SIAM J. Math. Anal. 1982, v. 13, pp. 421-458.

48. Jerome J. W. Minimization problems and linear and nonlinear spline functions // Existence. SIAM J. Numer. Anal. 1973, v. 10, pp. 808-819.

49. Jerome J. W. Smooth interpolating curves of prescribed length and minimum curvature // Proc. Amer. Math. Soc. 1975, v. 51, pp. 62-66.

50. Jurdjevic V. The geometry of the ball-plate problem // Arch. Rat. Mech. Anal. 1993, v. 124, pp. 305-328.

51. Jurdjevic V. Non-Euclidean elastica // Am. J. Math. 1995, v. 117, pp. 93-125.

52. Linner A. Unified representations of non-linear splines //J. Approx. Theory. 1996, v. 84. pp. 315-350.

53. Manning R.S., Maddocks J.H., Kahn J.D. A continuum rod model of sequence-dependent DNA structure // J. Chem. Phys. 1996, v. 105, pp. 5626-5646.

54. Manning R.S., Rogers K.A., Maddocks J.H. Isoperimetric conjugate points with application to the stability of DNA minicircles // Proc. R. Soc. Lond. A. 1998, v. 454, pp. 3047-3074.

55. Сачков Ю.Л. Экспоненциальное отображение в обобщенной задаче Дидоны, Мат. Сборник, 194 (2003), 9: 63-90.

56. Сачков Ю.Л. Дискретные симметрии в обобщенной задаче Дидоны // Мат. Сборник, 2006, Т. 197, No 2, 95-116.

57. Сачков Ю.Л. Множество Максвелла в обобщенной задаче Дидоны // Мат. Сборник, 2006, Т. 197, No 4, С. 123-150.

58. Сачков Ю.Л. Полное описание стратов Максвелла в обобщенной задаче Дидоны, Математический сборник, т. 197, No 6, 2006, 111-160.

59. Leung Т., Malik J. Contour continuity in region based image segmentationm, 5th. Euro. Conf. Computer Vision, June 1998, Frieburg, Germany.

60. Ссылка на слайды Sarel В., Zelnik-Manor L. „Image Completion: Filling in the Missing Data":http://webee.technion.ac.il/ lihi/Presentations/ImageCompletion.pdf

61. Shah J. Elastica with hinges, Journal of Visual Communication and Image Representation, v. 13, No 1, March, 2002.

62. 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-592.

63. Citti G., Sarti A. A cortical based model of perceptual completion in the roto-translation space, J. Math. Imaging Vision, v. 24, No 3, 2006, 307-326.

64. Duits R., Franken E.M. Left-invariant parabolic Evolutions on SE(2) and Contour Enhancement via Invertible Orientation Scores. Part I: Linear Left-invariant Diffusion

65. Equations on SE(2), Quarterly of Applied Mathematics, v. 68, No 2, June 2008, 255292

66. Petitot J. The neurogeometry of pinwheels as a sub-Riemannian contact structure, J. Physiology, Paris, No 97, 265-309.

67. Petitot J. Neurogeometrie de la vision. Modeles mathematiques et physiques des architectures fonctionelles, Editions de l'Ecole Poly technique, 2008.

68. Сачков Ю.Л., Ардентов А.А., Маштаков А.П. Параллельный алгоритм и программа восстановления изофот для поврежденных изображений, Программные системы: теория и приложения, v. 1, No 1, 2010, 3-20.

69. Сайт параллельной библиотеки TSim для языка С++: http://wiki.botik.ru/TSim/

70. Зеликин М.И. Оптимальное управление и вариационное исчисление, — УРСС, Москва, 2004.

71. Уиттекер Ю.Т., Ватсон Дж.Н. Курс современного анализа, — УРСС, М. 2002.

72. Murray R.M., Sastry, S.S. Steering controllable systems //29th IEEE Conf. Dec. and Control, Honolulu, Hawaii, 1990.

73. Jurdjevic V. Geometric Control Theory, Cambridge University Press, 1997.

74. Montgomery R. A tour of subriemannian geometries, their geodesies and applications, AMS, 2002.

75. Ссылка на сайт проекта Wolfram Demonstration Project: http://demonstrations.wolfram.com

76. Описание автомобиле-подобного робота Lego NXT с управлением с ПК на базе ROS: http: //robocraf t. ru/blog/811. html

77. Сачков Ю.Л. Симметрии и страты Максвелла в задаче об оптимальном качении сферы по плоскости, Математический сборник, т. 201, No 7, 2010, 1029-1091.

78. Ардентов А.А., Сачков Ю.Л. Решение задачи Эйлера об эластиках, Автоматика и телемеханика, 2009, No. 4, 78-88.

79. Ардентов А.А., Сачков Ю.Л. Экстремальные траектории в нильпотентной субри-мановой задаче на группе Энгеля, Математический сборник, Т. 202, No. 11, 2011, с. 31-54.

80. Agrachev А.А. Geometry of optimal control problems and Hamiltonian systems. In: Nonlinear and Optimal Control Theory, Lecture Notes in Mathematics. CIME, 1932, Springer Verlag, 2008, 1-59.

81. Sarychev A.V. The index of second variation of a control system, Matem. Sbornik 113 (1980), 464-486. English transl. in: Math. USSR Sbornik 41 (1982), 383-401.

82. Ардентов А.А. Множество разреза в задаче Эйлера об эластиках // Программные системы: теория и приложения. Сб. трудов конференции, Переславль-Залесский, 2008 г. Переславль-Залесский: Изд-во «Университет города Переславля», 2008. Т. 2. С. 58-66.

83. Анимация No 1 с непрерывной деформацией стержня:http://www.botik.ru/PSI/CPRC/sachkov/GROUP/elastical.avi

84. Анимация No 2 с непрерывной деформацией стержня:http://www.botik.ru/PSI/CPRC/sachkov/GR0UP/elastica2.avi

85. Boscain U., Rossi F. Invariant Carno-Caratheodory metrics on S3, SO(3), SL(2) and Lens Spaces, SIAM Journal on Control and Optimization, v. 47, 2008, 1851-1878

86. Boscain U., Duplaix J., Gauthier J.-P., Rossi F. Anthropomorphic image reconstruction via hypoelliptic diffusion. To appear on SIAM Journal of Control and Optimization.

87. Аграчев А.А., Сарычев А.В. Фильтрации алгебры Ли векторных полей и нильпо-тентная аппроксимация управляемых систем, ДАН СССР, No 295, 1987, 777-781.

88. Hermes H. Nilpotent and high-order approximations of vector field systems, SIAM Review, v. 33, No 2, 1991, 238-264.

89. Вершик A.M., Гершкович В.Я. „Неголономные динамические системы и геометрия распределений", Итоги науки и техники. Современные проблемы математики. Фундаментальные направления. Динамические системы, т. 7, ВИНИТИ, М., 1986.

90. Myasnichenko О. Nilpotent (3,6) Sub-Riemannian Problem, J. Dynam. Control Systems, v. 8, No 4, 2002, 573-597.

91. Myasnichenko O. Nilpotent (n,n(n + 1)/2) sub-Riemannian problem, J. Dynam. Control Systems, v. 8, No 1, 2006, 87-95.

92. Monroy-Perez F., Anzaldo-Meneses A. Nilpotent (n, n(n + 1)/2) sub-Riemannian problem, J. Dynam. Control Systems, v. 12, No 2, 2006, 185-216.

93. Agrachev A.A. Exponential mappings for contact sub-Riemannian structures Journal Dynamic and Control Systems, v. 2, No 3, 1996, 321-358.

94. Agrachev A.A., Bonnard В., Chyba M., Kupka I. Sub-Riemannian sphere in Martinet flat case, J. ESAIM: Control, Optimization and Calculus of Variations, v. 2, 1997, 377-448.

95. Agrachev A., Barilari D. Sub-Riemannian structures on 3D Lie groups, arXiv: 1007.4970, Journal of Dynamical and Control Systems, accepted.

96. Ссылка на интерфейс для моделирования эластик Эйлера:http://demonstrations.wolfram.com/preview.html?draft/47941/000045/ EulersElasticae