WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


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

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

Маштаков Алексей Павлович

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

05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей 05.13.01 Системный анализ, управление и обработка информации (технические наук

и)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук Переславль-Залесский 2012 г.

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

Официальные оппоненты:

Самохин Алексей Васильевич доктор технических наук, доцент Московский государственный Технический университет гражданской авиации, профессор Манита Лариса Анатольевна кандидат физико-математических наук, доцент Московский государственный институт электроники и математики (технический университет), доцент

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

Государственное образовательное учреждение высшего профессионального образования Российский университет дружбы народов

Защита диссертации состоится 25 мая 2012 года в 13 час. на заседании Диссертационного совета ДМ 002.084.01 при ИПС им. А.К.Айламазяна РАН по адресу: 152021, Ярославская область, Переславский район, с. Веськово, ул. Петра I, д.4а.

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

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

Ученый секретарь Диссертационного совета ДМ 002.084.кандидат технических наук С.М. Пономарева

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



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

В настоящее время не существует методов явного решения этой задачи в общем случае. Удовлетворительное решение имеется лишь для некоторых специальных классов систем. Дж. Лаферьер и Г. Суссманпредложили метод управления нильпотентными системами. Р. Мюррей и С. Састри4 исследовали класс систем, которые могут быть преобразованы в цепную форму. М. Флиссом и П. Рушоном5 был предложен метод управления дифференциально плоскими системами. Однако эти методы неприменимы для систем общего положения. В исключительных случаях для управляемых систем можно найти точный закон оптимального управления (в смысле минимума заданного функционала качества).

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

В. Джуржевич, Г. Суссман7, И. Купка8, Ж.П. Готье9, У. Боскаин10 и Laumond J. P., Robot Motion Planning and Control // Lecture Notes in Control and Information Sciences, № 229, p. 343, 1998.

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

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

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

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

Fernandes C., Gurvits L., Li Z. X., A variational approach to optimal nonholonomic motion planning// IEEE Int. Conf. on Robotics and Automation, pp. 680-685, Sacramento, 19Sussmann H. J., Jurdjevic V. Controllability of non-linear systems // J.Diff. Equations, V. 12. p.

95–116, 19Jurdjevic V., Kupka I. Control systems on semi-simple Lie groups and their homogeneous spaces Annales de l’institut Fourier, 31 no. 4, p. 151-179, 19Gauthier J.P., Controllability of right-invariant systems on Semi-simple Lie-groups// Springer-Verlag 122, New Trends in Nonlinear Control Theory, p. 54-64, 19Boscain U., Rossi F., Invariant Carnot–Caratheodory Metrics on S3, SO(3), SL(2), and Lens Spaces// SIAM Journal on Control and Optimization 47, p. 1851, 20Ю.Л. Сачков11, используя геометрические методы теории управления, описали технику решения инвариантных задач оптимального управления на группах Ли с применением принципа максимума Понтрягина12.

Именно эта техника была использована в рассматриваемых в диссертации задачах оптимального управления. Возможны также другие подходы, например, использующие необходимые условия оптимальности, основанные на уравнениях Эйлера-Лагранжа; достаточные условия оптимальности Кротова-Гурмана13 или метод динамического программирования Беллмана14.

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

Однако для приложений обычно достаточно приближенного управления, переводящего систему из начального состояния в терминальное состояние с любой наперед заданной точностью. Общепринятым подходом в данном направлении является разработка программных средств, реализующих итерационный алгоритм поиска приближенного управления. Дж. Лаферьер и Г. Суссман3 предложили итерационный метод поиска приближенного решения, основанный на замене исходной системы ее нильпотентной аппроксимацией (системой простой алгебраической структуры, локально приближающей исходную систему и сохраняющей свойство полной управляемости). Отечественные ученые А.Ю. Горнов15, С.С. Жулин16, В.А. Срочко17 внесли большой вклад в разработку алгоритмов и программных комплексов для решения задач оптимального управления. Однако алгоритмы и программные средства общего назначения встречают трудности при решении задачи управления неголономными системами, которые могут быстро перемещаться в одних направлениях в пространстве состояний, но гораздо медленнее в других направлениях. Современные программные комплексы управления техническими объектами сталкиваются с проблемами управления неголономЮ.Л. Сачков, Экспоненциальное отображение в обобщенной задаче Дидоны// Мат. Сборник, 194, 9, 63–90, 20Л.С. Понтрягин, В.Г.Болтянский, Р.В.Гамкрелидзе, Е.Ф.Мищенко,Математическая теория оптимальных процессов, М.: Наука, 19Гурман В.И., Принцип расширения в экстремальных задачах, M.: Физматлит, 19Беллман Р., Динамическое программирование, М.: Изд-во иностранной литературы, 19Горнов А.Ю., Технология проектирования программных комплексов для задач оптимального управления // Вестник ИрГТУ. - 2004. - Т. 17, № 2, c. 148-1Жулин С.С.,Численное решение задач оптимального управления с помощью системы OPTIMUS // Проблемы динамического управления: Сборник научных трудов факультета ВМиК МГУ Под ред. Ю.С.Осипова, А.В.Кряжимского. 2005. Выпуск 1. C. 158–165.

