Спросить
Войти
Systems of Control, Communication and Security
sccs.intelgr.com
УДК 004.896
Метод планирования траектории движения точки в пространстве с препятствием на основе итеративной кусочно-линейной
аппроксимации
Антонов В. О., Гурчинский М. М., Петренко В. И., Тебуева Ф. Б.
Постановка задачи: известные методы планирования траектории либо обладают высокой вычислительной сложностью, либо не позволяют найти траекторию, оптимальную по длине пути, что не позволяет использовать их в системах, где необходимо планирование траектории в режиме реального времени с условием минимизации перемещения. Целью работы является решение задачи планирования траектории движения точки из начального положения в конечное, в пространстве с препятствием, с малой вычислительной сложностью, в режиме реального времени. Используемые методы. Предложен метод планирования траектории на основе итеративной линейно-кусочной аппроксимации траектории. В методе анализируется возможность движения по прямой из начального состояния в конечное средствами аналитической геометрии. В случае пересечения траекторией препятствия, производится ввод дополнительного промежуточного состояния путем смещения наихудшей точки траектории по направлению от центра препятствия. Затем данные действия рекурсивно повторяются для движения из начального состояния в дополнительное, и из дополнительного в конечное. Критерием остановки рекурсии является возможность движения на каждом линейном участке траектории в обход препятствия. Результат: предложенный численный метод на основе итеративной кусочно-линейной аппроксимации позволяет выполнять поиск траектории движения точки в пространстве с препятствием. Метод можно использовать для работы в режиме реального времени за счет простоты исполняемых операций. Метод применим даже при большом количестве итераций, при условии использования параллельных вычислений, т.к. проверка возможности движения на каждом отрезке может выполняться в отдельном потоке. Новизна: предложен новый метод планирования траектории на основе рекурсивного алгоритма итеративной кусочно-линейной аппроксимации. Разработана схема предложенного метода. Определен способ анализа на предмет возможности прямого движения между двумя состояниями точки при наличии препятствия. Практическая значимость работы заключается в актуальности применения предложенного метода в различных областях техники: планирование траектории движения мобильных роботов и автономных транспортных средств, системы управления антропоморфными и промышленными манипуляторами, управление технологическими процессами в задачах поиска траектории движения и другие.
Библиографическая ссылка на статью:
Антонов В. О., Гурчинский М. М., Петренко В. И., Тебуева Ф. Б. Метод планирования траектории движения точки в пространстве с препятствием на основе итеративной кусочно-линейной аппроксимации // Системы управления, связи и безопасности. 2018. № 1. С. 168-182. URL: http://sccs.intelgr.com/archive/2018-01/09-Antonov.pdf Reference for citation:
Antonov V. O., Gurchinsky M. M., Petrenko V. I., Tebueva F. B. Numerical method of planning a trajectory of pass obstacles based on an iterative piecewise-linear approximation. Systems of Control, Communication and Security, 2018, no. 1, pp. 168-182. Available at: http://sccs.intelgr.com/archive/2018-01/09-Antonov.pdf (in Russian).
Системы управления,связи и безопасности №1. 2018
Systems of Control, Communication and Security sccs.intelgr.com
Актуальность
В ходе управления различными объектами или процессами в динамических средах является актуальной задача синтеза траектории перевода объекта из некоторого исходного состояния, в целевое, путем изменения его координат в некотором конечномерном пространстве.
Данная задача известна в литературе как задача «планирования траектории». Критерием оптимальности найденного решения обычно является минимизация расстояния или времени перехода между состояниями. Дополнительно, задача усложняется наличием «препятствий» в рассматриваемом многомерном пространстве.
В литературе широко освещены два подхода к планированию траектории [1] - подход на основе теории графов, а также сплайновая интерполяция. Первый подход сопряжен с большой вычислительной сложностью, а второй -со сложностью выбора опорных точек, излишним движением при их малом числе, и сложностью вычислений при большом.
В работе [2] отображены преимущества использования метода кусочно-линейной аппроксимации для решения задач оптимального управления на основе симплексного метода и метода последовательных итераций. Разработан алгоритм для решения краевых нелинейных задач управления.
В диссертационном исследовании [3] рассмотрено планирование траекторий движения многозвенного манипулятора в сложном трехмерном рабочем пространстве на основе эволюционных методов: генетического подхода, комбинирования генетического подхода и метода имитации отжига, комбинирования генетического подхода и метода репульсионного роя частиц.
Использование данных методов показывает, что средний процент достижимости точек составляет 77, 81, 85% соответственно, при среднем времени поиска решения от 3 до 9 с, что не позволяет использовать данные методы в режиме реального времени.
В статье [4] рассмотрены две экспериментальные платформы для тестирования систем управления и алгоритмов планирования движения в реальном времени. Для управления движением созданы контроллеры обратной связи, которые способны отслеживать опорные траектории на основе измерений датчиков. Опираясь на эффективность отслеживания этих контроллеров, разработаны эффективные по времени опорные траектории движений. При этом данный данные экспериментальные платформы при поиске опорного движения генерируют большое количество вариантов перемещения, что негативно сказывается на эффективности выбранной траектории при работе с простыми препятствиями.
Быстрый и унифицированный метод поиска траектории движения робота с минимальным рывком с использованием оптимизации роя частиц рассмотрен в работе [5]. Траектория с минимальным рывком делает алгоритм управления роботом простым и надежным. Для поиска траектории движения с минимальным рывком, была сформулирована проблема оптимизации траектории движения робота, ограниченная совместными параметрами узлов, включая начальное смещение и скорость смещения, промежуточное смещение сустава, конечное
Системы управления,связи и безопасности №1. 2018
Systems of Control, Communication and Security sccs.intelgr.com
смещение и скорость соединения. Для решения использовалась оптимизация роем частиц, в результате чего были найдены квазиоптимальные решения для траектории с минимальным рывком.
Планирование траектории обхода препятствий для космических манипуляторов на основе генетического алгоритма представлено в работе [6]. Предполагается, что в рабочем пространстве существует идеальная траектория, которая может быть описана двумя разделами сплайновой кривой высокого порядка и удовлетворяет всем динамическим характеристикам космического манипулятора. Параметры точки соединения между двумя сплайн-траекториями могут влиять на искаженную форму двух траекторий в пространстве. Следовательно, манипулятор движется в соответствии с траекториями сплайнов и в то же время избегает всех препятствий. Оптимальная траектория обхода препятствий с короткой длиной и минимальным временем движения в совместном пространстве планируется с помощью генетического алгоритма, а динамические характеристики манипулятора удовлетворяют требованиям позиционирования. Моделирование выполняется на платформе имитатора космического манипулятора. Результаты показывают, что метод является стабильным и эффективным, а генерируемая траектория удовлетворяет особым требованиям к производительности космического манипулятора.
В статье [7] представлено несколько практических алгоритмов планирования движения манипуляторов мобильных роботов. Алгоритмы реализованы на основе генерации графа траектории движения, который учитывает вычислительные и временные ограничения вычислительной системы робота. Алгоритм генерации траектории использует локальные поисковые графы на основе эвристического поиска, формирующиеся с учетом информации об окружающей среде для обхода препятствий в объемном пространстве.
Метод генерации и корректировки траектории для манипуляторов роботов рассмотрен в публикации [8]. Для планирования траектории манипуляторов служебных роботов в условиях с препятствиями предлагается метод генерации и корректировки траектории при работе человека с роботом. Подход предназначен для создания траектории манипулятора аналогичной движению человека на основе динамической модели примитивного движения. Далее происходит искажение траектории движения, вызванное высокой степенью подвижности манипулятора. В процессе искажения генерируется трехмерная траектория, используя формулы вращения Родригеса. Эксперименты с обходом препятствий подтверждают гибкость предлагаемого подхода, который может адаптироваться к сложной повседневной среде с несколькими видами препятствий.
В работе [9] представлен алгоритм решения обратной задачи кинематики избыточного манипулятора в ограниченном пространстве. В алгоритме вводится виртуальный отталкивающий крутящий момент, налагаемый топологической структурой робота и препятствием. Метод вычисляет кратчайшие расстояния между границами шарниров манипулятора и препятствиями. Связь манипулятора и препятствия моделируется эллипсоидами, для оценки минимальных расстояний между препятствиями и звеньями манипулятора.
Системы управления,связи и безопасности №1. 2018
Systems of Control, Communication and Security sccs.intelgr.com
В работах [10-13] исследованы методы планирования траектории движения манипулятора на основе методов потенциальных полей, копирования и обучения естественной оптимизации движения руки человека, аналитического подхода с использованием матриц Якоби, кривых Безье и др. Однако отсутствие критериев остановки при генерации траектории требует высокой производительности вычислительной системы.
В работах [14-15] рассмотрены методы планирования траектории движения гиперизбыточных манипуляторов на основе оптимизации генетическим алгоритмом и вариационного исчисления, из-за чего предлагаемые методы нельзя использовать в режиме реального времени.
Использование генетических алгоритмов для решения задач поиска траектории движения манипуляторов описана в статье [16] о прямом подходе к решению задач планирования траектории с учетом динамики в сложных условиях. Предложенная методика позволяет получить гладкие траектории для промышленных роботов в сложных средах с использованием прямого метода.
В изложенных работах [1-16] планирование траектории движения представлено для манипуляторов и аналогично решаемой задаче планирования движения точки в пространстве. Представленные методы обладают высокой вычислительной сложностью, либо не позволяют найти траекторию, оптимальную по длине пути, что не позволяет использовать их в системах, где необходимо планирование траектории в режиме реального времени с условием минимизации перемещения.
Постановка задачи
Целью данной статьи является решение задачи планирования траектории с учетом минимизации перемещений в режиме реального времени.
Для формальной постановки и решения задачи в работе введены обозначения, представленные в таблице 1.
Таблица 1 - Обозначения
Обозначение Физический смысл обозначения
n - размерность рассматриваемого пространства
XH = iXH\\, ХН2, &&&, XHn} - координаты точки в начальном состоянии
XK = {хК1, ХК 2 ,&&&, XKn} - координаты точки в конечном состоянии
R - радиус препятствия
d - минимальное расстояние траектории до центра препятствия
Xn - промежуточное состояние
хд - дополнительное состояние
h - параметр изломанности траектории
Суть планирования заключается в поиске траектории, переводящей объект из начального состояния в конечное, в обход препятствия.
Systems of Control, Communication and Security
sccs.intelgr.com
Ограничимся рассмотрением таких случаев, когда препятствие одно и может быть аппроксимировано многомерной сферой.
Исходными данными для задачи являются векторы значений координат в начальном и конечном положении:
а также информация о препятствии, аппроксимированном гиперсферой, в виде её центра и радиуса:
Для достижения поставленной цели необходима разработка низкозатратного по вычислительным ресурсам метода, который позволит производить планирование траектории в режиме реального времени.
Для определенности рассмотрим случай планирования траектории в двумерном пространстве, вследствие удобства визуализации, а затем покажем возможность распространения предложенного метода на многомерный случай. Постановка задачи для двумерного пространства имеет вид, изображенный на рис. 1 .
Для решения поставленной задачи предлагается численный метод планирования траектории, заключающийся в аппроксимации траектории кусочно -линейной функцией и последовательном увеличении количества её отрезков до тех пор, пока все ограничения по обходу препятствия не будут выполнены.
Данный метод основан на рекурсивном алгоритме.
На его вход подаются данные о начальном и конечном состоянии, а также информация о препятствии, приведенные в постановке задачи.
О = °о2,...,oj,R.
Численный метод планирования траектории
Траектория обхода препятствия
Препятствие
Рис. 1. Исходные данные задачи
Systems of Control, Communication and Security
sccs.intelgr.com
В теле рекурсии проверяется возможность движения из исходного состояния в конечное по траектории, состоящей из одного отрезка, т. е. прямое движение, приведенное на рис. 2.
•Начальное состояние
Препятствие Рис. 2. Прямое движение возможно
Если прямое движение возможно, данный отрезок добавляется к траектории, получаемой на выходе.
В случае же пересечения траекторией ХЯХ^. препятствия, как показано на рис. 3, находится промежуточное состояние Хя с наименьшим расстоянием ё до центра препятствия и вводится дополнительное состояние Хд, полученное путем перемещения точки Хя «наружу» окружности препятствия, с некоторым «запасом» к.
d > R
Конечное состояние
Препятствие Рис. 3. Введение дополнительного состояния
Затем исходная задача разбивается на две - планирование траектории для перемещения из Хя в Хд, и из Хд в ХК. Для каждой из них вызывается следующая итерация рекурсии.
Systems of Control, Communication and Security
sccs.intelgr.com
На каждой итерации рекурсии вводятся дополнительные состояния до тех пор, пока на каждом отрезке траектории не будет выполняться критерий обхода препятствия.
Рассмотрим методики для выполнения всех приведенных выше действий.
Множество точек пространства, лежащих на отрезке ХЯХ^. может быть описано с помощью параметрической функции:
ДЯ) = Л-Хн + (1-Я)• Хк, Я е [0,1]. (4)
Выполнение критерия обхода препятствия означает, что наименьшее расстояние d между точками отрезка и центром препятствия превышает его радиус, т. е.:
d = min (IIО - f Я)||)> R . (5)
Яе[0,1] v &
Данное высказывание проиллюстрировано на рис. 2.
Для нахождения данной величины можно воспользоваться следующей методикой.
Пусть имеется траектория в виде отрезка ХЯХ^. и окружность с центром в точке О и радиусом R . Рассмотрим плоскость, проходящую через точки Хя, Хк, О (рис. 4). В данной плоскости проведем перпендикуляры через точки Хя и Хд., перпендикулярно отрезку ХЯХ^., которые делят плоскость на области а, ß, у, как показано на рис. 4.
Очевидно, что в случае нахождения центра окружности в области а, например, в точке О , наименьшее расстояние от центра окружности до точек отрезка ХЯХ^. равно длине отрезка ОхХн.
Аналогично, для области у данное расстояние равно длине отрезка ОъХк.
В случае нахождения центра окружности в области ß, например, в точке О, минимальное расстояние равно расстоянию между данной точкой и прямой, проходящей через отрезок ХЯХ^.. Данное расстояние может быть найдено как расстояние между точкой и прямой:
ХНХК хХн02
хнхк
Таким образом, задача сводится к определению области нахождения центра окружности препятствия.
В случае нахождения центра окружности в области а, включая разделительный перпендикуляр, угол между векторами хнхк и х!!()] неострый, таким
образом, скалярное произведение хнхк-хн01 неположительно.
Аналогично, для области у, включая разделительный перпендикуляр, скалярное произведение хнхк ■ хк02 неотрицательно.
Systems of Control, Communication and Security
sccs.intelgr.com
Рис. 4. Варианты расположения центра окружности препятствия
Таким образом, минимальное расстояние от точек отрезка ХНХК до центра окружности О в выражении (5) может быть найдено по формуле:
если ХНХК ■ X,,О < О,
ХнХкхХн02
хнхк
если ХНХК ■ Хн0 > 0 и ХНХК ■ Хк0 < О,
если ХНХК ■ Хк0 > 0.
Тогда критерий успешного обхода препятствия принимает вид:
а >я . (8)
Рассмотрим введение дополнительного состояния Х . Для нахождения координат данного состояния, как показано на рис. 3, необходимо отложить от точки О вектор к-ОХп такой, чтобы выполнялось условие:
к-ОХ г
= R + h.
Для нахождения точки Хп и, соответственно вектора 0ХП точки Хн вектор хнхп , который может быть найден по формуле:
_. _. Y Г) Y Y
Y Y — Y Y H^ H К
Л „Л n — Л „Л „--ХНХК
отложим от (10)
Коэффициент к может быть найден из уравнения (9).
Схема предлагаемого метода приведена на рис. 5.
Предлагаемый метод описан на примере планирования траектории в двумерном пространстве. Однако все формулы и выкладки справедливы и для пространств с большей размерностью, что позволяет применять разработанный метод для пространств с любой размерностью.
Systems of Control, Communication and Security
sccs.intelgr.com
Рис. 5. Схема метода планирования кусочно-линейной траектории
Анализ гибкости и практической применимости метода
Данный метод обладает гибкостью, которая достигается за счет варьирования введенного ранее параметра к. Его увеличение делает траекторию объекта более «угловатой» за счет уменьшения количества промежуточных состояний, что уменьшает вычислительные затраты на планирование траектории, но также увеличивает длину пути, уменьшая при этом скорость перемещения.
Уменьшение параметра к наоборот, уменьшает длину пути, увеличивает скорость и делает траекторию более «гладкой», но также увеличивает вычислительную сложность, так как увеличивается количество промежуточных состояний. Иллюстрирует данное высказывание рис. 6 на котором схематично приведены траектории обхода препятствия при различных значениях параметра к При значении к = 0 применение предложенного метода недопустимо, т. к. траСистемы управления,связи и безопасности №1. 2018
Systems of Control, Communication and Security sccs.intelgr.com
ектория вырождается в гладкую кривую, а количество дополнительных состояний стремится к бесконечности.
Препятствие
Рис. 6. Влияние параметра к на плавность траектории: а) большее значение; б) меньшее значение
Время расчета траектории может быть уменьшено за счет применения параллельных вычислений. Проверка возможности движения на каждом отрезке может выполняться в отдельном потоке.
Предложенный метод может применяться в различных областях техники: планирование траектории мобильных роботов и автономных транспортных средств, системы управления промышленными и антропоморфными манипуляторами, управление технологическими процессами и т. п.
Данный метод может быть модифицирован для планирования траектории обхода препятствий более сложной формы, чем сфера, а также их большего количества. Также, необходимо провести исследования о возможности применения метода в динамически изменяющихся средах.
Выводы
В данной статье предложен численный метод планирования траектории движения точки в пространстве на основе кусочно-линейной аппроксимации путем итеративного введения дополнительных промежуточных состояний.
Анализ современных источников литературы [1-16] указывает на сложность при разработке систем планирования траектории движения точки на примерах планирования траектории движения манипуляторов для работы в режиме реального времени, а существующие методы обладают высокой вычислительной сложностью.
В основе работы используется метод планирования траектории на основе итеративной кусочно-линейной аппроксимации траектории движения точки в обход препятствия. Разработанный способ для определения невозможности прямого движения между двумя состояниями точки при наличии препятствия и критерии ввода промежуточных состояний обеспечивают успешный обход препятствий, представленных в виде одной гиперсферы. Приведенная схема
Системы управления,связи и безопасности №1. 2018
Systems of Control, Communication and Security sccs.intelgr.com
метода планирования кусочно-линейной траектории обеспечивает высокую скорость поиска и генерации вычисляемой траектории.
Проведенный анализ гибкости метода показал, что он может быть использован для генерации траектории движения с различным количеством промежуточных точек, что при дальнейшем развитии метода позволит проводить оптимизацию планирования траектории по различным критериям: вычислительные затраты, длина траектории и т. п.
Предлагаемый численный метод можно использовать в режиме реального времени за счет его низкой вычислительной сложности, что позволяет свести к минимуму оборотное время, от момента передачи задания и до момента завершения его выполнения.
Представленный численный метод может быть использован в таких областях науки и техники как планирование траектории движения мобильных роботов и автономных транспортных средств, систем управления антропоморфными и промышленными манипуляторами, управления технологическими процессами и др.
Системы управления,связи и безопасности №1. 2018
Systems of Control, Communication and Security sccs.intelgr.com
References
Системы управления,связи и безопасности №1. 2018
Systems of Control, Communication and Security sccs.intelgr.com
Статья поступила 27 февраля 2018 г.
Информация об авторах
Антонов Владимир Олегович - соискатель ученой степени кандидата технических наук. Аспирант кафедры организации и технологии защиты информации. Северо-Кавказский федеральный университет. Область научных интересов: математическое моделирование робототехнических систем, антропоморфная робототехника. E-mail: Ant.vl.02@gmail.com
Системы управления,связи и безопасности №1. 2018
Systems of Control, Communication and Security sccs.intelgr.com
Гурчинский Михаил Михайлович - студент магистратуры кафедры информационных систем и технологий. Северо-Кавказский федеральный университет. Область научных интересов: математическое моделирование автоматизированных систем, информационные технологии. E-mail: gurcmikhail@yandex.ru Петренко Вячеслав Иванович - кандидат технических наук, доцент. Заведующий кафедрой организации и технологии защиты информации. СевероКавказский федеральный университет. Область научных интересов: системы защиты информации, защита персональных данных, арифметические операции в конечных полях, синтез дискретных последовательностей, системы связи. E-mail: vip.petrenko@gmail.com
Тебуева Фариза Биляловна - доктор физико-математических наук, доцент. Заведующая кафедрой прикладной математики и компьютерной безопасности. Северо-Кавказский федеральный университет. Область научных интересов: моделирование процессов защиты информации в информационно-телекоммуникационных системах. E-mail: fariza.teb@gmail.com Адрес: 355000, Россия, г. Ставрополь, ул. Пушкина, д. 1.
Numerical method of planning a trajectory of pass obstacles based on an iterative piecewise-linear approximation
V. O. Antonov, M. M. Gurchinsky, V. I. Petrenko, F. B. Tebueva
Purpose. Known methods for planning a trajectory have a high computational complexity or cannot find a trajectory with a minimum length. This feature does not allow using them in systems where trajectory planning with a minimum length in real time mode is required. The aim of the paper is to solve the problem of planning the trajectory of a point between two states to bypass an obstacle, with a small computational complexity for real-time mode operation. Methods. The article proposes a numerical method for planning a trajectory based on iterative linear-piece approximation of a trajectory. The method analyzes the possibility of moving along a straight line from the initial state to the final state, using analytical geometry. If a straight trajectory crosses an obstacle, an additional state is introduced by displacing the worst point of the trajectory from the center of the obstacle. Then, these actions are recursively repeated for movement from the initial state to the additional state, and from the additional state to the final state. The criterion for stopping recursion is the ability to move on each linear section of the trajectory bypassing the obstacle. Results. The proposed numerical method, based on iterative piecewise linear approximation, makes it possible trajectory planning for the point bypass an obstacle. The method can be used for real-time mode operation due to the simplicity of the executed operations. The method can be used even for a large number of iterations, if parallel calculations are used (analysis of the possibility of movement on each segment can be performed in different threads). Novelty. The new method for planning a trajectory based on a recursive algorithm of iterative piecewise-linear approximation is proposed. The scheme of the proposed method is developed. Developed a method for analyzing the possibility of direct movement between two states of a point in a circumvention. Practical relevance. The proposed method of planning the trajectory can be used in various fields of technology: planning the trajectory of mobile robots and autonomous vehicles, anthropomorphic and industrial manipulator control systems, trajectory planning tasks in process control, and others.
Системы управления,связи и безопасности №1. 2018
Systems of Control, Communication and Security sccs.intelgr.com
Information about Authors
Antonov Vladimir Olegovich - Doctoral Student. The postgraduate student of the Department of Organization and Technology of Information Security. North-Caucasian Federal University. Field of research: mathematical modeling of robotic systems, anthropomorphic robotics. E-mail: Ant.vl.02@gmail.com
Gurchinsky Mikhail Mikhailovich - graduate student of the Department of Information Systems and Technology. North-Caucasian Federal University. Field of research: mathematical modeling of automated systems, information technologies. E-mail: gurcmikhail@yandex.ru
Petrenko Vyacheslav Ivanovich - Ph.D. of Engineering Sciences, Associate Professor. Head of the Department of Organization and Technology of Information Security. North-Caucasian Federal University. Field of research: information security systems, personal data protection, arithmetic operations in finite fields, synthesis of discrete sequences, communication systems. E-mail: vip.petrenko@gmail.com
Tebueva Fariza Bilyalovna - Dr. habil. of Physico-Mathematical Sciences, Associate Professor. Head of the Department of Applied Mathematics and Computer Security. North-Caucasian Federal University. Field of research: modeling of information security processes in information and telecommunication systems. E-mail: fariza.teb@gmail.com
Address: 355000, Russia, Stavropol, Pushkin st., 1.
