Применение генетических алгоритмов для эффективного решения задачи навигации (1187414), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Будем говорить, что наблюдение ω ∈ O достижимо в задаче θ, еслиθ ` ω ⇐⇒ ∃a ∈ A∗ : ω ∈ ω ∗ (θ, a)6(18)Наблюдение достижимо в наборе задач, если оно достижимо хотя бы для одной задачи:_Θ ` ω ⇐⇒θ`ω(19)θ∈ΘОбозначит соответствующие множества как Ω(θ) и Ω(Θ):Ω(θ) = {ω ∈ O | θ ` ω}[Ω(Θ) =Ω(θ)(20)(21)θ∈ΘАналогично определяются l ` ω, (r0 , d0 ) ` ω, rf ` ω:l ` ω ⇐⇒ ∃θ = (l, ·, ·, ·) ∈ Θ : θ ` ω(r0 , d0 ) ` ω ⇐⇒ ∃θ = (·, r0 , d0 , ·) ∈ Θ : θ ` ωrf ` ω ⇐⇒ ∃θ = (·, ·, ·, rf ) ∈ Θ : θ ` ω2.1Критерии качестваОпределение 5.

Пусть задан набор задач Θ. Тогда два алгоритма A1 , A2 считаютсяΘэквивалентными относительно набора Θ — A1 ∼ A2 , если:∀θ ∈ Θ : ϕ∗ (A1 , θ) = ϕ∗ (A2 , θ)(22)ΘЕсли для любого набора Θ A1 ∼ A2 , то будем говорить, что два алгоритма эквивалентны A1 ∼ A2 .Определение 6. Пусть задан набор задач Θ и некий критерий качества Q(θ, π). Будем говорить, что алгоритм A1 доминирует алгоритм A2 по критерию Q относительно набора Θ, если:[∀θ ∈ Θ : Q(θ, ϕ∗ (A1 , θ)) ≥ Q(θ, ϕ∗ (A2 , θ))] ∧ [∃θ ∈ Θ : Q(θ, ϕ∗ (A1 , θ)) > Q(θ, ϕ∗ (A2 , θ))](23)Если из контекста понятно о каких Q и Θ идет речь, будем писать A1  A2Перед тем как перейти далее, заметим, что в общем случае не гарантированно, чтоалгоритм хоть когда-либо достигнет цели в неком окружении.

Вместо того, чтобы исследовать возможность алгоритмической проверки на достижении цели, предъявим оценкусверху на количество команд, которое может потребоваться для достижения цели. Дляэтого рассмотрим алгоритм 13 .Теорема 1. Алгоритм 1 (A0 ) решает любую задачу навигации θ = (l, r0 , d0 , rf ), причем:|ϕ∗ (A0 , θ)| ≤ (8HW + 4)34HW(24)Dokazatel~stvo.Для начала заметим, что в любой задаче существует путь из π ∈(R × D) из (r0 , d0 ) в (rf , ·) такой, что все элементы пути различны, то есть путь безсамопересечений, так как для из любого пути с самопересечениями отрезав «петли»∗3Для удобства записи используется оператор yield — аналог return, но сохраняющий внутреннеесостояние функции, в том числе и текущее состояние потока исполнения.7Algorithm 1 Алгоритм верхней границы1:2:3:4:5:6:7:8:9:10:11:function GenerateActionSequence(n)if n ≤ 0 thenreturn []end ifactionSequence = GenerateActionSequence(n − 1)result = []for all a ∈ A dofor all s ∈ actionSequence doresult += [a] + send forend for12:13:return resultend function14:allActionSequences = GenerateActionSequence(4W H)15:16:17:18:19:20:21:22:23:24:25:26:27:28:function Act((π = [], ns = 1, na = 1, tostart? = FALSE), ω)if tostart? = TRUE AND na > 0 thenif allActionSequences[ns ][na ] = TURNLEFT thenreturn ((π, ns , na − 1, TRUE), TURNRIGHT)else if allActionSequences[ns ][na ] = TURNRIGHT thenreturn ((π, ns , na − 1, TRUE), TURNLEFT)elsereturn ((π, ns , na − 1, TRUE), TURNLEFT)end ifelse if na ≤ 0 thenyield TURNRIGHTyield TURNRIGHTreturn Act(([], ns + 1, 1, FALSE), ω)end if29:30:31:32:33:34:35:36:37:38:39:40:(r, d, v, rf ) = ωif (r, d) ∈ π thenyield TURNLEFTyield TURNLEFTreturn Act((π, ns , na , TRUE), ω)elseπ 0 = [(r, d)] + πs0 = (π 0 , ns , na + 1, FALSE)a = allActionSequences[ns ][na ]return (s0 , a)end ifend function8можно получить путь без самопересечений.

Так как |R × D| = 4HW , то |π| ≤ 4HW , азначит соответствующая этому пути последовательность команд |a| ≤ 4HW .Несложно заметить, что алгоритм 1 просто перебирает все возможные последовательности команд длины 4HW , возвращаясь на исходную позицию при наличии самопересечения, а значит в какой-либо момент найдет последовательность соответствующуюкакому-либо пути из начальной точки в целевую. Всего возможных последовательностей команд длины 4HW : 34HW . При этом для каждой последовательности алгоритмсовершает не более 8HW + 4 команд (путь в обе стороны, плюс 4 команды для двухразворотов), что доказывает оценку (24).Несмотря на то, что алгоритм 1 тривиален, не эффективен ни вычислительно, нис точки зрения навигации, используя оценку (24) можно частично решить проблемуотсечения алгоритмов, которые не всегда находят путь из начальной точки в конечную— так как множество Θ конечно, существует тривиальная алгоритмическая процедура,проверяющая алгоритм на выполнение оценки (24).

Тем самым мы фактически накладываем ограничение на рассматриваемые алгоритмы.Условие частичного наблюдаемого окружение влечет трудности при оценке качестваалгоритмов. Понятно, что алгоритма, который находит оптимальный маршрут в любомокружении набора Θ может и не существовать.Определение 7. В случае, когда существует алгоритм, находящий кратчайшие маршруты в любом окружении набора Θ, будем называть набор Θ тривиальным.Теорема 2. Если Θ — не тривиальный набор задач, то для любого критерия качестваQ, достигающего единственный глобальный максимум на кратчайших маршрутах, несуществует доминирующего алгоритма:hi¬ ∃Â : ∀A Â : Â  A(25)Dokazatel~stvo.Обозначим кратчайший маршрут в окружении θ как π̂(θ) Предположим существование доминирующего алгоритма Â.

Так как Θ не тривиален, то∃θ0 ∈ Θ : Q(θ0 , ϕ∗ (Â, θ0 )) < max Q(θ0 , π) = Q(θ0 , π̂(θ0 ))πПусть алгоритм A0 вне зависимости от окружения следует пути π̂(θ0 )4 , после чего, еслицель не достигнута, следует, например, правилу левой руки.

Но тогда:Q(θ0 , ϕ∗ (A0 , θ0 )) = Q(θ0 , π̂(θ0 )) = max Q(θ0 , π) > Q(θ0 , ϕ∗ (Â, θ0 ))πчто противоречит определению доминирующего алгоритма.Понятно, что тривиальный наборы Θ редко встречаются в практических задачахи для наших целей не представляют интереса. Теорема 2 фактически означает, что вэтом случае измерение качества алгоритмов должно опираться на весь набора задач Θ.Самый простой класс однозначных критериев качества — взвешенная сумма по всемокружениям набора Θ :XQ̂(Θ, A) =c(θ)Q(θ, ϕ∗ (A, θ))(26)θ∈Θ4Это можно реализовать, например, положив SA0 = N, st+1 = st + 1, s0 = 1, каждый раз выдавая пономеру команду соответствующую пути π̂(θ0 ), который в силу конечности может быть просто частьюалгоритма.9которому в силу конечности Θ всегда можно придать вероятностную интерпретацию.Пусть задано вероятностное пространство над Θ c вероятностной мерой P(θ):Q̂(Θ, A) = Eθ Q(θ, ϕ∗ (A, θ))(27)В данной работе будет использоваться два критерия качества:|ϕ∗ (A, θ)|→ max|π̂(θ)|Ia (Θ, A) = Eθ Qr (θ, ϕ∗ (A, θ)) = −Eθ |ϕ∗ (A, θ)| → maxIr (Θ, A) = Eθ Qa (θ, ϕ∗ (A, θ)) = −Eθ(28)(29)Другим важным классом критериев являются максиминные критерии, например:|ϕ∗ (A, θ)|→ maxθ∈Θθ|π̂(θ)|Iam (Θ, A) = min Qr (θ, ϕ∗ (A, θ)) = min − |ϕ∗ (A, θ)| → maxIrm (Θ, A) = min Qa (θ, ϕ∗ (A, θ)) = min −θ∈Θθ(30)(31)(32)2.2Алгоритмы навигацииЗаметим, что в общем случае поведение алгоритма в момент t существенно зависитот его состояния в этот момент времени, которое не всегда можно восстановить понаблюдению ω t−1 .Определение 8.

Пусть задано вероятностное пространство (Θ, 2Θ , P), где Θ — наборзадач. Алгоритм A существенно зависит от внутреннего состояния, если:∃θ1 = (·, r0 , d0 , ·), θ2 = (·, r0 , d0 , ·) ∈ Θ, P(θ1 )P(θ2 ) > 0 : ∃t1 , t2 : ωθt11 = ωθt22 ∧atθ11 6= atθ22 (33)Иными словами алгоритм существенно зависит от своего внутреннего состояния,если решение алгоритма зависит не только от текущего наблюдения и положения.Несложно заметить, что алгоритмы не зависящие существенно от внутреннего состояния эквивалентны отображениям R × D × O 7→ A.Теорема 3. Пусть задано вероятностное пространство (Θ, 2Θ , P), где Θ — набор задач. Тогда для любого существенно зависимого от внутреннего состояния алгоритмаA существует не зависимый существенно от внутреннего состояния алгоритм A0доминирующий A по некому критерию Q(θ, A), Q(θ, A) = Q0 (θ, |ϕ∗ (θ, A)|), где функцияQ0 (θ, ·) строго убывает по второму аргументу при каждом фиксированном θ.Dokazatel~stvo.Так как в силу ограничений алгоритм A решает каждую задачу из Θ,то можно построить следующее отображение, сопоставляющее каждой тройке (r0 , d0 , ω)внутренние состояния алгоритма в момент наблюдения ω в задаче с (r0 , d0 ):H : R × D × O → SA∗ ;H(r0 , d0 , ω) = {s | ∃θ ∈ Θ : (s, ·, ·, ·, ω) ∈ Φ∗ (θ, A) ∧ (·, r0 , d0 , ·) = θ}(34)Заметим, что одни и те же наблюдения могут соответствовать различным окружениям.На основе этого отображения построим новый алгоритм A0 не зависимый существенно от внутреннего состояния.

Так как ω 0 = (r0 , d0 , ·, ·), то есть доступны алгоритмуизначально, для удобства включим (r0 , d0 ) в состояние алгоритма — SA0 = R × D.10Введем множество Θ(r0 , d0 , ω):Θ(r0 , d0 , ω) = {θ ∈ Θ | θ = (·, r0 , d0 , ·) ∧ θ ` ω}(35)Так как количество возможных наблюдений конечно, A0 представим в виде отображения SA0 × O 7→ A:ψA0 ((r0 , d0 ), ω) = ((r0 , d0 ), ψ 0 (r0 , d0 , ω))ψ 0 (r0 , d0 , ω) = ψ(s0 (r0 , d0 , ω), ω)s0 (r0 , d0 , ω) = arg minmin |ϕ∗ ((ψ, s), l, r, d, rf , v)|(36)(37)(38)s∈H(r0 ,d0 ,ω) θ∈Θ(r0 ,d0 ,ω)Докажем, что алгоритм A0 не хуже A. Заметим, что в силу свойств (9) и (14) понаблюдению ω и начальной позиции (r0 , d0 ) для заданного алгоритма можно единственным образом восстановить последовательность состояний от начала до последнегополучения этого наблюдения, которое всегда существует, так как алгоритм завершаетлюбую задачу из набора. Для этого достаточно взять любое θ ∈ Θ(r0 , d0 , ω) и взятьначало Φ∗ (A, θ).