Срочко В.А., Итерационные методы решения задач оптимального управления, М.:Физматлит, 2000.

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

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

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

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

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

3) разработка математических методов, алгоритмов и программ (в том числе параллельных) приближенного решения двухточечной граничной задачи управления для нелинейных систем с двумерным линейным управлением;

4) программная реализация оптимального синтеза в обобщенной задаче Дидоны и задаче об оптимальном перемещении мобильного робота по плоскости;

5) разработка алгоритмов и программных средств обработки и восстановления изображений на основе результатов, полученных в п. 4.

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

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

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

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

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

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

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

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





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

1) международная конференция по математической теории управления и механике, Суздаль, 2009 г., 2) молодежная конференция Теория управления: новые методы и приложения, Переславль, 2009 г., 3) workshop on Nonlinear Control and Singularities, Toulon, 2010, 4) международная конференция по математической теории управления и механике, Суздаль, 2011 г., 5) международная конференция Управление и оптимизация неголономных систем, Переславль, 2011 г., 6) международная научная конференция студентов, аспирантов и молодых учёных Ломоносов-2011 (награжден грамотой за лучший доклад), Москва, 2011 г., 7) третья традиционная всероссийская молодежная летняя школа Управление, информация и оптимизация (награжден дипломом в номинации Замечательный доклад ), пос. Ярополец, 2011 г.

Результаты диссертации докладывались и обсуждались на научноисследовательских семинарах:

1) семинар по теории управления под рук. проф. Филиппа Жуана, Университет г. Руан, Франция, 2010 г., 2) объединенный семинар по оптимизации и управлению Исследовательского центра системного анализа и Исследовательского центра процессов управления ИПС им. А.К. Айламазяна РАН под рук.

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

Москва, 2012 г.

Научные исследования по теме диссертации были поддержаны следующими грантами РФФИ: 05-01-00703-а ( Исследование задач оптимального управления субримановой геометрии методами геометрической теории управления ), 09-01-00246-а ( Геометрические методы исследования задач оптимального управления с симметриями ), 09-01-90702-моб_ст ( Научная работа российского молодого ученого Маштакова Алексея Павловича в Математическом Институте им. В.А.Стеклова РАН ), 1001-91102-НЦНИ_з ( Участие в Франко-Российском семинаре Геометри” ческая теория управления: методы и приложения“ ), 11-01-16014-моб_з_рос ( Участие в третьей Традиционной всероссийской молодежной летней Школе Управление, информация и оптимиза” ция“ ), 12-01-00913-а ( Новые методы исследования инвариантных задач оптимального управления на группах Ли, с приложениями в классической и квантовой механике и робототехнике ).

Параллельные алгоритмы и программы, разработанные в диссертации, были внедрены при реализации Научно-технической программы Союзного государства Разработка и использование программно-аппаратных средств ГРИД-технологий и перспективных высокопроизводительных (суперкомпьютерных) вычислительных систем семейства СКИФ“, ” 2008-2010.

Получено Свидетельство о государственной регистрации программы для ЭВМ OptimalInpainting №2010614762 от 21 июля 2010 г.






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.
Результаты диссертации были внедрены в образовательный процесс Университета города Переславля им. А.К. Айламазяна (практикум на ЭВМ: приложение к курсу УМФ, работа в Wolfram Mathematica).

Публикации. Все результаты диссертации опубликованы в 8 работах автора, список которых приводится в конце автореферата. Работы [1]–[4] опубликованы в журналах, рекомендованных ВАК РФ.

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

