基于環(huán)境狀態(tài)分布優(yōu)化的POMDP 值迭代求解算法

摘 要： "基于點(diǎn)的值迭代算法是一類解決 POMDP 問題的有效算法，PBVI 是基于點(diǎn)集的經(jīng)典算法，但是其算法效率較為低下。FSVI使用內(nèi)在的 MDP 最優(yōu)策略來降低算法復(fù)雜度，但求解大規(guī)模問題的效果較差。為解決上述問題，提出了基于環(huán)境狀態(tài)分布優(yōu)化的前向搜索值迭代算法（PBVI-OSD），通過基于權(quán)重值的 QMDP 選出最佳的動作，基于信念狀態(tài)和轉(zhuǎn)換函數(shù)選取最大可能的狀態(tài)，基于動作和狀態(tài)從觀察中隨機(jī)選取一個觀察概率大于閾值的觀察，由此獲得更具探索價值的后繼信念點(diǎn)集，提升值迭代收斂的質(zhì)量。在四個基準(zhǔn)問題上的實(shí)驗(yàn)表明，相比于 FSVI 和 PBVI，PBVI-OSD能保證收斂效率，特別是在大規(guī)模問題上能收斂到更好的全局最優(yōu)解。

關(guān)鍵詞： "部分可觀測馬爾可夫決策過程； 可達(dá)信念空間； 智能體規(guī)劃

中圖分類號： "TP18 """文獻(xiàn)標(biāo)志碼： A

文章編號： "1001-3695（2022）02-008-0374-05

doi：10.19734/j.issn.1001-3695.2021.08.0310

Probability-based value iteration on optimal state "distribution algorithm for POMDP

Zhu Rongxin1，2， Wang Xuan3， Liu Feng3， Zhao Zhihong3，4

（1.School of Cyberspace Security， Hainan University， Haikou 570208， China; 2.Nanjing Normal University of Special Education， Nanjing 210038， China; 3.Software Institute， Nanjing University， Nanjing 210093， China; 4.Nanjing Tech University， Nanjing 211816， China）

Abstract： nbsp;Point-based value iteration methods are a class of practical algorithms for solving the POMDP model. PBVI is a classical point-based value iteration method with low efficiency. FSVI can reduce the complexity and improve efficiency significantly by using the optimal strategy of the underlying MDP. However， it is not efficient in the large-scale POMDP problems. The paper proposed a probability-based value iteration on optimal state distribution algorithm for POMDP （PBVI-OSD）. Du-ring the exploration， PBVI-OSD used the alias method to sample the action "a * based on weighted "QMDP "function and sample the state based on "b "and the transition function. Then PBVI-OSD selected the observation "z "whose probability was greater than the threshold， and got the successor point "b "with great value from "a * and "z ， which ensured the effect of value iteration. Experiment results of four benchmarks show that PBVI-OSD can achieve better global optimal solutions than FSVI and PBVI， especially in large-scale problems.

Key words： "partially observable Markov decision process （POMDP）; reachable belief space; agent planning

0 引言

部分可觀察馬爾可夫決策過程（partially observable Markov decision processes，POMDP）提供了一個強(qiáng)大的數(shù)學(xué)框架，解決在不確定環(huán)境中的順序決策問題，可應(yīng)用于較多復(fù)雜的場景，如機(jī)器人探索任務(wù)［1］、反隱身探測任務(wù)［2］和癌癥檢測［3］等。然而，精確求解POMDP復(fù)雜度太高，導(dǎo)致POMDP在很長一段時間內(nèi)難以應(yīng)用到實(shí)際問題的處理，因此，出現(xiàn)了很多近似求解POMDP的方法［4］。基于點(diǎn)的POMDP算法從信念空間中取樣出具有代表性的信念點(diǎn)集，在可達(dá)信念點(diǎn)集上進(jìn)行值函數(shù)迭代，直至收斂［5］。盡管基于點(diǎn)的算法是近似算法，但顯著降低了值迭代的代價，使得可以做更多次有效迭代，從而能夠提升全局的效率，因此成為了當(dāng)前研究的熱點(diǎn)。

基于點(diǎn)的POMDP方法的關(guān)鍵是如何采樣信念點(diǎn)集 B 。PBVI是經(jīng)典的基于密度標(biāo)準(zhǔn)擴(kuò)展探索點(diǎn)集的算法，對于當(dāng)前探索點(diǎn)集 B中的每個b，選取其后繼中距B最遠(yuǎn)的b *進(jìn)行探索［4］，使得從可達(dá)信念空間中選取的信念點(diǎn)盡可能分散。然而，PBVI算法在擴(kuò)展信念點(diǎn)集中計(jì)算代價大。因此出現(xiàn)了HSVI［6］和GapMin［7］等基于值函數(shù)的近似求解方案，這些方案根據(jù)最優(yōu)值函數(shù)上界來選擇最優(yōu)動作探索最優(yōu)可達(dá)信念點(diǎn)集，保證收斂到全局最優(yōu)［8］。然而這些方案在大規(guī)模問題上存在收斂效率不高的缺陷，因此難以應(yīng)用到在線問題的求解中。FSVI［9］等基于MDP的近似解法根據(jù)MDP的策略在信念空間獲得的最優(yōu)動作構(gòu)建求解降低了復(fù)雜度，從而在很大程度上提升了效率。然而，現(xiàn)有FVSI方法沒有利用模型的環(huán)境信息，在無峰值狀態(tài)的問題中會退化為隨機(jī)策略，使得FSVI很難應(yīng)用到實(shí)際的大規(guī)模問題中。近年來，HHVI［10］嘗試雜合PBVI和HSVI探索的標(biāo)準(zhǔn)，但也不能避免維護(hù)上下界值函數(shù)的開銷。

為了解決上述問題，本文提出一種新的基于環(huán)境狀態(tài)分布優(yōu)化的前向搜索值迭代算法PBVI-OSD（probability-based value iteration on optimal state distribution）。該算法基于MDP優(yōu)化策略，有效利用環(huán)境反饋的信息。首先，PBVI-OSD根據(jù)當(dāng)前信念狀態(tài)和 QMDP 函數(shù)，計(jì)算出各個動作對應(yīng)為最優(yōu)動作的概率，由此使用別名方法采樣一個最優(yōu)的動作 a *。其次，PBVI-OSD基于信念狀態(tài) b 與狀態(tài)轉(zhuǎn)換函數(shù)的結(jié)果進(jìn)行加權(quán)，選出最可能達(dá)到的狀態(tài)作為下一個狀態(tài)，即最有可能到達(dá)的狀態(tài) s 。最后，PBVI-OSD在保證觀察概率大于閾值的基礎(chǔ)上隨機(jī)選擇觀察 z ，并把由此獲得的信念狀態(tài)作為后繼信念點(diǎn)，從而擴(kuò)充探索信念點(diǎn)集 B 。PBVI-OSD根據(jù)權(quán)重選取更加合理的動作、狀態(tài)，以及在探索期間選擇更加合理的觀察，使得其能夠確保效率，提升算法的質(zhì)量。實(shí)驗(yàn)結(jié)果表明，PBVI-OSD在大規(guī)模問題上能收斂到更好的全局最優(yōu)解，同時能夠保證收斂效率和性能。

1 POMDP模型及其求解

1.1 POMDP問題

POMDP對agent在不確定性環(huán)境下的決策問題進(jìn)行建模，在此模型中，agent每一步執(zhí)行一個動作，其得到的結(jié)果是隨機(jī)的，且其觀察也并不完備。POMDP模型可以被描述為一個八元組 （S，A，Z，b 0，T，O，R，γ），其中：S為一個隱含狀態(tài)的有限集合，表示系統(tǒng)所有可能處于的狀態(tài)；A 為一個agent能采取的動作集合； Z 為一個觀察的有限集合，表示agent所有可能的輸入； b 0為初始的狀態(tài)分布，表示初始時刻t 0系統(tǒng)在狀態(tài)集合S上的概率分布；T（s，a，s′）=P（s t+1=s′|s t=s，a t=a）為狀態(tài)到狀態(tài)的轉(zhuǎn)移概率函數(shù)，描述 agent在 狀態(tài)s采取動作a后到達(dá)狀態(tài)s′的概率；O（s′，a，z）=P（z t+1=z|a t=a，s t+1=s′）為觀察函數(shù)，表示執(zhí)行a動作于t+1時刻轉(zhuǎn)移到s′狀態(tài)后觀察到z的概率；R（s，a）為回報函數(shù)，即在狀態(tài)s中采取動作a獲得的回報（效用值）；γ∈（0，1）為折扣因子，作用是淡化長期回報，并且保證無限步數(shù)的長遠(yuǎn)回報得以 收斂。

POMDP模型中，由于agent只能從環(huán)境中獲取觀察，且不能確定其所屬狀態(tài)。所以，它必須根據(jù)歷史動作和觀察集合 {a 0，z 1，a 1，z 2，a 2，z 3，…，a t－1，z t}決定下一個動作［11］。因而需要引入充分統(tǒng)計(jì)信念狀態(tài)b，用來維護(hù)歷史信息。b定義為［12］b（s）=P（s t=s|z t，a t -1，…，z 1，a 0） 。

將原始問題映射到一個信念空間，可以把POMDP問題轉(zhuǎn)換為MDP問題來求解。 因?yàn)闀r刻t處的信念狀態(tài)b t只需要前一步的信念狀態(tài)b t－1，最近采取的動作a t－1和得到的觀察z t來獲得，其表達(dá)式如下 ［13］：

b t（s′）=τ（b t－1，a t－1，z t）= O（s′，a t－1，z t）∑ "s∈S T（s，a t－1，s′）b t－1（s） P（z t|b t－1，a t－1）

其中： Pr（z t|b t－1，a t－1）為歸一 因子［12］，表示agent在信念 點(diǎn)b t-1處采取動作a t－1后觀察到z t的 概率。

P（z t|b t－1，a t－1）=∑ ""O（s′，a t－1，s）∑ "s∈S T（s，a t－1，s′）b t－1（s）

POMDP中的策略是信念空間到動作的映射： π（b）→a。給定一個策略π，π 的長遠(yuǎn)回報計(jì)算如下：

V π（b）=E［∑ T t=t o γt－t 0R（b t，π（b t））］

對于一個給定的POMDP模型，求解的任務(wù)就變成了計(jì)算最優(yōu) 策略π*，使得能最大化長遠(yuǎn)回報的期望。通過貝爾曼方程迭代可以求得最優(yōu)策略［11］。Q值函數(shù)Q t+1（b，a）定義為在信念狀態(tài)b選定動作a且保證持續(xù)優(yōu)化剩余的t 視野的動作值函數(shù)。

Q t+1（b，a）=∑ "s∈S b（s）R（s，a）+γ∑ "z∈Z P（z|b，a）V* t（τ（b，a，z））

V* t+1（b）= max "a∈A "Q t+1（b，a）

對應(yīng)的最優(yōu)策略表示為 π* t+1（b ）=argmax "a∈AQ t+1（b，a）。雖然b在|S|－1維的連續(xù) 單空間內(nèi)有無限個取值，Smallword［15］等證明對于任意的有限視野 t ，值函數(shù)為信念空間上的分段線性凸函數(shù)，表示為一個向量集合。

