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

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

Оттуда мы кратко рассказали о принципе максимума Понтрягина и о том, как его можно использовать для нашей задачи:
Учитывая путь, описывающий последовательность конфигураций робота от начала до конечной точки, самый быстрый способ достичь Конечная точка состоит в том, чтобы выбрать элементы управления (ускорение и скорость для каждого сустава), чтобы мы постоянно достигали контрольных пределов, чередуя фазы максимального ускорения и замедления, элемент управления Bang-Bang.
Мы также показали, что эта проблема может быть сведена к двум измерениям, одному для параметра пути s, а другому для элементов управления ṡ, путем проецирования ограничений на путь.

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

ТОТГ

Построение оптимальной по времени траектории.

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

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

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

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

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

1–2: Используя максимальное ускорение, достигните кривой максимальной скорости. 2–3: Оставайтесь на кривой максимальной скорости до тех пор, пока не найдете точку переключения: в этом случае предел скорости имеет разрыв, на финише предел скорости падает до нуля (автомобиль должен быть остановлен). 4: Начиная с точки переключения, выполните «обратный проход». Используя максимальное замедление, мы можем найти стык с траекторией, по которой мы шли (5).

Теперь посмотрим, как выглядит настоящий робот:

Здесь каждая вертикальная стрелка представляет точку переключения. Мы можем заметить две вещи, отличающиеся от нашего простого примера:

  • Ограничения по ускорению и скорости не являются линейными. Это связано с тем, что мы спроецировали ограничения из пространства суставов, где они являются линейными, на путь. Реализация TOTG действительно находит аналитическое выражение этих ограничений, проецируемых на путь.
  • У нас есть два типа ограничений скорости: кривая ограничения скорости и кривая ограничения ускорения. Хотя последнее называется «пределом ускорения», это ограничение скорости, но из-за ограничений ускорения. Представим, что мы достигли кривой предельной скорости. Мы постараемся держаться на нем как можно дольше. Но может случиться так, что пока мы «едем на нем», мы на самом деле слишком быстро ускоряемся. Кривая ускорения устанавливает предел скорости, чтобы не нарушить максимальное ускорение. Как вы можете видеть на рисунке, эти кривые ограничения ускорения в основном возникают, когда кривая скорости имеет резкое изменение.

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

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

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

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

TOPP-CO

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

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

В дискретизированной формулировке вектор x имеет размер N - количество точек дискретизации.

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

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

Теперь поговорим о TOPP-CO, представленном в статье [2], которая означает оптимальную по времени параметризацию пути посредством выпуклой оптимизации. В этом подходе используется техника, показанная ранее: мы начинаем с проблемы параметризации пути, описанной ниже (если это не помогает, проверьте еще раз часть 1):

Необходимо проделать некоторую работу, чтобы преобразовать эту постановку в задачу выпуклой оптимизации. Авторы публикации [2] решили предоставить модель для ṡ ². Параметр пути s показывает, как мы геометрически располагаемся на пути, подумайте о полосе загрузки прогрессии. Предполагая, что мы знаем элементы управления, одно значение s будет соответствовать определенной временной метке и наоборот. Тогда естественно попытаться выразить ṡ ² как функцию от s, называемую здесь b (s). После дискретизации пути авторы выбрали модель (на дискретизированном отрезке от k до k + 1):

Затем функция b (s) выбирается линейной по s с некоторыми параметрами. Выбор оптимального b (s) (оптимального управления) будет тогда эквивалентен поиску оптимальных параметров b ^ k. Создание модели позволяет переформулировать исходную проблему и выразить ее только как функцию параметра s. После некоторой интеграции авторы показывают, что задачу можно представить в виде (ограничения для краткости опущены):

Хотя совершенно ясно, что функция для оптимизации является выпуклой, авторы показывают, что ограничения могут быть представлены в форме, удовлетворяющей формулировке ограничений конуса второго порядка (подкласс задач выпуклой оптимизации). Преобразуя это в матричную запись, мы затем можем использовать существующие инструменты для решения этой задачи выпуклой оптимизации и найти выражение b (s). Авторы объясняют, что мы можем найти временную параметризацию (эквивалентную нахождению элементов управления проблемами), интегрировав следующим образом:

Это для техники, используемой TOPP-CO. Мы не описали здесь явно формулировку ограничений и то, как они проецируются на траекторию. Преимущество этой формулировки Convex Optimization заключается в том, что любое ограничение может быть включено в процесс, если оно является выпуклым, и пока мы можем найти, как проецировать такие ограничения на путь (выразить ограничения как функцию от s) . В частности, в рецептуру могут быть добавлены ограничения по крутящему моменту. Другое преимущество выпуклой оптимизации состоит в том, что можно использовать или смешивать другие цели с соответствующими весами. В частности, авторы описывают, как включить тепловую энергию и скорость изменения крутящих моментов в качестве целевых функций.

Динамическое программирование

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

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

Итак, как выглядит динамическое программирование в случае параметризации пути? Мы можем представить это в упрощенной форме:

Ключевым аспектом динамического программирования является дискретизация пространства состояний, а также элементов управления. В нашем случае пространство состояний можно уменьшить до одного измерения (параметр пути s). Элементы управления можно свести к определению скорости (ṡ) в каждой из точек. Затем у нас есть сетка в 2D, где каждая точка сетки имеет пару (s, ṡ).

Теперь динамическое программирование идет в обратном направлении. Стартуем из состояния N-1. Мы смотрим на все допустимые скорости и вычисляем ускорения на основе скорости в точке N (которая равна 0), и проверяем, находится ли она в допустимом диапазоне ускорений. Основываясь на скорости, используемой между сегментами N-1 и N, мы можем получить время, затраченное на пересечение этого участка. Время, необходимое для достижения этой точки сетки, становится стоимостью, связанной с этой точкой.
Самое интересное об алгоритме динамического программирования связано с пунктом N-2. На этом этапе мы пытаемся связать все допустимые скорости из состояния N-2 с каждой допустимой скоростью из состояния N-1.
Принцип оптимальности Беллмана гласит, что стоимость в точке сетки равна стоимость в этой точке + минимальная стоимость любой точки, которую она может достичь.
Если мы возьмем в качестве примера точку (b), связанная с ней стоимость будет

Где (b) - ›(e) и (b) -› (d) - время перехода от N-2 к N-1 с использованием соответствующих скоростей в точках b, e и d.
Мы не делаем ' t необходимо запомнить все потенциальные траектории, которые начинаются из точки сетки (b). Нам нужно только вспомнить оптимальный. Откатываясь к точке 1, естественным образом найдем оптимальную траекторию.

Важно отметить, что в статье [3] рассматриваются только ограничения на совместную скорость и совместное ускорение, однако любой тип ограничений может быть вычислен, чтобы «исключить» некоторые точки сетки. Мы также показали только случай чистой оптимизации по времени, хотя функция стоимости может быть адаптирована для других целей, как это было показано ранее с TOPP-CO.

Итак, насколько эффективен метод динамического программирования? Если мы дискретизируем параметр пути в N точках и диапазон его производной в M точках, в общей сложности нам придется выполнить N * M * M итераций, что звучит приемлемо.
Динамическое программирование часто является предметом «проклятия размерности» », Что происходит, когда элементы управления имеют высокую размерность. В нашем случае сокращение элементов управления до одного измерения делает динамическое программирование жизнеспособным вариантом.

Какой подход использовать для решения реальных задач планирования пути роботов?

Теперь мы прошли три метода:

  • Один косвенный метод, TOTG
  • Один прямой метод, TOPP-CO
  • Один подход к динамическому программированию

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

1- Гибкость (ограничения и объективные затраты)

2- Время вычисления

3- Надежность

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

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

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

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

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

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

Источники:

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

[1]: Построение оптимальной по времени траектории для следования по траектории с ограниченными ускорением и скоростью: Тобиас Кунц и Майк Стилман.

[2]: Практическое оптимальное по времени планирование траектории для роботов: подход к выпуклой оптимизации: Дидерик Вершуре, Брэм Демеуленаэр, Ян Свеверс, Йорис Де Шуттер и Мориц Диль.

[3] Построение оптимальной траектории для роботов-манипуляторов с использованием динамического программирования: С. Сингх, М.С. Лея.