Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Санкт-Петербургский государственный университет

Кафедра механики управляемого движения

Выпускная квалификационная работа бакалавра

Планирование пути манипуляционного робота в среде с препятствиями.

Направление 010400

Прикладная математика и информатика

Сырский Александр

Санкт-Петербург

2018

Содержание

• Введение
• Постановка задачи
• Обзор литературы
• Глава 1. Основные свойства рабочего пространства и манипуляционного робота
• 1.1 Математическая модель двухзвенного манипуляционного робота
• 1.2 Обозначения для объектов в рабочем пространстве
• 1.3 Операторы
• 1.4 Предположения для упрощения
• Глава 2. Алгоритм планирования
• 2.1 Проблемы прямого планирования
• 2.2 Обзор алгоритма
• 2.3 Выборка движения
• Глава 3. Результаты программной реализации
• Выводы
• Заключение
• Списоклитературы


Введение

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

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

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

Постановка задачи

Исследование и дальнейшая реализация алгоритма разрешения пространственных ограничений (ResolveSpatialConstraits) для сгенерированных с помощью модифицированного метода быстрорастущих рандомизированных деревьев (rapidRRT-Connect) путей дляманипуляционного робота в средах с подвижными препятствиями.

Цели работы:

- Анализ методапланирования пути достижения целевой конфигурации наразличных сценах;

-Создание навигационной системы, обеспечивающей автономное движение и манипуляционное воздействие на плоскости;

-Разработка программного обеспечения (ПО), реализующего рассмотренный алгоритм.

Обзор литературы

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

Также Догар и Шриниваса [3] рассматривали задачу перемещения объекта в условии помех и создали библиотеку управляющих действий, в том числе нехватательных манипуляций, полагая, что каждый объект или часть помех перемещается только один раз с помощью одного управляемого действия.В [4] разработана и представлена библиотека движений для использования в такого рода задачах.

В. Ю. Рутковский, В. М. Суханов, В. М. Глумов при решении задачи построения математической модели плоского движения свободнолетающего космического манипуляционного робота рассматривают составные примитивы трехзвенного манипулятора, описываемые системами уравнений движения[5].

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

В связи с успехами применения алгоритмов машинного обучения в современных системах.В [8] описан алгоритм RRT-Connect(Rapidly-exploringRandomTree-быстрорастущий рандомизированный лес), как один из наиболее эффективных методов планирования пути, в [9] предлагается нейроэволюционный подход, основанный на модульном программировании. В задачах, где рассматривается анализ и классификация свойстввозможных состоянийрабочего пространства, представляется удобным использованиеметода RRT.

Один из наиболее эффективных вариантов алгоритмадля решения поставленной задачи предложил MikeStilman в своих работах на тему “NavigationAmongMovableObstacles”(“NAMO”)[10],[11],в частности “Manipulation Planning Among Movable Obstacles”[12],основанную на использовании алгоритма ResolveSpatialConstraits для поиска расстановок движимых объектов, блокирующих доступ к целевой конфигурации.

Также в статье Е.А. Энгель[13] рассматриваютсяметоды решения задач NAMO и DAMA (DiverseActionManipulation), модификации алгоритма RRT, такие как DARRT (DiverseActionRapidly-exploringRandomTree), DARETH,DARRTH(данные методы определяют подцели для манипуляционной задачи, интуитивно соответсвующие решению задачи человеком: приблизиться к объекту, взять и переместить), оптимизирующие общее время планирования.

Глава 1. Основные свойства рабочего пространства и манипуляционного робота

1.1 Математическая модель двухзвенного манипуляционного робота

Для получения кинематической модели манипулятора необходимо решить прямую (ПЗК) и обратную (ОЗК) задачу кинематики.

Рис. 1.1 Кинематическая цепь.

На рисунке 1.1 представлена кинематическая схема плоского двухзвенника с длинами звеньев и. Введем прямоугольную систему координат ХОУ, связанную с основанием первого звена. Механизм имеет возможность вращаться вокруг оси, перпендикулярной плоскости механизма на угол . Звено 2 может вращаться относительно первого вокруг шарнира, ось которого также перпендикулярна плоскости механизма, на угол .