τ t={α 0，α 1，…，α |τ t|，V t（b）= max "α∈|τ t| b·α}

從 Γ t更新到Γ t+1，可以在整個信念空間上精確求解來獲得。然而，其更新的復(fù)雜度近似為O（|S|2|A||Z||B||Z| ），POMDP 的精確值迭代算法存在維度災(zāi)和歷史災(zāi)問題。盡管有些算法，如Witness［14］和增量裁剪算法［15］對精確求解的算法有所改進(jìn)，但它們還是不能降低在極端場景下的算法復(fù)雜度。

1.2 基于點(diǎn)的值迭代

由于精確計(jì)算POMDP問題的復(fù)雜度是指數(shù)級的，且值函數(shù)向量集的向量數(shù)目增加較快，導(dǎo)致了精確求解難以應(yīng)用于實(shí)際問題的求解［16］，所以研究人員提出了很多有效的近似求解算法。對于大部分的POMDP問題，agent所能到達(dá)的信念點(diǎn)集合 B 往往只是信念空間的一小部分［17］，因此可以用基于點(diǎn)的算法來求得其誤差在一定范圍之內(nèi)的近似解，避免精確求解中計(jì)算笛卡爾積的巨大計(jì)算量，從而通過增加迭代次數(shù)保證算法效果。基于點(diǎn)的算法有信念子集 B 的擴(kuò)張，以及實(shí)現(xiàn)信念點(diǎn)集上的值函數(shù)更新的backup操作兩個主要部分。

backup函數(shù)在點(diǎn) 集B上計(jì)算從Γ t到Γ t+1的復(fù)雜度近似為O（|S|2|A||Z||B|2）。雖然基于點(diǎn)的算法只會更新可達(dá)信念點(diǎn)集的向量集，但是可以保證獲得一個誤差范 圍可控的近似解。

基于點(diǎn)的方法在終止條件之前反復(fù)執(zhí)行兩個步驟：探索新的信念點(diǎn)以擴(kuò)張信念點(diǎn) 集合B；在B上更新值函數(shù)Γ。而基于點(diǎn)的值迭代 方法的主要差別在于不同的信念點(diǎn)集探索方法［18］。

1.3 前向搜索值迭代算法

前向搜索值迭代算法（FSVI）簡化了agent和環(huán)境之間的交互，基于狀態(tài)來貪婪探索信念空間，F(xiàn)SVI算法探索的過程如算法1所示。

算法1 FSVI exploration

輸入： b，s 。

輸出： V 。

if "s "is not a goal state then

a *←argmax "a∈AQMDP（s，a ）

sample "s ′ from "T（s，a*，* ）

sample "z "from "O（s′，a*，* ）

FSVIExploration（ bz a*，s ′）

end if

V←V ∪backup（ b，V ）

算法1中，F(xiàn)SVI通過使用信念狀態(tài)采 樣s，模擬在環(huán)境中的狀態(tài)，使用信念狀態(tài)b來 表示agent的當(dāng)前狀態(tài)，維護(hù)這樣一個狀態(tài)—信 念狀態(tài)對（s，b）。首先基于狀態(tài)s 得到POMDP下的最優(yōu)動作 a*，接著基于狀態(tài)轉(zhuǎn)移函數(shù)T（s，a，s′）隨機(jī)選取下一個狀態(tài)s′，再通過觀察函數(shù)得到隨機(jī)觀察值z，由此可根據(jù)信念狀態(tài)轉(zhuǎn)移函數(shù)得到下一個信念點(diǎn)b′ ，backup函數(shù)用于生成信念點(diǎn)集的最優(yōu)向量［9］，算法持續(xù)搜索直到agent到達(dá)某一個目標(biāo)狀態(tài)或其他結(jié)束條件［19］。

FSVI基于內(nèi)在的MDP最優(yōu)策略，選取最優(yōu)動作非常的快速，只需 要探索O（|A|） 個MDP的 Q 值函數(shù)。因此，該方法極大地降低了算法的復(fù)雜度。相比其他的如PBVI等廣度優(yōu)先的探索算法，F(xiàn)SVI通過深度優(yōu)先的探索能夠獲取一個更高效的結(jié)果；相比于同為深度優(yōu)先的HSVI［20］等算法，F(xiàn)SVI在探索過程中隨機(jī)獲取狀態(tài)和觀察，降低了計(jì)算的復(fù)雜度。

然而，F(xiàn)SVI過于簡化了采樣動作和狀態(tài)的過程，使得其在某些場景表現(xiàn)得并不是很好。主要有兩方面的缺陷：首先是選取動作的過程，其只基于MDP優(yōu)化的策略選擇，而沒有考慮到全局的狀態(tài)分布情況，F(xiàn)SVI的方案不能保證選擇全局最佳的動作，因而使FSVI易陷入局部最優(yōu)方案［21］；其次，F(xiàn)SVI隨機(jī)取樣狀態(tài)提升了效率，但是難以適用于稀疏狀態(tài)的POMDP問題。而實(shí)際的POMDP問題通常具有大規(guī)模的狀態(tài)，其狀態(tài)的分布也很分散［22］。

2 "基于環(huán)境狀態(tài)分布優(yōu)化的POMDP值迭代求解算法

2.1 算法思想

因POMDP應(yīng)用于不確定的環(huán)境，agent不能精確確定其所屬狀態(tài)，必須充分利用信念狀態(tài) b，根據(jù)環(huán)境的反饋選擇最佳策略。因此，本文探討了在信念探索中，當(dāng)前信念狀態(tài)對動作、狀態(tài)和觀察選擇的作用，提出了結(jié)合QMDP以及當(dāng)前信 念狀態(tài)，通過加權(quán)期望選取動作和狀態(tài)的采樣算法。

信念狀態(tài)是表示agent在各個狀態(tài)上的概率分布。因此，在選取最優(yōu)動作的過程中，可以根據(jù)信 念狀態(tài)和QMDP函數(shù)計(jì)算各個動作作為最優(yōu)動作的加權(quán)概率，I表示當(dāng)前動作是否為取得的最大QMDP對應(yīng)的動作值。用actionPr i表示每個動作被選擇的概率值。然后根據(jù)概率分布通過別名算法加權(quán)取樣出最佳的動作a* ，如式（1）（2）所示。

actionPr i←∑ "s∈S b（s）I a i= argmax "a（QMDP（s，a））， where "I a=b= 1 a=b """0 a≠b """"""""（1）

a *←AliasMethod（ {actionPr 1，actionPr 2，…，actionPr |A|}） ""（2）

在對下一時刻的狀態(tài)進(jìn)行采樣時，結(jié)合信念狀態(tài) b和狀態(tài)轉(zhuǎn)換函數(shù)T的結(jié)果進(jìn)行加權(quán)，結(jié)果用nextStatePr i表示下一個狀態(tài)可能出現(xiàn)的加權(quán)概率值。貪婪選出最有可能達(dá)到的狀態(tài)s ，如式（3）（4）所示。

nextStatePr i←∑ s∈S b（s）T（s，a*，s′） ""（3）

s′← max （{nextStatePr 1，nextStatePr 2，…，nextStatePr |S|}） ""（4）

當(dāng)選擇觀察 z 時，PBVI-OSD設(shè)置了一個閾值 ε來 過濾那些可能性過低的觀察，獲得后繼點(diǎn)集successors（ b ），然后使用別名方法從這個后繼信念點(diǎn)集中選取下一個信念點(diǎn) b ，如式（5）（6）所示。

successors （b）←{ba，z|O（s′，a*，z）gt;ε} ""（5）

b ′←AliasMethod（successors（ b ）） "（6）

2.2 PBVI-OSD算法步驟描述

PBVI-OSD形式化描述見算法2，PBVI-OSD首先由盲目策略（算法3）初始化值函數(shù) V，值函數(shù)V是一系列向量。接著從一個初始信念點(diǎn)B={b 0}開 始。通過PBVIOSDExplore（算法4）方法探索信念點(diǎn)集并進(jìn)行值迭代，直至達(dá)到目標(biāo)狀態(tài)或者迭代到限定步長時，算法才會終止。

算法3的盲目策略用于初始化值函數(shù) V 。算法4 PBVIOSD- Explore，基于信念狀態(tài)和 QMDP函數(shù)計(jì)算各個動作作為最優(yōu)動作的概率，然后根據(jù)概率分布通過別名算法加權(quán)取樣出最佳的動作a*；結(jié)合信念狀態(tài)b和狀態(tài)轉(zhuǎn)換函數(shù)的結(jié)果進(jìn)行加權(quán)，別名方法選出最有可能達(dá)到的狀態(tài)s；選擇觀察z時，設(shè)置閾值過濾可能性低的觀察，不斷擴(kuò)充信念點(diǎn)集，直至某一個目標(biāo)狀態(tài)或其他結(jié)束條件，算法 流程如圖1所示。

算法2 PBVI-OSD

輸入 ：POMDP 。

輸出： V 。

V ←BlindPolicy（）

B={b 0}

repeat

V ←PBVIOSDExplore （b 0，B ）

until convergence

算法3 blind policy

輸入： POMDP。

輸出： "V a（s ）。

V a（s）← "min "a，s′R a（s′） 1－γ "s，a

repeat

V a（s）←R a（s）+γ∑ s′∈s T（s，a，s′）V a（s′） s，a

until convergence

算法4 PBVIOSDExplore

輸入： b，B 。

輸出： V 。

action Pr s←{∑ "s∈S b（s）I a i =argmax "aQMDP（s）|a i∈A}

a* ←AliasMethod（ actionPr s）

NextStatePr s←{∑ "s∈S b（s）T（s，a*，s i）|s i∈S}

s′ ←max（{ nextStatePr 1，nextStatePr 2，…，nextStatePr |S|} ）

if "sgoalState "then

successors（ b）←{ba，z|O（s′，a*，z）gt;ε}

b ′←AliasMethod（successors（ b ））

B new←B∪{b′ }

PBVIOSDExplore（ b′，B new ）

end if

V←V ∪backup （b，V ）

通過求 解QMDP函數(shù)獲得狀態(tài)到最優(yōu)動作選擇的映射。對某一信念狀態(tài)點(diǎn)b，計(jì)算最優(yōu)動作的過程中，通過式（1）計(jì)算某個動作的選擇概率的時間復(fù)雜度為O（|S||A|）。式（2）使用別名方法選取最優(yōu)動作的時間復(fù)雜度為O（|A|）。式（3）計(jì)算下一個狀態(tài)的分布概率的時間復(fù)雜度為O（|S|2），式（4）選取狀態(tài)的時間復(fù)雜度為O（|S|）。后繼信念點(diǎn)的選擇首先根據(jù)設(shè)置的閾值過濾掉概率小于閾值的觀察，式（5）選擇觀察的時 間復(fù)雜度為|S||A||Z|。同樣，式（6）的時間復(fù)雜度為O（|S|）。 因此，一次擴(kuò)張過程的時間復(fù)雜度為O（|S|2|A||Z|+|S|2|A|+ O（|S|3）） 。

3 實(shí)驗(yàn)及結(jié)果分析

本文在Hallway2［23］和不同規(guī)模的RockSample［19］問題上進(jìn)行基準(zhǔn)測試，在其上分別運(yùn)行PBVI-OSD、FSVI和PBVI三個算法。Hallway2是一個經(jīng)典的迷宮問題。RockSample模擬了agent采樣礦石的科學(xué)考察任務(wù)，它是一個可擴(kuò)展的問題，agent要接觸某一區(qū)域的巖石并對巖石采樣以獲得回報，agent到達(dá)最右邊的出口也會獲得回報。RockSample規(guī)模可擴(kuò)展，為了分析算法的性能特性，故選擇的數(shù)據(jù)集規(guī)模較大，選取的數(shù)據(jù)集包括RockSample［7，8］、RockSample［10，10］和RockSample［11，11］。各個POMDP基準(zhǔn)測試的參數(shù)特征描述如表1所示，其中屬性| S|代表了狀態(tài)的數(shù)目，屬性|A|代表了動作的數(shù)目，屬性|Z|代表了觀察 的數(shù)目。

Hallway2是一個擁有較小規(guī)模的狀態(tài)集合、中等規(guī)模的觀察集合，以及較大規(guī)模的動作集合的數(shù)據(jù)集。RockSample有一個規(guī)模較大的狀態(tài)集合，但是它的觀察集合很小。這些數(shù)據(jù)集能夠覆蓋大部分實(shí)際應(yīng)用的場景。

實(shí)驗(yàn)環(huán)境為臺式工作站，內(nèi)存為16 GB，CPU為Core i7-9700，基于Java語言實(shí)現(xiàn)。在所有的實(shí)驗(yàn)中，折扣因子 γ=0.95，收斂閾值ε=0.01 。分別用FSVI、PBVI-OSD和PBVI三種算法在四個數(shù)據(jù)集上運(yùn)行，其中FSVI和PBVI的實(shí)驗(yàn)設(shè)計(jì)基于文獻(xiàn)[17]。每次update獲得一個值函數(shù)后，策略模擬運(yùn)行100步計(jì)算得到折扣回報值，通過反復(fù)500次的模擬來計(jì)算平均折扣回報（average discounted reward，ADR）。當(dāng)?shù)竭_(dá)預(yù)設(shè)的時間或者指定的步長時，實(shí)驗(yàn)將會終止。表2列出了每個算法最高的ADR，表3列出了每個算法收斂的時間。實(shí)驗(yàn)表明，PBVI-OSD相對其他兩種算法而言，能較快地收斂，并在RockSample［7，8］、RockSample［10，10］、RockSample［11，11］上ADR值較高。可見隨著問題規(guī)模的增大，其在取得最高ADR以及收斂時間所表現(xiàn)出來的優(yōu)勢愈發(fā)明顯。

圖2展示了PBVI-OSD、FSVI和PBVI三個算法在四個不同問題上，ADR與迭代時間的對比。表 中X軸表示算法的迭代時間，Y軸 表示ADR的值。圖中使用實(shí)線表示FSVI，圓點(diǎn)線表示PBVI，PBVI-OSD表示短畫線。

在Hallway2和RockSample［7，8］問題上，由于PBVI-OSD引入了基于信念狀態(tài)快速選取動作、狀態(tài)和后繼信念點(diǎn)，其收斂效率表現(xiàn)得不如FSVI，特別是在狀態(tài)較少的Hallway2問題上，PBVI-OSD的收斂速度比FSVI慢了三倍。PBVI-OSD和PBVI在Hallway2和RockSample［7，8］的問題上，收斂效率接近，PBVI-OSD的收斂效率略高于PBVI。由于狀態(tài)規(guī)模較小，F(xiàn)SVI和PBVI-OSD最后獲得相似的ADR值。這也表明了PBVI-OSD在處理中等規(guī)模的問題時，相比于FSVI并不占優(yōu)勢。PBVI基于距離尋找全局最優(yōu)解，其在狀態(tài)規(guī)模較小的Hallway2問題上取得ADR值高于FSVI和PBVI-OSD，而在RockSample［7，8］問題上的ADR值則略低于其他兩種算法，PBVI在狀態(tài)規(guī)模稍大的問題上實(shí)用性不高。

在規(guī)模較大的RockSample［10，10］和RockSample［11，11］問題中，PBVI-OSD的收斂效率明顯較高，PBVI-OSD在這兩個問題上表現(xiàn)出穩(wěn)定性。PBVI-OSD在RockSample［10，10］問題上的收斂效率比FSVI和PBVI算法分別快1.2倍和1.73倍；在RockSample［11，11］的問題上，由于狀態(tài)數(shù)規(guī)模大，基于MDP的近似解法PBVI-OSD和FSVI在值迭代的初始化階段耗費(fèi)了一段時間，初期收斂效率不如基于信念點(diǎn)集探索的算法PBVI。如圖2（d）所示，隨著初始化的完成，PBVI-OSD和FSVI的ADR值明顯高于PBVI，且由于有效利用了狀態(tài)分布的信息，PBVI-OSD表現(xiàn)更佳。PBVI-OSD收斂速度比FSVI和PBVI兩個算法分別快1.28倍和2.67倍。這說明在大規(guī)模問題上，PBVI-OSD比FSVI和PBVI能夠更快收斂，并能夠提供更加穩(wěn)定的ADR提升。

綜合上述分析，PBVI-OSD根據(jù)當(dāng)前信念狀態(tài)基于環(huán)境狀態(tài)分布優(yōu)化的算法，選取最優(yōu)動作、狀態(tài)，然后探索得到下一個信念點(diǎn)，從而保證了取樣的有效性。在Hallway2、RockSample［7，8］、RockSample［10，10］和RockSample［11，11］四個基準(zhǔn)問題上的實(shí)驗(yàn)表明，相比于FSVI和PBVI，PBVI-OSD能保證收斂效率，特別是在大規(guī)模問題上能收斂到更好的全局最優(yōu)解。

4 結(jié)束語

本文提出了一個基于環(huán)境狀態(tài)分布優(yōu)化的POMDP值迭代算法PBVI-OSD。PBVI-OSD能夠有效利用環(huán)境的反饋，基于信念狀態(tài)快速選取動作、狀態(tài)和后繼信念點(diǎn)，彌補(bǔ)了前向搜索值迭代算法僅依據(jù)MDP進(jìn)行隨機(jī)采樣的缺陷，避免了無峰值狀態(tài)的問題中退化為隨機(jī)策略。一方面，PBVI-OSD根據(jù)當(dāng)前信念狀態(tài)基于權(quán)重的標(biāo)準(zhǔn)選取最優(yōu)動作、狀態(tài)，有效利用了環(huán)境狀態(tài)分布的信息。另一方面，PBVI-OSD基于選取出的動作和狀態(tài)，從觀察中隨機(jī)選取一個觀察概率大于閾值的觀察，由此獲得后繼信念點(diǎn)，從而保證了取樣的有效性。這些改進(jìn)措施能夠幫助PBVI-OSD有效利用環(huán)境狀態(tài)來作出更佳的決策，而不僅僅依賴內(nèi)在的MDP。實(shí)驗(yàn)結(jié)果表明，PBVI-OSD在大規(guī)模的問題上能夠取得更佳的全局最優(yōu)解。

通過改進(jìn)前向搜索值迭代算法的不足之處，PBVI-OSD在大規(guī)模問題上取得了一定的改進(jìn)，但PBVI-OSD仍然需要提升。因此，下一步工作仍會集中在探索更加有效地解決大規(guī)模狀態(tài)引起稀疏的方案，以及嘗試解決隨著迭代時間的增長，動作和狀態(tài)取樣復(fù)雜度高的問題。

參考文獻(xiàn)：

[1] "Delamer J A， Watanabe Y， Chanel C P C. Safe path planning for UAV urban operation under GNSS signal occlusion risk［J］. Robotics and Autonomous Systems ，2021， 142 ：103800.

［2] 萬開方，高曉光，李波，等.基于部分可觀察馬爾可夫決策過程的多被動傳感器組網(wǎng)協(xié)同反隱身探測任務(wù)規(guī)劃［J］.兵工學(xué)報，2015， 36 （4）：731-743.（Wan Kaifang， Gao Xiaoguang， Li Bo， "et al . Mission planning of passive networked sensors for cooperative anti-stealth detection based on POMDP［J］. Acta Armamentarii ，2015， 36 （4）：731-743.）

