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

КИИ-2010
Метрический топологический граф
MT-GR=
A – множество клеток, представляющее собой матрицу Am×n={aij}: aij=0 1, i, j: 0≤i
d – метрика на множестве A+={aij|aij∈A, aij=0}
с: E→(0, +∞) – коммутативная функция, определяющая веса переходов между клетками МТ-графа (здесь, E⊂A×A).

КИИ-2010
Пусть aij, alk Am×n: aij≠alk , aij≠0, alk≠0. Путем из aij в alk будем называть последовательность смежных проходимых клеток МТ-графа
π={ai0 j0, ai1 j1,ai2 j2, …, ais js}, ai0 j0=aij, ais js=alk.
Будем обозначать путь как π(aij, alk) или просто π.
Клетку aij пути π будем называть начальной, alk – целевой.
Вес пути π - сумма весов переходов по всем
смежным клеткам, входящим в π:
Кратчайшим путем из aij в alk будем называть
такой путь π*(aij, alk), что ∀ π≠π* c(π)≤c(π*).
c(π)=
МТ-граф. Основные определения 1.

КИИ-2010
МТ-граф. Основные определения 2.
Две различные клетки МТ-графа ai1j1, ai2j2 Am×n будем называть смежными, если |i1-i2|≤1|j1-j2|≤1.
Две различные клетки ai1j1, ai2j2 Am×n будем называть:
горизонтально смежными, если|i1-i2|=0 ∧|j1-j2|=1
вертикально смежными, если|i1-i2|=1 ∧ |j1-j2|=0
диагонально смежными, если|i1-i2|=1 ∧ |j1-j2|=1
ADJ⊂A×A – множество всех пар смежных клеток
chv,cd∈R+
c:ADJ → {chv, cd, +∞}:
c(aij, alk)=chv, если aij=0 alk=0 и клетки aij, alk являются горизонтально или вертикально смежными;
c(aij, alk)=cd, если aij=0 alk =0 и клетки aij, alk являются диагонально смежными;
c(aij, alk)=+∞, если aij=1 alk=1.

КИИ-2010
МТ-граф. Основные определения 3.
d(aij, alk)=H(aij, alk)=
Δi=Δi(aij, alk)=|i-l|
Δj=Δj(aij, alk)=|j-k|

КИИ-2010
Задача планирования траектории
PTask=〈MT-Gr, astartI startJ, agoalI goalJ〉
π(astartI startJ, agoalI goalJ)
Решение задачи планирования
Оптимальное решение задачи планирования
Путь на МТ-графе
Кратчайший путь на МТ-графе
r=max{|startI−goalI|, |startJ−goalJ|}
Глубина решения
π*(astartI startJ, agoalI goalJ)

КИИ-2010
МТ-графы и взвешенные графы
Любой МТ-граф может имплицировать взвешенный граф
Все алгоритмы эвристического поиска, применимые на графах, являются применимыми и для МТ-Графов
каждой клетке МТ-графа соответствует вершина графа;
множеству ADJ МТ-графа соответствует множество ребер графа;
веса ребер, соединяющих смежные вершины графа, равняются весам переходов между соответствующими клетками МТ-графа.

КИИ-2010
Алгоритмы семейства A* при поиске пути на МТ-графе
Алгоритмическая сложность (как временная, так и емкостная) O(r2)
Проблема «локального минимума»

КИИ-2010
Иерархический подход
Разбить исходную задачу на упорядоченное множество «элементарных» подзадач

КИИ-2010
Операция поворота и взаимное расположение клеток на МТ-графе
ROT(Am×n)=RAnxm, где RAnxm={raij}, raij=am-j-1 i. Графически МТ-граф RA представляет собой перевернутый на 90 градусов по часовой стрелке МТ-граф Am×n.
Пусть aij, alk∈Am×n.
Δi(aij, alk)=|i-l|;
Δj(aij, alk)=|j-k|.
клетка alk расположена правее клетки aij, если
Δj≥Δi и k>j.

КИИ-2010
Нуль-траектория
Нуль-траекторией между двумя различными клетками aij и alk будем называть последовательность смежных клеток МТ-графа tr(aij, alk)={ai0j0, ai1j1, ai2j2, …, aisjs}, такую что:
ai0j0=aij, alk=aisjs.
∀v: 1≤v
∀v: 1≤v
Nd(tr)=Δi
Nh(tr)=Δj–Δi
Нуль траектория – отрезок дискретной прямой
Нуль-траектория tr(aij, alk) проходима ТТКГ aisjs =0 ∀aisjs ∈tr(aij, alk)
c(tr(aij, alk))=c(tr)=
Вес нуль-траектории определяется аналогично весу пути:

КИИ-2010
Препятствие
Препятствия
Obs={ai0j0, ai1j1, ai2j2, …, aisjs|аikjk=1, аikjk∈adj(аik-1jk-1) ∀k=0,1,2, …, s, s∈N}.
Препятствие Obs лежит между клетками aij и alk, если tr(aij, alk) ∩ Obs ≠∅

КИИ-2010
Секция
Секция
- упорядоченная пара клеток МТ-графа
Секция
проходима ТТТК нуль-траектория tr(aij, akl) проходима
Вес секции равен весу нуль-траектории с(
)=c(tr(aij, akl))

