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

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

Институт системного анализа Российской академии наук, *****@***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* с этими параметрами демонстрирует на практике наилучший результат.

Литература

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 Яковлев подход в задачах планирования траектории на плоскости. Двенадцатая национальная  конференция по искусственному интеллекту с международным участием КИИ-2010 (20-24 сентября 2010 г., г. Тверь, Россия): Труды конференции. Т. 3. – М.: Физматлит, 2010. Likhachev M., Stentz A. R* Search. // Proceedings of the National Conference on Articial Intelligence (AAAI), 2008. Яковлев методов и разработка алгоритмов автоматического планирования траектории на плоскости. // Диссертация на соискание учёной степени кандидата наук, ИСА РАН, 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*.