Иерархический подход в задачах планирования траектории на плоскости

Размещено на http://www.allbest.ru

ИЕРАРХИЧЕСКИЙ ПОДХОД В ЗАДАЧАХ ПЛАНИРОВАНИЯ ТРАЕКТОРИИ НА ПЛОСКОСТИ

К.С. Яковлев (yakovlev@isa.ru)

Институт Системного Анализа РАН,

Москва



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



Введение

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

Задача планирования траектории на плоскости может быть рассмотрена как задача поиска пути на взвешенном графе, вершинам которого соответствуют координаты точек двумерного пространства, а весам ребер - соответствующие расстояния. Так как в качестве исходных данных для построения графа используются цифровые карты и модели местности (ЦКМ), которые хранятся в памяти бортового вычислителя БТС, целесообразно (с точки зрения экономии вычислительных ресурсов) использовать такие графовые модели, которые могут быть извлечены напрямую из цифровой карты местности. Поскольку в двумерном случае (при навигации БТС на/в плоскости) ЦКМ фактически представляют из себя матрицу, элементам которой соответствуют проходимые либо непроходимые области пространства, в качестве подобной модели может выступать метрический топологический граф (МТ-граф) [Яковлев, 2009b].

Для осуществления поиска пути на МТ-графе могут быть использованы любые известные алгоритмы поиска пути на графе, наиболее распространенными из которых являются эвристические алгоритмы семейства A* [Hart et al., 1968], [Korf, 1996]. Однако, даже используя при поиске в качестве эвристик метрик МТ-графа (то есть, оперируя «лучшими» из возможных эвристик), A*-поиск производит слишком большой объем вычислений, требующих сохранения промежуточных результатов. Именно факт неэкономного использования оперативной памяти алгоритмами семейства A* препятствует их применению в ряде задач, когда размер (число вершин) вовлеченных графов (в том числе и МТ-графов) достаточно велик [Edelkamp et al., 2008].

Традиционный путь к снижению вычислительной нагрузки в рамках A*-поиска заключается в применении взвешенных эвристик, т.е. эвристик вида w•h(*), w?1, при поиске. Алгоритмы, использующие взвешенные эвристики принято обозначать как WA*. В качестве примеров подобных алгоритмов можно привести ARA* [Gordon et al., 2004], Alpha-A* [Reese, 1999]. Однако даже применение взвешенных эвристик зачастую не приводит к существенному сокращению пространства поиска из-за проблемы локального минимума [Яковлев, 2009a], [Likhachev et al., 2008].

Для решения проблемы локального минимума предлагается использовать принципиально иной алгоритм построения пути на МТ-графе, основанный на иерархическом подходе. Основная идея, лежащая в основе предлагаемого алгоритма, заключается в разбиении исходной задачи планирования на совокупность таких подзадач, каждая из которых может быть легко разрешена известными методами. В работе описывается подобный алгоритм - HGA* (Hierarchical A* for MT-Graphs). Даются оценки емкостной сложности алгоритма при определенных ограничениях. Приводятся результаты практических экспериментов, доказывающих перспективность применения HGA* для ряда задач.

траектория плоскость задача граф иерархический алгоритм



Постановка задачи

Будем рассматривать задачу планирования траектории на плоскости, как задачу поиска пути на графе особой структуры - метрическом топологическом графе (МТ-графе) [Яковлев, 2009b].

МТ-граф - это неупорядоченная пара:

MT-Gr=A, d,

где:

A - множество клеток, представляющее собой матрицу

A_mЧn={a_ij}: a_ij=01, i, j: 0?i<m, 0?j<n, m, n N\{0}.

d - метрика на множестве A.

Клетку МТ-графа будем называть проходимой, если a_ij=0; непроходимой, если a_ij=1. Множество клеток, смежных с a_ij будем обозначать как adj(a_ij). Множество смежных непроходимых клеток МТ-графа будем называть препятствием:

Obs={a_i0j0, a_i1j1, a_i2j2, …, a_isjs|а_ikjk=1, а_ikjkadj(а_ik-1jk-1) k=0,1,2, …, s, sN}.

В качестве метрики d будем использовать функцию:

H(a_ij, a_lk)=,