КИИ-2010
Задача планирования
Пусть на заданном МТ-графе MT-Gr зафиксированы начальная
astartI startJ и целевая agoalI goalJ клетки.
Задача планирования состоит в отыскании такой последовательности клеток PP={ai0 j0, ai1 j1,ai2 j2, …, ais js}, что
ai0 j0= astartI startJ
ais js= agoalI goalJ
секции
,
, …
- проходимы
PP – частичный путь
Клетки aij ∈ PP – опорные клетки
Вес частичного пути C(PP)=

КИИ-2010
Компоненты планирования
Выделение опорных клеток
Упорядочивание опорных клеток
Выбор опорных клеток для формирования итогового решения

КИИ-2010
Вероятностный иерархический алгоритм планирования траектории
Вход: PPС={PP={astartI startJ , agoalI goalJ }} – множество частичных путей кандидатов
Шаг 1. Выбрать лучший частичный PP из PPC согласно Критерию Выбора Частичного Плана
Шаг 2. Если PP удовлетворяет Критерию Останова, то вернуть PP в качестве решения задачи планирования
Шаг 3. В соответствии с Критерием Выбора Опорных Клеток выбрать пару опорных клеток из PP - aij, alk
Шаг 4. Построить нуль-траекторию tr(aij, alk)
Шаг 5. Если нуль-траектория tr(aij, alk) проходима, то перейти к шагу 1
Шаг 6. Случайным образом выбрать N опорных клеток C1, C2, …, Cn ∈ A+
Шаг 7. Разбить секцию
на N вариантов, а именно:
Для каждого PP ∈ PPC, включающего aij, alk
Шаг 7.1. Разбить PP на N дубликатов
Шаг 7.2. Заменить последовательность aij, alk на aij, C1, alk,
aij, C2, alk,…. aij, Cn, alk в каждом дубликате соответственно
Шаг 8. Перейти к шагу 1

КИИ-2010
Детерминированный выбор опорных клеток
Утверждение
Если препятствие Obs лежит между клетками aij, alk, то частичный план PP(aij, alk) необходимо содержит клетки, расположенные выше (либо ниже) препятствия Obs.

КИИ-2010
Детерминированный выбор опорных клеток
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
C.i=D.i=i_down;
C.j=j_left;
D.j=j_right
}
else
C=D=null;
return {A, B, C, D}

КИИ-2010
HGA*
Вход: PPС={PP={astartI startJ , agoalI goalJ }}
Шаг 1. Выбрать лучший частичный путь PP из PPC согласно Критерию Выбора Частичного Плана
Шаг 2. Если PP удовлетворяет Критерию Останова, то вернуть PP
Шаг 3. В соответствии с Критерием Выбора Опорных Клеток выбрать пару опорных клеток из PP - aij, alk
Шаг 4. Построить нуль-траекторию tr(aij, alk)
Шаг 5. Если нуль-траектория tr(aij, alk) проходима, то перейти к шагу 1
Шаг 6. Выполнить процедуру GetBaseCellsForExtension для получения опорных клеток A, B, C, D.
Шаг 7. Если A=B=C=D=null вернуть failure
Шаг 8. Разбить секцию
на 2 вариантa: aij, A, B, alk и aij,D, С, alk
Шаг 9. Перейти к шагу 1

КИИ-2010
Емкостная сложность HGA*
«Хранить» клетку – O(1)
A* – O(r2)
Obs: 2+4*Obs
Obs ≤ r/2
r = max{|goalI - startI|, |goalJ - startJ|}
HGA* – O(r)

КИИ-2010
Препятствия нетривиальной формы
Обход контура препятствия по (против) часовой стрелке от клетки X до «первого шага в горизонтальном направлении»

КИИ-2010

КИИ-2010
Препятствия нетривиальной формы

КИИ-2010
Экспериментальные результаты.
3 серии экспериментов
МТ-графы различных размеров с различной степенью заполнения препятствиями
МТ-графы – цифровые карты Москвы в разрешении необходимом для обеспечения маловысотного полета беспилотного вертолета

КИИ-2010
Экспериментальные результаты.
Алгоритмы
HGA*, A*, WA*-3, WA*-5
Отслеживаемые индикаторы
Q – число сохраненных клеток
W – вес пути
T – затраченное время
EQ=(Q/W) – коэффициент емкостной эффективности;
ENQalg=(Qalg/Walg) (QA*/WA*) – нормированный коэффициент емкостной эффективности alg.

КИИ-2010
1 серия экспериментов.
λ=[(l⋅2+d⋅4)⋅N]/(m⋅n)

КИИ-2010
0,01

КИИ-2010
1 серия экспериментов. Результаты.

КИИ-2010
2 серия экспериментов
Размер МТ-графа фиксирован 101х101
Глубина решения фиксирована 100
СЗП фиксирована λ = 0.5
Длины препятствий варьируются
l=2, 5, 10, 15, 25

КИИ-2010
0,05

КИИ-2010
3 серия экспериментов. Маловысотный полет вертолета.
2 МТ-графа (цифровые карты местности Москвы, 2х2 км)
Глубина решения r=100
Случайный выбор начальной и целевых клеток (10 повторений на каждый МТ-граф)
A*, WA*-5, HGA*

КИИ-2010
3 серия экспериментов.

КИИ-2010
3 серия экспериментов.

КИИ-2010
0,13

КИИ-2010
Выводы по результатам экспериментов
HGA* использует вычислительные ресурсы гораздо эффективней аналогов
HGA* лучше масштабируется
HGA* эффективно отрабатывает на МТ-графах с любой степенью заполнения любыми типами «элементарных» препятствий
HGA* может использоваться в задачах планирования траектории характерных для «городского» ландшафта