Структура и объем диссертации. Диссертация состоит из четырех глав (первая из них является введением) и заключения. Главы разбиты на 20 пунктов. Основной текст диссертации составляет 135 страниц и включает 47 рисунков и 3 таблицы. Библиография включает 68 наименований.

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

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

q = u1(t)X1(q) + u2(t)X2(q), (1) где пространство состояний Q q это связное гладкое многообразие, управление (u1, u2) R2 неограничено, а гладкие векторные поля X1, Xудовлетворяют условию полного ранга на многообразии Q18.

Управляемые системы вида (1) возникают в задачах о качении твердых тел19. Диссертация посвящена исследованию систем с пятимерным и А.А. Аграчев, Ю.Л. Сачков, Геометрическая теория управления, М.: Физматлит, 391 с., 20Bicchi A., Prattichizzo D., Sastry S. Planning motions of rolling surfaces//IEEE Conf. on Decision and Control, 19трехмерным состоянием. Конкретными примерами пятимерных систем такого вида являются система, моделирующая качение без прокручиваний и проскальзываний шара по плоскости, и система, моделирующая движение мобильного робота с двумя прицепами по плоскости. Конкретным примером трехмерной системы вида (1) является система, моделирующая движение мобильного робота по плоскости.

Для системы (1) исследуется двухточечная граничная задача управления:

q(0) = q0, q(T ) = q1, (2) где q0 Q начальное состояние, а q1 Q терминальное состояние системы (1). Задача управления (1),(2) рассматривается в следующих постановках:

1) конструктивная задача управления (или задача планирования движений1), в которой требуется найти управление (u1(t), u2(t)) из заданного класса функций, под действием которого система (1) переходит из начального состояния q0 в терминальное состояние q1 с любой наперед заданной точностью.

2) задача оптимального управления, в которой минимизируется интеграл действия T u2(t) + u2(t) dt min. (3) 1 Требуется найти управление (u1(t), u2(t)), под действием которого система (1) переходит из начального состояния q0 в терминальное состояние q1 так, чтобы функционал (3) принимал минимальное значение. В обоих постановках терминальное время T закреплено.

В диссертации исследуется конструктивная задача управления для произвольных пятимерных систем (1) в случае общего положения и следующие задачи оптимального управления:

1) задача об оптимальном качении шара по плоскости (глава 2), 2) обобщенная задача Дидоны (глава 3), 3) задача об оптимальном перемещении мобильного робота по плоскости (глава 4).

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

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

Задача об оптимальном качении шара по плоскости ставится следующим образом: по заданным двум точкам на плоскости (A(x0, y0) и B(x1, y1)) и двум ориентациям шара в трехмерном пространстве (R0 и R1) требуется найти кратчайшую кривую (t) = (x(t), y(t)), соединяющую A и B, при качении по которой ориентация шара переходит из R0 в R1. Управлением является скорость центра шара. Допустимое качение можно представить следующим образом: шар накрывается сверху плоскостью, параллельной плоскости качения, которая двигается поступательно в направлениях, параллельных плоскости качения. Получающееся при этом движение является качением без прокручиваний и проскальзываний.

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

Задача об оптимальном качении шара по плоскости формализуется в виде следующей задачи оптимального управления:

= u1, = u2, q0 = (q2u1 - q1u2), Q = (x, y, q) R2 S3, q1 = (q3u1 + q0u2), (u1, u2) R2, q2 = (-q0u1 + q3u2), q3 = (-q1u1 - q2u2), где (x, y) R2 точка контакта шара и плоскости (проекция центра шара на плоскость качения), а (q0, q1, q2, q3) S3 кватернион единичPetitot J., The neurogeometry of pinwheels as a sub-Riemannian contact structure // J. Physiology, №97, p. 265-309, Paris, 20Sang S., Zhao J., Wu H., Chen S., An Q., Modeling and Simulation of a Spherical Mobile Robot In:

Computer Science and Information Systems,v. 7, № 1, p. 51–62, 20Li Z., Canny J. Motion of two rigid bodies with rolling constraint//IEEE Trans. on Robotics and Automation, (1), 6, p. 62–72, 19ной длины, задающий ориентацию шара в пространстве.

Граничные условия закреплены:

Q(0) = Q0, Q(T ) = Q1.

Критерий оптимальности имеет вид:

T T T 2 + 2 dt = u2 + u2 dt min u2 + u2 dt min.

1 2 1 0 0 Задача об оптимальном качении шара по плоскости без прокручиваний и проскальзываний была поставлена в работе Дж.Хаммерсли23 (1983 г.).

А.Артурс и Дж.Уолш24 в 1986 г. доказали, что уравнения для экстремальных траекторий в этой задаче интегрируемы в эллиптических функциях. В 1990 г. З. Ли и Дж. Кэнни21 исследовали полную управляемость системы. В.Джурджевич25 (1993 г.) показал, что при оптимальном качении точка контакта шара и плоскости движется по эластикам Эйлера (стационарным конфигурациям упругого стержня на плоскости), и описал возможные типы качения шара. Далее Ю.Л. Сачков26 в 2010 г.

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

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

= c, = -r sin , = = 0. (4) Гамильтонова система принципа максимума Понтрягина упрощается при J.M. Hammersley. Oxford commemoration ball. In: Probability, Statistics and Analysis, pp. 112–142.

London Math. Soc. lecture notes, ser. 79 (1983) A.M. Arthurs, G.R.Walsh. On Hammersley’s minimum problem for a rolling sphere //Math. Proc.

Cambridge Phil. Soc., 99, 529–534, 19V. Jurdjevic, The geometry of the plate-ball problem, Arch. Rat. Mech. Anal., v. 124 (1993), 305–3Сачков Ю.Л. Симметрии и страты Максвелла в задаче об оптимальном качении сферы по плоскости // Матем. Сборник, 2010, T. 201, № 7, 99-1следующей замене переменных:

(t, , c, , r, x, y, u1, u2, q0, q1, q2, q3) (s, , d, , m, x, y, 1, 2, q0, q, q2, q3), s = mt, d = c/m, m = r, u1 1 cos - sin = A(), где A() =.

u2 2 sin cos q0 = q0, x x q1 q = A(), = A(), y y q2 q q3 = q3.

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

s x(s) = + O(2), y(s) = (0 sin s + d0(1 - cos s)) + O(2), 0 m m s s q0(s) = cos + O(2), q2(s) = - sin + O(2), 0 2m 2m 1 s s q1(s) = m cos sin s - (1 + cos s) sin 0+ 2(m2 - 1) 2m 2m 1 s s + m(1 - cos s) cos - sin s sin d0 + O(2), 2(m2 - 1) 2m 2m 1 s s q3(s) = (-1 + cos s) cos + m sin s sin 0+ 2(m2 - 1) 2m 2m 1 s s + sin s cos - m(1 + cos s) sin d0 + O(2), 2(m2 - 1) 2m 2m где 0 = 0 + d2 0.

Кривая (x, y) с точностью до O(2), а потому и исходная кривая (x, y), есть синусоида малой амплитуды. Сложность выражений асимптотиm ки кватерниона связана с вхождением в формулы тригонометрических функций различной частоты. С этим связано существование резонансных моментов времени, когда графики асимптотик первого времени Максвелла t1(m) и t2(m), имеют вертикальные касательные.

Причиной потери глобальной оптимальности является наличие точки Максвелла на экстремальной траектории. Точкой Максвелла называется точка в пространстве состояний, в которую приходят две разные экстремальные траектории, выходящие из одного начального состояния и имеющие одинаковое значение функционала качества. Соответствующее значение параметра на экстремальной траектории называется временем Максвелла. Отображение, переводящее вектор сопряженных переменных = (0, d0, , m) и момент времени t в конечную точку экстремальной траектории Q(t) называется экспоненциальным отображением в задаче оптимального управления и обозначается Exp : (, t) Qt.

Множество пар (, t) в прообразе экспоненциального отображения, соответствующих точкам Максвелла в пространстве состояний, называется множеством Максвелла в прообразе экспоненциального отображе ния и обозначается MAX = {(, t)| = : Qs Qs, Qt = Qt, Qs = Exp(, s), Qs = Exp(, s)}. Ю.Л. Сачков25 исследовал симметрии экспоненциального отображения и получил уравнения, определяющие множества Максвелла MAX1 и MAX2 для невырожденных эластик:

(1) q3(t) = 0 для эластик, нецентрированных в точке перегиба;

(2) (xq1 + yq2)(t) = 0 для эластик, нецентрированных в вершине.

В диссертации показано, что уравнения, задающие множества Максвелла MAX1 (1) и MAX2 (2), в асимптотическом случае равносильны следующим:

p p g1(p, m) = cos sin p - m cos p sin, m m p p g2(p, m) = mp cos sin p - p cos p + m2 - 1 sin p sin, m m s m (0, 1) (1, +), p = > 0.

