Вероятностный декомпозиционный подход к решению задачи планирования траектории на плоскости

ВЕроятностный декомпозиционный подход к решению задачи планирования траектории на плоскости

Институт системного анализа Российской академии наук, *****@***ru

Российский университет дружбы народов, ivan. *****@***com

В работе рассматривается параметрический алгоритм планирования траектории на плоскости, реализующий декомпозиционный подход к решению поставленной задачи. Описывается эвристическое правило выбора настроечных параметров алгоритма, использование которых на практике приводит к наилучшим результатам. Работа выполнена при финансовой поддержке РФФИ, проект 12-07-31058-мол_а.

Ключевые слова: планирование траектории, построение траектории, A*, R*.

Введение

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

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

Обычно в искусственном интеллекте и робототехнике, указанная выше задача построения траектории рассматривается как задача поиска пути на взвешенном графе. То есть окружающее БТС пространство моделируется графом, вершинам которого соответствуют некоторые области (точки) пространства (плоскости), а ребрам – элементарные траектории (обычно представляющие из себя отрезки прямых), следование по которым может быть обеспечено системой управления БТС в автоматическом режиме. После построения графа, осуществляется поиск пути на нем с помощью одного из известных алгоритмов [1].

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

В настоящем работе будет рассмотрен алгоритм, реализующий вероятностный декомпозиционный подход – R* [3]. Этот алгоритм использует в своей работе параметризованный случайный выбор для осуществления разбиения исходной задачи на подзадачи. Соответственно, в зависимости от значений установленных параметров меняется качество решения задачи планирования (скорость построения траектории, количество затраченной оперативной памяти, длина траектории). В работе будет показано, что существует способ эвристического задания параметров, который на практике (в ходе проведенных многочисленных экспериментов) приводит к наилучшим результатам.

Итерационный и декомпозиционный подходы к решению задачи планирования траектории на плоскости

Будем рассматривать задачу планирования траектории БТС на плоскости как задачу поиска пути на графе определенного вида – метрическом-топологическом графе (МТ-графе). Подробное описание этой графовой модели приведено в [4].

Основным структурным элементом МТ-графа является бинарная матрица, которая соответствует цифровой карте местности, - матрица проходимости. Имеет смысл представить эту матрицу в виде таблицы: закрашенным ячейкам соответствуют элементы матрицы со значением «1» (непроходимые для БТС области пространства); не закрашенным ячейкам – элементы со значением «0» (проходимые области). Задача планирования, таким образом, сводится к задаче отыскания последовательности смежных проходимых ячеек таблицы (или, что то же самое, элементов матрицы проходимости МТ-графа со значениями «0») – см. рис. 1. В дальнейшем элементы матрицы проходимости (они же – ячейки клетки в таблице) будем называть клетками МТ-графа. Вес найденного пути (длина построенной траектории) рассчитывается как сумма весов переходов по всем смежным клеткам, входящим в путь. При этом вес перехода между вертикально (горизонтально) смежными клетками полагается равным 10, вес перехода между диагонально-смежными клетками – 14.

Нетрудно убедиться, что любому МТ-графу может быть поставлен в соответствие взвешенный граф, поэтому для поиска пути на МТ-графе могут использоваться известные алгоритмы поиска пути на графе, например, эвристический алгоритм А*. К сожалению, однако, даже обладая наилучшей из возможных эвристик (а именно функцией задающей метрику на множестве клеток МТ-графа), алгоритм A* затрачивает слишком много вычислительных ресурсов на поиск пути. Дело в том, что алгоритм А* базируется на итерационном обходе элементов графа, начиная с начального и до выполнения некоторого критерия. В процессе такого обхода для каждого элемента рассчитывается и запоминается в оперативной памяти вычислителя определенный набор числовых характеристик. Только после того как обход завершен, искомый путь может быть восстановлен с использованием всех результатов промежуточных вычислений в совокупности. Как показывает практика (и тому существуют и теоретические обоснования) число рассмотренных алгоритмом A* элементов МТ-графа, чрезмерно велико, когда начальное и целевое положение отделены препятствием, что на практике наблюдается почти всегда – см. рис. 1.

Рис.1. МТ-граф и найденный с помощью алгоритма A* путь на нем (серым отмечены клетки рассмотренные алгоритмом)

Существуют определенные техники, позволяющие улучшить результат работы A* (т. е. сократить пространство поиска), но лишь до некоторого предела. Таким образом, целесообразно исследование и разработка алгоритмов поиска пути на МТ-графе, опирающихся на иные принципы, нежели итерационный обход. Одним из таких алгоритмов является алгоритм R* [3], который опирается на принцип декомпозиции. То есть исходная задача разбивается на подзадачи (локальные задачи), каждая из которых решается по отдельности, а итоговое решение получается композицией решений локальных задач.

