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

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

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

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

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

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

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

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

1 7 МАЙ 2012

005044Э**

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

005044322

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

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

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

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

Самохин Алексей Васильевич доктор технических наук, доцент

Московский государственный Технический университет гражданской авиации, профессор

Манита Лариса Анатольевна

кандидат физико-математических наук, доцент

Московский государственный институт электроники и математики (технический университет), доцент

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

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

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

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

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

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

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

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

Ученый секретарь

Диссертационного совета ДМ 002.СО/| т

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

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

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

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

1Laumond J. P., Robot Motion Planning and Control // Lecture Notes in Control and Information Sciences, № 229, p. 343, 1998.

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

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

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

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

6Fernandes 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, 1991

7Sussmann H. J., Jurdjevic V. Controllability of non-linear systems // J.Diff. Equations, V. 12,—p. 95-116, 1972

8Jurdjevic 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, 1981

9Gauthier J.P., Controllability of right-invariant systems on Semi-simple Lie-groups// Springer-Verlag 122, New Trends in Nonlinear Control Theory, p. 54-64, 1989

10Boscain 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, 2008

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

Точное решение двухточечной граничной задачи управления рассматриваемыми системами в общем случае является открытой проблемой. Однако для приложений обычно достаточно приближенного управления, переводящего систему из начального состояния в терминальное состояние с любой наперед заданной точностью. Общепринятым подходом в данном направлении является разработка программных средств, реализующих итерационный алгоритм поиска приближенного управления. Дж. Лаферьер и Г. Суссман3 предложили итерационный метод поиска приближенного решения, основанный на замене исходной системы ее нильпотентной аппроксимацией (системой простой алгебраической структуры, локально приближающей исходную систему и сохраняющей свойство полной управляемости). Отечественные ученые А.Ю. Горнов15, С.С. Жулин16, В.А. Срочко17 внесли большой вклад в разработку алгоритмов и программных комплексов для решения задач оптимального управления. Однако алгоритмы и программные средства общего назначения встречают трудности при решении задачи управления неголоном-ными системами, которые могут быстро перемещаться в одних направлениях в пространстве состояний, но гораздо медленнее в других направлениях. Современные программные комплексы управления техническими объектами сталкиваются с проблемами управления неголоном-

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

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

13Гурман В.II., Принцип расширения в экстремальных задачах, М.: Физматлит, 1997

14Беллман Р., Динамическое программирование, М.: Изд-во иностранной литературы, 1960

15Горнов А.Ю., Технология проектирования программных комплексов для задач оптимального управления // Вестник ИрГТУ. - 2004. - Т. 17, № 2, с. 148-153

16Жулин С.С., Численное решение задач оптимального управления с помощью системы ОРТ1М113 // Проблемы динамического управления: Сборник научных трудов факультета ВМиК МГУ Под ред. Ю.С.Осипова, А.В.Кряжимского.— 2005.— Выпуск 1,—С. 158-165.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4) семинар лаборатории 7 ИПУ РАН под рук. д.т.н. Поляка Б.Т., г. Москва, 2012 г.

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

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

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

Результаты диссертации были внедрены в образовательный процесс Университета города Переславля им. А.К. Айламазяна (практикум на ЭВМ: приложение к курсу УМФ, работа в Wolfram Mathematical

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

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

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

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

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

q = m(t)Xi(q) + u2(t)X2(q), (1)

где пространство состояний Q Э q — это связное гладкое многообразие, управление (ui, 112) 6 R2 неограничено, а гладкие векторные поля Х2 удовлетворяют условию полного ранга на многообразии Соуправляемые системы вида (1) возникают в задачах о качении твердых тел19. Диссертация посвящена исследованию систем с пятимерным и

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

"Bicchi A., Prattichizzo D., Sastry S. Planning motions of rolling surfaces//IEEE Conf. on Decision and Control, 1995

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

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

где 9° € ф — начальное состояние, а д1 6 <3 — терминальное состояние системы (1). Задача управления (1),(2) рассматривается в следующих постановках:

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

2)'задача оптимального управления, в которой минимизируется интеграл действия

Требуется найти управление под действием которого

система (1) переходит из начального состояния (р в терминальное состояние д1 так, чтобы функционал (3) принимал минимальное значение. В обоих постановках терминальное время Т закреплено.

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

1) задача об оптимальном качении шара по плоскости (глава 2),

2) обобщенная задача Дидоны (глава 3),

3) задача об оптимальном перемещении мобильного робота по плоскости (глава 4).

Оптимальные траектории мобильного робота на плоскости удовлетворяют вариацонному принципу, открытому нейрофизиологами зрения при

в(0) = 9°, 9(Т) = д\

(2)

(3)

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

Глава 2 диссертации посвящена исследованию задачи об оптимальном качении шара по плоскости без прокручиваний и проскальзываний. Задача об оптимальном качении шара по плоскости ставится следующим образом: по заданным двум точкам на плоскости {А{х0, у0) и В(хи yt)) и двум ориентациям шара в трехмерном пространстве (Rq и требуется найти кратчайшую кривую j(i) = (x(t),y(t)), соединяющую А и В, при качении по которой ориентация шара переходит из До в Ях. Управлением является скорость центра шара. Допустимое качение можно представить следующим образом: шар накрывается сверху плоскостью, параллельной плоскости качения, которая двигается поступательно в направлениях, параллельных плоскости качения. Получающееся при этом движение является качением без прокручиваний и проскальзываний.

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

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

х = щ, у = и2, Яо = - qiu2), < Qi = ЦчзЩ + qaui), Я2 = l(-qom + Язщ), ,9з = \{-qmi - q2u2),

где (х, у) е R2 — точка контакта шара и плоскости (проекция центра шара на плоскость качения), a (q0, quq2, q3) е S3 — кватернион единич-

20Petitot J., The neurogeometry of pinwheels as a sub-Riemannian contact structure //J PhvsioloKv №97, p. 265-309, Paris, 2003

"Sang 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, 2010

22Li Z., Canny J. Motion of two rigid bodies with rolling constraint//IEEE Ttans. on Robotics and Automation, (1), 6, p. 62-72, 1990

Q = (x,y,q)eR2xS3, Oi,u2) 6R2,

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

Q(o) = Qo, Q(T) = Qi. Критерий оптимальности имеет вид:

/ у/х2 + у2 dt = / Jи2 + и\ dt —> min / (u2 + U2) di —> min. Jo Jo v Уо

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

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

9 = с, с = — г sin в, á = г = 0. (4)

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

23Л.М. Hammersiey. Oxford commemoration ball. In: Probability, Statistics and Analysis, pp. 112-142. London Math. Soc. lecture notes, ser. 79 (1983)

24A.M. Arthurs, G.R.Walsh. On Hammersley's minimum problem for a rolling sphere //Math. Proc. Cambridge Phil. Soc., 99, 529-534, 1986

25V. Jurdjevic, The geometry of the plate-ball problem, Arch. Rat. Mech. Anal., v. 124 (1993), 305-328 2еСачков Ю.Л. Симметрии и страты Максвелла в задаче об оптимальном качении сферы по плоскости // Матем. Сборник, 2010, Т. 201, № Г, 99-120

следующей замене переменных:

(t, в, с, а, г, х, у, ui, щ, 5о, gi, 92, ?з) -+ (s, в, d, а, т, х, у, йь щ, q0, quq2, q3), s = mt, d=c/m, m = ^/r,

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

=~ + O(fiS), ff(я) = -(0osins + do(l- cos s)) + 0{pl),

¡TI ТП

®(e) = cos ¿ + °(Po), Ш = - sin ¿ +

Ш =2(rj- 1) (m cos ¿ sins - (1 + COS s) sin JL)e0+