где Д_i=Д_i(a_ij, a_lk)=|i-l|; Д_j=Д_j(a_ij, a_lk)=|j-k|; (вес перехода между диагонально смежными клетками); c_hvR⁺={r|r, r>0} (вес перехода между горизонтально и вертикально смежными клетками).

Задача планирования траектории формально представляется в виде тройки:

PTask=MT-Gr, a_{startI startJ}, a_{goalI goalJ}, (1.1)

и формулируется следующим образом. Пусть на МТ-графе зафиксированы начальная a_{startI,startJ} и целевая a_goalI,goalJ клетки, такие что a_{startI,startJ}?a_goalI,goalJ, a_{startI,startJ}=0, a_goalI,goalJ=0. Необходимо найти путь р(a_{startI,startJ}, a_goalI,goalJ), то есть последовательность клеток МТ-графа р={a_i0j0, a_i1j1, a_i2j2, …, a_isjs} такую, что a_i0j0=a_{startI,startJ}, a_isjs=a_goalI,goalJ, v:1?v<s a_{iv ,jv}adj(a_{iv-1 jv-1}).

Весом пути р будет называть величину c(р), равную сумме весов переходов по всем смежным клеткам, входящим в путь. Величину r=max{|startIgoalI|, |startJgoalJ|} будем называть глубиной решения задачи (1.1).

Нуль-траекторией между двумя различными клетками a_ij и a_lk будем называть последовательность смежных клеток МТ-графа tr(a_ij, a_lk)={a_i0j0, a_i1j1, a_i2j2, …, a_irjs}, представляющую собой отрезок дискретной прямой проходящей через клетки a_ij=a_i0j0 и a_lk=a_irjs (см. рис. 2b). Формальное определение нуль-траектории (как совокупности клеток МТ-графа, удовлетворяющих определенному набору ограничений) приведено в [Яковлев, 2009b]. Весом нуль-траектории будем называть величину с(tr(a_ij, a_lk)), определяемую аналогично весу пути (a_ij, a_lk). Примем без доказательства следующее утверждение: с(tr(a_ij, a_lk))= H(a_ij, a_lk).

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

Секцией будем называть упорядоченную пару клеток МТ-графа a_ij, a_lk. Секция a_ij, a_lk проходима, тогда и только тогда когда нуль-траектория tr(a_ij, a_lk) содержит лишь проходимые клетки МТ-графа. Весом секции назовем величину с(a_ij, a_lk)=с(tr(a_ij, a_lk))=H(a_ij, a_lk).

Пусть a_ij, a_lk A_mЧn, при этом a_ija_lk , a_ij1, a_lk1. Частичным путем из a_ij в a_lk будем называть последовательность клеток МТ-графа PP={a_{i0 j0}, a_{i1 j1}, a_{i2 j2}, …, a_{is js}}, такую что a_{i0 j0}=a_ij, a_{is js}=a_lk. Если при этом каждая из секций a_i0j0, a_i1j1, a_i1j1, a_i2j2,…, a_{is-1 j-1s}, a_{is js} является проходимой, то частичный путь PP будем называть допустимым, в противном случае - недопустимым. Клетки, входящие в частичный путь будем называть опорными. Вес частичного пути C(PP) определим как сумму весов всех секций, образуемых смежным опорным клеткам.

Используя приведенную выше терминологию, задача (1.1) может рассматриваться, как задача отыскания на МТ-графе допустимого частичного пути из a_{startI,startJ} в a_goalI,goalJ. Перед тем как описать иерархический алгоритм решения задачи планирования траектории в такой формулировке дадим еще несколько определений.

Будем говорить, что клетка a_ij расположена левее (правее) клетки a_lk, если j<k (j>k). Будем говорить, что клетка a_ij расположена ниже (выше) клетки a_lk, если i<l (i>l). Будем говорить, что препятствие Obs лежит между клетками a_ij и a_lk, если tr(a_ij, a_lk)Obs.



2. Иерархический подход в задачах планирования траектории

2.1 Простейшие иерархические алгоритмы планирования траектории

Задача планирования траектории может рассматриваться как задача построения множества клеток (называемых опорными), некоторое подмножество которого образует допустимый частичный путь. Таким образом, задача планирования может быть разбита на три подзадачи:

1. Выделение опорных клеток.

2. Упорядочивание опорных клеток (формирование частичных планов).

