CAJ | 학술논문

针对求解部分可观察马尔可夫决策过程(POMDP)规划问题时遭遇的“维数诅咒”，该文提出了一种基于非负矩阵分解(NMF)更新规则的 POMDP 信念状态空间降维算法，分两步实现低误差高维降维。第1步，利用POMDP 的结构特性，将状态、观察和动作进行可分解表示，然后利用动态贝叶斯网络的条件独立对其转移函数进行分解压缩，并去除概率为零的取值，降低信念状态空间的稀疏性。第2步，采用信念状态空间值直接降维方法，使降维后求出的近似最优策略与原最优策略保持一致，使用NMF更新规则来更新信念状态空间，避免Krylov迭代，加快降维速度。该算法不仅保证降维前后值函数不发生改变，又保留了其分段线性凸特性。实验结果表明，该算法具有较低误差率和较高收敛性。
침대구해부분가관찰마이가부결책과정(POMDP)규화문제시조우적“유수저주”，해문제출료일충기우비부구진분해(NMF)경신규칙적 POMDP 신념상태공간강유산법，분량보실현저오차고유강유。제1보，이용POMDP 적결구특성，장상태、관찰화동작진행가분해표시，연후이용동태패협사망락적조건독립대기전이함수진행분해압축，병거제개솔위령적취치，강저신념상태공간적희소성。제2보，채용신념상태공간치직접강유방법，사강유후구출적근사최우책략여원최우책략보지일치，사용NMF경신규칙래경신신념상태공간，피면Krylov질대，가쾌강유속도。해산법불부보증강유전후치함수불발생개변，우보류료기분단선성철특성。실험결과표명，해산법구유교저오차솔화교고수렴성。
For the curse of dimensionality encountered in solving the planning in Partially Observable Markov Decision Processes (POMDP), this paper presents a novel approach to compress belief states space using Non-negative Matrix Factorization (NMF) updating rules, which reduces high dimensional belief states space by two steps. First, the algorithm adopts factored representations of states, observations and actions by exploiting the structure of factored POMDP, then decomposes and compresses transition functions by exploiting conditional independence of dynamic Bayesian network, and then removes the zero probability to lower the sparsity of belief states space. Second, it adopts value-directed compression approach to make the obtained approximate belief states after dimension reduction be consistent with the original optimal, and exploits NMF updating rules instead of Krylov iterations to accelerate the dimension reduction. The proposed algorithm not only guarantees the value function and reward function of the belief states unchanged after reducing dimensions, but also keeps the piecewise linear and convex property to compute the optimal policy by using dynamic programming. Experiments demonstrate that the proposed belief compression algorithm has lower error rates and higher convergence.