+ 2(m2 - 1) (m(1 ~ COS s) COS ¿ ~ Sin S sin ^ + ,

Ш =2(m2 — 1) ((_1 + C0S5) COS¿ + msinssin

+ 2(¿^l)(SÍn5COS¿ " m(1 +cos5)sin^)4 +

где Po = Ve0 + 4 0-

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

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

ременных Л = (0О, do, а, т) и момент времени t в конечную точку экстремальной траектории Q(t) называется экспоненциальным отображением в задаче оптимального управления и обозначается Ехр : (A, í) н-> Qt. Множество пар (Л, t) в прообразе экспоненциального отображения, соответствующих точкам Максвелла в пространстве состояний, называется множеством Максвелла в прообразе экспоненциального отображения и обозначается МАХ = {(A,í)|3A ф А : Qs ф Qs,Qt = Qt,Qs = Exp(A,s),Qs = Ехр(А, s)}. Ю.Л. Сачков25 исследовал симметрии экспоненциального отображения и получил уравнения, определяющие множества Максвелла MAXj и МАХг для невырожденных эластик:

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

(2) (xq\ + yq_i){i) = 0 для эластик, нецентрированных в вершине.

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

gi(p,m) = cos — sinp — mcospsin —, m m

gtip, m) = mpcos (J— j sinp — (pcosp -f (m2 — l) sinp) sin ^ , m € (0,1) U (1, +oo), p = |>0.

Требуется при любом m € (0,1) U (1, -Ьоо) найти или возможно точнее оценить величину

Pi(m) = min{p > (%¿(p, т) = 0}, где ¿ = 1,2.

Основные результаты по этой задаче сведены в теорему 1 и теорему 2. Исследовано взаимное расположение графиков функций pi(m) и p2(m) (теорема 3). Возврат к исходному времени t дает утверждения для первых времен Максвелла íi(m) и t-^rn).

Причиной потери локальной оптимальности является наличие сопряженной точки на экстремальной траектории. Момент времени íconj, в который экстремальная траектория достигает первой сопряженной точки, называется первым сопряженным временем. Приближенные вычисления показывают, что функции t\{rii) и ¿-¿(тп) являются границами первого сопряженного времени íconj(m) вдоль экстремальных траекторий, см. рис. 1.

0.0 0.5 1.0 1.5 2.0 2.5 3.0

-----ti(m) -tconj(m) ___t2(m)

Рис. 1: Графики функций ti(m), ^¡(т), t2(m)

Отметим, что в родственных задачах оптимального управления (суб-римановазадача в случае Мартине27, обобщенная задача Дидоны11, задача Эйлера об эластиках28, задача об оптимальном перемещении мобильного робота на плоскости29) глобальное поведение аналогичных времен Максвелла ii(A), ¿2(A), гораздо проще, чем асимптотика h(m), ¿2(171) в задаче о качении шара по плоскости. Это отражает более сложный характер данной задачи, по сравнению с указанными родственными задачами. Учитывая также сложность параметризации экстремальных траекторий в данной задаче, представляется затруднительным получить ее точное решение. Однако на основе полученных результатов возможна разработка алгоритма и программы приближенного решения задачи о качении шара по плоскости.

В главе 3 рассматривается конструктивная задача управления ПЯТИ-

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

28Yu. L. Sachkov, Maxwell strata in Euler's elastic problem// Journal of Dynamical and Control Systems, Vol. 14, No. 2 (April), pp. 169-234, 2008

29I. 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, 2010

мерными системами с двумерным линейным управлением:

q = ul{t)Xi(q) + u2{t)X2(q), д(0) = g°, q(T)=q\

(5)

(6)

где пространство состояний Q Э q — это связное пятимерное гладкое многообразие, управление принимает значения на двумерной плоскости (щ, щ) € К2, а гладкие векторные поля Х2 удовлетворяют условию полного ранга на многообразии С,Условие полного ранга гарантирует, что система (5) вполне управляема, то есть для любых состояний ср, q1 6 <5 существует траектория системы (5), удовлетворяющая условиям (6). В настоящее время не существует методов явного решения задачи (5), (6) в общем случае. Удовлетворительное решение имеется лишь для некоторых специальных классов систем3. Тем не менее такие задачи возникают в инженерии1, где достаточно приближенного решения, погрешность которого не превышает наперед заданной. Конкретными примерами систем вида (5), которые представляют самостоятельный интерес из-за своего прикладного значения в робототехнике, являются система, моделирующая качение без прокручиваний и проскальзываний шара по плоскости, и система, моделирующая движение машины с двумя прицепами по плоскости. В работе предлагается метод конструирования управлений переводящих систему (5) из начального состояния q0 в терминальное состояние qx с любой наперед заданной точностью е > 0, то есть в такое состояние д1, что р(д1, д1) < е, где р — расстояние на мно-

гообразии Q. Например, если Q — область в R5, то р= ~ q})2-

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

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

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

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

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

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

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

Локальное приближение управляемой системы другой, более простой системой, широко используется в теории управления. Обычно в качестве локальной аппроксимации используется линеаризация управляемой системы. Однако для линейных по управлению систем вида (5) линеаризация дает слишком грубое приближение. Так как размерность управления меньше размерности состояния, то линеаризация не может быть вполне управляемой. Естественную замену линейной аппроксимации в этом случае доставляет нильпотентная аппроксимация — наиболее простая система, сохраняющая структуру управляемости исходной системы. Понятие нильпотентной аппроксимации управляемых систем было введено независимо А. А. Аграчевым и А. В. Сарычевым31, и X. Хермсом32. В работе

30Bellaiche А., Laumond J. P., Chyba M., Canonical nüpotent approximation of control systems: application to nonholonomic motion planning/ j 32nd IEEE Conf. on Decision and Control, 1993

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

32Hermes Н., Nilpotent and high-order approximations of vector fields systems // SIAM, v. 33, p. 238-264, 1991

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

Уі = «і, Ш = и2,

Уз = \Ыи2 - У2Щ), 2/4 = \{у\ + Уг)и2, .2/5 = -\{Уі+УІ)их,

У Є

(7)

Для построения приближенного решения исходной задачи (5), (6) требуется найти управления, переводящие систему (7) из произвольного состояния у0 в начало координат:

У(0) = у°, у(Т) = (0,0,0,0,0). (8)

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

U і =

