Алгоритмическое и программное обеспечение задач управления и обработки изображений тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Ардентов, Андрей Андреевич

• Ардентов, Андрей Андреевич
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Ардентов, Андрей Андреевич

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 был разработан интерфейс для моделирования эластик Эйлера, которые описывают экстремальные траектории в задаче Эйлера об эластиках и в задаче управления мобильным роботом с прицепом.

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

Список литературы диссертационного исследования кандидат технических наук Ардентов, Андрей Андреевич, 2012 год

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