'

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

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

КИИ-2010 3 Пусть 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.


Слайд 3

КИИ-2010 4 МТ-граф. Основные определения 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.


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

КИИ-2010 10 Операция поворота и взаимное расположение клеток на МТ-графе 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.


Слайд 10

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


Слайд 11

КИИ-2010 12 Препятствие Препятствия 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 ??


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

КИИ-2010 16 Вероятностный иерархический алгоритм планирования траектории Вход: 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. Разбить секцию <aij, alk> на N вариантов, а именно: Для каждого PP ? PPC, включающего aij, alk Шаг 7.1. Разбить PP на N дубликатов Шаг 7.2. Заменить последовательность aij, alk на aij, C1, alk, aij, C2, alk,…. aij, Cn, alk в каждом дубликате соответственно Шаг 8. Перейти к шагу 1


Слайд 16

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


Слайд 17

КИИ-2010 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<m){ C.i=D.i=i_down; C.j=j_left; D.j=j_right } else C=D=null; return {A, B, C, D}


Слайд 18

КИИ-2010 19 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. Разбить секцию <aij, alk> на 2 вариантa: aij, A, B, alk и aij,D, С, alk Шаг 9. Перейти к шагу 1


Слайд 19

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


Слайд 20

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


Слайд 21

КИИ-2010 22


Слайд 22

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


Слайд 23

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


Слайд 24

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


Слайд 25

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


Слайд 26

КИИ-2010 27


Слайд 27

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


Слайд 28

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


Слайд 29

КИИ-2010 30


Слайд 30

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


Слайд 31

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


Слайд 32

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


Слайд 33

КИИ-2010 34


Слайд 34

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


Слайд 35

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


×

HTML:





Ссылка: