Анализ алгоритмов планирования траекторий движения многокоординатных параллельных механизмов



жүктеу 97.62 Kb.
Дата23.07.2016
өлшемі97.62 Kb.
УДК 004.942
С.Е. АНТОНОВ

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

информационных технологий механики и оптики,

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



Анализ алгоритмов планирования траекторий движения многокоординатных параллельных механизмов


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

Введение


Перспективным направлением исследований является разработка прецизионных установок, позволяющих проводить высокоточные исследования. Механизмы параллельной кинематики (устройства, исполнительное звено которых соединяется с основанием с использованием нескольких независимых кинематических цепей) обладают рядом преимуществ, таких как: повышенная точность, обусловленная их параллельной структурой; жесткость; надежность; возможность манипулировать большими нагрузками [3]. Недостатком таких систем является повышенная математическая сложность программного обеспечения [1]. Исследователи механизмов параллельной кинематики отмечают недостаток в эмуляторах, с помощью которых можно было бы производить полноценное исследование и определение реальных возможностей проектируемых параллельных механизмов с количеством степеней свободы меньшим 6-ти [3]. Примеры использования параллельных механизмов приведены на рис. 1.

Рис. 1 — Применение параллельных механизмов

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

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

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

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


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

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

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

Обзор существующих алгоритмов планирования движений


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

В данный момент, для управления параллельными механизмами в основном предлагается использовать модифицированные волновые алгоритмы на основе А*, алгоритма Дейкстры.

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


  • проверка возможности позиционирования модели в крайние точки траектории;

  • проверка в одной ли зоне рабочей области находятся крайние точки;

    • необходим предварительный поиск рабочей области модели с выделением несвязанных зон;

  • выбор допустимой / необходимой дискретизация пространства поиска;

  • проверка прямолинейной траектории движения (по всем координатам);

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

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




      • поиск пути в заданном n мерном пространстве состояний с изменением остальных координат по линейному закону;

      • поиск пути в заданном n мерном пространстве состояний с изменением части параметров (например углов поворота платформы) после достижения целевой точки пути;

      • итеративное уточнение траектории до требуемого уровня дискретизации;

      • использование ускоренных реализаций A*, эвристик.

П
ример карты состояний, полученной по методы декомпозиции пространства приведен на рисунке 2. Метод включает в себя: разбиение рабочей области на ячейки с требуемой дискретностью (пересекающиеся в случае n-мерного пространства состояний); поиск пути волновым алгоритмом по центрам ячеек.

Рис. 2 — Карта возможных состояний модели, полученная по методу декомпозиции пространства

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

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



Описание предлагаемого алгоритма


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


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

Рис. 3 — Примеры рабочих областей моделируемых устройств

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


  • описывает декодирование, основанное на принципе максимального правдоподобия;

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

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

  • отбор выживающих путей выполняется для каждого состояния;

  • предварительный отказ от маловероятных путей упрощает процесс поиска.

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

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




Рис. 4 — Примеры работы предлагаемого алгоритма в двумерном пространстве состояний



Выводы


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

  • минимизация времени поиска траектории при препятствиях без локальных минимумов критерия оптимальности;

  • минимизация отклонения от заданной траектории;

  • эффективное использование памяти и ресурсов процессора;

  • возможность использования при высокой дискретности области поиска;

  • отсутствие необходимости предварительных расчетов (исключая общие шаги алгоритмов поиска).

В недостатки данного алгоритма можно выделить:

  • получаемая траектория не всегда оптимальна по длине, особенно при сложной структуре препятствий в рабочей области;

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

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

ЛИТЕРАТУРА


[1] «Наука и образование» [Электронный ресурс] / Электронное научно-техническое издание — Режим доступа: http://technomag.edu.ru/, свободный. – Яз. русский, английский.

[2] Винокурова C.И. Поиск пути в 3D-пространстве с учетом динамических объектов / Винокурова Светлана — 21-я Международная конференция по компьютерной графике и зрению: Москва, МГУ имени М.В. Ломоносова, 26–30 сентября 2011 г.: Труды конференции. – М.: МАКС Пресс, 2011. – 270 с. ISBN 978-5-317-03808-3, УДК 004.9, ББК 32.973.26-018.2, режим доступа:



http://www.graphicon.ru/proceedings/2011/conference/gc2011vinokurova.pdf.

[3] Parallel Robots (Second Edition) / J.-P. Merlet — The Netherlands: Springer, 2006. — 401pp.

[4] Xianwen Kong. Type Synthesis of Parallel Mechanisms / Xianwen Kong, Clément Gosselin — Berlin: Springer-Verlag Berlin Heidelberg, 2007. — 271 pp.

Работа выполнена самостоятельно.





©dereksiz.org 2016
әкімшілігінің қараңыз

    Басты бет