ИЕРАРХИЧЕСКИЙ ПОДХОД В ЗАДАЧАХ ПЛАНИРОВАНИЯ ТРАЕКТОРИИ НА ПЛОСКОСТИ Яковлев К.С. ИСА РАН yakovlev@isa.ru. - презентация

1 ИЕРАРХИЧЕСКИЙ ПОДХОД В ЗАДАЧАХ ПЛАНИРОВАНИЯ ТРАЕКТОРИИ НА ПЛОСКОСТИ Яковлев К.С. ИСА РАН

2 КИИ Метрический топологический граф MT-GR= A – множество клеток, представляющее собой матрицу A m×n ={a ij }: a ij =0 1, i, j: 0i

3 КИИ Пусть a ij, a lk A m×n : a ij a lk, a ij 0, a lk 0. Путем из a ij в a lk будем называть последовательность смежных проходимых клеток МТ-графа π={a i0 j0, a i1 j1,a i2 j2, …, a is js }, a i0 j 0 =a ij, a is j s =a lk. Будем обозначать путь как π(a ij, a lk ) или просто π. Клетку a ij пути π будем называть начальной, a lk – целевой. Вес пути π - сумма весов переходов по всем смежным клеткам, входящим в π: Кратчайшим путем из a ij в a lk будем называть такой путь π*(a ij, a lk ), что π π* c(π)c(π*). c(π)= МТ-граф. Основные определения 1.

4 КИИ МТ-граф. Основные определения 2. Две различные клетки МТ-графа a i1j1, a i2j2 A m×n будем называть смежными, если |i 1 -i 2 |1|j 1 -j 2 |1. Две различные клетки a i1j1, a i2j2 A m×n будем называть: горизонтально смежными, если|i 1 -i 2 |=0 |j 1 -j 2 |=1 вертикально смежными, если|i 1 -i 2 |=1 |j 1 -j 2 |=0 диагонально смежными, если|i 1 -i 2 |=1 |j 1 -j 2 |=1 ADJ A×A – множество всех пар смежных клеток c hv,c d R + c:ADJ {c hv, c d, +}: c(a ij, a lk )=c hv, если a ij =0 a lk =0 и клетки a ij, a lk являются горизонтально или вертикально смежными; c(a ij, a lk )=c d, если a ij =0 a lk =0 и клетки a ij, a lk являются диагонально смежными; c(a ij, a lk )=+, если a ij =1 a lk =1.

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

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

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

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

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

10 КИИ Операция поворота и взаимное расположение клеток на МТ-графе ROT(A m×n )=RA nxm, где RA nxm ={ra ij }, ra ij =a m-j-1 i. Графически МТ-граф RA представляет собой перевернутый на 90 градусов по часовой стрелке МТ-граф A m×n. Пусть a ij, a lk A m×n. Δ i (a ij, a lk )=|i-l|; Δ j (a ij, a lk )=|j-k|. клетка a lk расположена правее клетки a ij, если Δ j Δ i и k>j.

11 КИИ Нуль-траектория Нуль-траекторией между двумя различными клетками a ij и a lk будем называть последовательность смежных клеток МТ-графа tr(a ij, a lk )={a i0j0, a i1j1, a i2j2, …, a isjs }, такую что: 1.a i0j0 =a ij, a lk =a isjs. 2. v: 1v

12 КИИ Препятствие Препятствия Obs={a i0j0, a i1j1, a i2j2, …, a isjs |а ikjk =1, а ikjk adj(а ik-1jk-1 ) k=0,1,2, …, s, s N}. Препятствие Obs лежит между клетками a ij и a lk, если tr(a ij, a lk ) Obs

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

14 КИИ Задача планирования Пусть на заданном МТ-графе MT-Gr зафиксированы начальная a startI startJ и целевая a goalI goalJ клетки. Задача планирования состоит в отыскании такой последовательности клеток PP={a i0 j0, a i1 j1,a i2 j2, …, a is js }, что a i0 j0 = a startI startJ a is js = a goalI goalJ секции,, … - проходимы PP – частичный путь Клетки a ij PP – опорные клетки Вес частичного пути C(PP)=

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

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

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

18 КИИ Детерминированный выбор опорных клеток 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

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

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

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

22 КИИ

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

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

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

26 КИИ серия экспериментов. РазмерКоличество МТ-графов =0,3 51 x 5110 =0,3 101 x =0,3 251 x =0,3 501 x =0, x =0,5 51 x 5110 =0,5 101 x =0,5 251 x =0,5 501 x =0, x =0,8 51 x 5110 =0,8 101 x =0,8 251 x =0,8 501 x =0, x ИТОГО150 =[(l 2+d 4) N]/(m n)

27 КИИ Алгоритм Выходные параметры Глубина решения A*W A* , A*Q A* A*T A* 5,7757,741154, , ,80 A*EQ A* 0,951,553,075,1210,35 A*ENQ A* 1,00 WA*-3W WA* , WA*-3Q WA* WA*-3T WA*-3 0,290,804,6016,016560,85 WA*-3EQ WA*-3 0,310,30 0,29 WA*-3ENQ WA*-3 0,330,190,100,060,03 WA*-5W WA* , WA*-5Q WA* WA*-5T WA*-5 0,270,784,2615,325758,26 WA*-5EQ WA*-5 0,300,29 0,28 WA*-5ENQ WA*-5 0,320,190,090,050,03 HGA*W HGA* , HGA*Q HGA* HGA*T HGA* 0,280,993,7417,714867,85 HGA*EQ HGA* 0,120,14 HGA*ENQ HGA* 0,120,090,050,030,01

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

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

30 КИИ Алгоритм Выходные параметры Средняя длина препятствия A*W A* A*Q A* A*T A* 2,386,5549,9131,7686,77 A*EQ A* 0,460,591,571,211,74 A*ENQ A* 1,00 WA*-3W WA* WA*-3Q WA* WA*-3T WA*-3 0,580,550,901,013,28 WA*-3EQ WA*-3 0,300,290,31 0,41 WA*-3ENQ WA*-3 0,670,480,200,260,23 WA*-5W WA* WA*-5Q WA* WA*-5T WA*-5 0,590,550,850,922,18 WA*-5EQ WA*-5 0,300,280,29 0,35 WA*-5ENQ WA*-5 0,670,480,180,240,20 HGA*W HGA* HGA*Q HGA* HGA*T HGA* 0,450,741,060,57 HGA*EQ HGA* 0,080,120,160,090,08 HGA*ENQ HGA* 0,190,200,100,080,05

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

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

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

34 КИИ Алгоритм Выходные параметрыМТ-граф 1МТ-граф 2 A*W A* A*Q A* A*T A* 177,0480,55 A*EQ A* 0,951,10 A*ENQ A* 1,00 WA*-5W WA* WA*-5Q WA* WA*-5T WA*-5 6,481,80 WA*-5EQ WA*-5 0,290,26 WA*-5ENQ WA*-5 0,310,24 HGA*W HGA* HGA*Q HGA* HGA*T HGA* 3,302,94 HGA*EQ HGA* 0,060,14 HGA*ENQ HGA* 0,060,13

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

36 Спасибо за внимание