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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

• 
  поиск пути в заданном n мерном пространстве состояний с изменением остальных координат по линейному закону;
  
• 
  поиск пути в заданном n мерном пространстве состояний с изменением части параметров (например углов поворота платформы) после достижения целевой точки пути;
  
• 
  итеративное уточнение траектории до требуемого уровня дискретизации;
  
• 
  использование ускоренных реализаций A*, эвристик.
  

Рис. 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.