Решение ПЗК позволяет связать обобщенные координаты и с декартовыми координатами Х, У конца 2 звена (характеристической точки схвата).

Решение имеет вид:

Решение ОЗК, соответственно, позволяет определитьобобщенные координаты и по известным декартовым координатам Х,У конца второго звена:

1.2 Обозначения для объектов в рабочем пространстве

В рабочем пространстве определены:робот-манипулятор, набор твёрдых стационарных препятствий , набор твёрдых движимыхобъектов Каждый из движимых объектов обладает свойствами:

-Центр объекта - заданная точка, где i=1,…,m.

-Определён вектор, задающий допустимое движение в обобщённых координатах.

-Возможен набор преобразований рабочего пространства для взаимодействия конечного эффектора с объектом.

Каждый объект имеет конфигурацию рабочего пространства, состоящую из сдвига (относительно начала координат) и ориентации , i=1,…,m. Конфигурация робота определена впространствеобобщённых координат. Рассматриваем начальное состояние системы робота и подвижных объектов :

Рис. 1.2.1 Вид начального состояния рабочей сцены.

- конечная конфигурация для подвижного объекта .

Задача планирования:

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

Рис.1.2.2 Рабочая сцена в целевой конфигурации.

1.3 Операторы

Желаемая последовательность путей может быть представлена в виде повторного применения операторов: Навигация и Манипуляция . Первый оператор определяет путь схвата робота, второй размещает один жёстко захваченный объект. Каждый оператор параметризуется по пути в пространстве концигураций робота:

, где путь от -огодо -ого.

Пусть- конфигурация по пути.

Состояниеотображается в , где для всех незадействованных объектов.

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

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

- относительное преобразование от конечной позиции схвата к позиции объекта в начале действия. В связи с жёстким захватом, путь объекта определяется путём схвата:

Для необходимо три условия.

1) Преобразование должно быть доступно для схвата и объекта.

2) Любая конфигурация и соответствующая конфигурация объекта должны не конфликтовать с неиспользуемыми объектами в .

1.4 Предположения для упрощения

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

Рис.1.4.1 С-пространство (пространство конфигураций) первых двух сочленений манипулятора до и после перемещения препятствия B[12].

Рис.1.4.2 С-пространство робота, захватившего препятствие B до и после того, как перемещёнопрепятствиеC (для визуализации представлены только перемещения объекта B) [12].

Глава 2. Алгоритм планирования

2.1 Проблемы прямого планирования

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

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

2.2 Обзор алгоритма

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

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

Чтобы формализовать поиск порядка объектов, обозначим область рабочего пространства, которая должна быть не занята, или зарезервирована при перемещении объектов - .После отбора для , содержит область, занятую роботом и объектомпри следовании по .

Рис. 2.2 Схема составления плана движения через поиск размещений

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

Работа алгоритмаRSC (ResolveSpatialConstraits) начинаетсяс выбора целевого объекта и целевой конфигурации робота . Первый вызов RSCопределяет эти два параметра и обнуляет . Планировщик избавляется от тупиковой ветви, когда PlanGrasp, PlanManipulationили PlanNavigationпрерываются, не доходя до положения робота в начальном состоянии , а именно .

* PlanGraspопределяет, захватобъекта Это многозадачное планирование из , начального состояния, в любое r, захватывающее . Этот шаг обеспечивает возможность достижения из начального состояния.

* PlanManipulationопределеят : Для данного планировщика даны начальное состояние и соответствующий захват объекта Его цель - соединить с любой доступной конфигурацией в множестве возможных размещений. Возвращает значение

* PlanNavigation-финальныйпланировщикпути - одноцелевойRRT-Connect, определяющий . Планировщик производит поиск от конечного захвата объекта : к захвату следующего объекта в .

2.3 Выборка движения