Требуется при любом m (0, 1) (1, +) найти или возможно точнее оценить величину pi(m) = min{p > 0|gi(p, m) = 0}, где i = 1, 2.

Основные результаты по этой задаче сведены в теорему 1 и теорему 2.

Исследовано взаимное расположение графиков функций p1(m) и p2(m) (теорема 3). Возврат к исходному времени t дает утверждения для первых времен Максвелла t1(m) и t2(m).

Причиной потери локальной оптимальности является наличие сопряженной точки на экстремальной траектории. Момент времени tconj, в который экстремальная траектория достигает первой сопряженной точки, называется первым сопряженным временем. Приближенные вычисления показывают, что функции t1(m) и t2(m) являются границами первого сопряженного времени tconj(m) вдоль экстремальных траекторий, см. рис. 1.

t m 0.0 0.5 1.0 1.5 2.0 2.5 3.t1(m) tconj(m) t2(m) Рис. 1: Графики функций t1(m), tconj(m), t2(m) Отметим, что в родственных задачах оптимального управления (субриманова задача в случае Мартине27, обобщенная задача Дидоны11, задача Эйлера об эластиках28, задача об оптимальном перемещении мобильного робота на плоскости29) глобальное поведение аналогичных времен Максвелла t1(), t2(), гораздо проще, чем асимптотика t1(m), t2(m) в задаче о качении шара по плоскости. Это отражает более сложный характер данной задачи, по сравнению с указанными родственными задачами. Учитывая также сложность параметризации экстремальных траекторий в данной задаче, представляется затруднительным получить ее точное решение. Однако на основе полученных результатов возможна разработка алгоритма и программы приближенного решения задачи о качении шара по плоскости.

A. Agrachev, B. Bonnard, M. Chyba, I. Kupka, Sub-Riemannian sphere in Martinet flat case.// J. ESAIM: Control, Optimization and Calculus of Variations, v.2, 377–448, 19Yu. L. Sachkov, Maxwell strata in Euler’s elastic problem// Journal of Dynamical and Control Systems, Vol. 14, No. 2 (April), pp. 169–234, 20I. Moiseev, Yu. L. Sachkov, Maxwell strata in sub-Riemannian problem on the group of motions of a plane, ESAIM: COCV, Vol. 16, pp. 380–399, 20В главе 3 рассматривается конструктивная задача управления пятимерными системами с двумерным линейным управлением:

q = u1(t)X1(q) + u2(t)X2(q), (5) q(0) = q0, q(T ) = q1, (6) где пространство состояний Q q это связное пятимерное гладкое многообразие, управление принимает значения на двумерной плоскости (u1, u2) R2, а гладкие векторные поля X1, X2 удовлетворяют условию полного ранга на многообразии Q. Условие полного ранга гарантирует, что система (5) вполне управляема, то есть для любых состояний q0, q1 Q существует траектория системы (5), удовлетворяющая условиям (6). В настоящее время не существует методов явного решения задачи (5), (6) в общем случае. Удовлетворительное решение имеется лишь для некоторых специальных классов систем3. Тем не менее такие задачи возникают в инженерии1, где достаточно приближенного решения, погрешность которого не превышает наперед заданной. Конкретными примерами систем вида (5), которые представляют самостоятельный интерес из-за своего прикладного значения в робототехнике, являются система, моделирующая качение без прокручиваний и проскальзываний шара по плоскости, и система, моделирующая движение машины с двумя прицепами по плоскости. В работе предлагается метод конструирования управлений (u1(t), u2(t)), переводящих систему (5) из начального состояния qв терминальное состояние q1 с любой наперед заданной точностью > 0, то есть в такое состояние q1, что (q1, q1) < , где расстояние на мно гообразии Q. Например, если Q область в R5, то = (qi - qi 1)2.

i=Системы вида (5) характеризуются тем, что размерность управлений меньше размерности пространства состояний: 2 = dim R2 < dim Q = 5, однако при выполненном условии полного ранга (ситуация общего положения) любые точки пространства состояний могут быть соединены траекторией системы. В теории управления такие системы называются вполне неголономными. Нелинейные системы (5), линейно зависящие от управлений, количество которых меньше, чем размерность пространства состояний, характеризуются тем, что возможность перемещения неодинакова по различным направлениям. В силу этой анизотропии пространства состояний, задача управления для таких систем весьма нетривиальна.

