Software & Systems

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

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

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

                          (1)

                                       (2)

где пространство состояний qÎQ – это связное пятимерное гладкое многообразие, dim(Q)=5; управление принимает значения на двухмерной плоскости, (u1, u2)ÎÂ2; гладкие векторные поля X1(q), X2(q) удовлетворяют условию полного ранга [1] на многообразии Q. Требуется найти управление u(t)=(u1(t), u2(t)), переводящее систему (1) за время T>0 из начального состояния q0 в терминальное q1 с любой ранее заданной точностью e>0, то есть в такое состояние , что , где dist – расстояние на многообразии Q (например, если Q=Â5, то ).

Системы вида (1) характеризуются тем, что размерность пространства управлений меньше размерности пространства состояний dim(Â2)= =2

В последнее время конструктивная задача управления активно изучается в нелинейной теории управления. Удовлетворительное решение она имеет лишь для некоторых специальных классов систем [2]. Однако пятимерные системы общего положения с двумя управлениями имеют вектор роста (2, 3, 5), потому эти результаты неприменимы к таким системам.

В  данной  работе  представлен  способ  отыскания приближенного решения задачи (1)–(2), основанный на построении нильпотентной аппроксимации. Идея метода в том, что исходная нелинейная система заменяется приближенной нильпотентной системой, для которой точно решается задача управления. Затем найденные управления подставляются в исходную систему. Если состояние, достигнутое после применения найденного управления, отличается от желаемого в пределах допустимой погрешности, задача считается решенной, иначе процедура повторяется. Управления, точно решающие нильпотентную систему, дают приближенное решение исходной задачи управления в малой окрестности целевой точки. Метод нильпотентной аппроксимации применим к задачам управления общего вида; существенно только умение решать задачу управления для нильпотентной аппроксимации. Этот метод предложен в [3].

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

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

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

1. В окрестности конечной точки q1 строится аппроксимирующая система, для которой точно решается задача управления.

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

В среде Mathematica 8 (http://www.wolfram.com/ mathematica/) был реализован параллельный ПК MotionPlanning235 (см. рис. 1) решения задачи (1)–(2). Он является дополнительным пакетом для системы Wolfram Mathematica (MotionPlann­ing235.m) и состоит из следующих основных модулей:

–      NilpotentApproximation235 строит нильпотентную аппроксимацию NA (см. (3)) системы (1) и возвращает замену переменных t=A°F, в которых NA имеет канонический вид;

–      CPControl235 решает задачу (1)–(2) в классе кусочно-постоянных управлений;

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

Модуль NilpotentApproximation235 построения нильпотентной аппроксимации. Локальное приближение управляемой системы другой, более простой, широко используется в теории управления. Обычно в качестве локальной аппроксимации используется линеаризация управляемой системы. Однако для линейных по управлению систем вида (1) линеаризация дает слишком грубое приближение. Так как размерность управления меньше размерности состояния, линеаризация не может быть вполне управляемой. Естественной заменой линейной аппроксимации в этом случае является нильпотентная аппроксимация – наиболее простая система, сохраняющая структуру управляемости исходной системы (в частности, сохраняется такой важный инвариант, как вектор роста).

В данной работе использован алгоритм вычисления нильпотентной аппроксимации для линейных по управлению систем, предложенный в [2]. Этот алгоритм был конкретизирован для систем вида (1), а именно, вычислена замена переменных для перехода в привилегированные координаты A:q®z, а векторные поля нильпотентной аппроксимации  в привилегированных координатах zi, i=1, …, 5, были выражены через векторные поля исходной системы X1(z), X2(z) и их производные.

Кроме того, алгоритм Беллаиша дополнен следующим образом: выполняется переход в систему координат y (замена переменных F:z®y), в которой нильпотентная аппроксимация имеет канонический вид

                                       (3)

а граничные условия представлены как

y(0)=y0,  y(T)=(0, 0, 0, 0, 0).                                  (4)

Модуль CPControl235 решения задачи в классе кусочно-постоянных управлений. В ПК Moti­onPlanning235 реализован модуль CPControl235 решения задачи управления нильпотентной канонической системой (3) с граничными условиями (4) в классе кусочно-постоянных функций. При этом время можно перепараметризовать так, что T=1. Требуется найти управления (u1(t), u2(t)) в классе кусочно-постоянных функций на отрезке tÎ[0, 1], переводящие систему из произвольного начального состояния y0=Â5 в начало координат. Доказано следующее утверждение.

Предложение. Для решения задачи управления (3)–(4) достаточно управлений с тремя точками переключения:

Коэффициенты a, b, g, и d определяются из системы пяти алгебраических уравнений с восемью неизвестными. Получается трехпараметрическое семейство решений, причем для любого     начального состояния y0=Â5 существует способ зафиксировать свободные параметры так, чтобы получалось решение без особенностей. В модуле CPControl235 фиксация свободных параметров осуществляется так, чтобы в соответствующей траектории не было больших отклонений, а именно, используется критерий max½ui½®min.

Модуль OptimalControl235 решения задачи в классе оптимальных управлений. Для управляемой системы (3) с граничными условиями (4) рассматривается задача оптимального управления с естественным интегральным критерием (функционалом субримановой длины)

                                           (5)

Эта задача известна в теории управления как обобщенная задача Дидоны, а в субримановой геометрии – как субриманова задача с вектором роста (2, 3, 5). Она имеет богатую историю и была детально теоретически изучена в [4]. Основным результатом теоретических исследований явилось описание структуры экспоненциального отображения и первых времен Максвелла вдоль экстремальных траекторий. На основе этого задача оптимального управления (3)–(5) была сведена к задаче решения пяти алгебраических уравнений в неэлементарных функциях с пятью неизвестными. Явно решить эту систему практически невозможно из-за сложности получившихся формул, поэтому предложено использовать численные методы.

Приведем некоторые результаты из статьи [4], необходимые для дальнейшего изложения. Семейство экстремальных траекторий в задаче оптимального управления параметризуется экспоненциальным отображением exp, переводящим пару (вектор сопряженных переменных, время) в соответствующую точку экстремальной траектории. Прообраз L и образ M экспоненциального отображения exp: L®M разбиваются поверхностями разреза на четыре области (в прообразе и  в образе), таких, что Li переходит в Mi и экспоненциальное отображение является диффеоморфизмом на этих областях. В свою очередь, каждая область Li разбивается на непересекающиеся множества C1 и C2, в которых экспоненциальное отображение задается разными формулами. Задача построения оптимального синтеза состоит в обращении экспоненциального отображения. При этом разбиение L на Li и M на Mi  известно, а разбиение на Ci неизвестно. В задаче (3)–(5) была найдена двухмерная группа симметрий, состоящая из вращений и растяжений. Факторизация задачи по этой группе уменьшает размерность задачи с пяти до трех. Получается система из трех уравнений с тремя неизвестными:

                                                    (6)

Итак, для построения оптимального синтеза в задаче (3)–(5) требуется решить систему (6) относительно u, v, k при заданной правой части P1, Q1, R1. Заметим, что функции P(u, v, k), Q(u, v, k) и R(u, v, k) выражены в эллиптических функциях Якоби и эллиптических интегралах первого и второго рода и имеют сложную аналитическую запись. Известно, что при любой правой части (за исключением особых множеств меньшей размерности) система (6) имеет единственный корень.

Для решения поставленной задачи был разработан модуль OptimalControl235. Схема его работы представлена на рисунке 2. Пользователь легко может организовать параллельное вычисление корня на нескольких ядрах процессора. Для этого требуется указать системе Mathematica 8 (функция недоступна в более ранних версиях) количество ядер и изменить при необходимости функцию SolveHen (выбрать, какие алгоритмы решения системы – АlgorithmA, АlgorithmB, АlgorithmC, АlgorithmD – будут выполняться одновременно и сколько именно). Кроме стандартного метода Ньютона (АlgorithmA) и метода хорд (АlgorithmB), пользователю предлагаются гибридные методы (АlgorithmC, АlgorithmD). Проведенное обширное тестирование показало, что в большинстве случаев первым результат выдает АlgorithmA или Аlgo­rithmB, хотя и бывают ситуации, когда гибридные методы справляются с задачей быстрее. Поэтому по умолчанию предлагается делить доступные ядра поровну между AlgorithmA и АlgorithmB. Отметим, что одновременный запуск одного и того же алгоритма на разных ядрах имеет смысл, так как во всех алгоритмах используется генератор случайных начальных приближений. Так как основное время вычисления занимает выбор удачного начального приближения, использование нескольких ядер дает существенное ускорение.

Дополнительные функции ПК Motionlan­ning235. Помимо основных модулей Nilpotent­Approximation235, CPControl235 и OptimalCon­trol235, решающих задачу (1)–(2), пользователю предоставляются некоторые дополнительные инструменты для представления результатов и слежения за процессом вычислений. Речь идет о следующих функциях:

1. TrajectoryNatPar[X1, X2, {u1,u2,T}, q0, xs] возвращает траекторию q(t) системы (1), где tÎ[0, T], соответствующую управлениям {u1, u2}, выходящую из точки q0.

2. PlotTrajectoryNatPar[trajectory, q0, q1, T] строит разным цветом графики пяти компонент заданной траектории trajectory(t) за время tÎ[0, T], а также отмечает на нем заданные состояния q0 и q1. Эта функция может использоваться для визуальной оценки достигнутого состояния и найденных траекторий. Пользователь может включить режим работы ПК, в котором графики найденных траекторий будут выводиться на экран на каждой итерации.

3. PlotTrajectoryOtklNatPar[trajectory, q0, q1, T] строит разным цветом графики отклонений пяти компонент заданной траектории trajectory(t) за время tÎ[0, T] от состояния q1.

4. AnimateCar[trajectory, T, q0, q1, N, {{xmin, xmax}, {ymin, ymax}}] строит анимацию движения машины с двумя прицепами при движении по траектории trajectory(t) за время tÎ[0, T] из состояния q0. Область, по которой движется машина с прицепами, ограничивается прямоугольником {{xmin, xmax},{ymin, ymax}}. В результате на жестком диске создается последовательность из N кадров. Последовательность кадров – это упорядоченный набор изображений .png, который впоследствии легко может быть собран в видеофайл стандартными утилитами. Размер изображения является параметром, доступным пользователю (по умолчанию 1024´768 пикселей). Помимо положения машины и прицепов, на каждый кадр пунктиром наносится состояние q1. Функция предназначена как для самостоятельного использования (для моделирования системы «машина с двумя прицепами» и ее исследования), так и для проверки решений, найденных с помощью ПК MotionPlanning235.

5. AnimateBall[trajectory, T, q0, q1, N] визуализирует качение без прокручиваний и проскальзываний сферы по траектории trajectory(t) (аналогично функции AnimateCar).

Пример использования ПК MotionPlan­ning235. Продемонстрируем работу ПК Motion­Planing235 на задаче о перемещении по плоскости машины с двумя прицепами. Состояние системы описывается пятью координатами (x, y, q, j1, j2)ÎQ=Â2´S3. Здесь (x, y)ÎÂ2 – координаты центра машины на плоскости; q – угол, задающий ориентацию машины на плоскости; j1 – угол, задающий положение первого прицепа относительно машины; j2 – угол, задающий положение второго прицепа относительно первого прицепа. Динамика системы имеет вид

                 (7)

Зададим начальное состояние q0=(0, 0, p/4, p/4, –p/4) и целевое q1=(–0,252, –0,339, 1,085, 0,514,     –1,281), в которое система должна перейти с точностью e=10–3.

На рисунках 3 и 4 приведены результаты работы модулей CPControl235 и OptimalControl235. В случае применения кусочно-постоянных управлений алгоритму потребовалось шесть итераций для достижения требуемой точности, а для оптимальных управлений – четыре. При использовании кусочно-постоянных управлений система совершает больший маневр (траектория имеет большую амплитуду отклонений от целевого состояния).

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

Литература

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

2.     Bellaiche A. The tangent space in sub-Riemannian geometry // Sub-Riemannian Geometry, A. Bellaiche and J.J. Risler, Eds. Basel, Swizerland: Birkh auser, 1996, pp. 1–78.

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

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

5.     Laumond J.P. Lecture Notes in Control and Information Science. Springer. 1998. № 229. 343 с.

6.     Murray R.M., Sastry S.S. Steering controllable systems, Proc. 29th IEEE Conf. Dec. and Control. Honolulu, Hawaii, 1990, pp. 408–412.