Рассмотрим случай H(r0 , d0 , ω) = {s1 , s2 , . . . , sT }, T ≥ 2. Пусть состояния упорядочены по номеру шага, на котором они появляются. В силу свойства (14)между первым s1 и последним sf состояниями, алгоритм не получал зрение отличноеот v, ω = (r, d, v, rf ), а значит просто сделал петлю в известной области.∀θ = (l, r0 , d0 , rf ) ∈ Θ(r0 , d0 , ω) : |ϕ∗ ((ψ, sf ), l, r, d, rf , v)| < |ϕ∗ ((ψ, s1 ), l, r, d, rf , v)| (39)а значит sf будет минимизировать (38). Обозначим путь проделанный алгоритмом допервого наблюдения ω как π. Так как (39) верно для всех возможных при (r0 , d0 ) и ωзадачах, то:∀θ = (l, r0 , d0 , rf ) ∈ Θ(r0 , d0 , ω) :Q(θ, A0 ) = Q0 (θ, |π| + |ϕ∗ ((ψ, sf ), l, r, d, rf , v)|) >Q0 (θ, |π| + |ϕ∗ ((ψ, s1 ), l, r, d, rf , v)|) = Q(θ, A)Так как это верно для любых возможных ω и (r0 , d0 ), для которых |H(r0 , d0 , ω)| ≥ 2,f по определению существует хотя бы одна такая пара, и так как для |H(r0 , d0 , ω)| = 1алгоритмы принимают одинаковые решения, то:∀θ ∈ Θ : Q(θ, A0 ) ≥ Q(θ, A)∃θ ∈ Θ : Q(θ, A0 ) > Q(θ, A)что доказывает A0  A.Так как A0 по построению не зависим существенно от внутреннего состояние, теоремадоказана.Теорема 3 имеет два важных следствия.

Характеристики

Список файлов ВКР