3. Выбор опорных клеток, для формирования решения задачи (выбор частичного плана из множества кандидатов).

Опишем простейший недетерминированный алгоритм построения пути на МТ-графе, осуществляющий решение указанных выше подзадач в иерархической манере.

Шаг 1. Добавить в искомый частичный путь начальную и целевую клетки: PP={a_{startI,startJ}, a_goalI,goalJ}.

Шаг 2. Если текущий частичный путь PP является допустимым, то вернуть PP.

Шаг 3. Выбрать две опорные клетки, a_ij и a_lk, входящие в PP.

Шаг 4. Построить нуль-траекторию tr(a_ij, a_lk) с помощью алгоритма Брезенхема.

Шаг 5. Если нуль-траектория tr(a_ij, a_lk) проходима, то перейти к шагу 2.

Шаг 6. Выбрать клетку СA.

Шаг 7. Добавить клетку C в частичный путь PP (а именно - заменить последовательность a_ij и a_lk в PP на a_ij, C, a_lk).

Шаг 8. Перейти к шагу 2.

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

Шаг 1. Сформировать множество частичных путей кандидатов PPC, первоначально содержащее лишь частичный путь PP={a_{startI,startJ}, a_goalI,goalJ}.

Шаг 2. Выбрать из PPC кратчайший частичный путь PP.

Шаг 3. Если текущий частичный путь PP является допустимым, то вернуть PP.

Шаг 4. Выбрать две опорные клетки, a_ij и a_lk, входящие в PP.

Шаг 5. Построить нуль-траекторию tr(a_ij, a_lk).

Шаг 6. Если нуль-траектория tr(a_ij, a_lk) проходима, то перейти к шагу 2.

Шаг 7. Случайным образом выбрать N клеток С₁, С₂,…, С_n A.

Шаг 8. Разбить PP на N вариантов, а именно - для каждого PPPPC, содержащего последовательность a_ij, a_lk выполнить следующие шаги:

а) скопировать PP N раз в PPC;

б) для каждого из N cкопированных частичных путей заменить последовательность a_ij, a_lk на a_ij, C₁, a_lk; a_ij, C₂, a_lk; …; a_ij, C_n, a_lk соответственно.

Шаг 9. Перейти к шагу 2.

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

Для удобства дальнейшего изложения будем называть разбиением секции a_ij, a_lk процесс, выполняемый на 7-8 шагах алгоритма. Клетки a_ij, a_lk выбираемые на шаге 2 будем называть локальными начальной и целевой клетками соответственно.



2.2 HGA*

Алгоритм HGA* это алгоритм поиска пути на МТ-графе, реализующий иерархический подход к решению задачи планирования, главное отличие которого от алгоритма, описанного в предыдущем разделе - детерминированный выбор опорных клеток на этапе разбиения секции. Перед тем как описать алгоритм более подробно, предположим, что начальная клетка расположена не правее целевой. Данное предположение необходимо лишь для упрощения дальнейшего изложения и не может рассматриваться как ограничение, т.к. указанного расположения клеток всегда можно добиться с помощью поворота МТ-графа (формальное определение этой операции приведено в [Яковлев, 2009], а неформальное - очевидно). Сформулируем теперь очевидное утверждение, лежащее в основе алгоритма HGA*.

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

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

Итак, пусть некоторая локальная начальная клетка s расположена не правее локальной целевой g, а нуль-траектория tr(s, g) пересекает препятствие в некоторой клетке X (см. рис.1b). Рассмотрим следующую процедуру, выделяющую 4 опорные клетки для последующего разбиения секции.



GetBaseCellsForExtension(cell s, cell g, cell X)

int i_up, i_down, j_right, j_left=X.j-1; cell tmp=X;

while (tmp==1)

tmp.i--;

i_up=tmp.i; tmp.i++;

while(tmp==1)

tmp.j++;

j.right=tmp.j; tmp=X;

while (tmp==1)

tmp.i++;

i_down=tmp.i;

if (i_up>=0){

A.i=B.i=i_up; A.j=j_left; B.j=j_right

}else

A=B=null;

if (i_down<m){

C.i=D.i=i_down; C.j=j_left; D.j=j_right

} else

C=D=null;

return {A, B, C, D}

