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

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