［3] Ebadi M， Akhavan-Tabatabaei R. Personalized cotesting policies for cervical cancer screening： a POMDP approach［J］. Mathematics ，2021， 9 （6）：679.

［4] Burks L， Ahmed N， Lo E G， "et al . Collaborative human-autonomy semantic sensing through structured POMDP planning［J］. Robotics and Autonomous Systems ，2021， 140 （11-12）：103753.

［5] Khonji M， Jasour A， Williams B. Approximability of constant-horizon constrained POMDP［C］//Proc of the 28th International Joint Confe-rence on Artificial Intelligence Main Track.2019：5583-5590.

［6] Akbarinasaji S， Kavaklioglu C， Basar A， "et al . Partially observable Markov decision process to generate policies in software defect mana-gement［J］. Journal of Systems and Software ，2020， 163 ：110518-110518.

［7] Poupart P， Kim K E， Kim D. Closing the gap： improved bounds on optimal POMDP solutions［C］//Proc of the 21st International Confe-rence on Automated Planning and Scheduling.2011.

［8] 劉全，翟建偉，章宗長.深度強(qiáng)化學(xué)習(xí)綜述［J］.計(jì)算機(jī)學(xué)報，2018， 41 （1）：3-29.（Liu Quan， Zhai Jianwei， Zhang Zongzhang. A survey on deep reinforcement learning［J］. Chinese Journal of Compu-ters ，2018， 41 （1）：3-29.）

