Статья 'Планирование траектории движения мобильного робота с использованием градиента функции исследования областей пространства конфигураций' - журнал 'Кибернетика и программирование' - NotaBene.ru
по
Меню журнала
> Архив номеров > Рубрики > О журнале > Авторы > О журнале > Требования к статьям > Редакция и редакционный совет > Порядок рецензирования статей > Политика издания > Ретракция статей > Этические принципы > Политика открытого доступа > Оплата за публикации в открытом доступе > Online First Pre-Publication > Политика авторских прав и лицензий > Политика цифрового хранения публикации > Политика идентификации статей > Политика проверки на плагиат
Журналы индексируются
Реквизиты журнала

ГЛАВНАЯ > Вернуться к содержанию
Кибернетика и программирование
Правильная ссылка на статью:

Планирование траектории движения мобильного робота с использованием градиента функции исследования областей пространства конфигураций

Пыхтин Павел Сергеевич

аспирант, , Волгоградский Государственный Технический Университет

400005, Россия, Волгоград, пр. Ленина,28.

Pykhtin Pavel Sergeevich

graduate student, Volgograd State Technical University

400005, Russia, Volgograd, pr. Lenina,28.

pavel.pykhtin@gmail.com
Камаев Валерий Анатольевич

доктор технических наук

профессор, кафедра Системы Автоматизированного Проектирования и Поискового Конструирования, Волгоградский Государственный Технический Университет

Волгоградский Государственный Технический Университет. 400005, Волгоград, пр. Ленина,28

Kamaev Valerii Anatol'evich

Doctor of Technical Science

Volgogradskii Gosudarstvennyi Tekhnicheskii Universitet. 400005, Volgograd, pr. Lenina,28

kamaev@unix.cad.vstu.ru
Крыжановский Анатолий Иванович

аспирант, кафедра САПР и ПК, Волгоградский Государственный Технический Университет

Волгоградский Государственный Технический Университет. 400005, Волгоград, пр. Ленина,28.

Kryzhanovskii Anatolii Ivanovich

Volgogradskii Gosudarstvennyi Tekhnicheskii Universitet. 400005, Volgograd, pr. Lenina,28.

anatoly.kryzhanovsky@gmail.com
Никляев Илья Юрьевич

аспирант, кафедра САПР и ПК, Волгоградский Государственный Технический Университет

Волгоградский Государственный Технический Университет. 400005, Волгоград, пр. Ленина,28.

Niklyaev Il'ya Yur'evich

Volgogradskii Gosudarstvennyi Tekhnicheskii Universitet. 400005, Volgograd, pr. Lenina,28.

spirit.of.fire@mail.ru
Пыхтин Павел Сергеевич

аспирант, кафедра САПР и ПК, Волгоградский Государственный Технический Университет

Волгоградский Государственный Технический Университет

Pykhtin Pavel Sergeevich

Volgogradskii Gosudarstvennyi Tekhnicheskii Universitet

pavel.pykhtin@gmail.com

DOI:

10.7256/2306-4196.2014.1.9828

Дата направления статьи в редакцию:

18-01-2014


Дата публикации:

1-2-2014


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


Ключевые слова: Мобильные роботы, Планирование движения, RRT, Поиск пути, Пространство конфигураций, Качество исследования, Motion Planning, Narrow Passages, Робототехника, Алгоритмы

Abstract: The article proposes an algorithm for constructing the trajectory of motion of a mobile robot using quality assessment studies of various regions of space configuration (GIRRT). The described algorithm is based on the RRT algorithm and can significantly increase the effectiveness of the latter to meet the challenges in the search for ways of spaces containing a large number of narrow passages. The quality of research space configurations at a particular point in this paper refers to a numerical measure of the likelihood of building a successful trajectory connecting RRT tree and this configuration. A comparison of the proposed GIRRT algorithm and the classical RRT algorithm is given. A series of simulation way-finding experiments was held. While solving the task of finding ways in area with few obstacles, the GIRRT algorithm shows performance close to that of the RRT algorithm. In turn, when finding a way to the loosely coupled spaces (the space where there are areas for which the number of reachable configurations do not belong to the region itself, is small), the GIRRT algorithm demonstrates significantly better performance.