а,-, при t є [0,f], ßi, приі є (f,f], 7г, при t Є (f,

Sit при t є (f, Г],

где і = 1,2.

Получается трехпараметрическое семейство решений. Показатель Amp = тах(|а,-|, Щ, |7,|, |<5;|) характеризует величину отклонения искомой траектории от постоянной траектории. Свободные параметры фиксируются в соответствии с критерием Amp —» min.

Добавление к задаче (7), (8) естественного интегрального критерия оптимальности (минимальность функционала субримановой длины)

J y/ui(t)+ul(t)dt -»■ min (9)

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

^Bellaiche A., The tangent space in sub-Riemannian geometry , Sub-Riemannian Geometry, Eds. A. Bellaiche and J. J. Risler, Basel, Swizerland, Birkhäuser, p. 1-78, 1996

Ю.Л. Сачковым34. Основным результатом теоретических исследований явилось описание структуры экспоненциального отображения и первых времен Максвелла вдоль экстремальных траекторий. На основе этого результата задача оптимального управления (7)-(9) была сведена к задаче решения пяти алгебраических уравнений в неэлементарных функциях с пятью неизвестными. Явно решить эту систему не представляется возможным ввиду сложности получившихся формул, поэтому в данной работе используются численные методы. Для построения оптимального синтеза в задаче (7)-(9) требуется решить систему алгебраических уравнений

'P(u,v,k) = Pu

< Q(u,v,k) = Qu (10)

R(u,v,k) = i?i,

относительно (u,v,k) при заданной правой части Р\, Qi, R\. Известно, что при произвольной правой части (за исключением особых множеств меньшей размерности) система имеет единственный корень. В диссертации предложен генетический алгоритм решения системы (10).

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

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

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

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

• дополнительные функции программы MotionPlanning.

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

Рис. 2: Структура программы МоіїопРІаїтіїщ

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

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

Важным открытием нейрофизиологии зрения начала нынешнего века является геометрическая структура, соответствующая первичной зрительной коре головного мозга человека. Установлено36, что для сохранения изображений первичная кора моделирует контактную структуру {(х, у,р)} = О у, МР1 на поверхности сетчатки глаза О с М2. Оказалось, что для эффективной обработки изображений мозгу человека выгоднее сохранять контур не в виде набора последовательных точек (Х1,у¿), а в виде набора штрихов в пределе — в виде непрерывной кривой

(гс(£),V = ¿у/йх. Если часть кривой повреждена или скрыта от наблюдения, то недостающая дуга восстанавливается на основе следующего вариационного принципа: восстанавливающая дуга должна иметь минимальную евклидову длину в пространстве (х, у, в), в = аг^ р:

где а € R — масштабирующий коэффициент, служащий для выбора естественной (соответствующей устройству сетчатки глаза) метрики на плоскости {(х,у)}.

Этот принцип положен в основу метода восстановления скрытой дуги. Описанный способ восстановления кривой обладает важным свойством инвариантности относительно движений плоскости: при поворотах и па-

35Chan T.F., Kang S.H., Shen 3.,Euler's elastica and curvature based inpainting // SIAM Journal of Applied Math., v. 63,№ 2, p. 564-592, 2002

36Petitot J., Neurogeometrie de la vision. Modeles mathématiques et physiques des architectures fonctionelles, Editions de l'Ecole Polytechnique, 2008

(H)

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

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

х = и cos в, у = и sin в, 9 = v, (12)

{х,у) el2, 0е[О,2тг], (и,«)еМ2, (13)

(х(0), 2/(0), 0(0)) = (0,0,0), (х(Т),у('ПЛТ)) = (х1,у М, (14)

[ ,/и2 + a2v2dtmin. (15)

Jо

Для проверки предложенного подхода к задаче восстановления контуров поврежденного изображения был разработан программный комплекс Optimallnpainting. Он предназначен для восстановления поврежденных изображений портретов линий уровня гладких функций двух переменных антропоморфным (естественным для человека) способом. Optimallnpainting моделирует работу с бинарными и полутоновыми изображениями. В его функции входит:

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

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

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

Структура программного комплекса Optimallnpainting изображена на Рис. 3. Ядром комплекса является модуль GlobalSolver, вычисляющий восстанавливающую изофоту изображения, как решение задачи (12)-(15). Параллельный модуль CreateOriginal создает исходное растровое изображение портрета линий уровня функции F(x,y). Модуль Create-Corrupted наносит повреждения, определяемые пользователем, на исходное изображение. Параллельный модуль CreateRestored восстанавливает поврежденное изображение, дополняя недостающие фрагменты линий уровня, изофотами, параметры которых определяются из граничных условий модулем GlobalSolver. Функциональные модули разработаны на языке С++ с использованием следующих библиотек: libgsl (для вычисления неэлементарных функций и численного решения системы

алгебраических уравнений), libpng (для работы с растровыми изображениями в формате PNG) и libgomp (для распараллеливания процесса вычислений по технологии ОрепМР). Интерфейс комплекса разработан на языке tcl/tk. Разработанный программный комплекс Optimallnpainting

Рис. 3: Структура программного комплекса Оріітаїїпраіпіііщ

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

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

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

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

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

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

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

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

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

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

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

[3] Маштаков А.П. Параллельный программный комплекс решения неголономных задач управления// Программные продукты и системы, 2012, № 1, с. 146-151.

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

[5] Маштаков А.П. Алгоритмическое и программное обеспечение решения конструктивной задачи управления неголономными пятимерными системами // Программные системы: теория и приложения, 2012, № 1, с. 3-29.

[6] Сачков Ю.Л., Ардентов A.A., Маштаков А.П. Конструктивное решение задачи управления на основе метода нильпотентной аппроксимации// Программные системы: теория и приложения // Труды международной конференции «Программные системы: теория и приложения», 2009, т. 2, с. 5-23. (автора — 8 стр.)

[7] Сачков Ю.Л., Ардентов A.A., Маштаков А.П. Параллельный алгоритм и программа восстановления изофот для поврежденных изображений. Программные системы: теория и приложения, 2010, т. 1, с. 3-20. (автора — 2 стр.)

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

1 Введение

1.1 Задачи управления в робототехнике. Приложение к машинной графике

1.2 Математические определения

1.3 Обзор существующих методов решения

2 Задача об оптимальном качении шара по плоскости

2.1 Постановка задачи и известные результаты.

2.2 Управляемая система в терминах кватернионов.

2.3 Асимптотика экстремальных траекторий.

2.4 Исследование функции р\ (ш)

2.5 Исследование функции Р2(т)

2.6 Взаимное расположение графиков функций (т) и Р2(т).

2.7 Время Максвелла и время разреза при качении сферы по синусоидам малой амплитуды.

2.8 Оптимальность экстремальных траекторий

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

3.1 Постановка задачи планирования движений.

3.2 Неголономные системы в робототехнике.

3.3 Алгоритм приближенного решения.

3.4 Программный комплекс МоиопР1апшг^.

3.5 Пример использования ПК MotionPlanning

3.6 Применение ПК МоиопР1апшг^ для задачи планирования движений

1.1 Задачи управления в робототехнике. Приложение к машинной графике

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

Классическим объектом исследования в робототехнике являются модели разнообразных колесных мобильных роботов и роботов-манипуляторов. В общем случае, такие системы описываются нелинейными неголономными управляемыми системами с линейным управлением п ¿=1 где пространство состояний С} Э д — это связное гладкое многообразие, управление (иь ., ип) е М" неограничено, а ., Хп — гладкие векторные поля.

Актуальной является двухточечная граничная задача управления такими системами, то есть выбор закона управления переводящего систему из заданного начального состояния д° Е С} в заданное конечное состояние д1 Е С} [1]: д(0) = д°, д(Т) = д\ (1.2)

В настоящее время не существует методов явного решения этой задачи в общем случае. Удовлетворительное решение имеется лишь для некоторых специальных классов систем. Однако в приложениях обычно достаточно приближенного управления, переводящего систему (1.1) из начального состояния д° в терминальное состояние д1 с любой наперед заданной точностью. Общепринятым подходом в данном направлении является разработка программных средств, реализующих итерационный алгоритм поиска приближенного управления. При этом на первый план выдвигаются такие критерии, как простота реализации найденного закона управления а также величина маневра, совершаемого механической системой описанной уравнением (1.1). Современные программные комплексы управления техническими объектами сталкиваются с проблемами управления неголономными системами (понятие неголономности управляемой системы обсуждается в п. 3.2 главы 3). Такие системы традиционно представляют трудности для теоретического анализа в механике, а их широкое использование в современной робототехнике и инженерии (мобильные роботы, роботы-манипуляторы) делают весьма актуальной разработку новых математических, алгоритмических и программных средств для управления неголономными системами [2-4].

Добавление некоторого естественного критерия оптимальности решения задачи (1.1), (1.2) дает классическую задачу оптимального управления. В рассматриваемых в диссертации задачах критерием оптимальности является минимальность интеграла действия1 :

Заметим, что задача (1.1)—(1.3) является сложной математической проблемой, требующей отдельного исследования для каждой конкретной системы (1.1). Во-первых, сложность вызвана необходимостью интегрирования гамильтоновой системы, определяющей экстремальные траектории, во-вторых, с выбором оптимальных траекторий среди экстремалей.

Заметим, что в силу линейности системы (1.1) по управлениям и отсутствия ограничений на управление (и Е Мп), если управление £ 6 [О, Т], переводит эту систему из точки д° в точку д1, то для любого к > О управление «(¿) = к и(к ¿), £ € [0, Т/к], также переводит эту систему из д° в д1 (соответствующая траектория есть д(£) = д(А; ¿)). Эту возможность перепараметризации траекторий системы (1.1) мы неоднократно используем в дальнейшем. Благодаря ей, если задача (1.1), (1.2) разрешима для некоторого хДля рассматриваемых в диссертации систем в силу неравенства Коши-Буняковского задача минимизации интеграла действия ^ и\ + . ,+и^ сИ равносильна задаче минимизации интеграла субри-мановой длины /0Т у/и{ + М (см. [5])

1.3)

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

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

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

2. Конструктивная задача управления нелинейными пятимерными системами с двумерным линейным управлением (глава 3).

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

Все они описываются системами вида (1.1), где управление и = {щ,и2) Е К2 двумерно. В задачах 1, 2 пространство состояний пятимерно (dim Q = 5), а в задаче 3 — трехмерно (dim Q = 3). Во всех перечисленных задачах используются общие методы исследования (см. рис. 1.1):

• геометрическая теория управления,

• численные методы решения систем алгебраических уравнений,

• функциональное и императивное программирование,

• методы обработки изображений,

• методы разработки человеко-машинных интерфейсов,

• методы параллельного программирования,

В главе 2 диссертации исследуется задача об оптимальном качении без прокручиваний и проскальзываний шара по плоскости (см. рис. 1.2). Она имеет приложения в робототехнике при моделировании движения твердого тела в руке робота-манипулятора и в задаче управления сферическими роботами [6]. Задачи о качении поверхностей

Рис. 1.1: Общие методы исследования вызывают большой интерес в механике, робототехнике и теории управления (см., например, работы [7-10]). Задача об оптимальном качении шара по плоскости имеет богатую историю, но до сих пор остается открытой проблемой. Она была поставлена в работе Дж.Хаммерсли [11]. А.Артуре и Дж.Уолш [12] доказали, что уравнения для экстремальных траекторий в этой задаче интегрируемы в эллиптических функциях. В.Джурджевич [13,14] показал, что при оптимальном качении точка контакта шара и плоскости движется по эластикам Эйлера (стационарным конфигурациям упругого стержня на плоскости [15,16]), и описал возможные типы качения шара. Далее Ю.Л. Сачков в работе [17] получил явную параметризацию экстремальных траекторий и в работе [19] начал их исследование на оптимальность. Однако, вопрос оптимальности экстремальных траекторий в общем случае до сих пор остается открытым. Основным результатом главы 2 является описание верхней границы времени потери оптимальности экстремальных траекторий при качении шара вдоль синусоид малой амплитуды.

Глава 3 диссертации посвящена разработке математического и программного обеспечения для приближенного решения конструктивной задачи управления нелинейными

Рис. 1.2: Качение шара по плоскости пятимерными системами с двумерным линейным управлением: д = и1Ц)Х1(д)+и2(г)Х2(д), (1.4)

9(0) = <Д д(Т) = д\ (1.5) где пространство состояний Э д — это связное пятимерное гладкое многообразие, управление принимает значения на двумерной плоскости (111,112) € К2, а гладкие векторные поля Х\, Х2 удовлетворяют условию полного ранга на многообразии (см. далее п. 1.2, а также [10]). Условие полного ранга гарантирует, что система (1.4) вполне управляема, то есть для любых состояний д°,д1 6 существует траектория системы (1.4), удовлетворяющая условиям (1.5). Конкретными примерами систем такого вида являются система, моделирующая качение без прокручиваний и проскальзываний шара по плоскости, и система, моделирующая движение мобильного робота с двумя прицепами по плоскости (см. рис. 1.3). Отметим, что качение произвольных поверхностей также описывается системами вида (1.4). В работе представлен способ отыскания приближенного решения задачи (1.4), (1.5), основанный на построении нильпотентной аппроксимации. Идея метода заключается в том, что исходная система приближается нелинейной системой более простой структуры, для которой точно решается задача управления. Затем найденные управления подставляются в исходную систему. Если состояние, достигнутое после применения найденного управления, отличается от желаемого состояния в пределах допустимой погрешности, то задача считается решенной,

Рис. 1.3: Мобильный робот с двумя прицепами иначе процедура повторяется с новыми граничными условиями. Точное решение задачи управления нильпотентной системой дает приближенное решение исходной задачи управления в малой окрестности целевой точки. Алгоритм приближенного решения задачи (1.4), (1.5) реализован в виде пакета MotionPlanning.m для системы Wolfram Mathematica.

Глава 4 посвящена разработке программного комплекса Optimallnpainting для решения задачи восстановления поврежденного изображения антропоморфным (естественным для человека) способом. В качестве исходного изображения рассматривается портрет линий уровня некоторой функции F(x,y). Повреждения задаются в виде кругов на исходном изображении, внутри которых отсутствует информация о линиях уровня. Требуется естественным для человека способом восстановить эти кривые на поврежденных участках. Предлагается метод восстановления, основанный на положениях одного из новых направлений нейрофизиологии зрения — нейрогеометрии. В основу метода положен вариационный принцип минимальности длины восстанавливаемой кривой в пространстве контактных элементов. Разработанный параллельный программный комплекс Optimallnpainting является инструментом для проверки под

Рис. 1.4: Мобильный робот на плоскости хода нейрофизиологов к задаче восстановления изображения антропоморфным способом. Замечательным является тот факт, что кривые, удовлетворяющие приведенному вариационному принципу, являются оптимальными траекториями мобильного робота на плоскости. Задача об оптимальном перемещении мобильного робота по плоскости имеет следующий вид: х = и cos0, у = и&\пв, 0 = v, (1.6) x,y)eR2, 0€[О,2тг], (u,v)e М2, (1.7)

