УДК 004.023

Применение метода вероятностной маршрутной карты в задачах планирования движения манипуляторов

Строев Вадим Андреевич – магистрант МИРЭА – Российского технологического университета.

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

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

Введение

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

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

Разработка и внедрение подобных системы позволила бы повысить автономность имеющихся систем управления, качество управления и эффективность работы, а также привлекательность продукта со стороны заказчика.

Области применения манипуляторов

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

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

Задача планирования перемещения

Под планированием перемещения манипулятора понимается поиск бесконфликтного пути для кинематической конструкции, который удовлетворяет всем условиям. Искомый путь представляет собой непрерывную кривую в конфигурационном пространстве объекта планирования (манипулятора), которая соединяет его начальное и конечное положение, исключает столкновения с препятствиями сцены и удовлетворяет всем кинематическим и динамическим ограничениям [1].

Общую задачу планирования перемещения манипулятора можно описать так. Пусть задана сцена как непустое множество препятствий  в области эвклидова пространства . Пусть также задана кинематическая цепь , где  – множество твердотельных звеньев, а  – множество кинематических ограничений таких, что при конкретной конфигурации цепи предикаты ограничений  принимают истинное значение Под конфигурацией  здесь понимается набор значений параметров, однозначно определяющий положение точек объекта A в пространстве сцены. Пространством допустимых состояний назовем множество всех конфигураций объекта , удовлетворяющих кинематическим ограничениям и исключающих столкновения с препятствиями сцены С_free = {c ∈ CA | J1(c) ⋀ J2(c), …, ⋀ Jk(c) ⋀ B1(c) ∩ O = ∅, …, ⋀ Bn(c) ∩ O = ∅}. Тогда постановка задачи поиска пути может быть сформулирована следующим образом. Для пары заданных бесконфликтных конфигураций c_init, c_goal ∈ C_free требуется найти непрерывный путь p(t): [0,1] → C_free такой, что p(0) = c_init и p(1) = c_goal [1]. На рисунке 1[1] показано конфигурационное пространство двухзвенного манипулятора.

Рисунок 1. Конфигурационное пространства двухзвенного манипулятора.

Методы планирования перемещения манипулятора

Существу различные методы планирования перемещения. Далеко не все из них пригодны для задач управления манипуляторами, а даже если и пригодны, то показывают низкую эффективность и ограниченны областью применения и кинематикой манипулятора. Среди всех методов планирования перемещения лучшие результаты в задачах, связанных с манипуляторами, демонстрируют методы PRM, RRT [2] и градиентного спуска [5].

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

Другая группа методов основана на построении маршрутной сети и поиски в этой сети с помощью методов Дейкстры [3] или A*[4] необходимого пути. Данная сеть представляет собой граф, вершинами которого являются конфигурационные состояния манипулятора, а ребра между ними перехода. Примерами данных методов являются PRM и RRT. Оба этих алгоритмов являются вероятностными, так охватывают не все конфигурационное пространство, а лишь некоторые его часть необходимые для построения путь. В данной работе речь пойдет исключительно о PRM.

Метод вероятностной дорожной карты (PRM)

Метод PRM можно сформулировать следующим образом. Задана сцена с множеством препятствий . Также, задан маршрутный граф G, который изначально является пустым. На каждом шаге алгоритма генерируется точка c_rand в конфигурационном пространстве объекта планирования (), такая, что удовлетворяет условиям . Способ генерации новой точки определяется выбранной стратегией сэмплирования (методов управления выборкой). Затем выполняется проверка найденной точки конфигурационного пространства (состояния объекта) на бесконфликтность с препятствиями сцены. Если для точки выполняются условия , то точка считается бесконфликтной и она включается в сформированное на текущий момент представление вершин маршрутного графа G, иначе точка отбрасывается. На следующей фазе проводится попытка расширить множество ребер маршрутной сети G, путем отыскания бесконфликтных переходов между ее вершинами (главным образом путем формирования новых переходов с новой вершиной в графе). После этого алгоритм повторяется. На создаваемые переходы можно накладывать дополнительные ограничения в виде максимального количества найденных переходов (k) за одну итерацию или максимально допустимого расстояния между вершинами (R), для которых будет создаваться переход. Эти ограничения могут использоваться одновременно. Значения данных параметров могут фиксироваться или адаптивно меняться в ходе построения и расширения маршрутной сети.

Рисунок 2. Блок-схема метода PRM.

На рисунке 2 представлена блок-схема метода PRM с модификациями. Нахождение пути в итоговом маршрутном графе осуществляется путем добавления начальной и конченой конфигурации манипулятора и поиску с помощью методов поиска Дейкстры или A*. Найденный путь можно оптимизировать. Это можно сделать простым срезателем траектории [5].

Разработка программного обеспечения для тестирования PRM в задачах планирования движения манипуляторов

Для тестирования метода PRM в задачах планирования перемещения манипуляторов было разработано тестовое программное обеспечение. Программное обеспечение было разработано в среде Visual Studio 2022 на языке программирования C#. Данное программное обеспечение в двухмерном пространстве позволяет достраивает местность и планировать движение 6 звенного манипулятора, у которого 3 вращательные и 3 поступательные степени подвижность, которые соединены друг с другом последовательно. На рисунке 3 представлена схема данного манипулятора. На рисунке 4 представлен интерфейс разработанного программного обеспечения.

В первой зоне отображаются результаты работы программы и область сцены. Синие, зеленные и красные линии — это звенья манипулятора в начальном положении. Розовые, желтые и оранжевые линии — это звенья манипулятора в конечном положении. Серые прямоугольники все также остаются препятствиями сцены.

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

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

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

В пятой зоне также находится интерфейс, необходимый для создания и настройки маршрутной сети методом PRM, а также запуска планировщика движения. Можно настроить отображение маршрутной сети (в данном случае множество найденных всевозможных состояний манипулятора).

Рисунок 3. Кинематика тестируемого манипулятора.

Рисунок 4. Интерфейс второго разработанного ПО.

Результаты испытания разработанного программного обеспечения

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

Рисунок 5. Маршрутная сеть, построенная для манипулятора для заданной сцены.

В таблице 1 показаны результаты формирования маршрутной сети методом PRM. На каждом шаге маршрутная сеть расширялась на 2000 вершин. В данной таблице приведены данные по количество сформированных переходов, а также времени добавления новых вершин в маршрутную сеть. Общее время построения маршрутной сети, состоящей из 10000 вершин, составило 9.7 секунд. На основании данной таблице был построен график, представленный на рисунке 6.

Таблица 1. Зависимость времени добавления вершин маршрутной сети от ее размеров.

Рисунок 6. График скорость построения маршрутной сети.

Затем, в найденной маршрутной сети был осуществлен поиск пути для перемещения манипулятора. Для этого в маршрутную сеть было добавлено начальное и конечное положение манипулятора. С помощью метода A* была произведена попытка поиска пути в маршрутной сети. Путь был найден при 4000 вершинах, но для выявления зависимости времени добавления вершин в зависимости от размера сети было произведено расширение сети до 10000 вершин. Найденный путь был оптимизирован простым срезателем траектории. После того как путь был найден манипулятор осуществил движение по нему. На рисунке 7 показаны результаты планирования движения манипулятора. Порядок движения манипулятора такой: а-б-в-г-д-е. Видно, что манипулятор благополучно нашел маршрут из начального положения в конечное, который не конфликтует с препятствиями сцены.

Рисунок 7. Процесс движения манипулятора по найденному пути.

Заключение

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

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

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

Список литературы

1. Задача планирования движения: [Электронный ресурс]. URL: https://neerc.ifmo.ru/wiki/index.php?title=Задача_планирования_движения (Дата обращения: 20.04.2023).
2. Казаков К.А., Семенов В.А. Обзор современных методов планирования движения. Труды ИСП РАН, том 28, вып. 4, 2016, стр. 241-294
3. Алгоритм Дейкстры. Разбор Задач: [Электронный ресурс]. Habr 2022 URL: https://habr.com/ru/companies/otus/articles/599621/ (Дата обращения: 25.04.2023).
4. Простое объяснение алгоритмов поиска пути и A*: [Электронный ресурс]. Habr 2019 URL: https://habr.com/ru/articles/444828/ (Дата обращения: 26.04.2023).
5. Чему робототехника может научить игровой ИИ: [Электронный ресурс]. Habr 2018 URL: https://habr.com/ru/articles/349044/ (Дата обращения: 21.04.2023).