На каждом шаге алгоритм R* выбирает К клеток МТ-графа, расположенных на расстоянии Δ от текущей. Под расстоянием здесь и далее подразумевается значение, которое принимает метрическая функция (эвристика алгоритма А*) на заданных клетках МТ-графа. Далее выбранные клетки оцениваются с помощью того же правила, что и в алгоритме А*, и соответственно ранжируются. Выбирается минимальная в смысле заданного порядка клетка (локальная целевая клетка) и путь до нее строится с помощью алгоритма A* (локальный поиск). Однако на построение такого пути накладывается ограничение – если при локальном поиске рассмотрено больше, чем M клеток, то поиск прекращается и локальная целевая клетка помечается специальной меткой AVOID. На последующих итерациях эта клетка выбирается только в том случае, если других клеток (не помеченных как AVOID) не осталось в списке кандидатов на построение локального пути. Схематично процесс поиска пути алгоритмом R* представлен на рис. 2.

Рис. 2. Поиск пути с помощью алгоритма R*

Результат экспериментальных исследований

Очевидно, что эффективность алгоритма R* во многом зависит от задаваемых значений Δ, K, M. В ходе проведения многочисленных экспериментов, каждый из которых заключался в поиске пути на МТ-графе алгоритмом R* с отслеживанием следующих индикаторов – вес построенного пути, время работы, количество рассмотренных клеток (емкостная эффективность), было установлено, что существует эвристическое соотношение, придерживаясь которого достигаются наилучшие результаты по всем отслеживаемым индикаторам:

Δ=D

M=Δ/5

K=Δ/10,

где D=max{|is–ig|, |js–jg|}, is, js, ig, jg – i-й и j-й индексы начальной и целевой клеток соответственно.

Полученный результат допускает следующую трактовку. Величина D ­– характеризует насколько начальная клетка удалена от целевой (в клетках). Поскольку вес перехода между горизонтально (вертикально) смежными клетками равен 10, то равенство Δ=D означает, что мы разбиваем исходную задачу на 10 подзадач. Как следует из результатов проведенных экспериментов разбиение на меньшее число подзадач ведет к построению путей с большим весом, при разбиении же на большое число подзадач вес пути остается практически неизменным, в то время как показатели временной и емкостной эффективности падают. Соотношение M=Δ/5означает следующее. Если между текущей клеткой и локальной целевой нет препятствий, то каждая рассмотренная алгоритмом A* клетка – это клетка, входящая в искомый локальный путь, и всего таких клеток Δ /10 (с учетом веса перехода между смежными клетками). Таким образом, устанавливая значение M равным Δ/5 мы «разрешаем» алгоритму обойти в два раза больше клеток, чем в лучшем случае. Если требуется обход большего числа клеток, то локальный поиск «в этом направлении» признается трудоемким и его рассмотрение откладывается. Наконец равенство K=Δ/10 означает, что мы выбираем (примерно) 1/6 от максимально возможного числа клеток, расположенных на расстоянии Δ от текущей (т. к. число клеток, удаленных на Δ от некоторой фиксированной клетки не превосходит 2∙π∙Δ/10).

Выводы

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

Литература

1.  Korf R. E., Artificial intelligence search algorithms, CRC Handbook of Algorithms and Theory of Computation, M. J. Atallah (Ed.). Boca Raton, FL: CRC Press, 1998

2.  Яковлев подход в задачах планирования траектории на плоскости. Двенадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2010 (20-24 сентября 2010 г., г. Тверь, Россия): Труды конференции. Т. 3. – М.: Физматлит, 2010.

3.  Likhachev M., Stentz A. R* Search. // Proceedings of the National Conference on Articial Intelligence (AAAI), 2008.

4.  Яковлев методов и разработка алгоритмов автоматического планирования траектории на плоскости. // Диссертация на соискание учёной степени кандидата наук, ИСА РАН, 2011.

Probabilistic decompositional approach to path planning in 2d

Yakovlev K. S.

Institute for Systems Analysis of Russian Academy of Sciences, *****@***ru

Khramoin I. V.

Peoples Friendship University of Russia, ivan. *****@***com

The problem of path-planning in 2D is addressed. A set of heuristic rules to set the input parameters to the path finding algorithm based on random decomposition of given task to a series of subtasks (R*) is presented.

Кеу words: path planning, path finding, A*, R*.