В данной работе представлен способ отыскания приближенного решения задачи (5), (6). Задача поиска приближенного решения двухточечной граничной задачи управления понимается в следующем смысле.

Имеется исходная система в начальном состоянии q0; требуется найти управление, переводящее систему в терминальное состояние q1 с наперед заданной точностью > 0. Предлагается метод, основанный на построении нильпотентной аппроксимации30. Идея метода заключается в том, что исходная система приближается нелинейной системой более простой структуры, для которой точно решается задача управления. Точное решение задачи управления нильпотентной системой дает приближенное решение исходной задачи управления в малой окрестности целевой точки. Метод нильпотентной аппроксимации применим к задачам управления общего вида; существенно только уметь решать задачу управления для нильпотентной аппроксимации.

Алгоритм приближенного решения задачи (5), (6) выглядит следующим образом:

1. в окрестности целевой точки строится аппроксимирующая система;

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

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

Локальное приближение управляемой системы другой, более простой системой, широко используется в теории управления. Обычно в качестве локальной аппроксимации используется линеаризация управляемой системы. Однако для линейных по управлению систем вида (5) линеаризация дает слишком грубое приближение. Так как размерность управления меньше размерности состояния, то линеаризация не может быть вполне управляемой. Естественную замену линейной аппроксимации в этом случае доставляет нильпотентная аппроксимация наиболее простая система, сохраняющая структуру управляемости исходной системы. Понятие нильпотентной аппроксимации управляемых систем было введено незаBellaiche A., Laumond J. P., Chyba M., Canonical nilpotent approximation of control systems:

application to nonholonomic motion planning// 32nd IEEE Conf. on Decision and Control, 19висимо А. А. Аграчевым и А. В. Сарычевым31, и Х. Хермсом32. В работе был использован алгоритм вычисления нильпотентной аппроксимации, предложенный А. Беллаишем33, конкретизированный для систем (5) и дополненный переходом в систему координат, в которой нильпотентная аппроксимация имеет канонический вид:

1 = u1, 2 = u2, y R5. (7) 3 = (y1u2 - y2u1), 1 2 4 = (y1 + y2)u2, 2 5 = -1(y1 + y2)u1, Для построения приближенного решения исходной задачи (5), (6) требуется найти управления, переводящие систему (7) из произвольного состояния y0 в начало координат:

y(0) = y0, y(T ) = (0, 0, 0, 0, 0). (8) Управление ищется в классах кусочно-постоянных функций и оптимальных для нильпотентной системы управлений. С использованием системы Wolfram Mathematica было показано, что для решения задачи управления системой (7), (8) достаточно управлений с тремя точками переключения:

i, при t [0, T ], , при t (T, ], T i 4 ui = где i = 1, 2.

i, при t (T, 3T ], 2 , при t (3T, T ], i Получается трехпараметрическое семейство решений. Показатель Amp = max(|i|, |i|, |i|, |i|) характеризует величину отклонения искомой траектории от постоянной траектории. Свободные параметры фиксируются в соответствии с критерием Amp min.

Добавление к задаче (7), (8) естественного интегрального критерия оптимальности (минимальность функционала субримановой длины) T u2(t) + u2(t)dt min (9) 1 Аграчев А.А., Сарычев, А.В., Фильтрация алгебры Ли векторных полей и нильпотентная аппроксимация управляемых систем // ДАН СССР, т. 295, с. 777–781, 19Hermes H., Nilpotent and high-order approximations of vector fields systems // SIAM, v. 33, p.

238–264, 19Bellaiche A., The tangent space in sub-Riemannian geometry, Sub-Riemannian Geometry, Eds. A.

Bellaiche and J. J. Risler, Basel, Swizerland, Birkhuser, p. 1–78, 19дает известную в теории управления обобщенную задачу Дидоны. Эта задача имеет богатую историю и была детально теоретически изучена Ю.Л. Сачковым34. Основным результатом теоретических исследований явилось описание структуры экспоненциального отображения и первых времен Максвелла вдоль экстремальных траекторий. На основе этого результата задача оптимального управления (7)–(9) была сведена к задаче решения пяти алгебраических уравнений в неэлементарных функциях с пятью неизвестными. Явно решить эту систему не представляется возможным ввиду сложности получившихся формул, поэтому в данной работе используются численные методы. Для построения оптимального синтеза в задаче (7)–(9) требуется решить систему алгебраических уравнений P (u, v, k) = P1, (10) Q(u, v, k) = Q1, R(u, v, k) = R1, относительно (u, v, k) при заданной правой части P1, Q1, R1. Известно, что при произвольной правой части (за исключением особых множеств меньшей размерности) система имеет единственный корень. В диссертации предложен генетический алгоритм решения системы (10).

Рассматриваемый в работе метод приближенного решения двухточечной задачи управления (5), (6) реализован в виде параллельного программного комплекса MotionPlanning (см. Рис. 2) решения задачи (5), (6). Он является дополнительным пакетом для системы Wolfram Mathematica (MotionPlanning.m) и состоит из следующих функциональных модулей:

• NilpotentApproximation строит нильпотентную аппроксимацию NA системы (5) и возвращает замену переменных, в которых NA имеет канонический вид (7);

• CPControl решает задачу (5), (6) в классе кусочно-постоянных управлений;

• OptimalControl решает задачу (5), (6) в классе оптимальных для нильпотентной системы (7) управлений. Пользователь может легко организовать параллельное вычисление корня на нескольких ядрах процессора;

Ю.Л. Сачков, Полное описание стратов Максвелла в обобщенной задаче Дидоны, Матем. Сборник, т. 197, № 6, с. 111–160, 20Начало xs (символьное обозначение переменных), X1(xs), X2(xs) (векторные поля при управлениях), q0, q1 (начальное и целевое состояния), eps (точность), T(конечный момент времени), U (класс управлений) NilpotentApproximation2(Построение нильпотентной аппроксимации NA) U=CP Выбран класс U=OC кусочно-постоянных Выбран класс управлений оптимальных управлений Switch U Выбор класса функций, CPControl235 OptimalControl2в котором ищется управление Вывод результатов:

u1(t), u2(t) (найденные управления), q(t) (соответствующая траектория) Конец Рис. 2: Структура программы MotionPlanning • дополнительные функции программы MotionPlanning.

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

В главе 4 описывается программное обеспечение, разработанное для проверки подхода нейрофизиологов зрения к задаче восстановления поврежденных изображений антропоморфным способом. Задача восстановления поврежденных изображений является одной из актуальных проблем компьютерной графики, реставрации фотографии, фильмов и живописи. Для ее решения разработан ряд методов, многие из которых основаны на применении вариационного исчисления и оптимального управления35. Подход, используемый в данной главе, основан на положениях одного из новых направлений нейрофизиологии зрения нейрогеометрии, а также на недавних результатах по субримановой геометрии. На основе результатов этих исследований на языке C++ разработан параллельный программный комплекс OptimalInpainting ( Оптимальное Восстановление Изображений ) для восстановления серии изофот (линий постоянной яркости) на поврежденных штриховых (бинарных) и полутоновых изображениях.

Важным открытием нейрофизиологии зрения начала нынешнего века является геометрическая структура, соответствующая первичной зрительной коре головного мозга человека. Установлено36, что для сохранения изображений первичная кора моделирует контактную структуру {(x, y, p)} = D RP на поверхности сетчатки глаза D R2. Оказалось, что для эффективной обработки изображений мозгу человека выгоднее сохранять контур не в виде набора последовательных точек (xi, yi), а в виде набора штрихов (xi, yi, pi), в пределе в виде непрерывной кривой (x(t), y(t), p(t)), p = dy/dx. Если часть кривой повреждена или скрыта от наблюдения, то недостающая дуга восстанавливается на основе следующего вариационного принципа: восстанавливающая дуга должна иметь минимальную евклидову длину в пространстве (x, y, ), = arctg p:

2 + 2 + 22 dt min, (11) где R масштабирующий коэффициент, служащий для выбора естественной (соответствующей устройству сетчатки глаза) метрики на плоскости {(x, y)}.

Этот принцип положен в основу метода восстановления скрытой дуги.

Описанный способ восстановления кривой обладает важным свойством Chan T.F., Kang S.H., Shen J.,Euler’s elastica and curvature based inpainting // SIAM Journal of Applied Math., v. 63,№ 2, p. 564–592, 20Petitot J., Neurogeometrie de la vision. Modeles mathematiques et physiques des architectures fonctionelles, Editions de l’Ecole Polytechnique, 20инвариантности относительно движений плоскости: при поворотах и параллельных переносах плоскости решения задачи оптимального управления переходят в решения, поэтому форма восстанавливаемой кривой не зависит от положения и ориентации изображения на плоскости.

Кривые, удовлетворяющие вариационному принципу (11), являются оптимальными траекториями мобильного робота на плоскости:

= u cos , = u sin , = v, (12) (x, y) R2, [0, 2], (u, v) R2, (13) (x(0), y(0), (0)) = (0, 0, 0), (x(T ), y(T ), (T )) = (x1, y1, 1), (14) T u2 + 2v2dt min. (15) Для проверки предложенного подхода к задаче восстановления контуров поврежденного изображения был разработан программный комплекс OptimalInpainting. Он предназначен для восстановления поврежденных изображений портретов линий уровня гладких функций двух переменных антропоморфным (естественным для человека) способом.

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

1. создание изображения по аналитическим данным, заданным пользователем;

2. порождение повреждений с параметрами, определяемыми пользователем;

3. восстановление изофот на изображениях в последовательном или параллельном режимах.

Структура программного комплекса OptimalInpainting изображена на Рис. 3. Ядром комплекса является модуль GlobalSolver, вычисляющий восстанавливающую изофоту изображения, как решение задачи (12)– (15). Параллельный модуль CreateOriginal создает исходное растровое изображение портрета линий уровня функции F (x, y). Модуль CreateCorrupted наносит повреждения, определяемые пользователем, на исходное изображение. Параллельный модуль CreateRestored восстанавливает поврежденное изображение, дополняя недостающие фрагменты линий уровня, изофотами, параметры которых определяются из граничных условий модулем GlobalSolver. Функциональные модули разработаны на языке C++ с использованием следующих библиотек: libgsl (для вычисления неэлементарных функций и численного решения системы алгебраических уравнений), libpng (для работы с растровыми изображениями в формате PNG) и libgomp (для распараллеливания процесса вычислений по технологии OpenMP). Интерфейс комплекса разработан на языке tcl/tk. Разработанный программный комплекс OptimalInpainting Рис. 3: Структура программного комплекса OptimalInpainting доказывает работоспособность метода антропоморфного восстановления изображений, предложенного нейрофизиологами зрения.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ 1) В задаче об оптимальном качении шара по плоскости без прокручиваний и проскальзываний получена асимптотика экстремальных траекторий и первых времен Максвелла. Из аналитических функций простой структуры сконструированы двусторонние оценки для первых времен Максвелла в асимптотическом случае. Получена верхняя оценка для времени разреза на траекториях вблизи исследуемой асимптотики.

2) Разработан итерационный алгоритм приближенного решения двухточечной граничной задачи управления для нелинейных пятимерных систем с двумерным линейным управлением.

3) Создана программная реализация оптимального синтеза в обобщенной задаче Дидоны (параллельная программа) и задаче о перемещении мобильного робота на плоскости.

4) Разработан пакет программ MotionPlanning для приближенного решения задач управления с приложением к задачам робототехники.

5) Разработан параллельный программный комплекс OptimalInpainting для восстановления поврежденных бинарных или полутоновых изображений, заданных портретами линий уровня функций двух переменных.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ [1] Маштаков А.П. Асимптотика экстремальных кривых в задаче о качении шара по плоскости // Современная математика. Фундаментальные направления, 2011, Том 42, с. 158-165.

[2] Маштаков А.П., Сачков Ю.Л. Экстремальные траектории и точки Максвелла в задаче об оптимальном качении сферы по плоскости // Мат. сборник, 2011, 202:9, с. 97-120. (автора 16 стр.) [3] Маштаков А.П. Параллельный программный комплекс решения неголономных задач управления// Программные продукты и системы, 2012, № 1, с. 146-151.

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

[6] Сачков Ю.Л., Ардентов А.А., Маштаков А.П. Конструктивное решение задачи управления на основе метода нильпотентной аппроксимации// Программные системы: теория и приложения // Труды международной конференции Программные системы: теория и приложения, 2009, т. 2, с. 5-23. (автора 8 стр.) [7] Сачков Ю.Л., Ардентов А.А., Маштаков А.П. Параллельный алгоритм и программа восстановления изофот для поврежденных изображений. Программные системы: теория и приложения, 2010, т. 1, с. 3-20. (автора 2 стр.) [8] Сачков Ю.Л., Ардентов А.А., Маштаков А.П. Свидетельство о государственной регистрации программы для ЭВМ OptimalInpainting №2010614762 от 21 июля 2010 г.

Авторефераты по всем темам  >>  Авторефераты по техническим специальностям





© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.