Процедура GetBaseCellsForExtensions в точности возвращает клетки A, B, C, D «обрамляющие» препятствие по углам (см. рис. 1с). С помощью этих клеток не составляет труда осуществить разбиение секции <s, g> по следующему алгоритму: для каждого PPPPC, содержащего последовательность s, g выполнить:

Шаг 1. Скопировать PP в PP1 и PP2

Шаг 2. В PP1 заменить последовательность s, g на s, A, B, g

Шаг 3. В PP2 заменить последовательность s, g на s, D, C, g

Рис.1. Разбиение секции алгоритмом HGA*. a) начальная и целевая клетки; б) нуль-траектория; в) сформированные частичные пути

Заметим, что если процедура GetBaseCellsForExtensions возвращает только клетки A и B (либо C и D), то нет необходимости в копировании частичного пути PP, требуется лишь замена s, g на s, A, B, g (s, D, C, g). Если же A=B=C=D=null, то не существует пути из s в g, что в свою очередь означает, что не существует решения рассматриваемой задачи планирования. Таким образом, детерминированный, корректный алгоритм построения частичного пути - HGA* - может быть представлен в следующем виде.

Шаг 1. Сформировать множество частичных путей кандидатов PPC, первоначально содержащее лишь частичный путь PP={a_{startI,startJ}, a_goalI,goalJ}.

Шаг 2. Выбрать из PPC частичный путь PP.

Шаг 3. Если текущий частичный путь PP является допустимым, то вернуть PP.

Шаг 4. Выбрать две опорные клетки, a_ij и a_lk, входящие в PP.

Шаг 5. Построить нуль-траекторию tr(a_ij, a_lk).

Шаг 6. Если нуль-траектория tr(a_ij, a_lk) проходима, то перейти к шагу 2.

Шаг 7. Выполнить процедуру GET.

Шаг 8. Если все клетки, возвращенные Get, равны null, то осуществить выход (пути из a_{startI,startJ} в a_goalI,goalJ не существует).

Шаг 9. Осуществить разбиение секции a_ij, a_lk с помощью найденных клеток.

Шаг 10. Перейти к шагу 2.

Отметим, что практическая реализация HGA* возможна и без явного хранения частичных планов. Достаточно для каждой опорной клетки хранить указатель на предыдущую опорную клетку. Более того можно показать, что при определенных ограничениях требуется хранение не более 2 указателей для каждой опорной клетки. Таким образом, емкостная сложность HGA* может быть оценена следующим образом. Пусть объем памяти, необходимый для того, чтобы «хранить» опорную клетку оценивается в O(1). Если ни одно препятствие не лежит между a_{startI,startJ} и a_goalI,goalJ , то требуется хранение 2 опорных клеток. Если между a_{startI,startJ} и a_goalI,goalJ лежит 1 препятствие, то требуется хранение не более 6 клеток; если - 2 препятствия, то - не более 10; и так далее. По принципу математической индукции получаем, что всего требуется хранить на более 2+4NOBS опорных клеток, где NOBS - число препятствий, лежащих между a_{startI,startJ} и a_goalI,goalJ. Поскольку NOBS очевидно не может превышать r (где r - глубина решения задачи (1.1)), то емкостная сложность HGA* может быть оценена как O(r). В то время, как известно, что емкостная сложность эвристических алгоритмов семейства A* - O(r²) [Korf, 1996].

2.3 HGA* в сложных доменах

Ослабим предположение о том, что все препятствия на МТ-графе имеют прямоугольную форму. Опишем неформально процедуру выделения опорных клеток в этом случае.

Как и раньше будем полагать, что клетка s лежит на правее клетки g, а нуль-траеткория tr(s, g) пересекает препятствие Obs в клетке X. Будем двигаться вдоль границы препятствия по часовой стрелке до тех пор, пока не совершим движение в горизонтальном направлении слева направо. Таким образом, мы выделим опорную клетку A (см. рис. 2а), первую из серии опорных клеток, расположенных выше препятствия, которые войдут в искомый частичный путь. Для отыскания первой клетки, расположенной ниже, выполним аналогичные действия - будем двигаться вдоль границы препятствия, но против часовой стрелки, пока не совершим движение в горизонтальном направлении слева направо.

