半Markov决策过程基于灵敏度优化及其应用

半Markov决策过程(SMDP)优化算法在随机动态系统的性能优化方面起到重要的作用。目前SMDP优化算法多受到维数灾、模型灾、收敛速度慢和存储量大等问题的限制。本项目拟从SMDP性能灵敏度（包括性能差和性能导数）的角度，重点研究平均报酬准则下的SMDP的优化算法及其在多机器人协调控制问题中的应用，主要包括：（1）利用SMDP样本轨道的摄动分析，研究SMDP性能灵敏度的势结构特性；（2）基于SMDP性能差公式，研究SMDP基于值函数的强化学习算法；基于SMDP性能导数公式，研究SMDP策略梯度学习算法；（3）融合时间集中的思想，研究时间集中的基于值函数的强化学习算法和策略梯度学习算法；同时利用SMDP模型及其性能灵敏度阐明时间集中方法的机理，探索时间集中方法在MDP优化算法中的应用；（4）以多机器人协调控制问题为应用实例，验证学习算法的有效性和实用性。

半Markov决策过程(Semi-MDP, SMDP)是一类比Markov决策过程(MDP)更具一般性的随机过程，其优化算法在随机动态系统的性能优化方面起到重要的作用。目前SMDP 优化算法多受到维数灾、模型灾、收敛速度慢和存储量大等问题的限制。本项目从SMDP 性能灵敏度（包括性能差和性能导数）的角度，研究了平均报酬准则下的SMDP 的优化理论算法及其在相关实际问题中的应用，从多方面实现了对上述局限的解决，实现了项目申请既定的研究计划和目标，共发表论文10篇，其中在《欧洲运筹学》(JCR一区)发表长文2篇，EI检索7篇，申请1项专利。主要取得的成果包括：(1)在连续时间型性能灵敏度公式基础上，首次提出了离散时间型性能灵敏度公式，通过研究发现SMDP具有连续时间和离散时间两方面特征，即它可以从连续时间和离散时间两种角度进行理论分析和算法设计。这种两面性一方面从性能灵敏度角度为现有的优化算法提供了统一的研究思路，另一方面又发展了多种新的优化算法。从两种不同的角度，我们得到了不同的策略迭代算法和值迭代算法，虽然部分算法在以往的研究中曾经独立提出过，本项目将它们从性能灵敏度角度给出了系统的统一化；提出了新的SMDP优化算法，如新的值迭代算法，新的策略梯度优化算法和新的策略梯度算法。这些算法在存储量和运算量等方面得到了较大的改进，如：提出的策略梯度算法仅需要现有方法一半的存储空间和运算量。(2)基于摄动分析方法，通过引入广义摄动实现因子，利用样本轨道摄动直观构造出了SMDP的性能灵敏度公式，为SMDP性能灵敏度公式提供了直观解释，简化了SMDP的相关优化理论。(3)从SMDP角度研究了时间集中思想，为时间集中的MDP提出了统一的研究方法，不仅从性能灵敏度角度分析了已有的算法，而且给出了新的基于时间集中的优化算法，如基于最短路径的值迭代算法和在线的策略梯度算法等。(4)在值函数的估计方面，提出了一种基于耦合（Coupling）的具有几何方差减少的估计方法，避免了现有算法因需要计算稳态分布和数值截断所带了的收敛速度慢和截断误差大等问题。(5)将研究结果应用于动态电源管理问题，实现了一种在线式的动态电源管理方法，该方法已申请国家专利。 (6)在多机器人任务分配方面，利用性能灵敏度分析方法提出了一种基于拍卖的实时任务分配方法，实现了智能仓库系统中多机器人静态和动态任务分配。