Ое(О),у(О),0(О)) = (0,0,0), (х(Т),у(Т),е(Т)) = (x1)?/i,0i), (1.8) т и2 + a2v2dt -» min. (1.9)

Здесь рассматривается мобильный робот, который может перемещаться вперед-назад и поворачиваться на месте. Координаты (х, у) задают положение мобильного робота на плоскости а угол в задает его ориентацию (см. рис 1.4). В статье [20] Ю.Л. Сачков свел эту задачу к решению системы из 3-х алгебраических уравнений в эллиптических функциях с тремя неизвестными. Оптимальные траектории в задаче (1.6)—(1.9) являются кривыми, с помощью которых ПК Optimallnpainting восстанавливает контуры поврежденного изображения. I

Заключение

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

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

2. Рассмотрена двухточечная граничная задача управления для нелинейных пятимерных систем с двумерным линейным управлением с приложением к задачам робототехники. Представлен итерационный алгоритм поиска приближенного решения, основанный на локальном приближении исходной системы в окрестности целевой точки. Этот алгоритм реализован в виде параллельного пакета MotionPlanning.m для системы Wolfram Mathematica. Он был использован для управления системами «Машина с двумя прицепами» и «Шар, катящийся по плоскости». Для перевода системы из заданного начального состояния в заданное конечное состояние используются два класса управлений: кусочно-постоянное управление и оптимальное для приближающей системы управление.

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

