Применение генетических алгоритмов для эффективного решения задачи навигации (1187414), страница 4
Текст из файла (страница 4)
например, [13], [14], [15]).Так как мы переформулировали задачу навигации через POMDP, можно рассматривать данную работу, как иной подход к решению POMDP в случае конкретной задачи.Сразу следует отметить, что при определении модели для поиска, мы абстрагируемся отмногих специфических для навигации аспектов, поэтому построенные алгоритмы также можно рассматривать как демонстрацию решения POMDP с помощью генетическихалгоритмов в общем случае.162.4Дополнительные предположенияЛегко понять, что с практической точки зрения рассматривать произвольный наборзадач Θ не эффективно. В реальности большинство окружений, с которыми можетстолкнуться автономный робот имеют определенную структуры, часто влияющую наэффективность навигации.
Ярким примером являются окружения созданные человеком. Например, ширина автомобильных дорог часто определяет «ранг» дороги — оптимальный маршрут в дали от цели вероятнее пролегает по главным дорогам, однакопри приближении к цели, часто оптимальнее использовать «локальную» дорожную систему, которая обычно уже. Другим примером является помещения — большая частьмаршрута, скорее всего будет пролегать по коридорам.Говоря о наличии структуры или особенностей в наборе задач Θ, мы будет сравнивать его относительно некого универсального набора задач, который постулируетсякак абсолютно бесструктурный. В качестве такого набора логично взять набор с максимальной энтропией.Определение 13.
Пусть заданы набор задач Θ с вероятностной мерой P и критерийкачества I(Θ, A). Будем говорить, что набор задач Θ обладает структурой, если:I(Θ, Â) > I(Θ, Â0 ) + где — некая заданная константа, Â — оптимальный алгоритм (например, алгоритм2) для набора задач Θ с вероятностной мерой P, Â0 — оптимальный алгоритм длянабора задач U (уравнение (1)) с вероятностной мерой P0 (θ) ≡ const.Наборы задач в данной работе подбирались, исходя в первую очередь из практических соображений. К сожалению, строго проверить наличие структуры в наборе задач,следуя определению, на практике невозможно в силу чрезвычайно высокой алгоритмической сложности процедуры нахождения оптимального алгоритма. Изначально наборы задач были выбраны исходя из интуитивных и практических соображений, а проверка на наличии структуры производилась постфактум сравнением качеств построенногоалгоритма и Â0 , либо качества Â0 с максимумом для критерия (maxΘ,A Ir (Θ, A) = −1).В дополнение к наличию структуры, вводится интуитивно понятное предположениео том, что начальные и конечные точки как случайные величины не несут никакойинформации об окружении (см.
условия теоремы 5).2.5Наивный алгоритмФактически, алгоритм Â0 (в данной работе он назван «наивным» в силу простоты предположений на вероятностную меру для набора задач) в свете определения 13 выступает в роли базового уровня. Так как сам алгоритм будет использоваться в дальнейшем,предоставим пример его реализации (алгоритм 3).Данная реализация опирается на тот факт, что при равномерном распределениизадач на U , апостериорное распределение вероятностей для каждой точки вне областизрения P(l(x, y) = −1 | (r0 , d0 , ω), v(x, y) = 0) = const, поэтому алгоритм 3 осуществляеткоманду, соответствующую кратчайшему пути по точка v(x, y) 6= 1.4На практике для поиска кратчайшего пути эффективнее использовать, например, алгоритм A*вместо приведенного поиска в ширину.
Однако в дальнейшем мы будем использовать потенциал, вычисленный поиском в ширину.17Algorithm 3 Наивный алгоритм навигации1:2:3:4:5:6:7:8:9:10:11:12:13:14:function Wave(v, open, closed, u)if open = ∅ thenreturn uend ifopen0 := ∅for (r, d) ∈ open dostates := {(r − d, d), (r, TURNLEFT(d)), (r, TURNRIGHT(d))}for (r0 , d0 ) ∈ states doif (r0 , d0 ) ∈/ closed ∧ v[r0 ] 6= 1 ∧ u[d0 ][r0 ] > u[d][r] + 1 then00u[d ][r ] := u[d][r] + 1open0 := open0 ∪ {(r0 , d0 )}end ifend forend for15:16:return Wave(v, open0 , open ∪ closed, u, v)end function17:18:19:20:21:22:23:24:function Potential(v, rf )u := []for (r, d) ∈ R × D dou[d][r] := +∞end forfor d ∈ D dou[d][rf ] := 0end for25:26:return Wave({(rf , d) | d ∈ D}, ∅, u, v)end function27:28:29:30:31:32:33:34:35:36:37:38:function Act(ω)(r, d, v, rf ) := ωu := Potential(v, rf )â := NULLû = +∞for a ∈ A do(r0 , d0 ) := ϕ(v, r, d, a)if û0 > u[d0 ][r0 ] thenû := u[d0 ][r0 ]â := aend ifend for39:40:return âend function182.6МотивацияМожно заметить, что для набора задач Θ ∼ O(2H×W ) мощность прямой модели M0алгоритма навигации, то есть отображения A : R × D × O 7→ A, колоссальна с практической точки зрения уже при H, W = 4 (|AR×D×O | ∼ 7 · 10245 ) и растет быстрее, чемэкспоненциально:H×Wmax |M0 | = 4 · (H × W ) · 32Рассмотренный алгоритм policy iteration на каждой итерации для каждого наблюдения оперирует с распределением над возможными наблюдениями, чья мощность достигает ∼ 2|Θ| для начальных итераций.
[16] Для решения POMDP разработаны многиеэвристические методы (см., например, [17]), например,итерационный алгоритм, расSсматривающий состояние системы как S = S 0 ∪ i {si }, где S 0 рассматривается как единое состояние, а улучшение оценки происходит за счет добавление состояний из S 0 дляявного рассмотрения; позволяющие балансировать между вычислительной сложностьюи качеством.
Однако часто для успешного практического применения используются малые по мощности модели POMDP, построенные за счет дополнительной предобработки(см., например, [18], [19], [15], [13]).Несмотря на практический успех применения POMDP в навигации автономных роботов, автором было принято решение рассмотреть другой подход, основанный на применении генетических алгоритмов, показавший себя перспективным на задачах обходапрепятствий (см. [2], [3], [4]). Решение было продиктовано известным свойством генетических алгоритмов — лучшая по сравнению со многими классическими оптимизационными подходами устойчивость к высоким размерностям. Например, популярно применение классического генетического поиска для отбора признаков в задачах машинногообучения — в этом случае мощность модели |M | = |2F | = 2|F | , где F — множество признаков, что в условиях высокой вычислительной стоимости функции качества (котораяв этом случае включает обучение используемого метода, для которого происходит отборпризнаков) дает преимущество по сравнению с методами дискретной оптимизации.Другим важным преимуществом генетического подхода является слабые начальные предположения и соответственно общность алгоритмов, что открывает возможности применять обширные модификации, приспосабливая метод для конкретной задачи.Именно этому свойству обязаны положительные результаты эксперимента.33.1Генетические методы навигацииМодельТеорема 3 обосновывает возможность поиска оптимального алгоритма (и его приближений) в классе эквивалентном отображениям R × D × O 7→ A, а при предположенияхо независимости начальной, конечной точек и окружения, теорема 5 сужает класс доAO .Понятно, что производить поиск напрямую в этом классе крайне затратно, поэтому,следуя аналогии с работами [3], [2], используется подмножество отображений, задаваемое набором шаблонов p : [−1, 1]O , задающие некое условие на наблюдение.
Такжеможно рассматривать эти шаблоны как предикаты нечеткой логики ([20], [4]). Итоговое отображение A задается набором G ⊂ {(p, a) | p : O 7→ [−1, 1], a ∈ A} на основе19схемы наилучшего соответствия:(·, A(ω)) = arg max p(ω)(52)(p,a)∈Gлибо схемы голосования:PA(ω) = arg maxâ∈A(p,a)∈GPI[a = â ∧ p(ω) > 0]p(ω)(p,a)∈GI[a = â ∧ p(ω) > 0](53)Следуя терминологии генетических методов, мы будем называть множество G — геномом.
В качестве базовой модели для шаблона зрения используется следующая функция похожести наблюдений:p((r, d, v, rf )) = pν ((r, d, v, rf )) = ν ⊗ cr,d (v)(54)где cr,d (v) — преобразование центрирования по r и поворота к d наблюдения v, ν —некий шаблон зрения.Следуя стандартному подходу ν следует задавать в как ν ∈ V , то есть в виде дискретных значений.
В работе [21] показаны преимущества распространения значенийшаблонов на непрерывное множество. Мы последуем этому подходу и определим шаблон зрения как матрицу со значениями в отрезке [−1, 1]:ν ∈ [−1, 1]h×w | h, w ≤ max(H, W )(55)Px,y νx,y vx,y(56)ν⊗v = Px,y |νx,y |где суммирование ведется по всем возможным в обеих матрицах индексам, считая отсутствующие значения равными нулю. Иными словами шаблон p задается нормированной суммой элементов поэлементного произведения фиксированного для p шаблоназрения ν и выровненного зрения v.Легко заметить, что шаблон зрения можно представить в виде разложения:ν =v◦cv ∈ {−1, 1}(57)h×wh×wc ∈ [0, 1](58)(59)где ◦ — оператор поэлементного умножения, v — дискретный шаблон окружения, аматрицу c можно рассматривать как коэффициенты вклада каждой точки.NОпределение 14. Пусть дан вектор предикатов нечеткой логики p ∈ [−1, 1]Oи вектор коэффициентов c ∈ RN . Тогда определим оператор нечеткой конъюнкциипредикатов p с коэффициентами c как:q =c⊗pPci · pi (ω)q(ω) = iPi |ci |20(60)Легко видеть, что c ⊗ p ∈ [−1, 1]OДля удобства дальнейшего использования переформулируем модель.
Для каждойточки относительно позиции робота (x, y) зададим предикат:px,y (ω) = v̇x,y(61)где v̇ — относительно текущей позиции робота зрение. Тогда обозначив вектор всехпредикатов (61) как pv , легко видеть, что:pν = ν ⊗ pv(62)где ν — рассматривается как вектор коэффициентов. Вектор предикатов pv будем вдальнейшем называть вектором базисных предикатов зрения.Аналогично зрению можно расширить определение модели.Определение 15. Конечное множество предикатов нечеткой логики G будем называть моделью:G ⊂ P = [−1, 1]OКаждой модели G соответствует вектор базисных предикатов pG ∈ G |G| . Модельпорождает множество выражаемых в модели предикатов:PG = c ⊗ pG | c ∈ R|G|Будем говорить, что модель G содержит геном G если:G ` G ⇐⇒ G ∈ (PG × A)∗Пусть задана схема принятия решений Λ : (P × A)∗ → (O 7→ A).
Будем говорить,что модель G содержит отображение A : O 7→ A, если:G ` A ⇐⇒ ∃G : G ` G : Λ(G) ≡ AЗададим предикаты текущей точки, поворота и целевой точки:ω = (r, d, ·, rf )1−1pρ (ω) = 21 + kr − ρkpδ (ω) = δ · d1pρf (ω) = 2−11 + krf − ρf k(63)(64)(65)(66)Теорема 6. Для схемы принятия решений (52) модель:G0 ={pν | ν ∈ [−1, 1]h×w | h, w ≤ max(H, W ) } ∪ {pδ | δ ∈ D}∪{pρf | ρf ∈ R} ∪ {pρ | ρ ∈ R}содержит все возможные отображения A : O 7→ A.21(67)Dokazatel~stvo. Для доказательства достаточно заметить, что каждый из предикатов(62), (63), (64), (65) задается через константное значение соответствующей компонентыω при этом:Arg max px (ω) = {ω | x = ωx }ω∈Oгде ωx — соответствующая x компонента ω.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