Keywords:

mobile robots, planning movements, RRT, path finding, space of configurations, quality study, Motion Planning, Narrow Passages, robotics, algorithms

Введение

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

Одним из популярных алгоритмов планирования движения, который хорошо зарекомендовал себя в данной области, является алгоритм RRT (Rapidly exploring Random Trees). Этот алгоритм обеспечивает высокую скорость исследования пространства конфигураций, его сходимость была доказана при условии увеличения числа итераций, а также он неплохо зарекомендовал себя при решении задач большой размерности. Однако, данный алгоритм, как и другие алгоритмы на основе вероятностных дорожных карт, обладает плохой сходимостью, в случае если области, обеспечивающие связность отдельных компонент пространства конфигураций, имеют малый размер. Описанный случай соответствует наличию в пространстве конфигураций узких проходов. Описываемая в статье модификация алгоритма RRT может быть эффективно применена для построения траектории в подобных условиях.

Алгоритм RRT

Алгоритм RRT включает следующие шаги:

  1. Добавить в пустое дерево поиска начальную конфигурацию.
  2. Выбрать конфигурацию `C_(n)` , лежащую в `C_(Free)` .
  3. Найти в дереве `T` конфигурацию `C_(i)` , ближайшую к `C_(n)`.
  4. Построить путь `P_(i,n)` от `C_(i)` к `C_(n)` .
  5. Проверить на наличие коллизий путь `P_(i,n)` .
  6. Если коллизии не были найдены, добавить `C_(n)` и `P_(i,n)` в дерево `T`.
  7. Если `C_(n)` не является целевой конфигурацией, перейти к шагу 2.

На шаге 2 выбирается некоторая конфигурация из подмножества ` ` пространства конфигураций, не занятого препятствиями. Как правило, она выбирается случайным образом, что обеспечивает сходимость алгоритма в общем случае. Функция распределения вероятности, используемая для выбора новой конфигурации, может варьироваться. Классическим решением является использование равномерного распределения для выбора новых конфигураций. Очевидно, что в этом случае вероятность выбора новой конфигурации, такой, что она лежит в некоторой области `A` , будет равна отношению объемов областей `A` и `C_(Free)` . На рис. 1 приведен пример ситуации, когда две компоненты связности пространства разделены препятствиями с узким проходом между ними. Траектория, соединяющая начальную и конечную точки пути, может быть найдена только при условии, что новая конфигурация будет взята из пересечения пространств компоненты `B` и региона видимости конфигураций, лежащих в пространстве `A` . В этом случае вероятность успешного выбора новой конфигурации оказывается весьма низкой, что заметно увеличивает время работы алгоритма и может привести к ложно отрицательному результату.

Алгоритм RRT с использованием градиента качества исследования (GIRRT)

Для решения описанной выше проблемы нами предложено использовать функцию распределения вероятности, которая сопоставляет конфигурациям в регионе `C` большие значения плотности вероятности, чем значениям в регионах `A` и `B` (рис. 1). В данной работе предлагается использование в качестве таковой функции от градиента исследования `F_(IG)`.

picture1

Рис. 1. Пространство с двумя компонентами связности A и B, соединенное узким проходом C.

Функция `F_(IG)` отображает величину градиента качества исследования `G_(I)` в некоторой точке `C_(I)` в значение плотности распределения случайной величины, используемой при выборе новых конфигураций, в этой же точке.

`F_(IG)(C_(i)): G_(I)(C_(i))->P(C_(i))`

(1)

Функция `G_(I)(C_(i))` рассчитывается как:

`G_(I)(C_(i))=(dI)/(dC)`

(2)

где `I(C)` – функция качества исследования для некоторой конфигурации `C_(i)` . В общем случае функция `I(C)` отображает дерево поиска в поле скалярных значений. Под качеством исследования в данной статье понимается суммарная вероятность успешного добавления конфигурации `C` в дерево поиска `T` . Таким образом, она может быть описана как:

`I(C)=int P_(path)(C_(T),C)dC_(T)`

(3)` `

где `P_(path)(C_(T),C)` – функция, описывающая вероятность успешного соединения конфигурации `C_(T)` и конфигурации `C` . `C_(T)` – конфигурация дерева поиска `T` , т. е. `C in T` . Функция `P_(path)(C_(T),C)` не может быть выражена аналитически в подавляющем большинстве задач, однако можно сделать вывод о том, что она обратно зависит от длины ребра, соединяющего дерево `T` и конфигурацию `C` .

В данной работе для расчета функций `F_(IG)`, `G_(I)`, `I` применялась равномерная прямоугольная сетка – назовем ее «базовой» – размерности `N`, равной размерности пространства поиска, с шагом `M` по всем направлениям. Эта сетка разбивает исходное пространство конфигураций `bbbA` на множество областей `bbbA_(i)` . Таким образом, функции `F_(IG)`, `G_(i)`, `I`представлены тензорами ранга `N` и размерности `M`.

Как было замечено выше, необходимая для вычисления функции `I` функция вероятности успешного соединения новой конфигурации и конфигурации дерева поиска `P_(path)(C_(T),C)` не может быть формализована для многих прикладных задач. По этой причине она была заменена тензором весов `W` , который посредством свертки применяется к тензору `D` , описывающему распределение конфигураций дерева поиска по областям пространства конфигураций, соответствующим ячейкам базовой сетки. Таким образом, значение тензора `I` вычисляется как:

`I=D*W`

(4)

Для вычисления градиента исследования `G_(I)` был применен тензорный вариант оператора Собеля.

`(G_(I))_(1)=I*S_(1), (G_(I))_(2)=I*S_(2), ... , (G_(I))_(N)=I*S_(N)`

(5)

где `S_(i)` – тензор описывающий оператор Собеля для измерения `i` .

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

`hat I=I*B`

(6)

где `B` – тензор гауссианы для случая `N`-мерного пространства, обеспечивающий размытие.

Таким образом, тензор градиента исследования вычисляется следующим образом:

`(G_(I))_(1)=hat I*S_(1), (G_(I))_(2)=hat I*S_(2), ... , (G_(I))_(N)=hat I*S_(N)`

(7)

Отдельно следует рассмотреть значения градиента на границе препятствий. В силу того, что конфигурация `C_(obst)` , лежащая внутри препятствия, является некорректной и не может быть добавлена в дерево поиска, значение `D(C_(obst))` всегда равно 0. Таким образом, по мере роста дерева поиска на границе препятствий будет возникать градиент исследования. Однако результат проверки на наличие препятствия сам по себе является некоторым результатом исследования, что позволяет считать граничные области препятствий исследованными, начиная с момента достижения их деревом поиска.

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

`hat(G_(I))_(j)={(0,C_(j) in bbbA_(text(border))),(G_(I)_(j),):}`

(8)

где `bbA_(text(border))` – некоторая область на границе препятствия.

Областью на границе препятствия считается любая область `bbA_(i) in bbA`, для которой справедливо `i=[i_(1), ... , i_(N)]` , `i_(m) in [1 .. M]` , а также `EE k in [1 .. N]` , при котором выполняется условие `(bbA_(i) in bbA_(Free) ^^ bbA_(i^text(neighbour)) in bbA_(obst)) vv (bbA_(i) in bbA_(obst) ^^ bbA_(i^text(neighbour)) in bbA_(Free))` где `i^text(neighbour)=[1, ..., i_(k)+-1, ..., i_(N)]` , а `bbA_(Free)` , `A_(obst)` – области, соответственно, содержащие и не содержащие препятствия.

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

`F_(IG)=(f(|hat(G_(I))_j|))/(sum_(k)f(|hat(G_(I))_(k)|))`

(9)

где `j` , `k` ­- `N`-мерные вектора индексов элемента тензора, такие что `AA j,k=[i_(1), ..., i_(N)] | i_(m)=1 .. M` , а функция `f(x)` позволяет задать распределение весов для разных значений градиента.

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

Результаты

