Применение генетических алгоритмов для эффективного решения задачи навигации (1187414), страница 3
Текст из файла (страница 3)
Во-первых, при поиске (или аппроксимации)оптимального алгоритма навигации для любого набора задач с функцией качества,удовлетворяющей ограничениям теоремы (которые крайне слабы с практической точкизрения), можно ограничиться классом алгоритмов эквивалентным отображениям R ×D × O 7→ A. Во-вторых, это позволяет улучшить оценку (24).11Теорема 4. Пусть задан алгоритм-отображение A : R × D × O 7→ A и задача θ =(l, r0 , d0 , rf ).
Алгоритм A либо не решает задачу θ, либо:|ϕ(θ, A)| ≤ HW (4HW + 1)(40)Dokazatel~stvo.Так как r0 , d0 фиксированы, можно рассматривать отображение A0 (ω) =A(r0 , d0 , ω). Заметим, что если путь алгоритма содержит цикл, то алгоритм не решаетзадачу. Для фиксированного зрения v, ω = (r, d, v, rf ) существует не более 4HW различных позиций (r, d).
Так как алгоритм не содержит цикл, то он не встречает дваодинаковых наблюдения, значит для фиксированного зрения он может совершить неболее 4HW − 1 действий. Учитывая свойства функций зрения, после 4HW действий кv гарантированно добавиться как минимум одна известная точка. Всего точек не болееHW . Так как путь алгоритма не содержит цикл, то среди этих точек будет rf , чтодоказывает теорему.Теорема 5.
Пусть задано вероятностное пространство (Θ, 2Θ , P), где Θ — набор задач. Предположим, что окружение l, стартовая позиция (r0 , d0 ) и целевая точка rfнезависимы в совокупности как случайные величины. Тогда для любого существеннозависимого от внутреннего состояния алгоритма A существует не зависимый существенно от внутреннего состояния алгоритм A0 , такой что:Ia (Θ, A) ≤ Ia (Θ, A0 )(41)где Ia – критерий качества, заданный уравнением (29).Dokazatel~stvo.Для доказательства для алгоритма A для всех задач из Θ сопоставимкаждому возможному наблюдению состояния в момент получения этого наблюдения:H : O → SA∗ ;H(ω) = {s | ∃θ ∈ Θ : (s, ·, ·, ·, ω) ∈ Φ∗ (θ, A)}(42)Заметим, что одни и те же наблюдения могут соответствовать различным окружениям.На основе этого отображения построим новый алгоритм A0 c SA0 = {s0 } и ψ 0 (s, ω) =ψ(ω). Так как количество возможных наблюдений конечно, A0 представим в виде отображения O 7→ A.
Зафиксируем ω = (r, d, v, rf ) ∈ Ω(Θ). Если H(ω) = ∅, то полагаемψ 0 (ω) равным произвольной команде. Заметим, что ω ∈/ Ω(Θ) ⇒ H(ω) = ∅. Иначе,если ω ∈ Ω(Θ), то существует апостериорное распределение P(l | ω), определяемое поформуле Байеса. В силу независимости l, (r0 , d0 ) и rf как случайных величин:XP(ω | l) = I[l ` ω]P(θ)I[θ ` ω]I[θ = (l, ·, ·, rf )] = I[l ` ω]Cωθ∈Θгде(1, если t;I[t] =0, иначеОбозначим множество окружений из Θ как Lθ . Тогда:P(l)I[l ` ω]P(l)I[l ` ω]Cω= PP(l | ω) = PP(l)I[l ` ω]CωP(l)I[l ` ω]l∈LΘl∈LΘ12(43)Сопоставим каждому наблюдение из ΩA (Θ) = {ω | H(ω) 6= ∅} состояние ŝω :Xŝω = arg minP(l | ω) · |ϕ∗ ((ψ, s), l, r, d, rf , v)|(44)s∈H(ω) l∈LΘТогда:(·, ψ 0 (ω)) = ψ(ŝω , ω)Алгоритм A0 не является существенно зависимым от внутреннего состояния по построению.Докажем, что A0 не хуже алгоритма A по критерию I.Рассмотрим качество алгоритма A.
Заметим, что для заданной задачи существуеттолько единственная последовательность наблюдений и состояний. В силу свойства (9)текущее наблюдение ω = (r, d, rf , v) и начальная позиция (r0 , d0 ) полностью определяютапостериорное распределение θ:P(θ | ω ∗ ) = P(θ | (r0 , d0 ), ω)(45)где ω ∗ ∈ O∗ — последовательность наблюдений алгоритма. Рассмотрим промежуточное состояние: пусть алгоритма проделал путь π, наблюдая последовательность ω ∗ спервым наблюдением ω0 = (r0 , d0 , v0 , rf ) и последним ω = (r, d, v, rf ).
Рассмотрим «апостериорное» качество:−Ia (A, Θ | ω ∗ ) = −Eθ [Qa (θ, [π; ϕ∗ (A, l, r, d, rf , v)]) | (r0 , d0 ), ω]= Eθ [|ϕ∗ (A, l, r, d, rf , v)| | (r0 , d0 ), ω] + Eθ [|π| | (r0 , d0 ), ω]= Eθ [|ϕ∗ (A, l, r, d, rf , v)| | (r0 , d0 ), ω] − IπX=P(θ | (r0 , d0 ), ω)|ϕ∗ (A, l, r, d, rf , v)| − Iπ(46)(47)(48)(49)θ∈Θ= −Iω − Iπ(50)Заметим, что в силу независимости l и (r0 , d0 ) как случайных величин:P(θ | (r0 , d0 ), ω) = P((l, r00 , d00 , rf ) | (r0 , d0 ), ω)= P(l | (r0 , d0 ), ω) P((r00 , d00 ) | (r0 , d0 ), ω)I[θ ` ω]= P(l | ω)I[(r00 , d00 ) = (r0 , d0 )]I[θ ` ω]Тогда продолжая уравнение (50):X−Iω =P(θ | (r0 , d0 ), ω) · |ϕ∗ (A, l, r, d, rf , v)θ∈Θ=XP(l | ω) · I[(r00 , d00 ) = (r0 , d0 )] · I[θ ` ω] · |ϕ∗ (A, l, r, d, rf , v)|θ∈Θ= CωXP(l | ω) · |ϕ∗ (A, l, r, d, rf , v)|l∈LΘ≤ CωXP(l | ω) · |ϕ∗ ((ψ, ŝω )l, r, d, rf , v)|l∈LΘпо построению ŝω .13(51)Так как (51) верно для любого наблюдения и начальной позиции:Ia (A, Θ) ≤ Ia (A0 , Θ)что доказывает уравнение (41) и теорему.Стоит обратить внимание, что доказательство теоремы 5 неявно использует следующее свойство критерия Ia .Определение 9.
Пусть алгоритм проделал путь π, наблюдая последовательностьω ∗ , при этом отдавая команды ap ∈ A. Пусть Λ = AR×D×O — множество отображений (фактически, множество классов эквивалентности алгоритмов). Для λ ∈ Λможно построить составной алгоритм: A = [ap ; λ], который в начале исполняет последовательность ap , затем следует отображению λ. Тогда критерий I называетсяпотенциальным, если для набора задач Θ, для любого π возможного в наборе задач Θи соответствующих ap и ω ∗ существует функция Uθ ((r0 , d0 ), ω):â = Arg max max I([ap , a, λ], Θ | π, ω ∗ )a∈Aλ∈Λ= Arg max max I([ap , a, λ], Θ | (r0 , d0 ), ω)a∈Aλ∈Λ= Arg min Eθ [U ((r0 , d0 ), Φω (θ, ω, a)) | (r0 , d0 ), ω]a∈Aгде Φω (θ, ω, a) — наблюдение, которое будет получено после выполнения команды a взадаче θ при текущем наблюдении ω, следуя определению 2.Потенциальность критерия, фактически означает, что оптимальное действие в какомлибо состоянии не зависит от способа достижения этого состояния. В данном случаесостояние задается парой ((r0 , d0 ), ω).Очевидно, что для потенциалов Ia и Ir (уравнения (29) и (28)):Ua ((r0 , d0 ), ω) = Eθ∈Θ [ρθ (r, d)|(r0 , d0 ), ω]ρθ (r, d) (r0 , d0 ), ωUr ((r0 , d0 ), ω) = Eθ∈Θρθ (r0 , d0 ) где ρθ (r, d) — длина минимального пути из позиции (r, d) в точку rf в задаче θ =(l, r0 , d0 , rf ) (ρθ (r0 , d0 ) = |π̂(θ)|).Используя потенциал, довольно просто прийти к оптимальной стратегии, примерреализации которой приведен в алгоритме 2.2.3Частично наблюдаемый марковский процесс принятия решенийПотенциальность критериев качества позволяет сформулировать задачу в терминологии частично наблюдаемого марковского процесса принятия решения (partially observedMarkov decision process, POMDP)[11].14Algorithm 2 Оптимальный алгоритм навигацииRequire: Θ — набор задач, (Θ, 2Θ , P) — вероятностное пространство, U — потенциал.Ensure: Алгоритм (Act, ((0, 0), +∞, FALSE)) — оптимальный алгоритм для критерия,соответствующего потенциалу U .1: function Act(((r0 , d0 ) = (0, 0), u = +∞, initialSet? = FALSE), ω)2:if NOT initialSet? then3:(r, d, v, rf ) := ω4:(r0 , d0 ) := (r, f )5:u := U ((r0 , d0 ), ω)6:end if7:8:9:10:11:12:13:14:15:16:17:18:19:20:â := NULLua := +∞for a ∈ A dou0 := 0for θ ∈ Θ dou0 := u0 + Φω (θ, ω, a) · P(θ | (r0 , d0 ), ω)end forif u0 < ua thenua := u0â := aend ifend forreturn (((r0 , d0 ), ua , TRUE), â)end function15Определение 10.
Марковский процесс принятия решения задается набором (S, A, T, G),где S — конечное множество состояний системы, которые может различить агент,A — конечное множество возможных действий, T (s, a, s0 ) — функция перехода из состояния s при действии a агента, задающая дискретное распределение вероятностейна S, G(s, a) — функция награды при совершении действия a в состоянии s.Для заданной стратегии агента π : S 7→ A определяются соответствующие последовательности st , at .Определение 11.
Частично наблюдаемый марковский процесс принятия решения задается набором (S, A, O, T, G, O), где S, A, T , G задаются так же, как и в определении10, O — конечное множество наблюдений, O(s, ω) — функция, задающая распределениенаблюдений в состоянии s системы.Для заданной стратегии агента π : O 7→ A определяются соответствующие последовательности st , ωt at .Определим задачу навигации в терминах POMDP.Определение 12. Обобщенной задачей навигации будет называть частично наблюдаемый марковский процесс (S, A, O, T, G, O), где A и O соответствуют введеннымранее множествам доступный действий и наблюдений, S = R × D × Ξ(Θ), где Ξ(Θ)— множество возможных суперпозиций задач из Θ, а функции T , G и задаются следующим образом:s = (r, d, Ps )T (s, a, s ) = s0 = (r0 , d0 , Ps0 )(r0 , d0 ) = ϕ(ω, r, d)Ps (θ)I[θ ` Φω (θ, r, d, a)]Ps0 (θ) = Pϑ∈Θ Ps (ϑ)I[ϑ ` Φω (ϑ, r, d, a)]0Функция G(s, a) задается исходя из потенциала критерия качества.Заметим, что Ξ(Θ) — конечное множество как требуется в определениях 10 и 11, таккак множество возможных наблюдений всегда конечно |O| ≤ 3H×W , а каждая суперпозиция определяется через апостериорное распределение:Ps (θ) = P(θ | ω)Поэтому, фактически, можно рассматривать множество состояний S = O.Наиболее популярным алгоритмом решения POMDP в общем случае является policyiteration[12] — алгоритм динамического программирования, поледовательно находящийприближения потенциала для каждого наблюдения.Алгоритмы нахождения оптимальных стратегий для POMDP крайне популярныдля решения задач навигации в неизвестных окружениях (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