Для того чтобы применить алгоритм RSC, нам необходимо выбрать метод отбора пространства размещений объектов и множества путей манипулятора для Навигации и Манипуляции . Пути для операторов генерируются с использованием алгоритма RRT-Connect, который основан на одновременном построении случайных деревьев из начальной и целевой точек, продемонстрированном на Рис. 2.3, из каждого старта итеративно выполняется:сперва выбирается случайная точка xи ищется вершина, из которой путь до x будет минимальным, после чего функцией с некоторым весом выбирается на этом пути, добавляемая в общее дерево вместе с отрезком пути от до .

Рис. 2.3 Пути строятся из 2 точек.

Пример псевдо-кода для алгоритма RSC, предложенный в [11]:

Любому узлу в дереве RSC соответствует размещение некоторого объекта . Размещение может быть определено с помощью трёх конфигураций робота:,,.

- конфигурация робота для осуществления захвата объекта .

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

PlanGrasp,PlanManipulationиPlanNavigation - тривызоваалгоритма планировщика движения, используемые для выбора ,, а также для отбора ,и ,, по которым будут соединены эти пути.

Глава 3. Результаты программной реализации

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

На сцене представлены 5 объектов, 4 из которых можно двигать.

Целевая конфигурация -объект зелёного цвета должен находиться за рамкой.

Рис. 3.1 Робот перемещает конец второго звена (положение эффектора) к первому выбранному для перемещения объекту.

Рис. 3.2 Переместив первое препятсвие, переход на путь к следующему выбранному для перемещения объекту.

Рис. 3.3 Робот освобождает простраство для перемещения целевого объекта.

Рис. 3.4 Осуществляется захват целевого объекта и перемещение в его конечную позицию.

На таблице представлены результаты среднего общего времени планирования T в секундах, а такжесреднего времени, потребовавшегося на каждую отдельную операцию алгоритма RSC: , , - время на отбор путей для операций,, захватаи размещения соответственно,-время на построение путей с помощью RRT-Connect, - время планирования пространства.

Выводы

- Представлена система сортировки пространства путей для двухзвенного манипулятора, оперирующего в детерминированной среде с перемещаемыми препятсвиями.

- Исследован и программно реализован рассмотренный алгоритм.

Заключение

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

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

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

1.Brost R.C. Automatic Grasp Planning in the Presence of Uncertainty // IJRR. 1998. Vol. 7, No. 1.

2. Dogar M., Srinivasa S. Push-Grasping with Dexterous Hands: Mechanics and a Method // IROS. 2010.

3. Dogar M.R., Srinivasa S.S. A Framework for Push-Grasping in Clutter / RSS.2011.

4.Sucan I.A., Moll M., Kavraki L.E. The Open Motion Planning Library // RAM. 2012. Vol. 19, No. 4.

5.Рутковский В.Ю., Суханов В.М., Глумов В.М. Уравнения движения и управление свободнолетающим космическим манипуляционным роботом в режиме реконфигурации // Автоматика и телемеханика. 2010. №1.

6. Okada K., Haneda A., Nakai H., Inaba M., Inoue H. Environment Manipulation Planner for Humanoid Robots Using Task Graph That Generates Action Sequence // IROS.2004.

7. Ota J. Rearrangement of Multiple Movable Objects: Integration of global and Local Planning Methodology // ICRA. 2004. Vol. 2.

8. J. James J. Kuffner and S. M. LaValle, RRT-Connect: An Efficient Approach to Single-Query Path Planning, in ICRA, 2000.

9. Miikkulainen R., Valsalam V.K., Hiller J., MacCurdy R., Lipson H. Constructing Controllers for Physical Multilegged Robots using the ENSO Neuroevolution Approach // Evolutionary Intelligence. 2012. Vol. 5, No. 1. P. 45-56.

10. Stilman M., Kuffner J. Navigation Among Movable Obstacles: Real-Time Reasoning in Complex Environments // Humanoids. 2004.

11. Stilman M., Schamburek J.-U., Kuffner J., Asfour T. Manipulation Planning Among Movable Obstacles // ICRA. 2007.

12. van den Berg J., Stilman M., Kuffner J., Lin M., Manocha D. Path Planning among Movable Obstacles: A Probabilistically Complete Approach // WAFR. 2008

13. Е.А. Энгель“Интеллектуальная система управления манипуляционным роботом” 2014.

Размещено на Allbest.ru