在线信念状态规划与控制器抽象

# 在线信念状态规划与控制器抽象 ## 1. 在线信念状态规划 ### 1.1 启发式搜索 启发式搜索在部分可观测马尔可夫决策过程（POMDP）中起着重要作用，它可以通过使用近似值函数进行前瞻。在启发式搜索中，初始的上下界值对算法性能有重要影响。例如，随机滚动策略可用于计算下界 $U(b)$，不过由于它基于固定深度的单次试验，并不一定能保证产生真正的下界，但随着样本数量的增加，会收敛到真实下界。上界可以使用最佳动作最佳状态上界，如公式 (21.2) 所示。此外，还有其他形式的上下界，如使用快速知情界（算法 21.3）作为上界可以改善探索并缩小差距，对于下界，可以使用特定问题的滚动策略来更好地引导搜索。 ### 1.2 在线策略方法总结 - **一步前瞻**：考虑从当前信念采取的每个动作，并使用近似值函数估计其期望值。 - **前向搜索**：是前瞻的一般化，可应用于任意时间范围，能得到更好的策略，但计算复杂度随时间范围呈指数增长。 - **分支限界**：是前向搜索的更高效版本，通过对值函数设置上下界来避免搜索某些路径。 - **稀疏采样**：一种近似方法，可减少遍历所有可能观测空间的计算负担。 - **蒙特卡罗树搜索**：可通过操作历史而非状态来适应 POMDP。 - **确定性稀疏树搜索**：使用特殊形式的粒子信念，确保观测是确定性的，大大减少搜索树。 ### 1.3 启发式搜索代码实现 ```julia struct GapHeuristicSearch 𝒫 # problem Ulo # lower bound on value function Uhi # upper bound on value function δ # gap threshold k_max # maximum number of simulations d_max # maximum depth end function heuristic_search(π::GapHeuristicSearch, Ulo, Uhi, b, d) 𝒫, δ = π.𝒫, π.δ 𝒮, 𝒜, 𝒪, R, γ = 𝒫.𝒮, 𝒫.𝒜, 𝒫.𝒪, 𝒫.R, 𝒫.γ B = Dict((a,o)=>update(b,𝒫,a,o) for (a,o) in product(𝒜,𝒪)) B = merge(B, Dict(()=>copy(b))) for (ao, b′) in B if !haskey(Uhi, b′) Ulo[b′], Uhi[b′] = π.Ulo(b′), π.Uhi(b′) end end if d == 0 || Uhi[b] - Ulo[b] ≤ δ return end a = argmax(a -> lookahead(𝒫,b′->Uhi[b′],b,a), 𝒜) o = argmax(o -> Uhi[B[(a, o)]] - Ulo[B[(a, o)]], 𝒪) b′ = update(b,𝒫,a,o) heuristic_search(π,Ulo,Uhi,b′,d-1) Ulo[b] = maximum(lookahead(𝒫,b′->Ulo[b′],b,a) for a in 𝒜) Uhi[b] = maximum(lookahead(𝒫,b′->Uhi[b′],b,a) for a in 𝒜) end function (π::GapHeuristicSearch)(b) 𝒫, k_max, d_max, δ = π.𝒫, π.k_max, π.d_max, π.δ Ulo = Dict{Vector{Float64}, Float64}() Uhi = Dict{Vector{Float64}, Float64}() for i in 1:k_max heuristic_search(π, Ulo, Uhi, b, d_max) if Uhi[b] - Ulo[b] < δ break end end return argmax(a -> lookahead(𝒫,b′->Ulo[b′],b,a), 𝒫.𝒜) end ``` ### 1.4 哭泣婴儿问题示例 以下代码展示了如何将间隙启发式搜索应用于哭泣婴儿问题： ```julia δ = 0.001 # gap threshold k_max = 5 # maximum number of iterations d_max = 10 # maximum depth πrollout(b) = rand(𝒜) # random rollout policy Ulo(b) = rollout(𝒫, b, πrollout, d_max) # initial lower bound Rmax = maximum(R(s,a) for (s,a) in product(𝒮,𝒜)) # max reward Uhi(b) = Rmax / (1.0 - 𝒫.γ) # best action best state upper bound π = GapHeuristicSearch(𝒫, Ulo, Uhi, δ, k_max, d_max) π([0.5, 0.5]) # evaluate at initial belief point ``` ### 1.5 练习 #### 练习 22.1 假设 $A = \{a_1, a_2\}$，信念 $b = [0.5, 0.5]$，奖励始终为 1，观测函数为 $P(o_1 | a_1) = 0.8$ 和 $P(o_1 | a_2) = 0.4$，近似值函数由阿尔法向量 $\alpha = [-3, 4]$ 表示，$\gamma = 0.9$，使用深度为 1 的前向搜索计算 $U(b)$。 | a | o | Update(b, a, o) | |----|----|----------------| | a1 | o1 | [0.3, 0.7] | | a2 | o1 | [0.2, 0.8] | | a1 | o2 | [0.5, 0.5] | | a2 | o2 | [0.8, 0.2] | **解答步骤**： 1. 计算更新后信念的效用： - $U_0(Update(b, a_1, o_1)) = \alpha^⊤b′ = 0.3 × -3 + 0.7 × 4 = 1.9$ - $U_0(Update(b, a_2, o_1)) = 0.2 × -3 + 0.8 × 4 = 2.6$ - $U_0(Update(b, a_1, o_2)) = 0.5 × -3 + 0.5 × 4 = 0.5$ - $U_0(Update(b, a_2, o_2)) = 0.8