4. Рассмотрена задача восстановления поврежденных изображений, заданных портретом линий уровня некоторой функции двух переменных. Восстановление поврежденных контуров осуществляется антропоморфным (естественным для человека) способом. Восстанавливающие кривые удовлетворяют вариационному принципу, полученному нейрофизиологами зрения. Эти кривые являются оптимальными траекториями мобильного робота на плоскости. На языке С++ (с использованием языка Тс1/Тк для разработки интерфейса) создан параллельный программный комплекс Ор^таЛпрашЬ^ восстановления поврежденных изображений. Комплекс был использован для проверки подхода нейрофизиологов для задачи антропоморфного восстановления поврежденных кривых.

Полученные теоретические результаты могут быть использованы в дальнейших исследованиях методов управления неголономными системами. Разработанный пакет MotionPlanning.ni может применяться для исследования управляемых систем в механике, робототехнике, инженерных приложениях, а также при обучении студентов новым методам теории управления. Разработанный ПК ОрйтаНпрат^пд может применяться к задаче антропоморфного восстановления поврежденных контуров изображений. Практическая значимость полученных результатов определяется их применением для решения комплекса актуальных задач робототехники и машинной графики.

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

2. Горнов А.Ю., Технология проектирования программных комплексов для задач оптимального управления // Вестник ИрГТУ. 2004. - Т. 17, № 2. - С. 148-153.