Описанный в данной статье алгоритм был применен для решения задачи поиска пути на плоскости. Было произведено сравнение среднего количества итераций, необходимых для нахождения пути для предлагаемого алгоритма и классического алгоритма RRT. Были составлены два набора тестовых карт – с разреженными препятствиями и слабосвязанные (присутствуют области, соединяемые только лишь узкими проходами) и проведено моделирование работы алгоритмов на этих наборах (табл. 1). Как видно из результатов, число итераций, необходимое алгоритму GIRRT для нахождения пути, как правило, не превышает таковое для алгоритма RRT, а в случае слабосвязанных областей существенно ниже.

Таблица 1

Сравнение числа итераций поиска пути алгоритмами RRT и GIRRT.

Конфигурация препятствий

Число итераций алгоритма GIRRT

Число итераций алгоритма RRT

Высокая связность пространства

Конфигурация 1

165

173

Конфигурация 2

167

155

Слабосвязанные области

Конфигурация 4

546

>5000

Конфигурация 5

518

4612

Заключение

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

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

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

Библиография
1.
Камаев В.А. Принципы устройства контейнеров для построения гибких программных систем / Камаев В.А., Костерин В.В., Прыгунков М.О.// Известия Волгоградского государственного технического университета, 2007. – № 1. – С. 71-73.
2.
Bruce J., Veloso M. Real-Time Randomized Path Planning for Robot Navigation [Электронный ресурс]. – Режим доступа: http://www.cs.cmu.edu/~15780/readings/02iros-errt.pdf
3.
Jaillet L. Dynamic-Domain RRTs: Efficient Exploration by Controlling the Sampling Domain / Jaillet L., LaValle S.M., Simeon T., Yershove A. [Электронный ресурс]. – Режим доступа: http://msl.cs.uiuc.edu/~lavalle/papers/YerJaiSimLav05.pdf
4.
Н.П. Вашкевич, В.Н. Дубинин Вопросы разработки операционной семантики функциональных блоков IEC 61499 // Программные системы и вычислительные методы. - 2012. - 1. - C. 10 - 16.
5.
Горохов А.В. Формальный синтез структуры имитационной модели (на примере синтеза системно-динамических моделей) // Программные системы и вычислительные методы. - 2013. - 3. - C. 277 - 284. DOI: 10.7256/2305-6061.2013.3.8855.
References (transliterated)
1.
Kamaev V.A. Printsipy ustroistva konteinerov dlya postroeniya gibkikh programmnykh sistem / Kamaev V.A., Kosterin V.V., Prygunkov M.O.// Izvestiya Volgogradskogo gosudarstvennogo tekhnicheskogo universiteta, 2007. – № 1. – S. 71-73.
2.
Bruce J., Veloso M. Real-Time Randomized Path Planning for Robot Navigation [Elektronnyi resurs]. – Rezhim dostupa: http://www.cs.cmu.edu/~15780/readings/02iros-errt.pdf
3.
Jaillet L. Dynamic-Domain RRTs: Efficient Exploration by Controlling the Sampling Domain / Jaillet L., LaValle S.M., Simeon T., Yershove A. [Elektronnyi resurs]. – Rezhim dostupa: http://msl.cs.uiuc.edu/~lavalle/papers/YerJaiSimLav05.pdf
4.
N.P. Vashkevich, V.N. Dubinin Voprosy razrabotki operatsionnoi semantiki funktsional'nykh blokov IEC 61499 // Programmnye sistemy i vychislitel'nye metody. - 2012. - 1. - C. 10 - 16.
5.
Gorokhov A.V. Formal'nyi sintez struktury imitatsionnoi modeli (na primere sinteza sistemno-dinamicheskikh modelei) // Programmnye sistemy i vychislitel'nye metody. - 2013. - 3. - C. 277 - 284. DOI: 10.7256/2305-6061.2013.3.8855.
Ссылка на эту статью

Просто выделите и скопируйте ссылку на эту статью в буфер обмена. Вы можете также попробовать найти похожие статьи


Другие сайты издательства:
Официальный сайт издательства NotaBene / Aurora Group s.r.o.
Сайт исторического журнала "History Illustrated"