［9] 劉峰，王崇駿，駱斌.一種基于最優(yōu)策略概率分布的POMDP值迭代算法［J］.電子學(xué)報，2016， 44 （5）：1078-1084.（Liu Feng， Wang Chongjun， Luo Bin. A probabilitybased value iteration on optimal policy algorithm for POMDP［J］. Acta Electronica Sinica ，2016， 44 （5）：1078-1084.）

［10] Liu Feng， Hua Xia， Jin Xin. A hybrid heuristic value iteration algorithm for POMDP［C］//Proc of the 28th International Conference on Tools with Artificial Intelligence.Piscataway，NJ：IEEE Press，2016：304-310.

［11] 劉海濤，洪炳熔，樸松昊，等.不確定性環(huán)境下基于進(jìn)化算法的強(qiáng)化學(xué)習(xí)［J］.電子學(xué)報，2006， 34 （7）：1356-1360.（Liu Haitao， Hong Bingrong， Pu Songhao， "et al . Evolutionary algorithm based reinforcement learning in the uncertain environments［J］. Acta Electronica Sinica ，2006， 34 （7）：1356-1360.）

［12] Bang-Jensen J， Gutin G， Yeo A. When the greedy algorithm fails［J］. Discrete Optimization ，2004， 1 （2）：121-127.

［13] "Jazwinski A H. Stochastic processes and filtering theory［M］//Mathema-tics in Science and Engineering.[S.l.]：Academic Press，1970：1-376.

［14] "Cassandra A R， Littman M L， Zhang N L. Incremental pruning： a simple， fast， exact method for partially observable Markov decision processes［EB/OL］.（2013-02-06）.https：//arxiv.org/abs/1302.1525.

［15] Cassandra A R， Kaelbling L P， Littman M L. Acting optimally in partially observable stochastic domains［C］//Proc of the 20th AAAI National Conference on Artificial Intelligence.Palo Alto，CA：AAAI Press，1994：1023-1028.

［16] Smallwood R D， Sondik E J. The optimal control of partially observable Markov processes over a finite horizon［J］. Operations Research ，1973， 21 （5）：1071-1088.

［17] Shani G， Pineau J， Kaplow R. A survey of point-based pomdp solvers［J］. Autonomous Agents and Multi-Agent Systems ，2013， 27 （1）：1-51.

［18] Liu Feng， Song Zebang. A probabilistic greedy search value iteration algorithm for POMDP［C］//Proc of the 28th International Conference on Tools with Artificial Intelligence.Piscataway，NJ：IEEE Press，2016：926-929.

［19] Shani G， Brafman R I， Shimony S E. Forward search value iteration for POMDPs［C］//Proc of the 20th International Joint Conference on Artificial Intelligence.2007：2619-2624.

［20] Pineau J， Gordon G， Thrun S， "et al . Point-based value iteration： an anytime algorithm for POMDPs［C］//Proc of the 18th International Joint Conference on Artificial Intelligence.2003：1025-1032.

［21] Gefner H， Bonet B. Solving large POMDPs using real time dynamic programming［C］//Proc of Working Notes Fall AAAI Symposium on POMDPs.Palo Alto，CA：AAAI Press，1998.

［22] Liu Bingbing， Kang Yu， Jiang Xiaofeng， "et al . A fast approximation method for partially observable Markov decision processes［J］. Journal of Systems Science amp; Complexity ，2018， 31 ：1423-1436.

［23] Littman M L， Sutton R S， Singh S. Predictive representations of state［C］//Proc of the 14th International Conference on Neural Information Processing Systems：Natural and Synthetic.2001：1555-1561.