3. Жулин С.С., Численное решение задач оптимального управления с помощью системы OPTIMUS // Проблемы динамического управления: Сборник научных трудов факультета ВМиК МГУ Под ред. Ю.С.Осипова, А.В.Кряжимского.— 2005.— Выпуск 1,- С. 158-165.

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

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

6. Sang 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, 2010.

7. Li Z., Canny J. Motion of two rigid bodies with rolling constraint// IEEE Trans, on Robotics and Automation, (1), 6 (1990), 62-72.

8. Bicchi A., Prattichizzo D., Sastry S. Planning motions of rolling surfaces// IEEE Conf. on Decision and Control, 1995.

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

10. J.M. Hammersley. Oxford commemoration ball. In: Probability, Statistics and Analysis, pp. 112-142. London Math. Soc. lecture notes, ser. 79 (1983).

11. A.M. Arthurs, G.R.Walsh. On Hammersley's minimum problem for a rolling sphere // Math. Proc. Cambridge Phil. Soc., 99 (198G), 529-534.

12. V. Jurdjevic, The geometry of the plate-ball problem, Arch. Rat. Mech. Anal., v. 124 (1993), 305-328.

13. V. Jurdjevic, Geometric control theory, Cambridge University Press, 1997.

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

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

16. А.П. Маштаков, Ю.Л. Сачков, Экстремальные траектории и точки Максвелла в задаче об оптимальном качении сферы по плоскости // Мат. сборник, 2011, 202:9, 97-120.

17. А.П. Маштаков, Асимптотика экстремальных кривых в задаче о качении шара по плоскости // Современная математика. Фундаментальные направления. Том 42 (2011). С. 158-165.

18. Сачков Ю.Л. Симметрии и страты Максвелла в задаче об оптимальном качении сферы по плоскости // Матем. Сборник, 2010, Т. 201, № 7, 99-120.

19. Sachkov Yu. L., Cut locus and optimal synthesis in the sub-Riemannian problem on the group of motions of a plane // ESAIM: COCV, v. 17, № 2, p. 293-321, 2011.

20. Montgomery R., A Tour of Subriemannian Geometries, Their Geodesies and Applications, American Mathematical Soc., p. 259, 2006.

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

22. Зеликин М. И. Оптимальное управление и вариационное исчисление, М.: Едито-риал УРСС, 2004.

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

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

25. 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, San Antonio, 1993.

26. Bellaiche A., Laumond J. P., Riser J. J., Nilpotent infinetisimal approximations to a control Lie algebra // IFAC Nonlinear Control Systems Design Symposium, pp. 174181, Bordeaux, 1992.

