实时动态规划的最优行动判据及算法改进

Optimal Action Criterion and Algorithm Improvement of Real-Time Dynamic Programming

主要以提高求解马尔可夫决策问题的实时动态规划(real-time dynamic programming,简称RTDP)算法的效率为目的.对几类典型的实时动态规划算法所使用的收敛判据进行了对比分析,并利用值函数上界、下界给出了称为最优行动判据的收敛判据,以及一个更适合实时算法的分支选择策略.最优行动判据可以更早地标定当前状态满足精度要求的最优行动供立即执行,而新的分支选择策略可以加快这一判据的满足.据此设计了一种有界增量实时动态规划(bounded incremental RTDP,简称BI-RTDP)算法.在两种典型仿真实时环境的实验中,BI-RTDP均显示出优于现有相关算法的实时性能.

This paper is primarily to improve the efficiency of real-time dynamic programming （RTDP） algorithm for solving Markov decision problems. Several typical convergence criteria are compared and analyzed. A criterion called optimal action criterion and a corresponding branch strategy are proposed on the basis of the upper and lower bound theory. This criterion guarantees that the agent can act earlier in a real-time decision process while an optimal policy with sufficient precision still remains. It can be proved that under certain conditions one can obtain an optimal policy with arbitrary precision by using such an incremental method. With these new techniques, a bounded incremental real-time dynamic programming （BI-RTDP） algorithm is designed. In the experiments of two typical real-time simulation systems, BI-RTDP outperforms the other state-of-the-art RTDP algorithms tested.