После выделения опорных клеток A и B, разбиение секции s, g может быть осуществлено стандартным образом на {s, A, g} и {s, B, g}. Однако при таком подходе, возникает следующая проблема. Если, после нескольких итераций алгоритма, A и g становятся локальными начальной и целевой клетками, то при разбиении секции A, g клетка B будет обнаружена снова. И после разбиения A, g множество PPC будет содержать взаимно противоречивые элементы: PP₁={…, s, A, С, g, …}, PP₂={…, s, A, B, g, …}, PP₃={…, s, B, g…} (см. рис. 2).

Рис. 2. Взаимное противоречие частичных путей. а) Разбиение секции s, g; б) Последующее разбиение секции A, g

Для поддержания целостности множества PPC необходимо следовать следующему простому правилу: если некоторая секция s, g разбивается с помощью некоторой клетки A, лежащей выше препятствия Obs, секция A, g не должна разбиваться с помощью клетки, лежащей ниже Obs. Соблюдение данного правило может быть реализовано с помощью приписывания клетке A не только указателя на клетку s, но и на клетку X (клетку, в которой tr(s, g) пересекает Obs). Впоследствии, если клетка X будет обнаружена при «скольжении» вдоль контура препятствия по (против) часовой стрелки, во время разбиения A, g, необходимо остановить процедуру поиска опорной клетки и продолжить скольжение лишь в противоположную сторону.



3. Экспериментальный анализ

Был произведен экспериментальный анализ алгоритмов HGA*, A*, WA*-3 и WA*-5. Для этого были проведены три серии экспериментов по отысканию пути на МТ-графах. Отслеживались следующие индикаторы:

W_alg - вес пути, найденного алгоритмом alg;

Q_alg - число клеток МТ-графа, рассмотренных при нахождении пути, алгоритмом alg;

E_alg=(Q_alg/W_alg)/(Q_A*/W_A*) - интегральный показатель емкостной эффективности alg.

3.1 1-я серия экспериментов

Было сгенерировано 150 МТ-графов с различной степенью заполнения препятствиями, (0,3; 0,5; 0,8). Начальная и целевая клетки выбирались таким образом, чтобы глубина решения составляла 50, 100, 250, 500 и 1000. Препятствия являлись прямоугольниками шириной 1 клетку и длиной (в среднем) - 10 клеток. Усредненные (по всем прогонам) результаты экспериментов на МТ-графах с =0,8 представлены ниже.

Табл. 1. Результаты первой серии экспериментов на МТ-графах с =0,8

Алгоритм	Показатели	Глубина решения
		50	100	250	500	1000
A*	WA*	628	1235	3024	5938	12377
A*	QA*	656	1733	10281	32410	158328
A*	EA*	100%	100%	100%	100%	100%
WA*-3	WWA*-3	701	1416	3552	6911	14182
WA*-3	QWA*-3	206	384	951	1791	3779
WA*-3	EWA*-3	28%	19%	8%	5%	2%
WA*-5	WWA*-5	720	1442	3662	7008	14405
WA*-5	QWA*-5	203	381	933	1763	3745
WA*-5	EA*	27%	19%	7%	5%	2%
HGA*	WA*	682	1334	3381	6574	13911
HGA*	QA*	115	265	608	1311	2646
HGA*	EA*	16%	14%	5%	4%	1%

Из полученных данных можно сделать два основных вывода. Во-первых, разница между показателями WA*-3 и WA*-5 минимальна. Это значит, в свою очередь что… Во-вторых HGA* превосходит наиболее «оптимизированный» алгоритм планирования траектории, основанный на A*-поиске, в среднем в 1,5 раза. При этом на МТ-графах с меньшей плотностью препятствий превосходство HGA* еще более ярко выражено. Так для МТ-графов с параметром =0,3 получены следующие результаты: E_WA*-5/E_HGA*=4,58 ; W_WA*-5/W_HGA*=4,90.

3.2 2-я серия экспериментов

Было сгенерировано 50 МТ-графов с фиксированной степенью заполнения препятствиями: =0,5. Глубина решения была зафиксирована на отметке 100. Ширина препятствий была фиксирована и составляла 1 (клетку). Средняя длина препятствий l составляла 2, 5, 10, 15, 25 клеток (по 10 МТ-графов для каждого значения l было сгенерировано). Усредненные результаты A*, WA*-5 и HGA* представлены в таблице 2.