27. Bellaiche A., The tangent space in sub-Riemannian geometry , Sub-Riemannian Geometry, Eds. A. Bellaiche and J. J. Risler, Basel, Swizerland, Birkhauser, p. 1-78, 1996.

28. Murray R. M., Sastry S., Steering nonholonomic systems using sinusoids// IEEE Int. Conf. on Decision and Control, pp. 2097-2101, 1990.

29. Murray R. M., Robotic Control and Nonholonomic Motion Planning// PhD Thesis, Memorandum No. UCB/ERL M90/117, university of California, Berkeley, 1990.

30. Tilbury D., Murray R., Sastry S., Trajectory generation for the n-trailer problem using Goursat normal form// IEEE Trans, on Automatic Control, Vol 40(5), pp. 802-819, 1995.

31. Monaco S., Norman-Cyrot D., On Carnot-Caratheodory metrics// J. Differential Geometry, Vol 21, pp. 35-45, 1985.

32. Murray R. M., Nilpotent bases for a class on nonintegrable distributions with applications to trajectory generation for nonholonomic systems// Math. Control Signal Syst., university of California, Berkeley, 1990.

33. Fliess M., Levine J., Martin P., Rouchon P., Flatness and defect of non-linear systems: introductory theory and examples// Int. Journal of Control, Vol 61(6). pp. 1327-1361, 1995.

34. Rouchon P. Fliess M., Levine J., Martin P., Flatness and motion planning: the car with n trailers// European Control Conf., pp. 1518-1522, 1993.

35. Rouchon P., Necessary condition and genericity of dynamic feedback linearization// J. Math. Systems Estimation Control, Vol 4(2), 1994.

36. 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, 1991.

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

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

39. Sussmann Н., Lie brackets, real analyticity and geometric control // Geometric control Theory (Brockett R., Millman R. and Sussmann H., eds.) V. 27 of Progress in Mathematics, Michigan Technological University.— Birkhauser.— 1982.

40. Boscain U., Rossi F., Invariant Carnot-Caratheodory Metrics on S3, 50(3), SL(2), and Lens Spaces// SIAM Journal on Control and Optimization 47, p. 1851, 2008.

41. Гурман В.И., Принцип расширения в экстремальных задачах, М.: Физматлит, 1997.

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

43. Л.С. Понтрягин, Обобщения чисел, М.: Наука, 1986.

44. Арнольд, В.И. Геометрия комплексных чисел, кватернионов и спинов, М.: МЦН-МО, 2002.

45. Г.М. Фихтенгольц, Курс дифференциального и интегрального исчисления: Учебник. В 3-х т. Т.1. 9-е изд., стер.-СПб.: „Лань", 2009.

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

47. Yu. L. Sachkov, Maxwell strata in Euler's elastic problemj j Journal of Dynamical and Control Systems, Vol. 14 (2008), No. 2 (April), pp. 169-234.

48. I. Moiseev, Yu. L. Sachkov, Maxwell strata in sub-Riemannian problem on the group of motions of a plane, ESAIM: COCV, Vol. 16 (2010), pp. 380-399.

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

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

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

52. Venditelli M., Oriolo G., Jea F., Laumond J.P., Nonhomogeneous nilpotent approximations for nonholonomic systems with singularities // Transactions on Automatic Control, p. 261-266, 2004.

53. Laumond J. P., Robot Motion Planning and Control // Lecture Notes in Control and Information Sciences, № 229, p. 343, 1998.

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

55. Э.Т. Уиттекер, Аналитическая динамика, М.: Едиториал УРСС, 2004.

56. Черноусько Ф.Л., Ананьевский И.М., Решмин С.А., Методы управления нелинейными механическими системами, М.: Физматлит, 328 е., 2006.

57. Sachkov Yu.L., Symmetries of Flat Rank Two Distributions and Sub-Riemannian Structures // Transactions of the American Mathematical Society, v. 356, p. 457-494, 2004.

58. 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, 2002.

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

60. Petitot J., The neurogeometry of pinwheels as a sub-Riemannian contact structure // J. Physiology, №97, p. 265-309, Paris, 2003.

61. Petitot J., Neurogeometrie de la vision. Modeles mathématiques et physiques des architectures fonctionelles, Editions de l'Ecole Polytechnique, 2008.

62. Ю.JI.Сачков, А.А.Ардентов, В.М.Касимов, А.П.Маштаков, Восстановление изображений на основе вариационного принципа // Программные продукты и системы, № 4, 126-127, 2009.

63. GNU Scientific Library. Электронный ресурс: http://www.gnu.org/software/gsl/

64. Библиотека для работы с изображениями в формате PNG. Электронный ресурс: http://www.libpng.org/pub/png/libpng.html

65. Библиотека для распараллеливания по технологии ОрепМР. Электронный ресурс: http://gcc.gnu.org/onlinedocs/libgomp/

66. Boscain U., Duplaix J., Gauthier J.-P., Rossi F., Anthropomorphic image reconstruction via hypoelliptic diffusion/j eprint arXiv:1006.3735, 2010.

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