Табл. 2. Результаты второй серии экспериментов

Алгоритм	Показатели	Средняя длина препятствия
		2	5	10	15	25
A*	WA*	1143	1166	1158	1225	1335
A*	QA*	499	901	1478	1991	2662
A*	EA*	100%	100%	100%	100%	100%
WA*-5	WWA*-5	1181	1245	1290	1413	1500
WA*-5	QWA*-5	350	357	380	423	524
WA*-5	EA*	68%	37%	23%	18%	18%
HGA*	WA*	1146	1189	1235	1285	1516
HGA*	QA*	95	120	187	154	114
HGA*	EA*	19%	13%	12%	7%	4%

Опираясь на полученные результаты можно утверждать, что алгоритм HGA* превосходит алгоритмы, основанные на A*-поиске, не только на МТ-графах с небольшим числом «больших» препятствий, но и на МТ-графах с большим числом «небольших» препятствий.

3.3 3-я серия экспериментов

Рассматривалась задача автоматического построения траектории маловысотного полета вертолета в городских условиях. МТ-графы представляли собой модели двух фрагментов карты Москвы. Препятствиям соответствовали высотные здания, которые должен был облетать в горизонтальной плоскости воображаемый вертолет. На каждом их двух МТ-графов 10 раз случайным образом выбирались начальная и целевая клетки, так чтобы глубина решения равнялась 110.

Табл. 3. Результаты второй серии экспериментов

Алгоритм	Показатели	МТ-граф 1	МТ-граф 2
A*	WA*	1326	1424
A*	QA*	1344	1695
A*	EA*	100%	100%
WA*-5	WWA*-5	1368	1472
WA*-5	QWA*-5	372	394
WA*-5	EA*	20%	27%
HGA*	WA*	1404	1532
HGA*	QA*	229	355
HGA*	EA*	12%	24%

Результаты эксперимента подтверждают, что алгоритм HGA* эффективно решает задачу отыскания пути не только на случайно сгенерированных МТ-графах, но и на МТ-графах являющихся моделями городского ландшафта.



Заключение

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

Дальнейшая работа предполагается в направлении изучения теоретических свойств HGA* и создания модификаций алгоритма для планирования траектории в динамических средах.

Благодарности

Работа выполнена при финансовой поддержке РФФИ (проекты №№ 09-07-00043, 09-07-00006), Министерства образования и науки РФ (ФЦП «Научные и научно-педагогические кадры инновационной России»), Президиума РАН, ОНИТ РАН.



Список литературы

[Яковлев, 2009a] Яковлев К.С. Методы решения проблемы локального минимума при планировании траектории. // Труды IX международной научной конференция им.Таран Т.А. «Интеллектуальный анализ информации ИАИ-2009». - Киев: ПРОСВIТА, 2009.

[Яковлев, 2009b] Яковлев К.С. Графы специальной структуры в задачах планирования траектории. // Труды III международной конференции «Системный анализ и информационные технологии САИТ-2009». - M: ИСА РАН, 2009.

[Bresenham, 1965] J. E. Bresenham. Algorithm for computer control of a digital plotter. // IBM SystemsJournal, Vol. 4, №1, 1965.

[Edelkamp et al., 2008] S. Edelkamp, E. Hansen, S. Jabbar, R. Zhou. External Memory Graph Search. // 18th International Conference on Automated Planning and Scheduling (ICAPS08), Sydney, Australia, 2008.

[Gordon et al., 2004] G. Gordon, M. Likhachev, S. Thrun. ARA*: Anytime A* with provable bounds on sub-optimality. // In Advances in Neural Information Processing Systems, MIT Press, 2003.

[Hart et al., 1968] P. Hart, N. Nillson, B. Raphael. A formal basis for the heuristics determination of minimum costs path. // IEEE Transactions on Systems Science and Cybernetics, 2, 1968.

[Korf, 1996] R.E.Korf. Articial Intelligence Search Algorithms. // In Algorithms and Theory of Computation Handbook, CRC Press, 1996.

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

[Reese, 1999] B. Reese. AlphA*: An -admissible Heuristic Search Algorithm. // Institute for Production Technology, University of Southern Denmark 1999 -http://home1.stofanet.dk/breese/astaralpha-submitted.pdf.gz.

Размещено на Allbest.ru

...